第二章 线性表 其它链表 为什么要学习其他形式的链表？ 单链表在查询时，只是方便查询结点的直接后继结点 。如果查询直接前驱时，需要从头指针开始，顺着 next指针域顺次向后寻找，操作受到限制。 循环链表双向链表 双向循环链表二叉链表 十字链表邻接多重表 循环链表 定义 特点 基本形态 最后一个结点的链接又指回头结点（或第一个结点 ）的链表，整个链表形成一个环。 a1 a2 . an 1.与单链表相比，操作时判断最后一个结点的条 件为：结点的链接是否为头结点。 2.从表中任一结点出发，均可找到表中的其他结 点。 循环链表操作 循环链表与单链表的操作基本一致，差别仅 在于，当遍历链表时，判别当前指针p是否 指向表尾结点的终止条件不同。在单链表中 ，条件是p-next=NULL；而在循环链表中 ，条件为p-next=L。 循环链表基本形态 表空 头结点 L 条件：L-next=L 表非空 条件：p-next=L L p 循环链表应用 利用循环链表实现合并两个线性表，使时间复杂度为O(1)。 思考：在循环链表中，设立尾指针而不设立头指针，可以使 操作简化。 . A . B 循环链表应用 利用循环链表实现合并两个线性表，使时间复杂度为O(1)。 . A . B 方法：仅需将第一个链表的尾指针指向第二 个链表的第一个结点，第二个链表的尾指针 指向第一个链表的表头结点，然后释放第二 个链表的表头结点。 q p A q=B-next ; p=B-next-next; B-next=A-next; A-next=p; A=B; free(q); 双向链表 定义 特点 基本形态 C描述 操作特点 用两个链域表示元素间的逻辑关系，其一指向直接 后继，其二指向直接前驱。方便操作。 为克服单链表的单向性的缺点，线性表可采 用双向链表存储结点。 双向链表中，p指向某一结点，则有p-next-prior=p和 p-prior-next=p，这恰恰体现了双向链表的特性。 双向链表基本形态 表空 表非空 L 条件：L-next=NULL / 数据域 struct DuLNode *prior; / 指向前驱的指针域 struct DuLNode *next; / 指向后继的指针域 DuLNode, *DuLinkList; 双向链表操作特点 双向链表中，有些操作（ListLength、GetElem、 LocateElem）仅涉及一个方向的指针，它们的算法 描述和线性链表相同，但“插入” 和“删除”时 ，需要同时修改两个方向上的指针。 双向链表的插入算法 , 分析：先找到第i-1个结点，p指向它；改变第i-1 个结点的后继指针，第i个结点的前驱指针；同时 还要改变要插入结点的前驱和后继指针。 实现在双向链表中的第i个结点前插入一个结点。 ai-1ai e s-next = p-next; p-next = s; s-next-prior = s; s-prior = p; p s ai-1ai 演示插入过程 , 分析：先找到第i-1个结点，p指向它；改变第i-1 个结点的后继指针指向第i+1个结点；同时还要改 变第i+1个结点的前驱指针指向第i-1个结点。 双向链表的删除算法 实现在双向链表中删除第i个结点。 ai-1aiai+1 p-next = p-next-next; p-next-prior = p; p ai-1 演示删除过程 双向循环链表 特点：在双向链表的基础上，头结点 的直接前驱指针指向最后一个结点， 最后一个结点直接后继指针指向头结 点，整个链表中有两个环。 双向循环链表基本形态 表空 表非空 L 条件：L-next=L&L-prior=L a1 a2 . an L p 条件：p-next=L&L-prior=p