循环链表和双向链表

《循环链表和双向链表》由会员分享，可在线阅读，更多相关《循环链表和双向链表（38页珍藏版）》请在金锄头文库上搜索。

1、目 录5.1带头结点的链表5.2循环链表5.3 双向链表5.4 线性表的应用示例5.1几种特殊线性链表几种特殊线性链表 5.1 带头结点的链表 有时候为了处理上的方便，在线性链表的第一个结点的有时候为了处理上的方便，在线性链表的第一个结点的前面前面增设一个特殊的结点，称为头结点增设一个特殊的结点，称为头结点。头结点逻辑上不属。头结点逻辑上不属于相应的线性链表，它的作用主要有两点，一是存贮一些有于相应的线性链表，它的作用主要有两点，一是存贮一些有关线性表的信息（如表中结点总数关线性表的信息（如表中结点总数），另一是为了算法），另一是为了算法处理上的方便。处理上的方便。 图图 51 带头结点的链表

2、带头结点的链表1020303 头指针头结点头元素5.2 循环链表循环链表 图图5 2 循环单链表示意循环单链表示意20(a) 不带头结点不带头结点(b) 带头结点带头结点10303 n在线性表中，如果我们将第在线性表中，如果我们将第1 个结点视为最后一个个结点视为最后一个结点的后继，将最后一个结点视为第结点的后继，将最后一个结点视为第1个结点的前个结点的前趋，则这种线性表称为循环线性表，相应的链表称趋，则这种线性表称为循环线性表，相应的链表称循环线性链表（简称循环链表）。循环线性链表（简称循环链表）。 1020305.3 双向链表双向链表 为单向链表的每个结点增设一个指向相应结点为单向链表的每

3、个结点增设一个指向相应结点的前趋的指针，使其同时包含前驱和后继，这样的的前趋的指针，使其同时包含前驱和后继，这样的链表称为双向链表（简称双链表）。双向链表的结链表称为双向链表（简称双链表）。双向链表的结点的结构如下所示：点的结构如下所示： 这里各项含义为：这里各项含义为：info- 存放元素内容；存放元素内容；next-存放该元素的后继的指针（地址）；存放该元素的后继的指针（地址）；prior-存放该元素的前驱的指针（地址）；存放该元素的前驱的指针（地址）；priorinfonext循循环环单单链链表表是是单单链链表表的的另另一一种种形形式式，其其结结构构特特点点是是链链表表中中最最后后一一个

4、个结结点点的的指指针针不不再再是是结结束束标标记记，而而是是指指向向整整个个链链表表的的第第一一个个结结点点，从从而而使使单单链链表表形形成成一一个个环环。和和单单链链表表相相比比，循循环环单单链链表表的的长长处处是是从从链链尾尾到到链链头头比比较较方方便便。当当要要处处理理的的数数据据元元素素序序列列具具有有环环型型结结构构特特点点时时，适适合合于于采采用用循循环环单单链链表表。循循环环链链表表的的插插入入、删删除除运运算算基基本本同同单单向向链链表表，只只是是查查找找时时判判别别条条件件不不同同而而已已；但但是是这这种种循循环环链链表表实实现现各各种种运运算算时时的的危危险险之之处处在在于

5、于：链链表表没没有有明明显显的的尾尾端端，可可能能使使算算法法进进入入死死循循环环，所所以以判判断断条条件件应应该该用用curr.next()!=headcurr.next()!=head替替换换单单向向链链表表的的curr.next()!=nullcurr.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;图5 3 双链表插入pp-priorp-

6、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) return p; 注意：关键的两个指针域的变化5.4 线性表应用示例线性表应用示例 5.4.1 集合运算 对集合结构，一般可用线性表表示。所以，对集合的操作，可以在线性表上进行。 这里只从算法角度介绍一种集合运算-(A-B)(B-A)的实现 为了说明前面给出的线性表类的使

7、用，我们的实现在类TLinearListSqu的基础上进行。对应的子程序如下。 A-BB-AAB（A-B）（B-A）=（AB）-（AB）long DiDiff(TLinearListSqu &a, TLinearListSqu &b)/将将a中的出现在中的出现在b中的元素删除，返回从中的元素删除，返回从a中删除的元素的数中删除的元素的数/目目 a和和b都是前面定义的线性表类，都是前面定义的线性表类，元素类型实例化为元素类型实例化为long。 long i,j, k; j=0; for (i=0; i 0 ) /如在如在a中，则从中，则从a中将其删除中将其删除 a.Delete(k+1); j-

8、;Else a.Insert(b.Get(i),1);j+ return j; 先在B表中取得元素i的值，然后根据该值，查找属于A表中的第一个等于该值的序号，由于表的起始序号为0，故加1体现类模板的作用体现类模板的作用5.5一元多项式相加一元多项式相加 (一）一元多项式的表示数据结构 在数学上，一个一元在数学上，一个一元n次多项式可表示为次多项式可表示为 Pn(x)=p0+p1x+p2x2+pnxn它由它由(n+1)个系数序列个系数序列p0、p1、pn 唯一地确定。因此，在唯一地确定。因此，在计算机中，它可用一个线性表计算机中，它可用一个线性表P来表示：来表示：P=(p0, p1, ,pn)其

9、中，其中，pi代表代表Pn(x)中的中的i次项系数。次项系数。在这种表示法中，在这种表示法中，系数所对应的指数隐含在系数的序号中，所系数所对应的指数隐含在系数的序号中，所以值为以值为0的系数也要列出。的系数也要列出。现考虑两多项式进行符号相加的问题。设现考虑两多项式进行符号相加的问题。设Qm(x)是另一个一元是另一个一元m次多项式，它的线性表表示为次多项式，它的线性表表示为 Q=(q0, q1, , qm) 为解决为解决0系数问题，可以不存贮系数问题，可以不存贮0值元素。但这样值元素。但这样就不能利用位置关系隐含指出系数对应的指数了，就不能利用位置关系隐含指出系数对应的指数了，而必须显式地给出

10、指数。而必须显式地给出指数。 对任一个一元对任一个一元n次多项式，若不写出系数为次多项式，若不写出系数为0的项，的项，则可表示为则可表示为pn(x) = p1xe1+p2xe2+ +pnxen 这里，这里，p1, p2, , pn均非均非0，e1e2 en=n。 显然，对此形式多项式，可确定地用下列形式的显然，对此形式多项式，可确定地用下列形式的线性表表示线性表表示(p1,e1), (p2,e2), , (pn,en) ) 该线性表每个元素是个二元组该线性表每个元素是个二元组(pi,ei)，分别指出第，分别指出第i个非个非0项的系数和指数，二元组按指数递增的次序排项的系数和指数，二元组按指数递

11、增的次序排列。列。在这种结构中，元素之间的次序关系仅代表元在这种结构中，元素之间的次序关系仅代表元素对应的指数的大小关系。素对应的指数的大小关系。n对这种线性表，既可用顺序存贮结构，也可用链式对这种线性表，既可用顺序存贮结构，也可用链式存贮结构。但考虑到在进行符号加法时，要经常进存贮结构。但考虑到在进行符号加法时，要经常进行插入与删除操作，所以采用链式存贮结构较为合行插入与删除操作，所以采用链式存贮结构较为合适。这里，我们采用动态链式存贮结构，线性表每适。这里，我们采用动态链式存贮结构，线性表每个元素的结构为个元素的结构为系数指数它的它的C/C+语言描述为语言描述为struct TPolyno

12、mialItem float coef; int exp; 该类型在我们前面给出的线性表中，相当于元素类型该类型在我们前面给出的线性表中，相当于元素类型TElem，在具体使用线性表类时，应使用，在具体使用线性表类时，应使用TPolynomialItem实例化实例化TElem对应的类模板对应的类模板 为处理方便，在具体存储多项式时，为处理方便，在具体存储多项式时，我们规定：我们规定： 所存储的多项式已约简，即已合并同类项，不保所存储的多项式已约简，即已合并同类项，不保留留0系数项，各项按指数的升序排列。系数项，各项按指数的升序排列。 (二）多项式加法实现二）多项式加法实现直接操作链表直接操作链表

13、 为操作方便，我采用带头结点的非循环链表，下面给出为操作方便，我采用带头结点的非循环链表，下面给出一个例子说明多项式的这种表示法。一个例子说明多项式的这种表示法。设有一个一元设有一个一元5次多项式：次多项式： P5(x)=7+3x-9x3+x5 具体链表表示方法如图具体链表表示方法如图 5 5 一元一元n次多项式的（符号）相加，实质上是合次多项式的（符号）相加，实质上是合并同类项的过程，即指数相同的项，其系数相加，并同类项的过程，即指数相同的项，其系数相加，指数不同的项复抄。指数不同的项复抄。7031-9 315 图图 55 一个一元一个一元5次多项式的链表表示次多项式的链表表示下面考虑下面考

14、虑A(x)+B(x) A(x)A(x)+B(x) A(x)的实现方法。即将多项式的实现方法。即将多项式B(x)B(x)加加到多项式到多项式A(x)A(x)上面，这里假设各多项式均已约简，且各项已上面，这里假设各多项式均已约简，且各项已按升序排列。按升序排列。用高级语言实现时，设两个指针用高级语言实现时，设两个指针p p和和q q ，初始时它们分别指，初始时它们分别指向向A(x)A(x)与与B(x)B(x)中当前未被处理的结点中指数最小者。进行相中当前未被处理的结点中指数最小者。进行相加的过程，实质上是重复进行下列几个步骤：加的过程，实质上是重复进行下列几个步骤：（1 1）若若pexpqexp,

15、 pexpqexp pexpqexp ，则结点，则结点q q应为和的一个结点，应为和的一个结点，故应将故应将q q 从从B(x)B(x)中摘除后插入到中摘除后插入到A(x)A(x)中中p p之前，然后之前，然后q q向后移一步，向后移一步，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

16、) 中删除中删除q,q,并令并令p p 与与q q 分别指向下一结点。若分别指向下一结点。若相加和不为相加和不为0 0，则表明相加结果应为和式中的一个结，则表明相加结果应为和式中的一个结点，点，p p 后移一步，然后将后移一步，然后将q q从从B(x) B(x) 中摘除，令中摘除，令q q指向指向下一结点。下一结点。下面先给出算法的伪码。下面先给出算法的伪码。p=A的第一个元素；的第一个元素；q=B的第一个元素；的第一个元素；while (p存在存在 & q存在存在) if (p的指数的指数 next; 在算法运行中，在算法运行中，B(x)B(x)的链表中的结点，或被转移到的链表中的结点，或被

17、转移到A(x) A(x) 链表上，或被删除，运行结束后，链表上，或被删除，运行结束后，B(x) B(x) 链表链表就不存在了，而就不存在了，而A(x)A(x)链表就是所求的和。当然，也链表就是所求的和。当然，也可以设计一个将可以设计一个将B B加到加到A A上，但保留上，但保留B B，或将，或将A+BA+B之和之和放到另一链表中的算法。具体留作练习。放到另一链表中的算法。具体留作练习。else if (p的指数的指数 q的指数的指数) 将将q插入到插入到p之前；之前； 令令p0指向插入后的指向插入后的q，即，即p的当前前驱的当前前驱; 令令q指向它原所指的下一个结点；指向它原所指的下一个结点；

18、 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链中参加比

19、较链中参加比较的当前结点都是它们的第一个元素。的当前结点都是它们的第一个元素。主循环主循环while结束后，可能出现下列结束后，可能出现下列3种情况：种情况：A A链链和和B B链同时被处理完；链同时被处理完；只有只有B B链处理完；链处理完；只有只有A A链链处理完。处理完。对第一和第二种情况，不需要对第一和第二种情况，不需要“善后善后”处理。对第处理。对第三种情况，三种情况，B B链中尚有未被处理完的结点，需将其挂链中尚有未被处理完的结点，需将其挂接在结果链的尾部。循环外的接在结果链的尾部。循环外的“if(q if(q 不为空）将不为空）将q q挂接在挂接在p p之后之后”就是处理该情况的

20、。就是处理该情况的。 n一元n次多项式加法程序PolynomialAdd如下。为了能访问到TLinearListLink的私有成员，下面的PolynomialAdd函数应指定为TLinearListLink的友元。int PolynomialAdd(TLinearListLink &a, TLinearListLink &b)/线性表线性表a和和b的元素类型被实例化为的元素类型被实例化为TPolynomialItem TLinkNode *p, *p0, *q, *q0; float x; long k; k=0; p = a.head-next; p0 = a.head; q = b.hea

21、d-next;为什么这里对于为什么这里对于a、b链表需要链表需要两个指针？两个指针？ while (p!=NULL & q!=NULL) if (p-exp exp) p0 = p; /永远使永远使p0保持为保持为p的前驱，以方便对在的前驱，以方便对在p前插入，或删除前插入，或删除p p = p-next; k+; else if (p-exp q-exp ) q0 = q; /在下面用在下面用q0操作原操作原q q = q-next; /q先行一步先行一步 q0-next = p; p0-next = q0; / 以上两句，将以上两句，将q0插入到插入到p0之后（即之后（即p之前）之前） k

22、+; else x = p-coef + q-coef; if (x=0) p0-next = p-next; delete p; /以上两句，将以上两句，将p从表中删除并将其所指对象释放从表中删除并将其所指对象释放 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新指向原所新指向原所指的下一个指的下一个 /

23、 if (p-exp q-exp ) else /whileif (q!=NULL) p0-next = q;b.head-next = NULL; /此时，此时，b中已只剩第一个结点（头），中已只剩第一个结点（头），为其置空表标志为其置空表标志return k; /返回结果链表中的元素个数返回结果链表中的元素个数为了进一步说明上述程序，举一个程序运行的例子，其各次循环的运行结果如图5-6所示（a）A(x)=p5(x)=7+3x2-9x3+x5，进入循环前，进入循环前（b ) B(x)=3x+9x3+x5-X8，进入循环前，进入循环前（d）B(x)：第一次进入循环后，：第一次进入循环后，q保持

24、不变保持不变（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 被删除，重新指向下一个被删除，重新

25、指向下一个（k）A(x)：第五次进入循环后，：第五次进入循环后，p 与与q合并，合并，p重新指向下一个重新指向下一个(空）空）（l）B(x)：第五次进入循环后，：第五次进入循环后，q 合并到合并到p，然后被删除，重新指向下一个，然后被删除，重新指向下一个（m ）A(x)：退出循环后，：退出循环后，q后面挂接了后面挂接了p的前驱的尾的前驱的尾（n）B(x)：退出循环后，：退出循环后，q挂接到了挂接到了p的前驱的后面的前驱的后面（三）多项式加法实现（三）多项式加法实现借助抽象操作借助抽象操作 下面在前面给出的TLinearListSqu类(对TLunearListLink也相同)的基础上实现一元多

26、项式相加。 首先，定义表示多项式的元素的类型。多项式的元素类型已不是象long、float等那样的简单类型，所以必须考虑如何兼容基本操作中使用的赋值（=）运算、恒等运算（=）和输出运算（coef = i1.coef; /定义多项式项赋值为指数和系数分别赋值定义多项式项赋值为指数和系数分别赋值 this-exp = i1.exp; return i1; ;ostream& operator (ostream& oo, TPolynomialItem &i1)/重载标准输出算符，以支持重载标准输出算符，以支持Print() ooi1.coef,i1.exp ; return oo;有了上面的定义，

27、我们可以写出多项式加法程序了：有了上面的定义，我们可以写出多项式加法程序了：long PolynomialAdd(TLinearListSqu &a, TLinearListSqu &b) long currE1, currE2, k; TPolynomialItem e1,e2; k=0; /记录最终元素个数记录最终元素个数 currE1=0; /记录线性表记录线性表a的元素序号的元素序号 currE2=0; /记录线性表记录线性表b的元素序号的元素序号 while (currE1 a.len & currE2b.len) e1=a.Get(currE1); /按序号取对应元素内容按序号取对

28、应元素内容 e2=b.Get(currE2);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 (int i = currE2+1; ib.len+1; i+) a.Insert(*(b.Delete(i), a.l

29、en+1); return k;一元多项式的乘法设Am(x)与Bn(x)为两个一元多项式，设其中，每一项aiBn(x)都是一个关于x的一元多项式。由此可知，两个一元多项式相乘，可以化为多个一元多项式相加，这可利用前面给出的算法实现。它们的积为本讲小结本讲重点介绍带头结点的链表、循环链表和双向链表等几种特殊的线性链表的特征，基本运算。对于循环链表要突出掌握判断链表空满的条件；双向链表要强调插入和删除算法的实现。最后通过一元多项式加法的示例，介绍一元多项式的数据结构、它的直接操作链表和多项式加法的实现。重点说明前面的构造类TLinearListSqu/TLinearListSqu的应用。思考与练习1、分别针对链式与顺序存储结构，编写程序实现Josephus 问题：设有个人围坐在一个圆桌周围，从第个人开始数，数到第的人就出列，然后从出列这的下一个人开始重新按上述方式数，数到就出列，如此重复，直到所有的人都出列为止。要求给出每个人的出列次序，即求一个按出列次序排列的个人的顺序表。、在类TLinearListSqu 或TLinearListLink 基础上，实现一个学生基本信息登记表的操作，包括输入、修改、打印、查询、统计等功能。