数据结构.第2章.线性表.2.一元多项式的表示及相加

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,数据结构,Data Structures,张 凯,计算机学院 软件工程系,2011,年,3,月,12,日,一元多项式,的表示及相加,第,2,章 线性表,线性表,的类型定义,线性表,的顺序表示和,实现,线性表,的链式表示和,实现,2.4,一元多项式,的表示及相加,计算机中，可以用一个关于系数的线性表来表示：,P,=,(,p,0,p,1,p,n,),但是对于形如,S,(,x,)=1+3,x,10000,2,x,20000,的多项式，,上述表示方法是否合适,？,2.4,一元多项式,的表示及相加,一般情况下的一元稀疏多项式可写成,P,n,(,x,)=,p,1,x,e,1,+,p,2,x,e,2,+,p,m,x,e,m,其中,：,p,i,是指数,为,e,i,的项的非零系数，,0,e,1,e,2,expn,=,、,Pb,expn,等情况，再决定是将两系数域的数值,相加,(,并,判其和是否为,0),，,还是将较高指数项的结点插入到新,表,C,中,。,2.4,一元多项式的表示及相加,例,1,：,设两个一元多项式为,2.4,一元多项式的表示及相加,A(,x,)=3,x,14,+2,x,8,+,1,B(,x,)=,8,x,14,-3,x,10,+,10,x,6,求此两一元多项式之和,:C(,x,)=A(,x,)+,B(,x,),2.4,一元多项式的表示及相加,3 14,2 8,1 0,/,8 14,B,-3 10,10 6,/,11 14,C,-3 10,2 8,10 6,1 0,/,Pa,A,Pa,Pa,Pb,Pb,Pb,Pc,Pc,Pc,Pc,Pc,Pb,Pa,例,2,：,设两个一元多项式为,2.4,一元多项式的表示及相加,A(,x,)=,4,+,6,x,4,+,5,x,8,+,4,x,12,B(,x,)=2,x,3,-,5,x,8,+,3,x,12,+,7,x,15,求此两一元多项式之和,:C(,x,)=A(,x,)+,B(,x,),2.4,一元多项式的表示及相加,4,0,6,5,8,4,12,head,A,2,3,-5,8,3,12,head,B,7,15,7 12,7 15,4 0,6 4,head,C,2,3,4,C,(,x,)=,4+2,x,3,+6,x,4,+,7,x,12,+7,x,15,2.4,一元多项式的表示及相加,Void,AddPolyn(polynomial&pa,polynomial&pb),ha=GetHead(pa);hb=GetHead(pb);,/ha,和,hb,分别指向,Pa,和,Pb,的头结点,qa=NextPos(pa,ha);qb=NextPos(pb,hb);,/qa,和,qb,分别指向,Pa,和,Pb,中当前结点,while(qa&qb),/Pa,和,Pb,均非空,a=GetCurElem(qa);b=GetCurElem(qb);,/a,和,b,为两表中当前比较元素,switch(*cmp(a,b),case-1;,/pa,当前的指数小于,pb,当前的指数,ha=qa;qa=NextPos(pa,qa);break;,case 1;,/pa,当前的指数大于,pb,当前的指数,DelFirst(hb,qb);InsFirst(ha,qb);,qb=NextPos(pb,hb);ha=NextPos(pa,ha);,break;,int cmp(term a,，,term b),；,依,a,的指数值,)b,的指数值，分别返回,-1,0,和,1,；,2.4,一元多项式的表示及相加,case,0;,sum=a.coef+b.coef;,if(sum!=0),/,修改,pa,当前结点系数,SetCurElem(qa,sum);ha=qa;,else,/,删除,pa,当前结点,DelFirst(ha,qa);FreeNode(qa);,DelFirst(hb,qb);FreeNode(qb);,qb=NextPos(pb,hb);qa=NextPos(pa,ha);break;,/switch,/while,if(!ListEmpty(pb)Append(pa,qb);,/,链接,pb,剩余结点,FreeNode(hb);,/,释放,pb,头结点,/AddPolyn,Void AddPolyn(polynomial&pa,polynomial&pb),ha=GetHead(pa);hb=GetHead(pb);,/ha,和,hb,分别指向,Pa,和,Pb,的头结点,qa=NextPos(pa,ha);qb=NextPos(pb,hb);,/qa,和,qb,分别指向,Pa,和,Pb,中当前结点,ha,qa,qb,4 0,6,4,5 8,4,12,2 3,-,5 8,3 12,7,15,0 -1,hb,0 -1,while(qa&qb),/Pa,和,Pb,均非空,a=GetCurElem(qa);b=GetCurElem(qb);,/a,和,b,为两表中当前比较元素,switch(*cmp(a,b),case-1;,/pa,当前的指数小于,pb,当前的指数,ha=qa;qa=NextPos(pa,qa);break;,case 1;,/pa,当前的指数大于,pb,当前的指数,DelFirst(hb,qb);,InsFirst(ha,qb);,qb=NextPos(pb,hb);,ha=NextPos(pa,ha);,break;,case 0;,sum=a.coef+b.coef;,if(sum!=0),/,修改,pa,当前结点系数,SetCurElem(qa,sum);ha=qa;,DelFirst(ha,qa);,FreeNode(qa);,DelFirst(hb,qb);,FreeNode(qb);,qb=NextPos(pb,hb);qa=NextPos(pa,ha);break;,else,/,删除,pa,当前结点,7,if(!ListEmpty(pb)Append(pa,qb);,/,链接,pb,剩余结点,FreeNode(hb);,/,释放,pb,头结点,pa,12,15,4,7,7,6,4,),(,x,x,x,x,C,+,+,+,=,3,2,x,+,pb,2.4,一元多项式的表示及相加,Void,AddPolyn(polynomial&pa,polynomial&pb),ha=GetHead(pa);hb=GetHead(pb);,/ha,和,hb,分别指向,Pa,和,Pb,的头结点,qa=NextPos(pa,ha);qb=NextPos(pb,hb);,/qa,和,qb,分别指向,Pa,和,Pb,中当前结点,while(qa&qb),/Pa,和,Pb,均非空,a=GetCurElem(qa);b=GetCurElem(qb);,/a,和,b,为两表中当前比较元素,switch(*cmp(a,b),case-1;,/pa,当前的指数小于,pb,当前的指数,ha=qa;qa=NextPos(pa,qa);break;,case 1;,/pa,当前的指数大于,pb,当前的指数,DelFirst(hb,qb);InsFirst(ha,qb);,qb=NextPos(pb,hb);ha=NextPos(pa,ha);,break;,int cmp(term a,，,term b),；,依,a,的指数值,)b,的指数值，分别返回,-1,0,和,1,；,2.4,一元多项式的表示及相加,case,0;,sum=a.coef+b.coef;,if(sum!=0),/,修改,pa,当前结点系数,SetCurElem(qa,sum);ha=qa;,else,/,删除,pa,当前结点,DelFirst(ha,qa);FreeNode(qa);,DelFirst(hb,qb);FreeNode(qb);,qb=NextPos(pb,hb);qa=NextPos(pa,ha);break;,/switch,/while,if(!ListEmpty(pb)Append(pa,qb);,/,链接,pb,剩余结点,FreeNode(hb);,/,释放,pb,头结点,/AddPolyn,运算,效率分析,(1,),系数相加,：,0,加法次数,min(,m,n,),其中,m,和,n,分别表示表,A,和表,B,的结点数。,(2),指数比较,：极端,情况是表,A,和表,B,没有一项指数,相同，比较,次数最多为,m,+,n,-1,(3,),新,结点的,创建,：极端,情况是产生,m,+,n,个,新,结点,合计,时间复杂度为,O,(,m,+,n,),2.4,一元多项式的表示及相加,1.,了解,线性表的逻辑结构特性是数据元素,之间存在,着线性关系，在计算机中表示这种,关系的两类不同,的存储结构是顺序存储结构和,链式,存储结构。用前者表示的线性表简称为,顺序,表，用后者表示的线性表简称为链表,。,本章小结,2,.,熟练掌握这两类存储结构的描述方法，,以及线性表,的各种基本操作的实现。,3.,能够从时间和空间复杂度的角度综合,比较线性表,两种存储结构的不同特点及其适用场合,本章小结,习题,与,练习,1.,在一个单链表,HL,中，若要向表头插入一个由,指针,P,指向的结点，则执行（）。,A,）,HL=p,；,p,-,next=HL,；,B,）,p,-,next=HL,；,HL=p,；,C,）,p,-,next=HL,；,p=HL,；,D,）,p,-,next=HL,-,next,；,HL,-,next=p,；,习题,与,练习,2.,在一个单链表,HL,中，若要在指针,q,指向的,结点,的后面插入一个由指针,P,指向的结点，,则执行,（）。,A,）,q-next=p-next,；,p=q,；,B,）,p-next=q-next,；,q=p,；,C,）,q-next=p-next,；,p,-next=q,；,D,）,p-next=q-next,；,q,-next=p,；,习题,与,练习,H,2,8,3,7,5,P,(1)L=P-link;,2,8,3,7,5,P,H,L,3.,对以下单链表分别执行下列各程序段，画出结果示意图。,习题,与,练习,3.,对以下单链表分别执行下列各程序段，画出结果示意图。,(2)R-data=P-data;,2,8,5,7,5,P,R,H,H,2,8,3,7,5,P,R,习题,与,练习,3.,对以下单链表分别执行下列各程序段，画出结果示意图。,(3)R-data=P-link-data;,2,8,7,7,5,P,R,H,H,2,8,3,7,5,P,R,习题,与,练习,3.,对以下单链表分别执行下列各程序段，画出结果示意图。,(4)P-link-link-link-data=P-data;,2,5,3,7,5,P,H,H,2,8,3,7,5,P,习题,与,练习,3.,对以下单链表分别执行下列各程序段，画出结果示意图。,(5)T=P;,while(T!=NULL),T-data=(T-data)*2;,T=T-link;,H,2,P,10,14,6,16,H,2,8,3,7,5,P,习题,与,练习,3.,对以下单链表分别执行下列各程序段，画出结果示意图。,(6)T=P;,while(T-link!=NULL),T-data=(T-data)*2;,T=T-link;,H,2,8,3,7,5,P,H,2,P,10,14,6,8,习题,与,练习,3.,对以下单链表分别执行下列各程序段，画出结果示意图。,(7)P=(JD*)malloc(sizeof(JD);,P-data=10;,R-link=P;,P-link=S;,H,S,2,8,3,7,5,P,R,习题,与,练习,3.,对以下单链表分别执行下列各程序段，画出结果示意图。,(7),P=(JD*)malloc(sizeof(JD);,P-data=10;,R-link=P;