数据结构线性表一元多项式的表示及相加.pptx
2.4 一元多项式一元多项式的表示及相加的表示及相加计算机中，可以用一个关于系数的线性表来表示：P=(p0,p1,pn)但是对于形如S(x)=1+3x100002x20000的多项式，上述表示方法是否合适？第1页/共37页2.4 一元多项式一元多项式的表示及相加的表示及相加一般情况下的一元稀疏多项式可写成Pn(x)=p1xe1+p2xe2+pmxem其中：pi 是指数为ei的项的非零系数，0e1e2em=n可以下列线性表表示：(p1,e1),(p2,e2),(pm,em)将单链表的每个结点对应着一元多项式中的一个非零项，它由三个域组成，分别表示非零项的系数、指数和指向下一个结点的指针。第2页/共37页2.4 一元多项式一元多项式的表示及相加的表示及相加P99(x)=7x3-2x12-8x99例:可用线性表(7,3),(-2,12),(-8,99)表示：73 Head-212-899/第3页/共37页v一元多项式的表示2.4 一元多项式的表示及相加一元多项式的表示及相加typedefstructpoly_node*poly_pointer;typedefstructpoly_node/项的表示floatcoef;/系数intexpn;/指数poly_pointerlink;/指针;结点的数据元素类型定义为:第4页/共37页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项的系数和指数，建立一元多项式PDestroyPolyn(&P)操作结果：销毁一元多项式PPrintPolyn(P)操作结果：打印输出一元多项式P。PolynLength(P)操作结果：返回一元多项式P中的项数。AddPolyn(&Pa,&Pb)操作结果：完成多项式相加运算，并销毁一元多项式SubtractPolyn(&Pa,&Pb)操作结果：完成多项式相减运算，并销毁一元多项式PbMultiplyPolyn(&Pa,&Pb)操作结果：完成多项式相乘运算，并销毁一元多项式Pb ADT Polynomial 第5页/共37页v实现思路依次比较Pa和Pb所指结点中的指数项，依Paexpn=、Pbexpn等情况，再决定是将两系数域的数值相加(并判其和是否为0)，还是将较高指数项的结点插入到新表C中。2.4 一元多项式的表示及相加一元多项式的表示及相加第6页/共37页v例1：设两个一元多项式为2.4 一元多项式的表示及相加一元多项式的表示及相加A(x)=3x14+2x8+1B(x)=8x14-3x10+10 x6求此两一元多项式之和:C(x)=A(x)+B(x)第7页/共37页2.4 一元多项式的表示及相加一元多项式的表示及相加 31428 10/814B-310 106/1114C-310 28106 10/PaAPaPaPbPbPbPcPcPcPcPcPbPa第8页/共37页v例2：设两个一元多项式为2.4 一元多项式的表示及相加一元多项式的表示及相加A(x)=4+6x4+5x8+4x12B(x)=2x3-5x8+3x12+7x15求此两一元多项式之和:C(x)=A(x)+B(x)第9页/共37页2.4 一元多项式的表示及相加一元多项式的表示及相加40 6 58 4 12 headA 23-58 312headB7 15 712 71540 64 headC2 34C(x)=4+2x3+6x4+7x12+7x15第10页/共37页2.4 一元多项式的表示及相加一元多项式的表示及相加VoidAddPolyn(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;case1;/pa当前的指数大于pb当前的指数DelFirst(hb,qb);InsFirst(ha,qb);qb=NextPos(pb,hb);ha=NextPos(pa,ha);break;intcmp(terma，termb)；依a的指数值)b的指数值，分别返回-1,0和1；第11页/共37页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);/链接pb剩余结点FreeNode(hb);/释放pb头结点/AddPolyn第12页/共37页VoidAddPolyn(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=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;case0;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+pb第13页/共37页2.4 一元多项式的表示及相加一元多项式的表示及相加VoidAddPolyn(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;case1;/pa当前的指数大于pb当前的指数DelFirst(hb,qb);InsFirst(ha,qb);qb=NextPos(pb,hb);ha=NextPos(pa,ha);break;intcmp(terma，termb)；依a的指数值)b的指数值，分别返回-1,0和1；第14页/共37页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);/链接pb剩余结点FreeNode(hb);/释放pb头结点/AddPolyn第15页/共37页v运算效率分析(1)系数相加：0 加法次数 min(m,n)其中m和n分别表示表A和表B的结点数。(2)指数比较：极端情况是表A和表B没有一项指数相同，比较次数最多为m+n-1(3)新结点的创建：极端情况是产生m+n个新结点合计时间复杂度为O(m+n)2.4 一元多项式的表示及相加一元多项式的表示及相加第16页/共37页v1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。本章小结本章小结第17页/共37页v2.熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。v3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合本章小结本章小结第18页/共37页习题习题与与练习练习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；第19页/共37页习题习题与与练习练习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；第20页/共37页习题习题与与练习练习H28375P(1)L=P-link;28375PHL3.对以下单链表分别执行下列各程序段，画出结果示意图。第21页/共37页习题习题与与练习练习3.对以下单链表分别执行下列各程序段，画出结果示意图。(2)R-data=P-data;28575PRHH28375PR第22页/共37页习题习题与与练习练习3.对以下单链表分别执行下列各程序段，画出结果示意图。(3)R-data=P-link-data;28775PRHH28375PR第23页/共37页习题习题与与练习练习3.对以下单链表分别执行下列各程序段，画出结果示意图。(4)P-link-link-link-data=P-data;25375PHH28375P第24页/共37页习题习题与与练习练习3.对以下单链表分别执行下列各程序段，画出结果示意图。(5)T=P;while(T!=NULL)T-data=(T-data)*2;T=T-link;H2P1014616H28375P第25页/共37页习题习题与与练习练习3.对以下单链表分别执行下列各程序段，画出结果示意图。(6)T=P;while(T-link!=NULL)T-data=(T-data)*2;T=T-link;H28375PH2P101468第26页/共37页习题习题与与练习练习3.对以下单链表分别执行下列各程序段，画出结果示意图。(7)P=(JD*)malloc(sizeof(JD);P-data=10;R-link=P;P-link=S;HS28375PR第27页/共37页习题习题与与练习练习3.对以下单链表分别执行下列各程序段，画出结果示意图。(7)P=(JD*)malloc(sizeof(JD);P-data=10;R-link=P;P-link=S;PHS28375PRHS28375R第28页/共37页习题习题与与练习练习3.对以下单链表分别执行下列各程序段，画出结果示意图。(7)P=(JD*)malloc(sizeof(JD);P-data=10;R-link=P;P-link=S;PHS28375PRHS28375R10第29页/共37页习题习题与与练习练习3.对以下单链表分别执行下列各程序段，画出结果示意图。(7)P=(JD*)malloc(sizeof(JD);P-data=10;R-link=P;P-link=S;PHS28375PRHS28375R10第30页/共37页习题习题与与练习练习3.对以下单链表分别执行下列各程序段，画出结果示意图。(7)P=(JD*)malloc(sizeof(JD);P-data=10;R-link=P;P-link=S;PHS28375PRHS28375R10第31页/共37页习题习题与与练习练习3.对以下单链表分别执行下列各程序段，画出结果示意图。(8)T=H;T-link=P-link;free(P);H2837PT5H28375P第32页/共37页习题习题与与练习练习3.对以下单链表分别执行下列各程序段，画出结果示意图。(9)S-link=H;HS28375如果S-link=H则S所指向的结点为尾结点.HS28375第33页/共37页习题习题与与练习练习4.比较顺序表与链表的优缺点。在什么情况下用顺序表比链表好？5.为什么在单循环链表中设置尾指针比设置头指针更好？6.已知L是无表头结点的单链表，且P结点既不是首元结点，也不是尾元结点，试写出完成下列功能的语句：(1)在P结点后插入S结点的语句序列是。(2)在P结点前插入S结点的语句序列是。(3)在表首插入S结点的语句序列是。(4)在表尾插入S结点的语句序列是。第34页/共37页习题习题与与练习练习7.已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试写出完成下列功能的语句：(1)删除P结点的直接后继结点的语句序列是。(2)删除P结点的直接前驱结点的语句序列是。(3)删除P结的语句序列是。(4)删除首元结点的语句序列是。(5)删除尾元结点的语句序列是。第35页/共37页第36页/共37页感谢您的观看！第37页/共37页
