|
循环链表(Circular Linked List) 循环链表是一种首尾相接的链表 循环链表 ()单循环链表 ——在单链表中将终端结点的指针域NULL改为指向表头结点或开始结点即可 ()多重链的循环链表 ——将表中结点链在多个环上 带头结点的单循环链表 注意 判断空链表的条件是head==head>next; 仅设尾指针的单循环链表 用尾指针rear表示的单循环链表对开始结点a 和终端结点a n 查找时间都是O()而表的操作常常是在表的首尾位置上进行因此实用中多采用尾指针表示单循环链表带尾指针的单循环链表可见下图 注意 判断空链表的条件为rear==rear>next; 循环链表的特点 循环链表的特点是无须增加存储量仅对表的链接方式稍作改变即可使得表处理更加方便灵活 【例】在链表上实现将两个线性表(a a …a n )和(b b …b m )连接成一个线性表(a …a n b …b m )的运算 分析 若在单链表或头指针表示的单循环表上做这种链接操作都需要遍历第一个链表找到结点a n 然后将结点b 链到a n的后面其执行时间是O(n)若在尾指针表示的单循环链表上实现则只需修改指针无须遍历其执行时间是O() 相应的算法如下 LinkList Connect(LinkList ALinkList B) {//假设AB为非空循环链表的尾指针 LinkList p=A>next;//①保存A表的头结点位置 A>next=B>next>next;//②B表的开始结点链接到A表尾 free(B>next);//③释放B表的头结点 B>next=p;//④ return B;//返回新循环链表的尾指针 } 注意 ①循环链表中没有NULL指针涉及遍历操作时其终止条件就不再是像非循环链表那样判别p或p>next是否为空而是判别它们是否等于某一指定指针如头指针或尾指针等 ②在单链表中从一已知结点出发只能访问到该结点及其后续结点无法找到该结点之前的其它结点而在单循环链表中从任一结点出发都可访问到表中所有结点这一优点使某些运算在单循环链表上易于实现 |
