《数据结构.第2章.线性表.2.一元多项式的表示及相加.pptx》由会员分享，可在线阅读，更多相关《数据结构.第2章.线性表.2.一元多项式的表示及相加.pptx（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、武汉科技大学Wuhan University of Science and Technology张 凯计算机学院 软件工程系2011年3月12日一元多项式的表示及相加第第2 2章章 线性表线性表线性表的类型定义线性表的顺序表示和实现线性表的链式表示和实现2.4 一元多项式一元多项式的表示及相加的表示及相加计算机中，可以用一个关于系数的线性表来表示：P=(p0,p1,pn)但是对于形如S(x)=1+3x100002x20000的多项式，上述表示方法是否合适？2.4 一元多项式一元多项式的表示及相加的表示及相加一般情况下的一元稀疏多项式可写成Pn(x)=p1xe1+p2xe2+pmxem其中：pi
2、 是指数为ei的项的非零系数，0e1e2em=n可以下列线性表表示：(p1,e1),(p2,e2),(pm,em)将单链表的每个结点对应着一元多项式中的一个非零项，它由三个域组成，分别表示非零项的系数、指数和指向下一个结点的指针。2.4 一元多项式一元多项式的表示及相加的表示及相加P99(x)=7x3-2x12-8x99例:可用线性表(7,3),(-2,12),(-8,99)表示：73 Head-212-899/v一元多项式一元多项式的的表示表示2.4 一元多项式的表示及相加一元多项式的表示及相加typedefstructpoly_node*poly_pointer;typedefstruct
3、poly_node/项的表示floatcoef;/系数intexpn;/指数poly_pointerlink;/指针;结点的数据元素类型定义为:2.4 一元多项式的表示及相加一元多项式的表示及相加v抽象数据类型抽象数据类型一元多项式的定义一元多项式的定义ADT Polynomial 数据对象数据对象:Dai|aiTermSet,i=1,2,.,m,m0TermSet中的每个元素包含一个表示系数的实数和表示指数的整数 数据数据关系关系:R|ai-1,aiD,i=2,.,n且ai-1中的指数值ai中的指数值 基本基本操作：操作：CreatPolyn(&P,m)操作结果：输入m项的系数和指数，建立一
4、元多项式PDestroyPolyn(&P)操作结果：销毁一元多项式PPrintPolyn(P)操作结果：打印输出一元多项式P。PolynLength(P)操作结果：返回一元多项式P中的项数。AddPolyn(&Pa,&Pb)操作结果：完成多项式相加运算，并销毁一元多项式SubtractPolyn(&Pa,&Pb)操作结果：完成多项式相减运算，并销毁一元多项式PbMultiplyPolyn(&Pa,&Pb)操作结果：完成多项式相乘运算，并销毁一元多项式Pb ADT Polynomial v实现思路实现思路依次比较Pa和Pb所指结点中的指数项，依Paexpn=、Pbexpn等情况，再决定是将两系数
5、域的数值相加(并判其和是否为0)，还是将较高指数项的结点插入到新表C中。2.4 一元多项式的表示及相加一元多项式的表示及相加v例例1：设两个一元多项式为设两个一元多项式为2.4 一元多项式的表示及相加一元多项式的表示及相加A(x)=3x14+2x8+1B(x)=8x14-3x10+10 x6求此两一元多项式之和:C(x)=A(x)+B(x)2.4 一元多项式的表示及相加一元多项式的表示及相加 31428 10/814B-310 106/1114C-310 28106 10/PaAPaPaPbPbPbPcPcPcPcPcPbPav例例2：设两个一元多项式为设两个一元多项式为2.4 一元多项式的表
6、示及相加一元多项式的表示及相加A(x)=4+6x4+5x8+4x12B(x)=2x3-5x8+3x12+7x15求此两一元多项式之和:C(x)=A(x)+B(x)2.4 一元多项式的表示及相加一元多项式的表示及相加40 6 58 4 12 headA 23-58 312headB7 15 712 71540 64 headC2 34C(x)=4+2x3+6x4+7x12+7x152.4 一元多项式的表示及相加一元多项式的表示及相加VoidAddPolyn(polynomial&pa,polynomial&pb)ha=GetHead(pa);hb=GetHead(pb);/ha和hb分别指向Pa
7、和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;case1;/pa当前的指数大于pb当前的指数DelFirst(hb,qb);InsFirst(ha,qb);qb=NextPos(pb,hb);ha=NextPos(pa,ha);break;i
8、ntcmp(terma，termb)；依a的指数值)b的指数值，分别返回-1,0和1；2.4 一元多项式的表示及相加一元多项式的表示及相加case0;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/whileif(!ListEmpty(pb)Append(pa,qb);/链接p
9、b剩余结点FreeNode(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中当前结点中当前结点 haqaqb40 6 458 4 12 23-58 3127 15 0-1 hb0-1 while(qa&qb)/Pa和和Pb均非空均非空 a=GetCurElem(qa);b=GetCur
10、Elem(qb);/a和和b为两表中当前比较元素为两表中当前比较元素 switch(*cmp(a,b)case-1;/pa当前的指数小于当前的指数小于pb当前的指数当前的指数ha=qa;qa=NextPos(pa,qa);break;case1;/pa当前的指数大于当前的指数大于pb当前的指数当前的指数DelFirst(hb,qb);InsFirst(ha,qb);qb=NextPos(pb,hb);ha=NextPos(pa,ha);break;case0;sum=a.coef+b.coef;if(sum!=0)/修改修改pa当前结点系数当前结点系数SetCurElem(qa,sum);ha
11、=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 一元多项式的表示及相加一元多项式的表示及相加VoidAddPolyn(polynomial&pa,polynomial&pb)ha=GetHead
12、(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;case1;/pa当前的指数大于pb当前的指数DelFirst(hb,qb);InsFirst(ha,qb);qb=NextPos(
13、pb,hb);ha=NextPos(pa,ha);break;intcmp(terma，termb)；依a的指数值)b的指数值，分别返回-1,0和1；2.4 一元多项式的表示及相加一元多项式的表示及相加case0;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/whileif(
14、!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.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表
15、简称为顺序表，用后者表示的线性表简称为链表。本章小结本章小结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；习题习题与与练习练习2.在一个单链表HL中，若要在指针q指向的结点的后面插入一个由指针P指向的结点，则执行（）。A）q-
16、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-data;28575PRHH28375PR习题习题与与练习练习3.对以下单链表分别执行下列各程序段，画出结果示意图。(3)R-data=P-link-data;28775PRHH28375PR习题习题与
17、与练习练习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.对以下单链表分别执行下列各程序段，画出结果示意图。(6)T=P;while(T-link!=NULL)T-data=(T-data)*2;T=T-link;H28375PH2P101468习题习题与与练习练习3.对以
18、下单链表分别执行下列各程序段，画出结果示意图。(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;PHS28375
19、PRHS28375R10习题习题与与练习练习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.对以下单链表分别执行下列各程序段，画出结果示意图。(8)T=H;T-link=P-link;free
20、(P);H2837PT5H28375P习题习题与与练习练习3.对以下单链表分别执行下列各程序段，画出结果示意图。(9)S-link=H;HS28375如果S-link=H则S所指向的结点为尾结点.HS28375习题习题与与练习练习4.比较顺序表与链表的优缺点。在什么情况下用顺序表比链表好？5.为什么在单循环链表中设置尾指针比设置头指针更好？6.已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试写出完成下列功能的语句：(1)在P结点后插入S结点的语句序列是。(2)在P结点前插入S结点的语句序列是。(3)在表首插入S结点的语句序列是。(4)在表尾插入S结点的语句序列是。习题习题与与练习练习7.已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试写出完成下列功能的语句：(1)删除P结点的直接后继结点的语句序列是。(2)删除P结点的直接前驱结点的语句序列是。(3)删除P结的语句序列是。(4)删除首元结点的语句序列是。(5)删除尾元结点的语句序列是。武汉科技大学Wuhan University of Science and Technology