环形单链表的实现基本字典操作

 概念定义：  

    环形单链表是单链表的另一种形式，其结构特点链表中最后一个结点的指针域不再是结束标记，而是指向整个链表的第一个结点，从而使链表形成一个环。和单链表相同，循环链表也有带头结点结构和不带头结点结构两种，带头结点的循环单链表实现插入和删除操作较为方便。所以本文中就用带头结点的循环单链表。

#include <iostream>
#include <time.h>
using namespace std;
#define LEN sizeof(struct List)
struct List*head=NULL;//链表头部
struct List*tail=NULL;//链表尾部
struct List
{
    int key;
    struct List*next;
};
//插入数据
struct List*insert(struct List *p,struct List*x)
{//由于链表没有像数组一样的越界限制，所以不用检查上溢。
    x=(struct List*)malloc(LEN);//最多会出现不能申请堆中内存。
    x->key=rand()%100;
    p=tail;
    if (head==NULL)
    {
        p=head=x;
    }
    else
    {
        p->next=x;
        p=p->next;
    }
    p->next=head;
    tail=p;
    return p;
}
//按顺序从头删除函数
struct List*In_order_to_delete(struct List *p)
{//时间复杂度为O(1)
    struct List *x;
    x=p=head;
    if (head==NULL)//当链表里没有元素而继续删除时，会发生上溢。
    {
        cout<<"underflow!"<<endl;
        return NULL;
    }
    else
    {
        if (tail==head)
        {
            head=tail=NULL;
        } 
        else
        {
            p=p->next;
            head=p;
            tail->next=head;
        }
        return x;
    }
}
bool search(struct List *p,int k);
//删除指定元素函数
struct List*Delete_specified_element(struct List *p,int k)
{//这个函数代表了最坏情况删除元素的时间复杂度O(n)
  if (!search(p,k))
  {
      cout<<"不存在这个数据,无法删除！"<<endl;
      return NULL;
  }
  else
  {
      p=head;
      if (p->key==k)//如果头结点即为所要查找的k
      {
          p=p->next;
          head=p;
          tail->next=p;
      }
      else//否则进入循环
      {
          while (p->next->key!=k)
          {
              p=p->next;
          }
          p->next=p->next->next;
      }
      return head;
  }
}
//查找数据
bool search(struct List *p,int k)
{
   p=head;
   while (p!=tail&&p->key!=k)
   {
       p=p->next;
   }
   if (p==tail&&p->key!=k)
   {
       cout<<"没有找到！"<<endl;
       return false;
   }
   else
   {
       cout<<"已经找到！"<<p->key<<endl;
       return true;
   }
}
void Print()  
{  
    struct List*p =head; 
    if(p!=NULL)
    {
        while(p->next!=head)  
        {  
            cout<<p->key<<"->";  
            p = p->next;  
        } 
        cout<<p->key<<"->"<<endl;
    }
    else
    {
        cout<<"此链表为空！"<<endl;
    }
} 
void main()
{
   struct List *p=NULL,*x=NULL;
   srand( (unsigned)time( NULL ) );
   cout<<"数据插入链表中。。"<<endl;
   for (int i=0;i<30;i++)
   {
       insert(p,x);
   }
   Print();
   cout<<"查找特定元素中。。"<<endl;
   search(p,60);
   cout<<"按顺序删除的元素如下：";
   for ( i=0;i<=3;i++)
   {
       p=In_order_to_delete(p);
       if (p==NULL)
       {
           continue;
       }
       cout<<p->key<<"->";
   }
   cout<<endl;
   cout<<"打印删除数个元素后的数据："<<endl;
   Print();
   cout<<"删除特定元素中。。"<<endl;
   Delete_specified_element(p,11);
   cout<<"删除特定元素后链表中剩下的数据"<<endl;
   Print();
}

环形单链表的实现基本字典操作

原文：http://blog.csdn.net/z84616995z/article/details/19496363