《循环链表和双向链表.ppt》由会员分享，可在线阅读，更多相关《循环链表和双向链表.ppt（38页珍藏版）》请在三一办公上搜索。
1、目 录,5.1带头结点的链表5.2循环链表5.3 双向链表5.4 线性表的应用示例,5.1几种特殊线性链表,5.1 带头结点的链表,有时候为了处理上的方便，在线性链表的第一个结点的前面增设一个特殊的结点，称为头结点。头结点逻辑上不属于相应的线性链表，它的作用主要有两点，一是存贮一些有关线性表的信息（如表中结点总数），另一是为了算法处理上的方便。,头指针,头结点,头元素,5.2 循环链表,图5 2 循环单链表示意,(a)不带头结点,(b)带头结点,在线性表中，如果我们将第1 个结点视为最后一个结点的后继，将最后一个结点视为第1个结点的前趋，则这种线性表称为循环线性表，相应的链表称循环线性链表（简
2、称循环链表）。,5.3 双向链表,为单向链表的每个结点增设一个指向相应结点的前趋的指针，使其同时包含前驱和后继，这样的链表称为双向链表（简称双链表）。双向链表的结点的结构如下所示：这里各项含义为：info-存放元素内容；next-存放该元素的后继的指针（地址）；prior-存放该元素的前驱的指针（地址）；,循环单链表是单链表的另一种形式，其结构特点是链表中最后一个结点的指针不再是结束标记，而是指向整个链表的第一个结点，从而使单链表形成一个环。和单链表相比，循环单链表的长处是从链尾到链头比较方便。当要处理的数据元素序列具有环型结构特点时，适合于采用循环单链表。循环链表的插入、删除运算基本同单向链
3、表，只是查找时判别条件不同而已；但是这种循环链表实现各种运算时的危险之处在于：链表没有明显的尾端，可能使算法进入死循环，所以判断条件应该用curr.next()!=head替换单向链表的curr.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;,注意关键的四个指针域的变化,（二）双链表删除,现设删除结点p所指结点，程序片段如下。(1)p-prior-next=p-next;(2)p-next
4、-prior=p-prior;(3)return p;,注意：关键的两个指针域的变化,5.4 线性表应用示例,5.4.1 集合运算,对集合结构，一般可用线性表表示。所以，对集合的操作，可以在线性表上进行。这里只从算法角度介绍一种集合运算-(A-B)(B-A)的实现 为了说明前面给出的线性表类的使用，我们的实现在类TLinearListSqu的基础上进行。对应的子程序如下。,A-B,B-A,AB,（A-B）（B-A）=（AB）-（AB）,long DiDiff(TLinearListSqu,先在B表中取得元素i的值，然后根据该值，查找属于A表中的第一个等于该值的序号，由于表的起始序号为0，故加1
5、,体现类模板的作用,5.5一元多项式相加,(一）一元多项式的表示数据结构,在数学上，一个一元n次多项式可表示为 Pn(x)=p0+p1x+p2x2+pnxn它由(n+1)个系数序列p0、p1、pn 唯一地确定。因此，在计算机中，它可用一个线性表P来表示：P=(p0,p1,pn)其中，pi代表Pn(x)中的i次项系数。在这种表示法中，系数所对应的指数隐含在系数的序号中，所以值为0的系数也要列出。现考虑两多项式进行符号相加的问题。设Qm(x)是另一个一元m次多项式，它的线性表表示为 Q=(q0,q1,qm),为解决0系数问题，可以不存贮0值元素。但这样就不能利用位置关系隐含指出系数对应的指数了，而
6、必须显式地给出指数。对任一个一元n次多项式，若不写出系数为0的项，则可表示为pn(x)=p1xe1+p2xe2+pnxen 这里，p1,p2,pn均非0，e1e2 en=n。显然，对此形式多项式，可确定地用下列形式的线性表表示(p1,e1),(p2,e2),(pn,en)该线性表每个元素是个二元组(pi,ei)，分别指出第i个非0项的系数和指数，二元组按指数递增的次序排列。在这种结构中，元素之间的次序关系仅代表元素对应的指数的大小关系。,对这种线性表，既可用顺序存贮结构，也可用链式存贮结构。但考虑到在进行符号加法时，要经常进行插入与删除操作，所以采用链式存贮结构较为合适。这里，我们采用动态链式
7、存贮结构，线性表每个元素的结构为,它的C/C+语言描述为struct TPolynomialItem float coef;int exp;该类型在我们前面给出的线性表中，相当于元素类型TElem，在具体使用线性表类时，应使用TPolynomialItem实例化TElem对应的类模板,为处理方便，在具体存储多项式时，我们规定：所存储的多项式已约简，即已合并同类项，不保留0系数项，各项按指数的升序排列。,(二）多项式加法实现直接操作链表,为操作方便，我采用带头结点的非循环链表，下面给出一个例子说明多项式的这种表示法。设有一个一元5次多项式：P5(x)=7+3x-9x3+x5具体链表表示方法如图
8、55,一元n次多项式的（符号）相加，实质上是合并同类项的过程，即指数相同的项，其系数相加，指数不同的项复抄。,下面考虑A(x)+B(x)A(x)的实现方法。即将多项式B(x)加到多项式A(x)上面，这里假设各多项式均已约简，且各项已按升序排列。用高级语言实现时，设两个指针p和q，初始时它们分别指向A(x)与B(x)中当前未被处理的结点中指数最小者。进行相加的过程，实质上是重复进行下列几个步骤：,（1）若pexpqexp，则结点q应为和的一个结点，故应将q 从B(x)中摘除后插入到A(x)中p之前，然后q向后移一步，p 不动。（3）若pexp=qexp,则表明p与q 所指为同类项，应合并，故要将
9、q的系数加到p的系数上。若相加结果为0，则表明和式中无此项，故应从A(x)中删除p，从B(x)中删除q,并令p 与q 分别指向下一结点。若相加和不为0，则表明相加结果应为和式中的一个结点，p 后移一步，然后将q从B(x)中摘除，令q指向下一结点。,下面先给出算法的伪码。p=A的第一个元素；q=B的第一个元素；while(p存在,在算法运行中，B(x)的链表中的结点，或被转移到A(x)链表上，或被删除，运行结束后，B(x)链表就不存在了，而A(x)链表就是所求的和。当然，也可以设计一个将B加到A上，但保留B，或将A+B之和放到另一链表中的算法。具体留作练习。,else if(p的指数 q的指数)
10、将q插入到p之前；令p0指向插入后的q，即p的当前前驱;令q指向它原所指的下一个结点；else x=p的系数+q的系数之和；if(x=0),删除p;使p指向它原指结点的下一个；else 令p的系数为x;使p指向它原指结点的下一个；删除q;使q指向它原指结点的下一个；/if(p的指数 q的指数)else/whileif(q不为空)将q挂接在p之后；,该程序不断比较A链和B链中的一对结点的指数值（称其为当前结点）。开始时A链和B链中参加比较的当前结点都是它们的第一个元素。主循环while结束后，可能出现下列3种情况：A链和B链同时被处理完；只有B链处理完；只有A链处理完。对第一和第二种情况，不需要
11、“善后”处理。对第三种情况，B链中尚有未被处理完的结点，需将其挂接在结果链的尾部。循环外的“if(q 不为空）将q挂接在p之后”就是处理该情况的。,一元n次多项式加法程序PolynomialAdd如下。为了能访问到TLinearListLink的私有成员，下面的PolynomialAdd函数应指定为TLinearListLink的友元。int PolynomialAdd(TLinearListLink,为什么这里对于a、b链表需要两个指针？,while(p!=NULL,else x=p-coef+q-coef;if(x=0)p0-next=p-next;delete p;/以上两句，将p从表中
12、删除并将其所指对象释放 p=p0-next;/令p指向相对于它原指的下一个/if(x=0)else p-coef=x;p0=p;,p=p-next;/if(x=0)else q0=q;q=q-next;delete q0;/将q所指结点从表中删除并释放，令q新指向原所指的下一个/if(p-exp q-exp)else/whileif(q!=NULL)p0-next=q;b.head-next=NULL;/此时，b中已只剩第一个结点（头），为其置空表标志return k;/返回结果链表中的元素个数,为了进一步说明上述程序，举一个程序运行的例子，其各次循环的运行结果如图5-6所示,（a）A(x)=
13、p5(x)=7+3x2-9x3+x5，进入循环前,（b)B(x)=3x+9x3+x5-X8，进入循环前,（d）B(x)：第一次进入循环后，q保持不变,（c）A(x)：第一次进入循环后，p 后移,（e）A(x)：第二次进入循环后，q被插入到p 前,（f）B(x):第二次进入循环后，q被插入到p 前,q重新指向下一个,（g）A(x)：第三次进入循环后，p 后移,（h）B(x)：第三次进入循环后，q保持不变,（i）A(x)：第四次进入循环后，p 被删除，重新指向下一个,（j）B(x)：第四次进入循环后，q 被删除，重新指向下一个,（k）A(x)：第五次进入循环后，p 与q合并，p重新指向下一个(空）
14、,（l）B(x)：第五次进入循环后，q 合并到p，然后被删除，重新指向下一个,（m）A(x)：退出循环后，q后面挂接了p的前驱的尾,（n）B(x)：退出循环后，q挂接到了p的前驱的后面,（三）多项式加法实现借助抽象操作,下面在前面给出的TLinearListSqu类(对TLunearListLink也相同)的基础上实现一元多项式相加。首先，定义表示多项式的元素的类型。多项式的元素类型已不是象long、float等那样的简单类型，所以必须考虑如何兼容基本操作中使用的赋值（=）运算、恒等运算（=）和输出运算（）等，即定义相应的运算符重载函数。,struct TPolynomialItem floa
15、t coef;int exp;operator=(TPolynomialItem,有了上面的定义，我们可以写出多项式加法程序了：long PolynomialAdd(TLinearListSqu,if(e1.exp e2.exp)a.Insert(e2,currE1+1);currE1+;b.Delete(currE2+1);k+;else e1.coef=e1.coef+e2.coef;,if(e1.coef=0)a.Delete(currE1+1);else a.Set(currE1,e1);currE1+;b.Delete(currE2+1);if(currE2 b.len)for(in
16、t i=currE2+1;ib.len+1;i+)a.Insert(*(b.Delete(i),a.len+1);return k;,一元多项式的乘法,设Am(x)与Bn(x)为两个一元多项式，设,其中，每一项aiBn(x)都是一个关于x的一元多项式。由此可知，两个一元多项式相乘，可以化为多个一元多项式相加，这可利用前面给出的算法实现。,它们的积为,本讲小结,本讲重点介绍带头结点的链表、循环链表和双向链表等几种特殊的线性链表的特征，基本运算。对于循环链表要突出掌握判断链表空满的条件；双向链表要强调插入和删除算法的实现。最后通过一元多项式加法的示例，介绍一元多项式的数据结构、它的直接操作链表和多项式加法的实现。重点说明前面的构造类TLinearListSqu/TLinearListSqu的应用。,思考与练习,1、分别针对链式与顺序存储结构，编写程序实现Josephus 问题：设有个人围坐在一个圆桌周围，从第个人开始数，数到第的人就出列，然后从出列这的下一个人开始重新按上述方式数，数到就出列，如此重复，直到所有的人都出列为止。要求给出每个人的出列次序，即求一个按出列次序排列的个人的顺序表。、在类TLinearListSqu 或TLinearListLink 基础上，实现一个学生基本信息登记表的操作，包括输入、修改、打印、查询、统计等功能。,
