几种常见的循环链表介绍

与单链表相似但有区别
服务器君一共花费了363.248 ms进行了5次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

循环链表的运算与单链表的运算基本一致,不同的有以下几点:

  1. 在建立一个循环链表时,必须使其最后一个结点的指针指向表头结点,而不是像单链表那样置为NULL。此种情况适用于在最后一个结点后插入一个新结点。
  2. 判断是否到表尾采用判断该结点链域的值是否是表头结点的方法,当链域值等于表头指针时,说明已到表尾,而不是像单链表那样判断链域值是否为NULL。

循环链表是一种首尾相接的链表。

1、循环链表

  • 单循环链表——在单链表中,将终端结点的指针域NULL改为指向表头结点或开始结点即可。
  • 多重链的循环链表——将表中结点链在多个环上。

2、带头结点的单循环链表

注意:判断空链表的条件是head==head->next;

3、仅设尾指针的单循环链表

用尾指针rear表示的单循环链表对开始结点a1和终端结点an查找时间都是O(1)。而表的操作常常是在表的首尾位置上进行,因此,实用中多采用尾指针表示单循环链表。带尾指针的单循环链表可见下图。

注意:判断空链表的条件为rear==rear->next;

4、循环链表的特点

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

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

分析:若在单链表或头指针表示的单循环表上做这种链接操作,都需要遍历第一个链表,找到结点an,然后将结点b1链到an的后面,其执行时间是O(n)。若在尾指针表示的单循环链表上实现,则只需修改指针,无须遍历,其执行时间是O(1)。  

相应的算法如下:

LinkList Connect(LinkList A,LinkList B)
{
	//假设A,B为非空循环链表的尾指针
	LinkList p=A->next;		//①保存A表的头结点位置
	A->next=B->next->next;	//②B表的开始结点链接到A表尾
	free(B->next);	//③释放B表的头结点
	B->next=p;		//④
	return B;		//返回新循环链表的尾指针
} 

注意:

  1. 循环链表中没有NULL指针。涉及遍历操作时,其终止条件就不再是像非循环链表那样判别p或p->next是否为空,而是判别它们是否等于某一指定指针,如头指针或尾指针等。
  2. 在单链表中,从一已知结点出发,只能访问到该结点及其后续结点,无法找到该结点之前的其它结点。而在单循环链表中,从任一结点出发都可访问到表中所有结点,这一优点使某些运算在单循环链表上易于实现。

本文地址:http://www.nowamagic.net/librarys/veda/detail/1862,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/1862

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《Python在Unix和Linux系统管理中的应用》 Noab Gift (作者), Jeremy M.Jones (作者)

《Python在Unix和Linux系统管理中的应用(影印版)》作者们还构建了一个可以免费下载的Ubuntu虚拟机。该虚拟机包含了这《Python在Unix和Linux系统管理中的应用(影印版)》的源代码,还可以用来运行书中的实例,包括SNMP、IPython、SQLAlchemy和许多其他工具。《Python在Unix和Linux系统管理中的应用》展示了Python语言如何提供一种更加高效的方式来处理Unix和Linux服务器管理工作中的各种任务。《Python在Unix和Linux系统管理中的应用(影印版)》的每一章都会提出一个特定的管理问题,例如并发或数据备份,然后通过实际的例子提供基于Python的解决方案。

更多计算机宝库...