《第3周线性表（下）第2讲-循环链表.pdf》由会员分享，可在线阅读，更多相关《第3周线性表（下）第2讲-循环链表.pdf（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、循环循环链表链表是另一种形式的链式是另一种形式的链式存储存储结构形式。结构形式。 循环单链表循环单链表：将：将表中尾节表中尾节点的点的指针域改为指针域改为 指向指向表头节点，整个链表形成一个环。由表头节点，整个链表形成一个环。由 此从表中任一节点出发均可找到链表中其此从表中任一节点出发均可找到链表中其 他节点。他节点。 循环双链表循环双链表：形成两个环。：形成两个环。 节点类型与非节点类型与非 循环单链表的循环单链表的 相同相同 节点类型与非节点类型与非 循环双链表的循环双链表的 相同相同 线性表线性表 (a1, a2, , ai, an) 映射映射 逻辑结构逻辑结构 存储结构存储结构a1a2
2、an L 带头节点带头节点循环单链表循环单链表示意图示意图 1、循环单链表、循环单链表 链表中没有空指针域链表中没有空指针域 p所指节点为尾节点的条件：所指节点为尾节点的条件：p- -next=L 与非循环单与非循环单链表相比，循环单链表：链表相比，循环单链表： a1a2an L p 【例例2- -8】某线性表最常用的操作是在尾元素之后插入一个某线性表最常用的操作是在尾元素之后插入一个 元素和删除第一个元素，故采用元素和删除第一个元素，故采用存储方式最节省运算时间。存储方式最节省运算时间。 A.单链表单链表 B.仅有头结点指针的循环单链表仅有头结点指针的循环单链表 C.双链表双链表 D.仅有尾
3、结点指针的循环单链表仅有尾结点指针的循环单链表 D.仅有尾结点指针的循环单链表仅有尾结点指针的循环单链表 a1a2an L 在尾元素之后插入一个元素在尾元素之后插入一个元素 删除第一个元素删除第一个元素 时间复杂度时间复杂度 均为均为O(1) 选择选择D 线性表线性表 (a1, a2, , ai, an) 映射映射 逻辑结构逻辑结构 存储结构存储结构 a1a2an L 带头节点带头节点循环双链循环双链表示意图表示意图 2、循环双链表、循环双链表 链表中没有空指针域链表中没有空指针域 p所指节点为尾节点的条件：所指节点为尾节点的条件：p- -next=L 一步操作即一步操作即L- -prior可
4、以找到尾节点可以找到尾节点 与非循环双与非循环双链表相比，循环双链表：链表相比，循环双链表： L a1a2an p 【例例2- -9】如果对含有如果对含有n（n1）个元素的线性表的运算只有）个元素的线性表的运算只有4种，种， 即删除第一个元素、删除尾元素、在第一个元素前面插入新元素、即删除第一个元素、删除尾元素、在第一个元素前面插入新元素、 在尾元素的后面插入新元素，则最好使用在尾元素的后面插入新元素，则最好使用。 A.只有尾结点指针没有头结点的循环单链表只有尾结点指针没有头结点的循环单链表 B.只有尾结点指针没有头结点的非循环双链表只有尾结点指针没有头结点的非循环双链表 C.只有首结点指针没
5、有尾结点指针的循环双链表只有首结点指针没有尾结点指针的循环双链表 D.既有头指针也有尾指针的循环单链表既有头指针也有尾指针的循环单链表 a1a2an L C.只有首结点指针没有尾结点指针的循环双链表只有首结点指针没有尾结点指针的循环双链表 删除第一个元素删除第一个元素 删除尾元素删除尾元素 在第一个元素前面插入新元素在第一个元素前面插入新元素 在尾元素的后面插入新元素在尾元素的后面插入新元素 时间复杂度时间复杂度 均为均为O(1) 选择选择C 【例例2-10】设计判断带头节点的循环双设计判断带头节点的循环双链表链表L（含两个以含两个以 上的节点上的节点）是否是否对称相等的算法对称相等的算法。
6、p从左向右扫描从左向右扫描L，q从右向左从右向左扫描扫描L 若若对应数据节点的对应数据节点的data域不相等，则域不相等，则退出循环退出循环 否则否则继续比较，直到继续比较，直到p与与q相等相等或或p的下一个节点为的下一个节点为*q为止。为止。 a1a2an L pq 算法思路算法思路 数据数据节点为节点为奇数奇数的情况：的情况： a b c b a p q p=q：结束：结束 a b b a pq p=q- -prior：结束：结束 数据数据节点为节点为偶数偶数的情况：的情况： int Equal(DLinkList *L) int same=1; DLinkList *p=L-next;/p指向第一个数据节点指向第一个数据节点 DLinkList *q=L-prior;/q指向最后数据节点指向最后数据节点 while (same=1) if (p-data!=q-data) same=0; else if (p=q | p=q-prior) break; q=q-prior;/q前移前移 p=p-next;/p后移后移 return same; 本讲完本讲完