循环链表和双向链表.ppt

目 录



线性表的应用示例
循环链表和双向链表

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