循环链表和双向链表

*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数据结构与算法,-,第五讲,北方民族大学,计算机科学与工程学院,王伦津 研究员,循环链表、双向链表及线性表应用示例,5,、循环链表和双向链表,本讲重点：带头结点的链表、循环链表和双向链表的特征，基本运算。对于循环链表要突出掌握判断链表空满的条件；双向链表要强调插入和删除算法的实现。最后通过多项式加法的示例，介绍线性表的应用。,目 录,5.1,带头结点的链表,5.2,循环链表,5.3,双向链表,5.4,线性表的应用示例,5.1,几种特殊线性链表,5.1,带头结点的链表,有时候为了处理上的方便，在线性链表的第一个结点的前面,增设一个特殊的结点，称为头结点,。头结点逻辑上不属于相应的线性链表，它的作用主要有两点，一是存贮一些有关线性表的信息（如表中结点总数,），另一是为了算法处理上的方便。,图,51,带头结点的链表,10,20,30,3,头指针,头结点,头元素,5.2,循环链表,图,5 2,循环单链表示意,20,(a),不带头结点,(b),带头结点,10,30,3,在线性表中，如果我们将第,1,个结点视为最后一个结点的后继，将最后一个结点视为第,1,个结点的前趋，则这种线性表称为循环线性表，相应的链表称循环线性链表（简称循环链表）。,10,20,30,5.3,双向链表,为单向链表的每个结点增设一个指向相应结点的前趋的指针，使其同时包含前驱和后继，这样的链表称为双向链表（简称双链表）。双向链表的结点的结构如下所示：,这里各项含义为：,info-,存放元素内容；,next-,存放该元素的后继的指针（地址）；,prior-,存放该元素的前驱的指针（地址）；,prior,info,next,循环单链表是单链表的另一种形式，其结构特点是链表中最后一个结点的指针不再是结束标记，而是指向整个链表的第一个结点，从而使单链表形成一个环。和单链表相比，循环单链表的长处是从链尾到链头比较方便。当要处理的数据元素序列具有环型结构特点时，适合于采用循环单链表。,循环链表的插入、删除运算基本同单向链表，只是查找时判别条件不同而已；但是这种循环链表实现各种运算时的危险之处在于：链表没有明显的尾端，可能使算法进入死循环，所以判断条件应该用,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;,图,5 3,双链表插入,p,p-prior,p-next,(4),q,(3),(2),(1),注意关键的四个指针域的变化,(2),(1),p,p-prior,p-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),的实现,为了说明前面给出的线性表类的使用，我们的实现在类,TLinearListSqu,的基础上进行。对应的子程序如下。,A-B,B-A,AB,（,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-;,Else a.Insert(b.Get(i),1);j+,return j;,先在,B,表中取得元素,i,的值，然后根据该值，查找属于,A,表中的第一个等于该值的序号，由于表的起始序号为,0,，故加,1,体现类模板的作用,5.5,一元多项式相加,(,一）一元多项式的表示,数据结构,在数学上，一个一元,n,次多项式可表示为,P,n,(x,)=p,0,+p,1,x+p,2,x,2,+,p,n,x,n,它由,(n+1),个系数序列,p,0,、,p,1,、,、,p,n,唯一地确定。因此，在计算机中，它可用一个线性表,P,来表示：,P=(p,0,p,1,p,n,),其中，,p,i,代表,P,n,(x,),中的,i,次项系数。,在这种表示法中，,系数所对应的指数隐含在系数的序号中，所以值为,0,的系数也要列出。,现考虑两多项式进行符号相加的问题。设,Q,m,(x,),是另一个一元,m,次多项式，它的线性表表示为,Q=(q,0,q,1,q,m,),为解决,0,系数问题，可以不存贮,0,值元素。但这样就不能利用位置关系隐含指出系数对应的指数了，而必须显式地给出指数。,对任一个一元,n,次多项式，若不写出系数为,0,的项，则可表示为,p,n,(x,)=p,1,x,e,1,+p,2,x,e,2,+,p,n,x,e,n,这里，,p,1,p,2,p,n,均非,0,，,e,1,e,2,e,n,=n,。,显然，对此形式多项式，可确定地用下列形式的线性表表示,(p,1,e,1,),(p,2,e,2,),(,p,n,e,n,),该线性表每个元素是个二元组,(,p,i,e,i,),，分别指出第,i,个非,0,项的系数和指数，二元组按指数递增的次序排列。,在这种结构中，元素之间的次序关系仅代表元素对应的指数的大小关系。,对这种线性表，既可用顺序存贮结构，也可用链式存贮结构。但考虑到在进行符号加法时，要经常进行插入与删除操作，所以采用链式存贮结构较为合适。这里，我们采用动态链式存贮结构，线性表每个元素的结构为,系数,指数,它的,C/C+,语言描述为,struct,TPolynomialItem,float,coef,;,int,exp;,该类型在我们前面给出的线性表中，相当于元素类型,TElem,，在具体使用线性表类时，应使用,TPolynomialItem,实例化,TElem,对应的类模板,为处理方便，在具体存储多项式时，,我们规定：,所存储的多项式已约简，即已合并同类项，不保留,0,系数项，各项按指数的升序排列。,(,二）多项式加法实现,直接操作链表,为操作方便，我采用带头结点的非循环链表，下面给出一个例子说明多项式的这种表示法。,设有一个一元,5,次多项式：,P,5,(x)=7+3x-9x,3,+x,5,具体链表表示方法如图,55,一元,n,次多项式的（符号）相加，实质上是合并同类项的过程，即指数相同的项，其系数相加，指数不同的项复抄。,7,0,3,1,-9,3,1,5,图,55,一个一元,5,次多项式的链表表示,下面考虑,A(x)+B(x,),A(x,),的实现方法。即将多项式,B(x,),加到多项式,A(x,),上面，这里假设各多项式均已约简，且各项已按升序排列。,用高级语言实现时，设两个指针,p,和,q,，初始时它们分别指向,A(x,),与,B(x,),中当前未被处理的结点中指数最小者。进行相加的过程，实质上是重复进行下列几个步骤：,（,1,）,若,pexp,qexp,，则结点,q,应为和的一个结点，故应将,q,从,B(x,),中摘除后插入到,A(x,),中,p,之前，然后,q,向后移一步，,p,不动。,（,3,）若,pexp,=,qexp,则表明,p,与,q,所指为同类项，应合并，故要将,q,的系数加到,p,的系数上。若相加结果为,0,，则表明和式中无此项，故应从,A(x,),中删除,p,，从,B(x,),中删除,q,并令,p,与,q,分别指向下一结点。若相加和不为,0,，则表明相加结果应为和式中的一个结点，,p,后移一步，然后将,q,从,B(x,),中摘除，令,q,指向下一结点。,下面先给出算法的伪码。,p=A,的第一个元素；,q=B,的第一个元素；,while(p,存在,&q,存在,),if(p,的指数,next;,在算法运行中，,B(x,),的链表中的结点，或被转移到,A(x,),链表上，或被删除，运行结束后，,B(x,),链表就不存在了，而,A(x,),链表就是所求的和。当然，也可以设计一个将,B,加到,A,上，但保留,B,，或将,A+B,之和放到另一链表中的算法。具体留作练习。,else,if(p,的指数,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,if(q,不为空,),将,q,挂接在,p,之后；,该程序不断比较,A,链和,B,链中的一对结点的指数值（称其为当前结点）。开始时,A,链和,B,链中参加比较的当前结点都是它们的第一个元素。,主循环,while,结束后，可能出现下列,3,种情况：,A,链和,B,链同时被处理完；只有,B,链处理完；只有,A,链处理完。,对第一和第二种情况，不需要,“,善后,”,处理。对第三种情况，,B,链中尚有未被处理完的结点，需将其挂接在结果链的尾部。循环外的,“,if(q,不为空）将,q,挂接在,p,之后,”,就是处理该情况的。,一元,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.head,-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+;,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,新指向原所指的下一个,/if(p-exp q-exp)else,/while,if(q!=NULL)p0-next=q;,b.head,-next=NULL;/,此时，,b,中已只剩第一个结点（头），为其置空表标志,return k;/,返回结果