文字描述

　　循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中其他结点。

 

示意图

 

算法分析

插入、删除、查找等同单链表。

 

代码实现

1 //  2 // Created by lady on 19-1-27.  3 //  4   5 #include 
      
         6 #include 
       
          7   8 //线性表的单向循环链表存储结构  9 typedef struct ElemType{ 10     char data[10]; 11 }ElemType; 12 typedef struct CNode{ 13     ElemType e; 14     struct CNode *next; 15 }CNode; 16 typedef struct { 17     CNode *head;//指向第一个指针 18     CNode *tail;//指向最后一个指针 19     int length;//表示链表数据元素个数 20 }CLinkNode, *CLinkList; 21  22 //构造一个空的线性表 23 static int InitList_CL(CLinkList *L) 24 { 25     (*L) = (CLinkList)malloc(sizeof(CLinkNode)); 26     (*L)->length = 0; 27     (*L)->head = NULL; 28     (*L)->tail = NULL; 29 } 30  31 //销毁线性表 32 static int Destory_CL(CLinkList *L) 33 { 34     if(L == NULL || (*L) == NULL){ 35         return -1; 36     } 37     CNode *p = (*L)->head; 38     CNode *q; 39     while(p){ 40         q = p; 41         p = p->next; 42         free(q); 43         if(p == (*L)->head) 44             break; 45     } 46     free(*L); 47     (*L) = NULL; 48 } 49  50 //返回1表示空， 0表示非空 51 static int ListEmpty_CL(CLinkList L) 52 { 53     return L->length ? 0: 1; 54 } 55  56 //返回线性表L中的数据元素个数 57 static int ListLength_CL(CLinkList L) 58 { 59     return L->length; 60 } 61  62 //在线性表末尾插入数据元素e 63 static int ListInsert_CL(CLinkList *L,ElemType e) 64 { 65     CNode *new = (CNode *)malloc(sizeof(CNode)); 66     if(new == NULL){ 67         return -1; 68     } 69     CNode *p; 70     new ->e = e; 71     new->next = NULL; 72     if(ListEmpty_CL(*L)){ 73         (*L)->length += 1; 74         new->next = new; 75         (*L)->head = new; 76         (*L)->tail = new; 77     }else{ 78         (*L)->length +=1; 79         new->next = (*L)->head; 80         (*L)->tail->next = new; 81         (*L)->tail = new; 82     } 83     return 0; 84 } 85  86 //删除L中的第loc个数据元素，并将被删元素的值存放在e中 87 static int ListDelete_CL(CLinkList *L, int loc, ElemType *e) 88 { 89     CNode *p = (*L)->head; 90     CNode *q = NULL; 91     int i = 1; 92     int f = 0; 93     while(p){ 94         if(i == loc){ 95             f = 1; 96             break; 97         } 98         i += 1; 99         q = p;100         p = p->next;101         if(p == (*L)->head){102             f = -1;103             break;104         }105     }106     if(f<1)107         return -1;108     (*L)->length -= 1;109     (*e) = p->e;110     if((*L)->length == 0){111         free(p);112         (*L)->head = NULL;113         (*L)->tail = NULL;114     }115     if(q == NULL){116         q = p->next;117         free(p);118         (*L)->tail->next = q;119     }else{120         q->next = p->next;121         free(p);122     }123     return 0;124 }125 126 //依次对L的每个数据元素调用函数fun127 static int ListTraverse_CL(CLinkList L, int (*fun)(ElemType,int), char note[])128 {129     printf("遍历循环链表%s:", note);130     CNode *p = L->head;131     int i = 0;132     while(p){133         if(fun(p->e, ++i)){134             return -1;135         }136         p = p->next;137         if(p == L->head)138             break;139     }140     printf("\n");141     return 0;142 }143 144 static int print(ElemType e, int loc)145 {146     printf("%3d=%-10s", loc, e.data);147     return 0;148 }149 150 //创建一个长度为n的链表151 static int CreateList_CL(CLinkList *L, int n, char note[])152 {153     printf("创建一个长度为%d的循环链表%s!\n", n, note);154     InitList_CL(L);155     ElemType e;156     int i = 0;157     for(i=0; i
       
      

 

代码运行

/home/lady/CLionProjects/untitled/cmake-build-debug/untitled创建一个长度为5的循环链表L:!输入第1个元素:WU输入第2个元素:ZHENG输入第3个元素:WANG输入第4个元素:SUN输入第5个元素:LI遍历循环链表L:  1=WU          2=ZHENG       3=WANG        4=SUN         5=LI        输入删除元素的位置:2位于2的元素ZHENG已经从循环链表中被删除！遍历循环链表L:  1=WU          2=WANG        3=SUN         4=LI        Process finished with exit code 0