【数据结构】【线性表】循环链表(附C语言源码)

循环链表

循环链表其实很简单，无论是之前的单链表还是双链表，链表结尾结点的next都指向NULL，简单来说就是非循环链表就是一条线，循环链表就是将表尾和表头的两个结点连接起来，构建成一个环。
循环链表一个简单的改变让链表的操作变得更加多元和便捷，例如

• 可以在链表的任意结点作为起点开始遍历整个链表
• 在删除和插入操作时可以不用考虑边界问题，因为环中的每一个结点都可以视为中间的结点，可以视为没有边界。
  但同样的，这个改变也需要我们对原有的一些逻辑进行修改，主要表现在表头和表尾两个结点的处理上
• 链表初始化的处理，有头结点的才需要处理。对于单链表需要将头结点的next指向自己，对于双链表，需要将头结点的next和prior都指向自己
• 空链表的判断。非循环链表只需要看L->next(有头结点)是不是NULL即可判断；而循环链表看的是L->next是不是等于L本身。
• 表尾结点的判断。非循环链表的表尾结点的next是NULL；而循环链表的表尾结点的next是表头结点。

循环链表初始化

/*功能：初始化循环单链表
  输入：
&L->单链表结构体
  输出：
flase：初始化失败
true ：初始化成功
  说明：适用于有头结点的单链表
*/
bool InitLinkList(LinkList &L){
L=(LNode *)malloc(sizeof(LNode));//给头结点分配空间
if(L=NULL)//判断空间分配情况
return false;//空间分配失败，初始化失败；

L->next=L;//初始化头结点的next指针指向自己

return true;//初始化成功
}
/*功能：初始化循环双链表
  输入：
&L->双链表结构体
  输出：
flase：初始化失败
true ：初始化成功
  说明：适用于有头结点的双链表
*/
bool InitDLinkList(DLinkList &L){
L=(DNode *)malloc(sizeof(DNode));//给头结点分配空间
if(L=NULL)//判断空间分配情况
return false;//空间分配失败，初始化失败；

L->next=L;//初始化头结点的next指针指向自己
L->prior=L;//初始化头结点的prior指针指向自己

return true;//初始化成功
}

循环链表的判空

/*功能：判断链表是否为空
  输入：
L->链表结构体
  输出：
flase：本身空链表
true ：是空链表
  说明：适用于循环单/双链表
*/
bool Empty(){
if(L->next==L)
return true;
eles
return false;
}

循环链表的表尾结点的判定

/*功能：判断结点是否是链表中的尾结点
  输入：
&L->链表结构体
*p->需要判定的结点
  输出：
flase：该结点不是链表的尾结点
true ：该结点是链表的尾结点
  说明：适用于循环单/双链表
*/
bool isTail(LinkList &L,Node *p){
if(P->next==L)
return true;
else
return false;
}

循环链表结点的插入和删除

循环链表的结点插入和删除都不需要考虑边界问题了，循环链表不仅仅是原来的线性结构了而是一个环状，每个结点都可视为中间的结点，可以不考虑头结点和尾结点的边缘问题。

/*功能：循环双链表在p结点之后插入s结点
  输入：
*p->指定的结点指针
*s->要插入的结点
  输出：
flase：插入失败
true ：插入成功
  说明：
*/
bool InsertNextDNode(DNode *p,DNode *s){
if(p==NULL)//判断插入结点合法性
return false;//结点不合法，插入失败

s->next=p->next;//更新插入结点的next指向后继结点
s->prior=p;//更新插入结点的prior指向前驱结点
p->next->prior=s;//将后续结点的prior结点指向插入结点
p->next=s;//前驱结点的next指向插入结点

return true;//插入成功
}

/*功能：循环双链表删除p结点
  输入：
*p->要被删除的结点p
&e->反馈删除的数据
  输出：
flase：删除失败
true ：删除成功
  说明：适用于双链表的所有结点的删除，时间复杂度为O(n)。
*/
bool DeleteDNode(DNode *p,ElemType &e){
if(p==NULL)//判断p结点是否存在
return false;
p->prior->next=p->next;//将删除结点的next给前驱结点的next
p->next-prior=p->proir;//将删除结点的prior给后驱结点的prior
e= p->data;//将第i个节点的数据传递给e
free(p);//释放结点的存储空间

return true;//删除成功
}

原文地址：https://blog.csdn.net/weixin_58498967/article/details/143806567

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！