《数据结构.第2章.线性表.2.一元多项式的表示及相加》由会员分享，可在线阅读，更多相关《数据结构.第2章.线性表.2.一元多项式的表示及相加（38页珍藏版）》请在金锄头文库上搜索。
1、武汉科技大学Wuhan University of Science and Technology数据结构数据结构 Data StructuresData Structures张 凯 计算机学院 软件工程系2011年3月12日一元多项式的表示及相加第2章 线性表线性表的类型定义线性表的顺序表示和实现线性表的链式表示和实现2.4 一元多项式的表示及相加计算机中，可以用一个关于系数的线性表来表示：P = ( p0, p1, , pn )但是对于形如S (x) = 1 + 3x10000 2x20000的多项式，上述表示方法是否合适？2.4 一元多项式的表示及相加一般情况下的一元稀疏多项式可写成Pn(
2、x) = p1xe1 + p2xe2 + + pmxem其中：pi 是指数为 ei 的项的非零系数，0 e1 |ai-1 ,aiD, i=2,.,n 且ai-1中的指数值ai中的指数值 基本操作：CreatPolyn( hb=GetHead(pb) ; / ha和hb分别指向Pa和Pb的头结点 qa=NextPos(pa, ha); qb=NextPos(pb, hb) ;/qa和qb分别指向Pa和Pb中当前结点 while (qa b=GetCurElem(qb); /a和b为两表中当前比较元素 switch(*cmp(a, b) ) case -1; /pa当前的指数小于pb当前的指数ha
3、=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(
4、ha,qa); FreeNode(qa); DelFirst(hb,qb); FreeNode(qb); qb=NextPos(pb,hb); qa=NextPos(pa,ha); break; / switch /whileif (!ListEmpty(pb) Append(pa, qb) ; /链接pb剩余结点FreeNode(hb); /释放pb头结点 / AddPolynVoid AddPolyn( polynomial hb=GetHead(pb) ; / ha和hb分别指向Pa和Pb的头结点 qa=NextPos(pa, ha); qb=NextPos(pb, hb) ;/qa和q
5、b分别指向Pa和Pb中当前结点 haqaqb4 0 6 4 5 8 4 12 2 3 -5 8 3 12 7 15 0 -1 hb0 -1 while (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
6、;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当前结点7if (!ListEmpty(pb) Append(pa, qb) ; /链接pb剩余结点FreeNode(hb); /释放pb头结点pa121547764)(xxxxC+=32x+pb2.4 一元多项式的表示及相加Void
7、 AddPolyn( polynomial hb=GetHead(pb) ; / ha和hb分别指向Pa和Pb的头结点 qa=NextPos(pa, ha); qb=NextPos(pb, hb) ;/qa和qb分别指向Pa和Pb中当前结点 while (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)
8、;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
9、); break; / switch /whileif (!ListEmpty(pb) Append(pa, qb) ; /链接pb剩余结点FreeNode(hb); /释放pb头结点 / AddPolynv运算效率分析 (1)系数相加：0 加法次数 min(m, n)其中m和n分别表示表A和表B的结点数。 (2)指数比较：极端情况是表A和表B 没有一项指数相同，比较次数最多为m+n-1 (3)新结点的创建：极端情况是产生m + n个新结点 合计时间复杂度为 O(m+n)2.4 一元多项式的表示及相加v1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的
10、存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。本章小结v2.熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。v3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合本章小结习题与练习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 ；习题与练
11、习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 ；习题与练习H28375 P(1) L=P-link;28375PHL3.对以下单链表分别执行下列各程序段，画出结果 示意图。习题与练习3.对以下单链表分别执行下列各程序段，画出结果 示意图。(2) R-data=P-dat
12、a;28575PRHH28375 PR习题与练习3.对以下单链表分别执行下列各程序段，画出结果 示意图。(3) R-data=P-link-data;28775PRHH28375 PR习题与练习3.对以下单链表分别执行下列各程序段，画出结果 示意图。(4) P-link-link-link-data=P-data;25375 PHH28375 P习题与练习3.对以下单链表分别执行下列各程序段，画出结果 示意图。(5) T=P;while(T!=NULL) T-data=(T-data)*2;T=T-link; H2 P1014616H28375 P习题与练习3.对以下单链表分别执行下列各程序段
13、，画出结果 示意图。(6) T=P;while(T-link!=NULL) T-data=(T-data)*2;T=T-link; H28375 PH2 P101468习题与练习3.对以下单链表分别执行下列各程序段，画出结果 示意图。(7) P=(JD*)malloc(sizeof(JD);P-data=10;R-link=P;P-link=S;HS28375 PR习题与练习3.对以下单链表分别执行下列各程序段，画出结果 示意图。(7) P=(JD*)malloc(sizeof(JD);P-data=10;R-link=P;P-link=S;PHS28375 PRH S28375 R习题与练习
14、3.对以下单链表分别执行下列各程序段，画出结果 示意图。(7) P=(JD*)malloc(sizeof(JD);P-data=10;R-link=P;P-link=S;PHS28375 PRH S28375 R10习题与练习3.对以下单链表分别执行下列各程序段，画出结果 示意图。(7) P=(JD*)malloc(sizeof(JD);P-data=10;R-link=P;P-link=S;PHS28375 PRH S28375 R10习题与练习3.对以下单链表分别执行下列各程序段，画出结果 示意图。(7) P=(JD*)malloc(sizeof(JD);P-data=10;R-link=
15、P;P-link=S;PHS28375 PRH S28375 R10习题与练习3.对以下单链表分别执行下列各程序段，画出结果 示意图。(8) T=H; T-link=P-link; free(P);H2837 PT 5H28375 P习题与练习3.对以下单链表分别执行下列各程序段，画出结果 示意图。(9) S-link=H;H S28375如果 S-link= =H 则S所指向的结点为尾结点.HS28375习题与练习4. 比较顺序表与链表的优缺点。在什么情况下用顺序 表比链表好？ 5. 为什么在单循环链表中设置尾指针比设置头指针更 好？ 6. 已知L是无表头结点的单链表，且P结点既不是首元 结点，也不是尾元结点，试写出完成下列功能的语 句：(1) 在P结点后插入S结点的语句序列是。(2) 在P结点前插入S结点的语句序列是。(3) 在表首插入S结点的语句序列是。(4) 在表尾插入S结点的语句序列是。习题与练习7.已知L
