《最新循环链表和双向链表PPT课件.ppt》由会员分享，可在线阅读，更多相关《最新循环链表和双向链表PPT课件.ppt（39页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、循环链表和双向链表循环链表和双向链表5.1几种特殊线性链表几种特殊线性链表 5.1 带头结点的链表 有时候为了处理上的方便，在线性链表的第一个结点的有时候为了处理上的方便，在线性链表的第一个结点的前面前面增设一个特殊的结点，称为头结点增设一个特殊的结点，称为头结点。头结点逻辑上不属。头结点逻辑上不属于相应的线性链表，它的作用主要有两点，一是存贮一些有于相应的线性链表，它的作用主要有两点，一是存贮一些有关线性表的信息（如表中结点总数关线性表的信息（如表中结点总数），另一是为了算法），另一是为了算法处理上的方便。处理上的方便。图图 51 带头结点的链表带头结点的链表1020303 头指针头结点头元
2、素A-BB-AAB（A-B）（B-A）=（AB）-（AB）longDiDiff(TLinearListSqu&a,TLinearListSqu&b)/将将a中的出现在中的出现在b中的元素删除，返回从中的元素删除，返回从a中删除的元素的数中删除的元素的数/目目a和和b都是前面定义的线性表类，都是前面定义的线性表类，元素类型实例化为元素类型实例化为long。longi,j,k;j=0;for(i=0;i0)/如在如在a中，则从中，则从a中将其删除中将其删除a.Delete(k+1);j-;Elsea.Insert(b.Get(i),1);j+returnj;先在B表中取得元素i的值，然后根据该值，
3、查找属于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次项系数。次项系数。在这种表示法中，在这种表示法中，系数所对应的指数隐含在系数的序号中，所
4、系数所对应的指数隐含在系数的序号中，所以值为以值为0的系数也要列出。的系数也要列出。现考虑两多项式进行符号相加的问题。设现考虑两多项式进行符号相加的问题。设Qm(x)是另一个一元是另一个一元m次多项式，它的线性表表示为次多项式，它的线性表表示为Q=(q0,q1,qm)为解决为解决0系数问题，可以不存贮系数问题，可以不存贮0值元素。但这样值元素。但这样就不能利用位置关系隐含指出系数对应的指数了，就不能利用位置关系隐含指出系数对应的指数了，而必须显式地给出指数。而必须显式地给出指数。对任一个一元对任一个一元n次多项式，若不写出系数为次多项式，若不写出系数为0的项，的项，则可表示为则可表示为pn(x
5、)=p1xe1+p2xe2+pnxen这里，这里，p1,p2,pn均非均非0，e1e2en=n。显然，对此形式多项式，可确定地用下列形式的显然，对此形式多项式，可确定地用下列形式的线性表表示线性表表示(p1,e1),(p2,e2),(pn,en)该线性表每个元素是个二元组该线性表每个元素是个二元组(pi,ei)，分别指出第，分别指出第i个非个非0项的系数和指数，二元组按指数递增的次序排项的系数和指数，二元组按指数递增的次序排列。列。在这种结构中，元素之间的次序关系仅代表元在这种结构中，元素之间的次序关系仅代表元素对应的指数的大小关系。素对应的指数的大小关系。n对这种线性表，既可用顺序存贮结构，
6、也可用链式对这种线性表，既可用顺序存贮结构，也可用链式存贮结构。但考虑到在进行符号加法时，要经常进存贮结构。但考虑到在进行符号加法时，要经常进行插入与删除操作，所以采用链式存贮结构较为合行插入与删除操作，所以采用链式存贮结构较为合适。这里，我们采用动态链式存贮结构，线性表每适。这里，我们采用动态链式存贮结构，线性表每个元素的结构为个元素的结构为系数指数它的它的C/C+语言描述为语言描述为structTPolynomialItemfloatcoef;intexp;该类型在我们前面给出的线性表中，相当于元素类型该类型在我们前面给出的线性表中，相当于元素类型TElem，在具体使用线性表类时，应使用，
7、在具体使用线性表类时，应使用TPolynomialItem实例化实例化TElem对应的类模板对应的类模板为处理方便，在具体存储多项式时，为处理方便，在具体存储多项式时，我们规定：我们规定：所存储的多项式已约简，即已合并同类项，不保所存储的多项式已约简，即已合并同类项，不保留留0系数项，各项按指数的升序排列。系数项，各项按指数的升序排列。(二）多项式加法实现二）多项式加法实现直接操作链表直接操作链表为操作方便，我采用带头结点的非循环链表，下面给出为操作方便，我采用带头结点的非循环链表，下面给出一个例子说明多项式的这种表示法。一个例子说明多项式的这种表示法。设有一个一元设有一个一元5次多项式：次多
8、项式：P5(x)=7+3x-9x3+x5具体链表表示方法如图具体链表表示方法如图5 5一元一元n次多项式的（符号）相加，实质上是合次多项式的（符号）相加，实质上是合并同类项的过程，即指数相同的项，其系数相加，并同类项的过程，即指数相同的项，其系数相加，指数不同的项复抄。指数不同的项复抄。7031-9 315 图图 55 一个一元一个一元5次多项式的链表表示次多项式的链表表示下面考虑下面考虑A(x)+B(x)A(x)A(x)+B(x)A(x)的实现方法。即将多项式的实现方法。即将多项式B(x)B(x)加加到多项式到多项式A(x)A(x)上面，这里假设各多项式均已约简，且各项已上面，这里假设各多项
9、式均已约简，且各项已按升序排列。按升序排列。用高级语言实现时，设两个指针用高级语言实现时，设两个指针p p和和q q，初始时它们分别指，初始时它们分别指向向A(x)A(x)与与B(x)B(x)中当前未被处理的结点中指数最小者。进行相中当前未被处理的结点中指数最小者。进行相加的过程，实质上是重复进行下列几个步骤：加的过程，实质上是重复进行下列几个步骤：（1 1）若若pexpqexp,pexpqexp pexpqexp，则结点，则结点q q应为和的一个结点，应为和的一个结点，故应将故应将q q 从从B(x)B(x)中摘除后插入到中摘除后插入到A(x)A(x)中中p p之前，然后之前，然后q q向后
10、移一步，向后移一步，p p 不动。不动。（3 3）若）若pexp=qexp,pexp=qexp,则表明则表明p p与与q q 所指为同类项，所指为同类项，应合并，故要将应合并，故要将q q的系数加到的系数加到p p的系数上。若相加结果的系数上。若相加结果为为0 0，则表明和式中无此项，故应从，则表明和式中无此项，故应从A(x)A(x)中删除中删除p p，从从B(x)B(x)中删除中删除q,q,并令并令p p 与与q q 分别指向下一结点。若分别指向下一结点。若相加和不为相加和不为0 0，则表明相加结果应为和式中的一个结，则表明相加结果应为和式中的一个结点，点，p p 后移一步，然后将后移一步，
11、然后将q q从从B(x)B(x)中摘除，令中摘除，令q q指向指向下一结点。下一结点。下面先给出算法的伪码。下面先给出算法的伪码。p=A的第一个元素；的第一个元素；q=B的第一个元素；的第一个元素；while(p存在存在&q存在存在)if(p的指数的指数next;在算法运行中，在算法运行中，B(x)B(x)的链表中的结点，或被转移到的链表中的结点，或被转移到A(x)A(x)链表上，或被删除，运行结束后，链表上，或被删除，运行结束后，B(x)B(x)链表链表就不存在了，而就不存在了，而A(x)A(x)链表就是所求的和。当然，也链表就是所求的和。当然，也可以设计一个将可以设计一个将B B加到加到A
12、 A上，但保留上，但保留B B，或将，或将A+BA+B之和之和放到另一链表中的算法。具体留作练习。放到另一链表中的算法。具体留作练习。elseif(p的指数的指数q的指数的指数)将将q插入到插入到p之前；之前；令令p0指向插入后的指向插入后的q，即，即p的当前前驱的当前前驱;令令q指向它原所指的下一个结点；指向它原所指的下一个结点；elsex=p的系数的系数+q的系数之和；的系数之和；if(x=0)删除删除p;使使p指向它原指结点的下一个；指向它原指结点的下一个；else令令p的系数为的系数为x;使使p指向它原指结点的下一个；指向它原指结点的下一个；删除删除q;使使q指向它原指结点的下一个；指
13、向它原指结点的下一个；/if(p的指数的指数q的指数的指数)else/whileif(q不为空不为空)将将q挂接在挂接在p之后；之后；该程序不断比较该程序不断比较A链和链和B链中的一对结点的指数值链中的一对结点的指数值（称其为当前结点）。开始时（称其为当前结点）。开始时A链和链和B链中参加比较链中参加比较的当前结点都是它们的第一个元素。的当前结点都是它们的第一个元素。主循环主循环while结束后，可能出现下列结束后，可能出现下列3种情况：种情况：A A链链和和B B链同时被处理完；链同时被处理完；只有只有B B链处理完；链处理完；只有只有A A链链处理完。处理完。对第一和第二种情况，不需要对第
14、一和第二种情况，不需要“善后善后”处理。对第处理。对第三种情况，三种情况，B B链中尚有未被处理完的结点，需将其挂链中尚有未被处理完的结点，需将其挂接在结果链的尾部。循环外的接在结果链的尾部。循环外的“if(q if(q 不为空）将不为空）将q q挂接在挂接在p p之后之后”就是处理该情况的。就是处理该情况的。n一元n次多项式加法程序PolynomialAdd如下。为了能访问到TLinearListLink的私有成员，下面的PolynomialAdd函数应指定为TLinearListLink的友元。intPolynomialAdd(TLinearListLink&a,TLinearListLi
15、nk&b)/线性表线性表a和和b的元素类型被实例化为的元素类型被实例化为TPolynomialItemTLinkNode*p,*p0,*q,*q0;floatx;longk;k=0;p=a.head-next;p0=a.head;q=b.head-next;为什么这里对于为什么这里对于a、b链表需要链表需要两个指针？两个指针？while(p!=NULL&q!=NULL)if(p-expexp)p0=p;/永远使永远使p0保持为保持为p的前驱，以方便对在的前驱，以方便对在p前插入，或删除前插入，或删除pp=p-next;k+;elseif(p-expq-exp)q0=q;/在下面用在下面用q0操
16、作原操作原qq=q-next;/q先行一步先行一步q0-next=p;p0-next=q0;/以上两句，将以上两句，将q0插入到插入到p0之后（即之后（即p之前）之前）k+;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所指结点从表中删除
17、并释放，令所指结点从表中删除并释放，令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
18、)：第一次进入循环后，：第一次进入循环后，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)：第四次进入循环后，：第四次进入循环后，
19、q被删除，重新指向下一个被删除，重新指向下一个（k）A(x)：第五次进入循环后，：第五次进入循环后，p与与q合并，合并，p重新指向下一个重新指向下一个(空）空）（l）B(x)：第五次进入循环后，：第五次进入循环后，q合并到合并到p，然后被删除，重新指向下一个，然后被删除，重新指向下一个（m）A(x)：退出循环后，：退出循环后，q后面挂接了后面挂接了p的前驱的尾的前驱的尾（n）B(x)：退出循环后，：退出循环后，q挂接到了挂接到了p的前驱的后面的前驱的后面（三）多项式加法实现（三）多项式加法实现借助抽象操作借助抽象操作 下面在前面给出的TLinearListSqu类(对TLunearListLi
20、nk也相同)的基础上实现一元多项式相加。首先，定义表示多项式的元素的类型。多项式的元素类型已不是象long、float等那样的简单类型，所以必须考虑如何兼容基本操作中使用的赋值（=）运算、恒等运算（=）和输出运算（coef=i1.coef;/定义多项式项赋值为指数和系数分别赋值定义多项式项赋值为指数和系数分别赋值this-exp=i1.exp;returni1;ostream&operator(ostream&oo,TPolynomialItem&i1)/重载标准输出算符，以支持重载标准输出算符，以支持Print()ooi1.coef,i1.exp;returnoo;有了上面的定义，我们可以写
21、出多项式加法程序了：有了上面的定义，我们可以写出多项式加法程序了：longPolynomialAdd(TLinearListSqu&a,TLinearListSqu&b)longcurrE1,currE2,k;TPolynomialIteme1,e2;k=0;/记录最终元素个数记录最终元素个数currE1=0;/记录线性表记录线性表a的元素序号的元素序号currE2=0;/记录线性表记录线性表b的元素序号的元素序号while(currE1a.len&currE2b.len)e1=a.Get(currE1);/按序号取对应元素内容按序号取对应元素内容e2=b.Get(currE2);if(e1.
22、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)都是
23、一个关于x的一元多项式。由此可知，两个一元多项式相乘，可以化为多个一元多项式相加，这可利用前面给出的算法实现。它们的积为本讲小结本讲重点介绍带头结点的链表、循环链表和双向链表等几种特殊的线性链表的特征，基本运算。对于循环链表要突出掌握判断链表空满的条件；双向链表要强调插入和删除算法的实现。最后通过一元多项式加法的示例，介绍一元多项式的数据结构、它的直接操作链表和多项式加法的实现。重点说明前面的构造类TLinearListSqu/TLinearListSqu的应用。思考与练习1、分别针对链式与顺序存储结构，编写程序实现Josephus 问题：设有个人围坐在一个圆桌周围，从第个人开始数，数到第的人就出列，然后从出列这的下一个人开始重新按上述方式数，数到就出列，如此重复，直到所有的人都出列为止。要求给出每个人的出列次序，即求一个按出列次序排列的个人的顺序表。、在类TLinearListSqu 或TLinearListLink 基础上，实现一个学生基本信息登记表的操作，包括输入、修改、打印、查询、统计等功能。结束语结束语谢谢大家聆听！谢谢大家聆听！39