第二章 线性表(3)

在双向链表中，每个结点包括三个域， 在双向链表中，每个结点包括三个域，分别是 element域、next域和 域和prior域，其中 域 域和 域 其中element域为数据 域为数据 元素域， 域为指向后继结点的对象引用， 元素域，next域为指向后继结点的对象引用，prior 域为指向后继结点的对象引用 域为指向前驱结点的对象引用。 域为指向前驱结点的对象引用。
...
an-1
head2
p=head1.next; head1.next=head2.next.next; head2.next=p;
b0
b1
...
bn-1
p a0 a1
head1
...
an-1
head2
b0
b1
...
bn-1
2.5
指针。 指针。
双向链表
双向链表是每个结点除后继指针外还有一个前驱 双向链表是每个结点除后继指针外还有一个前驱
提示： 提示：要考虑在第一个数据元素结点前插入和删除第一个数据元素 结点时与在其他位置插入和删除其他位置结点时的不同情况。 结点时与在其他位置插入和删除其他位置结点时的不同情况。
head
a0
a1
...
an-1 ^
插入
if(i==0){ head=new Node(obj, head); size++; } else{ index(i - 1); current.next=new Node(obj,current.next); size ++; }
ai−1
ai
双向链表的关系
ai+1
循环双向链表的插入过程如下图所示。 循环双向链表的插入过程如下图所示。图中的指针 p表示要插入结点的位置， s表示要插入的结点， ① 、 表示要插入结点的位置， 表示要插入的结点 表示要插入结点的位置 表示要插入的结点， ②、③、④表示实现插入过程的步骤。 表示实现插入过程的步骤。
上机练习：设计一个不带头结点的单链表类，要求： 上机练习：设计一个不带头结点的单链表类，要求：
（1）不带头结点单链表类的成员函数包括取数据元素个数、 ）不带头结点单链表类的成员函数包括取数据元素个数、 插入、删除、取数据元素。 插入、删除、取数据元素。 （2）设计一个测试主函数，实际运行验证所设计不带头结点 ）设计一个测试主函数， 的单链表各成员函数的正确性。 的单链表各成员函数的正确性。
下图是带头结点的循环双向链表的图示结构。 下图是带头结点的循环双向链表的图示结构。循环双向 链表的next和prior各自构成自己的循环单链表。 各自构成自己的循环单链表。 链表的 和 各自构成自己的循环单链表
head
(a)
head
a0
a1
...
an-1
(b)
带头结点的循环双向链表 ；（b） （a）空链表；（ ）非空链表 ）空链表；（
p
head ... ai-1 ai ai+1 ... an-1 a1 − n
①
②
① p.prior.next=p.next ② p.next.prior=p.prior
2.6 仿真链表
在链式存储结构中， 在链式存储结构中，我们实现数据元素之间的次序 关系依靠指针。我们可以用数组来构造仿真链表。 关系依靠指针。我们可以用数组来构造仿真链表。 方法是在数组中增加一个（或两个）int类型的变量 方法是在数组中增加一个（或两个） 类型的变量 域，这些变量用来表示后一个（或前一个）数据元素在 这些变量用来表示后一个（或前一个） 数组中的下标。我们把这些 类型变量构造的指针称为 数组中的下标。我们把这些int类型变量构造的指针称为 仿真指针。这样， 仿真指针。这样，就可以用仿真指针构造仿真的单链表 （或仿真的双向链表）。 或仿真的双向链表）。
a0
a1
...
an-1
Next
current = head.next; int j = 0; while((current != head) && j < i){ current=current.next; j ++; }
的循环单链表中， 例：假设长度大于1的循环单链表中，既无头结点也无头指针， 假设长度大于 的循环单链表中 既无头结点也无头指针， 单链表只能从头结点开始遍历整个链表，而循环单链表则 单链表只能从头结点开始遍历整个链表， p指向该链表中某一结点，编写一个算法删除该结点的前驱结 指向该链表中某一结点， 指向该链表中某一结点 可以从表中任意结点开始遍历整个链表。 任意结点开始遍历整个链表 可以从表中任意结点开始遍历整个链表。 点。 如何寻找前 驱结点？ 驱结点？ a0 p s=p; while(s.next.next!=p) s=s.next; s.next=p; 删除该结点的前驱结点 s指向该结点的前 驱结点的前驱结点 a1 a2
判断题： 判断题： （1）线性表的逻辑顺序与存储顺序总是一致的。 F ）线性表的逻辑顺序与存储顺序总是一致的。 （2）顺序存储的线性表可以按序号随机存取。 ）顺序存储的线性表可以按序号随机存取。 T
（3）在线性表的链式存储结构中，逻辑上相邻的元素在物理 ）在线性表的链式存储结构中， 位置上不一定相邻。 位置上不一定相邻。 T （4）在线性表的顺序存储结构中，插入和删除时移动元素 ）在线性表的顺序存储结构中， 的个数与该元素的位置有关。 的个数与该元素的位置有关。T （5）在单链表中，要取得某个元素，只要知道该元素的指针 ）在单链表中，要取得某个元素， 即可，因此单链表是随机存取的存储结构。 即可，因此单链表是随机存取的存储结构。 F
设对象引用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。 仍表示第 个结点， 。
删除
if(i==0){ Object obj=head.getElement(); head=head.next; size--; return obj; } else{ index(i - 1); Object obj = current.next.getElement(); current.next=current.next.next; size --; return obj; }
3.顺序存储 3.顺序存储
改进方案： 改进方案：链表存储结构
4.链式存储 4.链式存储
特征：逻辑上相邻，物理上未必相邻； 特征：逻辑上相邻，物理上未必相邻； 优点：插入、 优点：插入、删除快 O(1) 缺点： 缺点：随机查找慢 O(n)
5.几种特殊链表的特点： 5.几种特殊链表的特点： 几种特殊链表的特点 循环链表的特点：从任一结点出发均可找到表中其他结点 循环链表的特点： 双向链表的特点：可方便找到任一结点的前驱 双向链表的特点：可方便找到任一结点的前驱 仿真链表的特点： 仿真链表的特点：不用指针也能实现链式存储和运算
LinList(){ head = current = new Node(null); }
current head
^
public void index(int i) { if(i == -1) {current=head; return;} current = head.next; int j = 0; while((current != null) && j < i){ current=current.next; j ++; } } head
head
(a)
head
a0
(b)
a1
...
an-1
带头结点的循环单链表的操作实现方法和带头结点的单 链表的操作实现方法类同，差别仅在于： 链表的操作实现方法类同，差别仅在于： （1）在构造函数中，要把初始时的带头结点的循环单链表 ）在构造函数中， 设计成下图所示的状态。 设计成下图所示的状态。
head
第2章 线性表 章
2.1 线性表 2.2 顺序表 2.3 单链表 2.4 循环单链表 2.5 双向链表 2.6 仿真链表
2.4
循环单链表
循环单链表是单链表的另一种形式，其结构特点是链 循环单链表是单链表的另一种形式，其结构特点是链 表中最后一个结点的指针不再是结束标记， 表中最后一个结点的指针不再是结束标记 ， 而是指向整 个链表的第一个结点，从而使单链表形成一个环 个链表的第一个结点，从而使单链表形成一个环。 和单链表相比， 和单链表相比，循环单链表的长处是从链尾到链头比 较方便。 当要处理的数据元素序列具有环型结构特点时， 较方便 。 当要处理的数据元素序列具有环型结构特点时 ， 适合于采用循环单链表。 适合于采用循环单链表。
...
an-1 s
思考：对于单链表而言，连接两个单链表应该如 思考：对于单链表而言， 何实现？ 何实现？
current an-1 ^ bn-1 ^
head1
a0
a1
...
head2
b0
b1
...
current.next=head2.next 对于循环单链表呢？ 对于循环单链表呢？
p a0 a1
head1
p head
a0
...
ai−1
ai
Hale Waihona Puke ...a−1 n① ② ...④ ③
① s.prior=p.prior ② p.prior.next=s ③ s.next=p ④ p.prior=s