循环链表和双向链表

《循环链表和双向链表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、目录5.1带头结点的链表5.2循环链表5.3双向链表5.4线性表的应用示例5.1几种特殊线性链表5.1带头结点的链表有时候为了处理上的方便，在线性链表的第一个结点的前面增设一个特殊的结点，称为头结点。头结点逻辑上不属于相应的线性链表，它的作用主要有两点，一是存贮一些有关线性表的信息（如表中结点总数……），另一是为了算法处理上的方便。图5‑1带头结点的链表1020^303头指针头结点头元素5.2循环链表图5‑2循环单链表示意20(a)不带头结点(b)带头结点10303在线性表中，如果我们将第1个结点视为最后一个结点的后继，将最后一个结点视为第1个

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

3、形成一个环。和单链表相比，循环单链表的长处是从链尾到链头比较方便。当要处理的数据元素序列具有环型结构特点时，适合于采用循环单链表。循环链表的插入、删除运算基本同单向链表，只是查找时判别条件不同而已；但是这种循环链表实现各种运算时的危险之处在于：链表没有明显的尾端，可能使算法进入死循环，所以判断条件应该用curr.next()!=head替换单向链表的curr.next()!=null完成遍历所有结点。（一）双链表的插入现设在结点p之前插入结点q，其程序片段如下。(1)q->next=p;//让q的next指向p(2)q->prior=p->pr

4、ior;(3)p->prior->next=q;(4)p->prior=q;图5‑3双链表插入pp->priorp->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)returnp;注意：关键的两个指针域的变化5.4线性表应用示例5.4.1集合运算对集合结构，一般可用线性表表示。所以，对集合的操作，可以在线

5、性表上进行。这里只从算法角度介绍一种集合运算----(A-B)∪(B-A)的实现为了说明前面给出的线性表类的使用，我们的实现在类TLinearListSqu的基础上进行。对应的子程序如下。A-BB-AA∩B（A-B）∪（B-A）=（A∪B）-（A∩B）longDiDiff(TLinearListSqu&a,TLinearListSqu&b){//将a中的出现在b中的元素删除，返回从a中删除的元素的数//目a和b都是前面定义的线性表类，元素类型实例化为long。longi,j,k;j=0;for(i=0;i

6、++)//扫描b{k=a.Locate(b.Get(i),1);//依次检查b中每个元素是否在a中if(k>0)//如在a中，则从a中将其删除{a.Delete(k+1);j--;}Else{a.Insert(b.Get(i),1);j++}}returnj;}先在B表中取得元素i的值，然后根据该值，查找属于A表中的第一个等于该值的序号，由于表的起始序号为0，故加1体现类模板的作用5.5一元多项式相加(一）一元多项式的表示──数据结构在数学上，一个一元n次多项式可表示为Pn(x)=p0+p1x+p2x2+…+pnxn它由(n+1)个系数序列p0

7、、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这

8、里，p1,p2,…,pn均非0，e1