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

1、一元多项式的表示及相加第2章 线性表线性表的类型定义线性表的顺序表示和实现线性表的链式表示和实现2.4 一元多项式的表示及相加计算机中，可以用一个关于系数的线性表来表示： P = ( p0, p1, , pn )但是对于形如S (x) = 1 + 3x10000 2x20000的多项式，上述表示方法是否合适？2.4 一元多项式的表示及相加 一般情况下的一元稀疏多项式可写成 Pn(x) = p1xe1 + p2xe2 + + pmxem 其中：pi 是指数为 ei 的项的非零系数， 0 e1 e2 em = n可以下列线性表表示： ( (p1, e1) , (p2, e2), , (pm, em

2、) )将单链表的每个结点对应着一元多项式中的一个非零项，它由三个域组成，分别表示非零项的系数、指数和指向下一个结点的指针。2.4 一元多项式的表示及相加 P99(x) = 7x3 - 2x12 - 8x99例:可用线性表( (7, 3),(-2, 12),(-8, 99) )表示： 7 3 Head -2 12 -8 99 /一元多项式的表示 2.4 一元多项式的表示及相加typedef struct poly_node *poly_pointer;typedef struct poly_node / 项的表示 float coef; / 系数 int expn; / 指数 poly_poin

3、ter link; /指针 ;结点的数据元素类型定义为:2.4 一元多项式的表示及相加抽象数据类型一元多项式的定义ADT Polynomial 数据对象: D ai|aiTermSet, i=1,2,.,m, m0 TermSet 中的每个元素包含一个表示系数的实数和表示指数的整数 数据关系: R |ai-1 ,aiD, i=2,.,n 且ai-1中的指数值ai中的指数值 基本操作： CreatPolyn(&P,m) 操作结果：输入m项的系数和指数，建立一元多项式P DestroyPolyn(&P) 操作结果：销毁一元多项式P PrintPolyn(P) 操作结果：打印输出一元多项式P。 Po

4、lynLength(P) 操作结果：返回一元多项式P中的项数。 AddPolyn(&Pa,&Pb) 操作结果：完成多项式相加运算，并销毁一元多项式 SubtractPolyn(&Pa,&Pb) 操作结果：完成多项式相减运算，并销毁一元多项式Pb MultiplyPolyn(&Pa,&Pb) 操作结果：完成多项式相乘运算，并销毁一元多项式Pb ADT Polynomial 例1：设两个一元多项式为2.4 一元多项式的表示及相加A(x)= 3x14 + 2x8 + 1B(x)= 8x14 - 3x10 + 10 x6求此两一元多项式之和: C(x)=A(x)+B(x)实现思路依次比较Pa和Pb所指

5、结点中的指数项，依Paexpn =、 Pbexpn等情况，再决定是将两系数域的数值相加(并判其和是否为0)，还是将较高指数项的结点插入到新表C中。 2.4 一元多项式的表示及相加2.4 一元多项式的表示及相加 3 14 2 8 1 0 / 8 14B -3 10 10 6 /11 14C -3 10 2 8 10 6 1 0 /PaAPaPaPbPbPbPcPcPcPcPcPbPa例2：设两个一元多项式为2.4 一元多项式的表示及相加 A(x)= 4 + 6x4 + 5x8 + 4x12 B(x)= 2x3 - 5x8 + 3x12 + 7x15 求此两一元多项式之和: C(x)=A(x)+B

6、(x)2.4 一元多项式的表示及相加 4 0 6 5 8 4 12 headA 2 3 -5 8 3 12 headB 7 15 7 12 7 15 4 0 6 4 headC 2 3 4C(x)= 4+2x3 + 6x4 + 7x12 + 7x15 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中

7、当前结点 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的指数

8、值)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剩余结点 Fre

9、eNode(hb); /释放pb头结点 / AddPolynVoid 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中当前结点 haqaqb4 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=GetC

10、urElem(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

11、);FreeNode(qa); DelFirst(hb,qb);FreeNode(qb); qb=NextPos(pb,hb); qa=NextPos(pa,ha); break;else /删除pa当前结点7if (!ListEmpty(pb) Append(pa, qb) ; /链接pb剩余结点FreeNode(hb); /释放pb头结点 pa121547764)(xxxxC+=32x+ pb2.4 一元多项式的表示及相加Void AddPolyn( polynomial &pa, polynomial &pb ) ha=GetHead(pa); hb=GetHead(pb) ; / ha

12、和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

13、=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)

14、; 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.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结

15、构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。本章小结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 ；习题与练

16、习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 ；习题与练习H28375P(1) L=P-link;28375PHL3.对以下单链表分别执行下列各程序段，画出结果示意图。习题与练习3.对以下单链表分别执行下列各程序段，画出结果示意图。(2) R-data=P-da

17、ta;28575PRHH28375PR习题与练习3.对以下单链表分别执行下列各程序段，画出结果示意图。(3) R-data=P-link-data;28775PRHH28375PR习题与练习3.对以下单链表分别执行下列各程序段，画出结果示意图。(4) P-link-link-link-data=P-data;25375PHH28375P习题与练习3.对以下单链表分别执行下列各程序段，画出结果示意图。(5) T=P; while(T!=NULL) T-data=(T-data)*2; T=T-link; H2P1014616H28375P习题与练习3.对以下单链表分别执行下列各程序段，画出结果示

18、意图。(6) T=P; while(T-link!=NULL) T-data=(T-data)*2; T=T-link; H28375PH2P101468习题与练习3.对以下单链表分别执行下列各程序段，画出结果示意图。(7) P=(JD*)malloc(sizeof(JD); P-data=10; R-link=P; P-link=S;HS28375PR习题与练习3.对以下单链表分别执行下列各程序段，画出结果示意图。(7) P=(JD*)malloc(sizeof(JD); P-data=10; R-link=P; P-link=S;PHS28375PRHS28375R习题与练习3.对以下单链表分别执行下列各程序段，画出结果示意图。(7) P=(JD*)malloc(sizeof(JD); P-data=10; R-link=P; P-link=S;PHS28375PRHS28375R10习题与练习3.对以下单链表分别执行下列各程序段，画出结果示意图。(7) P=(JD*)malloc(sizeof(JD); P-data=10; R-link=P; P-link=S;PHS28375PRHS28375R10习题与练习3.对以下单链表