数据结构之线性表(六)——循环链表

科技前沿 • 2025-02-08 16:41 • 阅读 53

大家好，我是讯享网，很高兴认识大家。

循环链表的定义

1.概念与特点

循环链表：是一种头尾相接的链表。
表中的最后一个结点的指针域指向头结点，整个链表形成环状结构。
在这里插入图片描述
讯享网
优点：从表中任意一个结点出发均可找到表中其他结点。

补充：
由于循环链表中没有NULL指针，所以涉及到遍历操作时，其终止条件不再像单链表那样判断p或者p->next是否为空，而是判断它们是否等于头指针，如下图所示，
在这里插入图片描述
2.循环链表的查找(两种表示法)

用头指针表示单循环链表
- 找 $a_1$ 的时间复杂度： $O (1)$
- 找 $a_n$ 的时间复杂度： $O (n)$

因为对表的操作常常是在首尾位置上进行，所以该表示方法对于查找首尾元素而言不方便。

用尾指针表示单循环链表
- $a_1$ 的存储位置：R->next->next
- $a_n$ 的存储位置：R
  
  所以查找首尾元素的时间复杂度为： $O (1)$ ，所以用尾指针的这种表示法，在操作循环链表时更为方便。

循环链表的合并

这里主要描述带 尾指针的循环链表合并(将Tb合并在Ta之后)
在这里插入图片描述

具体步骤：
- 1.p保存Ta表的表头结点，即p=Ta->next。
- 2.将Tb表的表头接到Ta表的表尾，即 Ta->next=Tb->next->next。
- 3.释放Tb表的头结点，即delete Tb->next。
- 4.修改指针，使Tb的表尾连结到Ta的表头，即Tb->next=p。
算法描述：

LinkList Connect(LinkList Ta, LinkList Tb) { p = Ta->next; //p存放Ta表的表头结点 Ta->next = Tb->next->next; //Tb表头连结Ta表尾 delete Tb->next; //释放Tb表头结点 Tb->next = p; //修改指针，使Tb的表尾连结到Ta的表头 return Tb; }

讯享网

上述算法的时间复杂度为 $O (1)$ 。

数据结构之线性表(六)——循环链表

相关推荐