《循环链表和双向链表》由会员分享，可在线阅读，更多相关《循环链表和双向链表（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-nex
4、t=p-next; (2) p-next-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表中的第一个
5、等于该值的序号，由于表的起始序号为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系数问题，可以不存贮
6、0值元素。但这样就不能利用位置关系隐含指出系数对应的指数了，而必须显式地给出指数。对任一个一元n次多项式，若不写出系数为0的项，则可表示为pn(x) = p1xe1+p2xe2+ +pnxen这里，p1, p2, , pn均非0，e1e2 q的指数)将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 /while i
7、f (q不为空) 将q挂接在p之后；,该程序不断比较A链和B链中的一对结点的指数值（称其为当前结点）。开始时A链和B链中参加比较的当前结点都是它们的第一个元素。 主循环while结束后，可能出现下列3种情况：A链和B链同时被处理完；只有B链处理完；只有A链处理完。 对第一和第二种情况，不需要“善后”处理。对第三种情况，B链中尚有未被处理完的结点，需将其挂接在结果链的尾部。循环外的“if(q 不为空）将q挂接在p之后”就是处理该情况的。,一元n次多项式加法程序PolynomialAdd如下。为了能访问到TLinearListLink的私有成员，下面的PolynomialAdd函数应指定为TLin
8、earListLink的友元。 int PolynomialAdd(TLinearListLink ,为什么这里对于a、b链表需要两个指针？,while (p!=NULL ,elsex = p-coef + q-coef;if (x=0)p0-next = p-next;delete p; /以上两句，将p从表中删除并将其所指对象释放p = p0-next; /令p指向相对于它原指的下一个 / if (x=0)elsep-coef = x;p0 = p;,p = p-next; / if (x=0) else q0 = q; q = q-next;delete q0; /将q所指结点从表中删除
9、并释放，令q新指向原所指的下一个 / if (p-exp q-exp ) else /while if (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保持不变,（c）A(x)：第一次进入循环后，p 后移,（e）A(x
10、)：第二次进入循环后，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的前驱的后面,（三）多项式加法实
11、现借助抽象操作,下面在前面给出的TLinearListSqu类(对TLunearListLink也相同)的基础上实现一元多项式相加。首先，定义表示多项式的元素的类型。多项式的元素类型已不是象long、float等那样的简单类型，所以必须考虑如何兼容基本操作中使用的赋值（=）运算、恒等运算（=）和输出运算（）等，即定义相应的运算符重载函数。,struct TPolynomialItemfloat coef;int exp;operator =(TPolynomialItem ,有了上面的定义，我们可以写出多项式加法程序了：long PolynomialAdd(TLinearListSqu ,if
12、 (e1.exp e2.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 (currE2 b.len)for (int i = currE2+1; ib.len+1; i+)a.Insert(*(b.Delete(i), a.len+1);return k; ,一元多项式的乘法,设Am(x)与Bn(x)为两个一元多项式，设,其中，每一项aiBn(x)都是一个关于x的一元多项式。由此可知，两个一元多项式相乘，可以化为多个一元多项式相加，这可利用前面给出的算法实现。,
