当前位置:鱼C工作室 >数据结构和算法 > 查看文章

线性表14 – 数据结构和算法19

线性表14

 

让编程改变世界

Change the world by program


 

循环链表的特点

 

回顾一下,在单链表中,我们有了头结点时,我们可以用O(1)的时间访问第一个结点,但对于要访问最后一个结点,我们必须要挨个向下索引,所以需要O(n)的时间。

大家猜的没错,如果用上今天我们学习到的循环链表的特点,用O(1)的时间就可以由链表指针访问到最后一个结点。

 

不过我们需要改造一下现有的循环链表,我们不用头指针,而是用指向终端结点的尾指针来表示循环链表,此时查找开始结点和终端结点都很方便了,如图:

循环链表的特点

 

那么按照这个逻辑的话,判断是否为空链表的条件应该如何呢?

就是判断rear是否等于rear->next,大家猜对了吗?

循环链表的特点是无须增加存储量,仅对链接方式稍作改变,即可使得表处理更加方便灵活。

 

一道例题

 

题目:

实现将两个线性表(a1,a2,…,an)和(b1,b2,…,bm)连接成一个线性表(a1,…,an,b1,…bm)的运算。

 

分析:

若在单链表或头指针表示的单循环表上做这种链接操作,都需要遍历第一个链表,找到结点an,然后将结点b1链到an的后面,其执行时间是O(n)。

若在尾指针表示的单循环链表上实现,则只需修改指针,无须遍历,其执行时间是O(1)。

 

循环链表的特点

 

稍作思考看代码实现:cennect.c

 

判断单链表中是否有环

 

有环的定义是,链表的尾节点指向了链表中的某个节点。

带环单链表

 

那么要判断单链表中是否有环,主要有以下两种方法:

 

方法一:使用p、q两个指针,p总是向前走,但q每次都从头开始走,对于每个节点,看p走的步数是否和q一样。如图,当p从6走到3时,用了6步,此时若q从head出发,则只需两步就到3,因而步数不等,出现矛盾,存在环。

 

方法二:使用p、q两个指针,p每次向前走一步,q每次向前走两步,若在某个时候p == q,则存在环。

 

详细实现代码:loop.c


为您推荐

报歉!评论已关闭.