2.10.循环链表

---

一.循环单链表：

1.图示：

2.代码阐明：

• 初始化循环单链表时头结点的next指针必须指向头结点
  
• 判断循环单链表是否为空只需要判断头结点的next指针是否指向头结点？是:循环单链表为空；否:循环单链表不为空
  
• 判断某个结点是否为循环单链表的表尾结点，只需要判断该结点的next指针是否指向该循环单链表的头结点即可
  
• 如果循环单链表不为空的话，就需要把表尾结点的next指针指向头结点
  

3.代码演示：

1. #include<stdio.h>
2. #include<stdlib.h>
3. ​
4. typedef struct LNode
5. {
6.     int data; //这个数据的类型不是固定的
7.     struct LNode *next;
8. }LNode,*LinkList;
9. ​
10. //初始化一个循环单链表
11. bool InitList(LinkList &L) //函数的结果和函数体的结果最终都要用，所以加&
12. {
13.     L = (LNode *)malloc( sizeof(LNode) ); //分配一个头结点
14.     if(L==NULL)
15.     {
16.         return false; //内存不足，分配失败
17.     }
18.     L->next = L; //头结点的next指针必须指向L即头结点指向头结点(L代表头结点)
19.     return true;
20. }
21. ​
22. //判断循环单链表是否为空
23. bool Empty(LinkList L)
24. {
25.     if(L->next = L) return true; //头结点指向头结点说明为空
26.     else return false;
27. }
28. ​
29. //判断结点p是否为循环单链表的表尾结点
30. bool isTail(LinkList L,LNode *p)
31. {
32.     //L代表头结点
33.     if(p->next = L) //p结点的next指针指回头结点就说明p为表尾结点
34.     {
35.         return true;
36.     }
37.     else
38.     {
39.         return false;
40.     }
41. }
42. ​
43. int main()
44. {
45.     return 0;
46. }

复制代码

4.循环单链表与非循环单链表的对比：

5.基础操作：

循环单链表和非循环单链表找到尾结点的时间复杂度都是O(n)，因为要重新循环遍历到尾；
循环单链表从尾部找到头部的时间复杂度为O(1)，因为尾部下一个就是头部->如果经常操作表头和表尾的话，可以让循环单链表的指针指向表尾结点，此时如果在表尾插入或删除结点时大概需要修改该指针；

---

二.循环双链表：

1.图示：

2.代码阐明：

3.代码演示：

1. #include<stdio.h>
2. #include<stdlib.h>
3. ​
4. typedef struct DNode
5. {
6.     int data;
7.     struct DNode *prior,*next; //*prior为前驱指针,*next为后继指针
8. }DNode,*DLinklist;
9. ​
10. ​
11. //初始化空的循环单链表
12. bool InitDLinkList(DLinklist &L)
13. {
14.     L = (DNode *)malloc( sizeof(DNode) ); //分配一个头结点
15.     if(L==NULL) return false; //内存不足，分配失败
16.     L->prior = L; //头结点的前驱指针prior指向头结点
17.     L->next = L; //头结点的后继指针next指向头结点
18.     return true;
19. }
20. ​
21. //判断循环双链表是否为空
22. bool Empty(DLinklist L)
23. {
24.     if(L->next = L)
25.     {
26.         return true; //循环双链表的头结点的next指针指向头结点就说明循环双链表为空
27.     }
28.     else
29.     {
30.         return false;
31.     }
32. }
33. ​
34. //判断结点p是否为循环双链表的表尾结点
35. bool isTail(DLinklist L,DNode *p)
36. {
37.     if(p->next == L) //结点p的next指针指向头结点就说明p为尾结点
38.     {
39.         return true;
40.     }
41.     else
42.     {
43.         return false;
44.     }
45. }
46. ​
47. ​
48. int main()
49. {
50.     return 0;
51. }

复制代码

4.循环双链表的插入：

5.循环双链表的删除：

---

三.总结：

1.对于平凡带头结点的双链表而言，只有头结点时，它的后继指针和前驱指针都指向NULL;
2.知道表为空时的状态就可以知道怎样初始化;
3.知道怎样判断某个结点是否是表头/尾结点时，就可以知道怎样前向遍历和后向遍历；
4.注：所有链表都不具有随机访问的特性，因此找某个结点时只能通过循环查找，循环要么停在表头结点，要么停在表尾结点。

---

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。