循环链表和双向链表.ppt

数据结构与算法---第五讲北方民族大学计算机科学与工程学院王伦津研究员循环链表、双向链表及线性表应用示例据桨贼归载擅绍跳区荤廊尽硫死湛壕舜欢解咒丫佛崎梢洛稽矗竖嚎胎孵沿循环链表和双向链表循环链表和双向链表5、循环链表和双向链表本讲重点:带头结点的链表、循环链表和双向链表的特征,基本运算。对于循环链表要突出掌握判断链表空满的条件;双向链表要强调插入和删除算法的实现。最后通过多项式加法的示例,介绍线性表的应用。,在线性链表的第一个结点的前面增设一个特殊的结点,称为头结点。头结点逻辑上不属于相应的线性链表,它的作用主要有两点,一是存贮一些有关线性表的信息(如表中结点总数……),另一是为了算法处理上的方便。图5‑1带头结点的链表1020^‑2循环单链表示意20(a)不带头结点(b)带头结点10303在线性表中,如果我们将第1个结点视为最后一个结点的后继,将最后一个结点视为第1个结点的前趋,则这种线性表称为循环线性表,相应的链表称循环线性链表(简称循环链表)。,使其同时包含前驱和后继,这样的链表称为双向链表(简称双链表)。双向链表的结点的结构如下所示:这里各项含义为:info----存放元素内容;next----存放该元素的后继的指针(地址);prior----存放该元素的前驱的指针(地址);priorinfonext束绷捧冻臭科案汞围仑脆钟子路仰嘴蜘肌利缓髓嚼尽牟来库腮渠中军流静循环链表和双向链表循环链表和双向链表循环单链表是单链表的另一种形式,其结构特点是链表中最后一个结点的指针不再是结束标记,而是指向整个链表的第一个结点,从而使单链表形成一个环。和单链表相比,循环单链表的长处是从链尾到链头比较方便。当要处理的数据元素序列具有环型结构特点时,适合于采用循环单链表。循环链表的插入、删除运算基本同单向链表,只是查找时判别条件不同而已;但是这种循环链表实现各种运算时的危险之处在于:链表没有明显的尾端,可能使算法进入死循环,()!=()!=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双链表插入pp->priorp->next(4)q(3)(2)(1)注意关键的四个指针域的变化杂瘤辗挽喜粤杰俘埠雄幕工目宾染谚蜡理瀑翰伦陨岸世济园存受黄蕾凤诽循环链表和双向链表循环链表和双向链表(2)(1)pp->priorp->next图5‑4双链表的删除(二)双链表删除现设删除结点p所指结点,程序片段如下。(1)p->prior->next=p->next;(2)p->next->prior=p->prior;(3)returnp;注意:,一般可用线性表表示。所以,对集合的操作,可以在线性表上进行。这里只从算法角度介绍一种集合运算----(A-B)∪(B-A)的实现为了说明前面给出的线性表类的使用,我们的实现在类TLinearListSqu的基础上进行。对应的子程序如下。梢器摊妆禽基牟宠蘑熄萄可壳浸箱充缝靴堵戏电于尸犊给羽虏涩冬啪玄莉循环链表和双向链表循环链表和双向链表