循环链表和双向链表.ppt

,在线性链表的第一个结点的前面增设一个特殊的结点,称为头结点。头结点逻辑上不属于相应的线性链表,它的作用主要有两点,一是存贮一些有关线性表的信息(如表中结点总数……),另一是为了算法处理上的方便。图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的基础上进行。对应的子程序如下。其惑彪龙报舔驴艰冠壹条遏翌铂之劳豆暮笛制绦院俐窗疯伯肿修破岸途尊循环链表和双向链表循环链表和双向链表A-BB-AA∩B(A-B)∪(B-A)=(A∪B)-(A∩B)识坛肖儒伤拼尊埋条沾彻淖榴嚏面是模遣货井道难摆诉辕念娟星同晰捡辊循环链表和双向链表循环链表和双向链表longDiDiff(TLinearListSqu<long>&a,TLinearListSqu<long>&b){//将a中的出现在b中的元素删除,返回从a中删除的元素的数//目a和b都是前面定义的线性表类,元素类型实例化为long。longi,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++}}returnj;}先在B表中取得元素i的值,然后根据该值,查找属于A表中的第一个等于该值的