课程名称：数据结构第4周，第4讲次摘 要第二章线性表授课题目（章、节）第四节循环单链表第五节双向链表第六节仿真链表【目的要求】通过本讲课程的学习，了解循环单链表、双向链表和仿真链表的结构。【重点】掌握各种链表的结构特点，根据实际应用可以选择适当的存储方式。【难点】双向链表的插入和删除。内容【本讲课程的引入】对于链表根据结点构造链的方法不同，链表主要有单链表、循环单链表和双向链表三种。上一次课我们学习了单链表，这一次课我们主要了解循环单链表、双向链表，以及一种仿真链表（用数组构造的仿真链表）。【本讲课程的内容】2.4循环单链表循环单链表是单链表的另一种形式，其结构特点是链表中最后一个结点的指针不再是结束标记，而是指向整个链表的第一个结点，从而使单链表形成一个环。和单链表相比，循环单链表的长处是从链尾到链头比较方便。当要处理的数据元素序列具有环型结构特点时，适合于采用循环单链表。和单链表相同，循环单链表也有带头结点结构和不带头结点结构两种，带头结点的循环单链表实现插入和删除操作时，算法实现较为方便。带头结点的循环单链表结构如下：+aoanead带头结点的循环单链表的操作实现方法和带头结点的单链表的操作实现方法类同，差别仅在于：（1）在构造函数中，要加一条head.next=head语句。（2）在index(i）成员函数中，把循环结束判断条件current！=null改为current！=head。单链表只能从头结点开始遍历整个链表，而循环单链表则可以从表中任意结点开始遍历整个链表。有些情况为了方便操作，头指针将指向表尾，其好处是既能立即找到链表的尾结点，也容易找到链表中的第一个结点。这种情况下串联两个链表要优于单链表。2.5双向链表双向链表是每个结点除后继指针外还有一个前驱指针。和单链表类同，双向链表也有带头结点结构和不带头结点结构两种，带头结点的双向链表更为常用：另外，双向链表也可以有循环和非循环两种结构，循环结构的双向链表更为常用。在双向链表中，每个结点包括三个域，分别是element域、next域和prior域，其中element域为数据元素域，next域为指向后继结点的对象引用，prior域为指向前驱结点的对象引用
课程名称：数据结构 第 4 周，第 4 讲次 摘 要 授课题目（章、节） 第二章 线性表 第四节 循环单链表 第五节 双向链表 第六节 仿真链表 【目的要求】通过本讲课程的学习，了解循环单链表、双向链表和仿真链表的结构。 【重 点】掌握各种链表的结构特点，根据实际应用可以选择适当的存储方式。 【难 点】双向链表的插入和删除。 内 容 【本讲课程的引入】对于链表根据结点构造链的方法不同，链表主要有单链表、循环单链表和 双向链表三种。上一次课我们学习了单链表，这一次课我们主要了解循环单链表、双向链表， 以及一种仿真链表（用数组构造的仿真链表）。 【本讲课程的内容】 2.4 循环单链表 循环单链表是单链表的另一种形式，其结构特点是链表中最后一个结点的指针不再是结束 标记，而是指向整个链表的第一个结点，从而使单链表形成一个环。和单链表相比，循环单链 表的长处是从链尾到链头比较方便。当要处理的数据元素序列具有环型结构特点时，适合于采 用循环单链表。 和单链表相同，循环单链表也有带头结点结构和不带头结点结构两种，带头结点的循环单 链表实现插入和删除操作时，算法实现较为方便。 带头结点的循环单链表结构如下： 带头结点的循环单链表的操作实现方法和带头结点的单链表的操作实现方法类同，差别仅 在于： （1）在构造函数中，要加一条 head.next = head 语句。 （2）在 index(i)成员函数中，把循环结束判断条件 current != null 改为 current != head。 单链表只能从头结点开始遍历整个链表，而循环单链表则可以从表中任意结点开始遍历 整个链表。 有些情况为了方便操作，头指针将指向表尾，其好处是既能立即找到链表的尾结点，也容 易找到链表中的第一个结点。这种情况下串联两个链表要优于单链表。 2.5 双向链表 双向链表是每个结点除后继指针外还有一个前驱指针。和单链表类同，双向链表也有带头 结点结构和不带头结点结构两种，带头结点的双向链表更为常用；另外，双向链表也可以有循 环和非循环两种结构，循环结构的双向链表更为常用。 在双向链表中，每个结点包括三个域，分别是 element 域、next 域和 prior 域，其中 element 域为数据元素域，next 域为指向后继结点的对象引用，prior 域为指向前驱结点的对象引用。 . . head a0 a1 an-1
下图为双向链表结点的图示结构datapriornext图a是带头结点的空循环双向链表的图示结构。从图b可见，循环双向链表的next和prior各自构成自己的循环单链表。headLa.lahead-(b)在双向链表中，有如下关系：设对象引用p表示双向链表中的第i个结点，则p.next表示第i+1个结点，p.next.prior仍表示第i个结点，即p.next.prior==p；同样地，p.prior表示第i-1个结点，p.prior.next仍表示第i个结点，即p.prior.next==p。下图是双向链表上述关系的图示。Paaa-循环双向链表的插入过程如下图所示。图中的指针p表示要插入结点的位置，s表示要插入的结点，①、②、③、④表示实现插入过程的步骤。phead→aaa×①+②④? s.prior=p.prior②p.prior.next=s③ s.next=pp.prior=s循环双向链表的删除过程如图所示。图中的指针p表示要插入结点的位置，①、②表示实现删除过程的步骤
下图为双向链表结点的图示结构 图 a 是带头结点的空循环双向链表的图示结构。从图 b 可见，循环双向链表的 next 和 prior 各自构成自己的循环单链表。 在双向链表中，有如下关系：设对象引用 p 表示双向链表中的第 i 个结点，则 p.next 表示 第 i+1 个结点，p.next.prior 仍表示第 i 个结点，即 p.next.prior == p；同样地，p.prior 表示第 i-1 个结点，p.prior.next 仍表示第 i 个结点，即 p.prior.next == p。下图是双向链 表上述关系的图示。 循环双向链表的插入过程如下图所示。图中的指针 p 表示要插入结点的位置，s 表示要插 入的结点，①、②、③、④表示实现插入过程的步骤。 ① s.prior=p.prior ② p.prior.next=s ③ s.next=p ④ p.prior=s 循环双向链表的删除过程如图所示。图中的指针 p 表示要插入结点的位置，①、②表示实 现删除过程的步骤。 prior data next ( a) head 0 a 1 a . (b) n−1 head a ai−1 ai ai+1 p a0 ai . n−1 . a x i−1 a ① ② . ④ ③ p head s
heada-a.-l@p.prior.next=p.next②p.next.prior=p.prior2.6仿真链表在链式存储结构中，我们实现数据元素之间的次序关系依靠指针。我们也可以用数组来构造仿真链表。方法是在数组中增加一个（或两个）int类型的变量域，这些变量用来表示后个（或前一个）数据元素在数组中的下标。我们把这些int类型变量构造的指针称为仿真指针。这样，就可以用仿真指针构造仿真的单链表（或仿真的双向链表）。B-CEhead-2143:maxSize-1maxSize-1(c)(b)(a)是一个有5个数据元素的不带头结点的常规单链表，（b）和（c）是（a）的仿真单链表，其中数组的element域存放数据元素，数组的next域为该元素的后继元素在数组中的下标。next域值为一1是单链表表尾标志。（b）（c）是相同线性表结构的两个不同仿真单链表结构。分析各链表的特点循环链表的特点：从任一结点出发均可找到表中其他结点双向链表的特点：可方便找到任一结点的前驱仿真链表的特点：不用指针也能实现链式存储和运算【本讲课程的小结】这节课我们学习了循环单链表、双向链表以及仿真链表，并分析了这几种链表各自的特点，希望大家能够结合前两次课所学的顺序表以及单链表，对于具体的应用问题，能够针对问题的特点选择线性表适当的存储方式【本讲课程的作业】假设长度大于1的循环单链表中，既无头结点也无头指针，P指向该链表中某一结点，编写一个算法删除该结点的前驱结点
① p.prior.next=p.next ②p.next.prior=p.prior 2.6 仿真链表 在链式存储结构中，我们实现数据元素之间的次序关系依靠指针。我们也可以用数组来 构造仿真链表。方法是在数组中增加一个（或两个）int 类型的变量域，这些变量用来表示后一 个（或前一个）数据元素在数组中的下标。我们把这些 int 类型变量构造的指针称为仿真指针。 这样，就可以用仿真指针构造仿真的单链表（或仿真的双向链表）。 (a)是一个有 5 个数据元素的不带头结点的常规单链表，（b）和（c）是（a）的仿真单链表，其 中数组的 element 域存放数据元素，数组的 next 域为该元素的后继元素在数组中的下标。next 域值为－1 是单链表表尾标志。（b）（c）是相同线性表结构的两个不同仿真单链表结构。 分析各链表的特点 循环链表的特点：从任一结点出发均可找到表中其他结点 双向链表的特点：可方便找到任一结点的前驱 仿真链表的特点：不用指针也能实现链式存储和运算 【本讲课程的小结】这节课我们学习了循环单链表、双向链表以及仿真链表，并分析了这几种 链表各自的特点，希望大家能够结合前两次课所学的顺序表以及单链表，对于具体的应用问题， 能够针对问题的特点选择线性表适当的存储方式。 【本讲课程的作业】假设长度大于 1 的循环单链表中，既无头结点也无头指针，p 指向该链表 中某一结点，编写一个算法删除该结点的前驱结点。 . ai+1 . an−1 ① ② n−1 head a p ai−1 ai A B 1 2 C 3 D 4 E -1 0 1 2 3 4 maxSize-1 . element next A E 2 -1 B 4 D 1 C 3 0 1 2 3 4 maxSize-1 . next . . (a) (b) (c) head A B C D E ∧ element element next