循环链表和双向链表.ppt

数据结构与算法 ---第五讲
王伦津 研究员
循环链表、双向链表及线性表应用示例
1
5、循环链表和双向链表
本讲重点：带头结点的链表、循环链表和双向链表的特征，基本运算。对于循环链表要突出掌握判断链表空满的条件；双向链表要强调插入和删除算法的实现。最后通过多项式加法的示例，介绍线性表的应用。
2
目 录


双向链表
线性表的应用示例
3

带头结点的链表
有时候为了处理上的方便，在线性链表的第一个结点的前面增设一个特殊的结点，称为头结点。头结点逻辑上不属于相应的线性链表，它的作用主要有两点，一是存贮一些有关线性表的信息（如表中结点总数……），另一是为了算法处理上的方便。
图 5‑1 带头结点的链表
10
20
^
30
3
头指针
头结点
头元素
4
循环链表
图5 ‑2 循环单链表示意
20
(a) 不带头结点
(b) 带头结点
10
30
3
在线性表中，如果我们将第1 个结点视为最后一个结点的后继，将最后一个结点视为第1个结点的前趋，则这种线性表称为循环线性表，相应的链表称循环线性链表（简称循环链表）。
10
20
30
5
双向链表
为单向链表的每个结点增设一个指向相应结点的前趋的指针，使其同时包含前驱和后继，这样的链表称为双向链表（简称双链表）。双向链表的结点的结构如下所示：
这里各项含义为：
info---- 存放元素内容；
next----存放该元素的后继的指针（地址）；
prior----存放该元素的前驱的指针（地址）；
prior
info
next
6
循环单链表是单链表的另一种形式，其结构特点是链表中最后一个结点的指针不再是结束标记，而是指向整个链表的第一个结点，从而使单链表形成一个环。和单链表相比，循环单链表的长处是从链尾到链头比较方便。当要处理的数据元素序列具有环型结构特点时，适合于采用循环单链表。循环链表的插入、删除运算基本同单向链表，只是查找时判别条件不同而已；但是这种循环链表实现各种运算时的危险之处在于：链表没有明显的尾端，可能使算法进入死循环，()!=()!=null完成遍历所有结点。
7
（一）双链表的插入
现设在结点p之前插入结点q，其程序片段如下。
(1) q->next=p; //让q的next指向p
(2) q->prior=p->prior;
(3) p->prior->next=q;
(4) p->prior=q;
图5 ‑3 双链表插入
p
p->prior
p->next
(4)
q
(3)
(2)
(1)
注意关键的四个指针域的变化
8
(2)
(1)
p
p->prior
p->next
图 5‑ 4双链表的删除
（二）双链表删除
现设删除结点p所指结点，程序片段如下。
(1) p->prior->next=p->next;
(2) p->next->prior=p->prior;
(3) return p;
注意：关键的两个指针域的变化
9
线性表应用示例
集合运算
对集合结构，一般可用线性表表示。所以，对集合的操作，可以在线性表上进行。
这里只从算法角度介绍一种集合运算----(A-B)∪(B-A)的实现
为了说明前面给出的线性表类的使用，我们的实现在类TLinearListSqu的基础上进行。对应的子程序如下。
10