线性表类型定义章课件及作业chap2-2014.pptx

12.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.3.1线性链表2.3.2循环链表2.3.3双向链表2.4一元多项式的表示及相加第二章线性表

22.3.2循环链表循环链表是一种头尾相接的链表，其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表的处理更加方便灵活。单循环链表：在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点，就得到了单链形式的循环链表，可简单称之为单循环链表。(1)非空表a1a2aiai+1……H

3(2)空表H为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p-next是否为空，而是判断它们是否等于头指针。

4在用头指针表示的单链表中，找开始结点a1的时间是O(1)，然而要找到终端结点an，则需从头指针开始遍历整个链表，其时间是O(n)。在很多实际问题中，常在循环链表中设立尾指针，可使某些操作简化，如查找开始结点和终端结点，则开始结点a1和终端结点an的存储位置分别是(rear-next)-next和rear，查找时间都是O(1)。实际中多采用尾指针表示单循环链表。

2024/8/135图带头结点的循环单链表

2024/8/136例有两个带头结点的循环单链表A、B，编写一个算法，将两个循环单链表合并为一个循环单链表，其头指针为A、B。算法思想1（非循环链表必需的方法）：先找到两个链表的尾，并分别由指针p、q指向它们，然后将第一个链表的尾与第二个表的第一个结点链接起来，并修改第二个表的尾q，使它的链域指向第一个表的头结点。a1a2a3……^nanb1b2b3……^bmBmA(1)p(2)q(3)(4)

2024/8/137采用上面的方法，需要遍历链表，找到表尾，其执行时间是O(n)。若在尾指针表示的单循环链表上实现，则只需要修改指针，无需遍历，其执行时间是O(1)。a1a2a3……^nanb1b2b3……^bmBmAp(1)(2)释放（3）(4)A(5)

2024/8/138voidmerge（LNode*A,LNode*B){/*此算法将两个链表首尾连接起来*/LNode*p;p=A-next;/*保存链表A的头结点地址*/A-next=B-next-next;/*链表B的开始结点链到链表A的终端结点之后*/deleteB-next;/*释放链表B的头结点*/B-next=p;/*链表A的头结点链到链表B的终端结点之后*/A=B;}

2024/8/139单链表与循环链表：

（2）差别：（1）操作基本相同a.查找单链表：从表头开始查表头结点O(1)

查表尾结点O(n)

b.判定是否到链尾：单链表p-next==NULL

循环链表p-next==L循环链表：从任一点出发均可

用尾指针表示查表尾O(1)rear

查表头O(1)rear-next

c.链表的合并

2024/8/13102.3.3双向链表循环单链表的出现，虽然能