2.10.循环链表
https://i-blog.csdnimg.cn/direct/89539fb2e9dd435fb3c4c68f5fa6783b.png一.循环单链表：
1.图示：
https://i-blog.csdnimg.cn/direct/04452b0229354305ba7c1a9653b8edb3.png
2.代码阐明：
https://i-blog.csdnimg.cn/direct/398c675206f0409ba55dbe9ed69a426c.png
[*] 初始化循环单链表时头结点的next指针必须指向头结点
[*] 判断循环单链表是否为空只需要判断头结点的next指针是否指向头结点？是:循环单链表为空；否:循环单链表不为空
[*] 判断某个结点是否为循环单链表的表尾结点，只需要判断该结点的next指针是否指向该循环单链表的头结点即可
[*] 如果循环单链表不为空的话，就需要把表尾结点的next指针指向头结点
3.代码演示：
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode
{
int data; //这个数据的类型不是固定的
struct LNode *next;
}LNode,*LinkList;
//初始化一个循环单链表
bool InitList(LinkList &L) //函数的结果和函数体的结果最终都要用，所以加&
{
L = (LNode *)malloc( sizeof(LNode) ); //分配一个头结点
if(L==NULL)
{
return false; //内存不足，分配失败
}
L->next = L; //头结点的next指针必须指向L即头结点指向头结点(L代表头结点)
return true;
}
//判断循环单链表是否为空
bool Empty(LinkList L)
{
if(L->next = L) return true; //头结点指向头结点说明为空
else return false;
}
//判断结点p是否为循环单链表的表尾结点
bool isTail(LinkList L,LNode *p)
{
//L代表头结点
if(p->next = L) //p结点的next指针指回头结点就说明p为表尾结点
{
return true;
}
else
{
return false;
}
}
int main()
{
return 0;
} 4.循环单链表与非循环单链表的对比：
https://i-blog.csdnimg.cn/direct/2c6c6e9cc4a04c39ac7534185790d93a.png
5.基础操作：
https://i-blog.csdnimg.cn/direct/034ee9a1e4764f3ca84b3044eaea65be.png
循环单链表和非循环单链表找到尾结点的时间复杂度都是O(n)，因为要重新循环遍历到尾；
循环单链表从尾部找到头部的时间复杂度为O(1)，因为尾部下一个就是头部->如果经常操作表头和表尾的话，可以让循环单链表的指针指向表尾结点，此时如果在表尾插入或删除结点时大概需要修改该指针；
二.循环双链表：
1.图示：
https://i-blog.csdnimg.cn/direct/6d0e12c588a94a828019ba8fc8ded7e0.png
2.代码阐明：
https://i-blog.csdnimg.cn/direct/5f797ce0ce90420dbb219c40ec5a24dc.png
3.代码演示：
#include<stdio.h>
#include<stdlib.h>
typedef struct DNode
{
int data;
struct DNode *prior,*next; //*prior为前驱指针,*next为后继指针
}DNode,*DLinklist;
//初始化空的循环单链表
bool InitDLinkList(DLinklist &L)
{
L = (DNode *)malloc( sizeof(DNode) ); //分配一个头结点
if(L==NULL) return false; //内存不足，分配失败
L->prior = L; //头结点的前驱指针prior指向头结点
L->next = L; //头结点的后继指针next指向头结点
return true;
}
//判断循环双链表是否为空
bool Empty(DLinklist L)
{
if(L->next = L)
{
return true; //循环双链表的头结点的next指针指向头结点就说明循环双链表为空
}
else
{
return false;
}
}
//判断结点p是否为循环双链表的表尾结点
bool isTail(DLinklist L,DNode *p)
{
if(p->next == L) //结点p的next指针指向头结点就说明p为尾结点
{
return true;
}
else
{
return false;
}
}
int main()
{
return 0;
} 4.循环双链表的插入：
https://i-blog.csdnimg.cn/direct/e57db6b13f2444b0ace597390b0cb52e.png
5.循环双链表的删除：
https://i-blog.csdnimg.cn/direct/08aabbdf0fa14a64a719b236001a19d4.png
三.总结：
https://i-blog.csdnimg.cn/direct/b0cf5bb5ce2f4985b14b55cc82234407.png
1.对于平凡带头结点的双链表而言，只有头结点时，它的后继指针和前驱指针都指向NULL;
2.知道表为空时的状态就可以知道怎样初始化;
3.知道怎样判断某个结点是否是表头/尾结点时，就可以知道怎样前向遍历和后向遍历；
4.注：所有链表都不具有随机访问的特性，因此找某个结点时只能通过循环查找，循环要么停在表头结点，要么停在表尾结点。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]