循环链表和双向链表.pptVIP

目录,5.1带头结点的链表5.2循环链表5.3双向链表5.4线性表的应用示例,5.1几种特殊线性链表,5.1带头结点的链表,有时候为了处理上的方便，在线性链表的第一个结点的前面增设一个特殊的结点，称为头结点。头结点逻辑上不属于相应的线性链表，它的作用主要有两点，一是存贮一些有关线性表的信息（如表中结点总数），另一是为了算法处理上的方便。,头指针,头结点,头元素,5.2循环链表,图52循环单链表示意,(a)不带头结点,(b)带头结点,在线性表中，如果我们将第1个结点视为最后一个结点的后继，将最后一个结点视为第1个结点的前趋，则这种线性表称为循环线性表，相应的链表称循环线性链表（简称循环链表）。,5.3双向链表,为单向链表的每个结点增设一个指向相应结点的前趋的指针，使其同时包含前驱和后继，这样的链表称为双向链表（简称双链表）。双向链表的结点的结构如下所示：这里各项含义为：info-存放元素内容；next-存放该元素的后继的指针（地址）；prior-存放该元素的前驱的指针（地址）；,循环单链表是单链表的另一种形式，其结构特点是链表中最后一个结点的指针不再是结束标记，而是指向整个链表的第一个结点，从而使单链表形成一个环。和单链表相比，循环单链表的长处是从链尾到链头比较方便。当要处理的数据元素序列具有环型结构特点时，适合于采用循环单链表。循环链表的插入、删除运算基本同单向链表，只是查找时判别条件不同而已；但是这种循环链表实现各种运算时的危险之处在于：链表没有明显的尾端，可能使算法进入死循环，所以判断条件应该用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-prior=p-prior;(3)returnp;,注意：关键的两个指针域的变化,5.4线性表应用示例,5.4.1集合运算,对集合结构，一般可用线性表表示。所以，对集合的操作，可以在线性表上进行。这里只从算法角度介绍一种集合运算-(A-B)(B-A)的实现为了说明前面给出的线性表类的使用，我们的实现在类TLinearListSqu的基础上进行。对应的子程序如下。,A-B,B-A,AB,（A-B）（B-A）=（AB）-（AB）,longDiDiff(TLinearListSqu,先在B表中取得元素i的值，然后根据该值，查找属于A表中的第一个等于该值的序号，由于表的起始序号为0，故加1,体现类模板的作用,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值元素。但这样就不能利用位置关系隐含指出系数对应的指数了，而必须显式地给出指数。对任一个一元n次多项式，若不写出系数为0的项，则可表示为pn(x)=p1xe1+p2xe2+pnxen这里，p1,p2,pn均非0，e1e2q的指数)else/whileif(q不为空)将q挂接在p之后；,该程序不断比较A链和B链中的一对结点的指数值（称其为当前结点）。开始时A链和B链中参加比较的当前结点都是它们的第一个元素。主循环while结束后，可能出现下列3种情况：A链和B链同时被处理完；只有B链处理完；只有A链处理完。对第一和第二种情况，不需要“善后”处理。对第三种情况，B链中尚有未被处理完的结点，需将其挂接在结果链的尾部。循环外的“if(q不为空）将q挂接在p之后”就是处理该情况的。,一元n次多项式加法程序PolynomialAdd如下。为了能访问到TLinearListLink的私有成员，下面的PolynomialAdd函数应指定为TLinearListLink的友元。intPolynomialAdd(TLinearListLink,为什么这里对于a、b链表需要两个指针？,while(p!=NULL,elsex=p-coef+q-coef;if(x=0)p0-next=p-next;deletep;/以上两句，将p从表中删除并将其所指对象释放p=p0-next;/令p指向相对于它原指的下一个/if(x=0)elsep-coef=x;p0=p;,p=p-next;/if(x=0)elseq0=q;q=q-next;deleteq0;/将q所指结点从表中删除并释放，令q新指向原所指的下一个/if(p-expq-exp)else/whileif(q!=NULL)p0-next=q;b.head-next=NULL;/此时，b中已只剩第一个结点（头），为其置空表标志returnk;/返回结果链表中的元素个数,为了进一步说明上述程序，举一个程序运行的例子，其各次循环的运行结果如图5-6所示,（a）A(x)=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重新指向下一个(空）,（l）B(x)：第五次进入循环后，q合并到p，然后被删除，重新指向下一个,（m）A(x)：退出循环后，q后面挂接了p的前驱的尾,（n）B(x)：退出循环后，q挂接到了p的前驱的后面,（三）多项式加法实现借助抽象操作,下面在前面给出的TLinearListSqu类(对TLunearListLink也相同)的基础上实现一元多项式相加。首先，定义表示多项式的元素的类型。多项式的元素类型已不是象long、float等那样的简单类型，所以必须考虑如何兼容基本操作中使用的赋值（=）运算、恒等运算（=）和输出运算（）等，即定义相应的运算符重载函数。,structTPolynomialItemfloatcoef;intexp;operator=(TPolynomialItem,有了上面的定义，我们可以写出多项式加法程序了：longPolynomialAdd(TLinearListSqu,if(e1.expe2.exp)a.Insert(e2,currE1+1);currE1+;b.Delete(currE2+1);k+;elsee1.coef=e1.coef+e2.coef;,if(e1.coef=0)a.Delete(currE1+1);elsea.Set(currE1,e1);currE1+;b.Delete(currE2+1);if(currE2b.len)for(inti=currE2+1;ib.len+1;i+)a.Insert(*(b.Delete(i),a.len+1);returnk;,一元多项式的乘法,设Am(x)与Bn(x)为两个一元多项式，设,其中，每一项aiBn(x)都是一个关于x的一元多项式。由此可知，两个一元多项式相乘，可以化为多个一元多项式相加，这可利用前面给出的算法实现。,它们的积为,本讲小结,本讲重点介绍带头结点的链表、循环链表和双向链表等几种特殊的线性链表的特征，基本运算。对于循环链表要突出掌握判断链表空满的条件；双向链表要强调插入和删除算法的实现。最后通过一元多项式加法的示例，介绍一元多项式的数据结构、它的直接操作链表和多项式加法的实现。重点说明前面的构造类TLinearListSqu/TLinearListSqu的应用。,思考与练习,1、分别针对链式与顺序存储结构，编写程序实现Joseph