循环链表

循环链表，相对于普通单向链表，就是最后一个元素的指针域指向头结点
  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define sc scanf
  4 #define pr printf
  5 
  6 typedef struct LNode{
  7     int data;
  8     struct LNode *next;
  9 }LNode,*LinkList; 
 10 
 11 void Create_CircleList(LinkList &L,int n)
 12 {
 13     LNode *p,*q;
 14     L = (LNode *)malloc(sizeof(LNode));
 15     L->data = 0;
 16     L->next = NULL;
 17     
 18     //创建最后一个结点 
 19     q = (LNode *)malloc(sizeof(LNode));
 20     scanf("%d",&q->data);
 21     q->next = L->next;
 22     L->next = q;
 23     
 24     for(int i = 1;i < n;i++)
 25     {
 26         p = (LNode *)malloc(sizeof(LNode));
 27         scanf("%d",&p->data);
 28         p->next = L->next;
 29         L->next = p;
 30     }
 31     //因为是循环链表，所以最后一个结点的指针指向头结点 
 32     q->next = L;
 33     
 34 }
 35 
 36 //遍历循环链表  
 37 void Traver_CircleList(LinkList &L)
 38 {
 39   LNode *p = L;
 40   while(p->next != L)
 41   {
 42        p = p->next;
 43      cout << p->data << " "; 
 44   }    
 45   puts("");
 46 } 
 47 
 48 int getLength(LinkList &L)
 49 {
 50   LNode *p = L;
 51   int cnt = 0;
 52   while(p->next != L)
 53   {
 54        p = p->next;
 55      cnt++;
 56   }    
 57   return cnt;
 58 }
 59 
 60 //删除循环链表的某个结点
 61 bool Delete_Node(LinkList &L,int i,int &e)
 62 {
 63     int len = getLength(L);
 64     
 65     if(L->next == NULL)
 66     {
 67         puts("Sorry! Empty LinkList!");
 68         return 0;
 69     }
 70     if(i < 1 || i > len)
 71     {
 72         puts("Oh! Baby! The position is invalid. Please re-enter the position!");
 73         return 0;
 74     }
 75     LNode *p = L;
 76     int j = 0;
 77     while(p->next != L && j < i - 1)
 78     {
 79          p = p->next;
 80          j++;
 81     }    
 82     LNode *q;
 83     q = p->next;
 84     p->next = q->next;
 85     e = q->data;
 86     free(q);
 87     return 1;
 88 } 
 89 
 90 int main()
 91 {
 92     LNode *la;
 93     int n,m;
 94     scanf("%d%d",&n,&m);
 95     Create_CircleList(la,n);
 96     
 97     cout << "La length = " << getLength (la) << endl;
 98     Traver_CircleList(la);
 99     int e;
100     bool ok = Delete_Node(la,1,e);
101     if(ok)
102     {
103         cout << "The delete number is " << e << endl;
104         cout << "after delete La length = " << getLength(la) << endl;
105         pr("after delete La is ");
106         Traver_CircleList(la);
107     }
108     return 0;
109 }
View Code