数据结构一元多项式的相加.ppt

《数据结构一元多项式的相加.ppt》由会员分享，可在线阅读，更多相关《数据结构一元多项式的相加.ppt（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2.4 线性表的性表的应用用举例例 一元多一元多项式的表示及相加式的表示及相加一元多一元多项式的表示：式的表示：可用线性表P表示但对S(x)这样的多项式浪费空间一般其中用数据域含两个数据项的线性表表示其存储结构可以用顺序存储结构，也可以用单链表单链表的表的结点定点定义coef expnext-1A7 0 3 1 9 8 5 17 -1B8 1 22 7 -9 8 -1C7 0 11 1 22 7 5 17 一元多项式相加typedef struct node int coef,exp;struct node *next;JD;设设p,q分别指向分别指向A,B中某一结点，中某一结点，p,q初值是

2、第一结点初值是第一结点比较比较p-exp与与q-expp-exp exp:p结点是结果多项式结点是结果多项式中的一中的一 项，项，p后移后移,q不动不动p-exp q-exp:q结点是结果多项式中结点是结果多项式中的一的一 项，将项，将q插在插在p之前之前,q后移后移,p不动不动p-exp=q-exp:系数相加系数相加0：从：从A表中删去表中删去p所指所指结点结点 释放释放p,q，p,q后移后移 0：修改：修改p系数域系数域,释放释放q，p,q后移后移直到直到p或或q为为NULL 若若q=NULL，结束结束 若若p=NULL，将将B中剩余部分连到中剩余部分连到A上即可上即可运算规则q-1pa7

3、 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppre q-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq=NULL-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq=NULL-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppre-1pa7 0 11 1 22 7 5 17 Ch2_

4、7.c算法描述void add_poly(JD*pa,JD*pb)JD*p,*q,*u,*pre;int x;p=pa-next;q=pb-next;pre=pa;while(p!=NULL)&(q!=NULL)if(p-expexp)pre=p;p=p-next;else if(p-exp=q-exp)x=p-coef+q-coef;if(x!=0)p-coef=x;pre=p;else pre-next=p-next;free(p);p=pre-next;u=q;q=q-next;free(u);else u=q-next;q-next=p;pre-next=q;pre=q;q=u;if(q!=NULL)pre-next=q;free(pb);重点：线性表的顺序存储；线性表的链式存储；顺序表的插入、删除 单链表的插入、删除难点：双向链表的系列操作 线性表的应用。