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

2.4 线性表的应用举例 一元多项式的表示及相加 一元多项式的表示： 可用线性表P表示 但对S(x)这样的多项式浪费空间 一般 其中 用数据域含两个数据项的线性表表示 其存储结构可以用顺序存储结构，也可以用单链表 单链表的结点定义 coef exp next -1 A 7 0 3 1 9 8 5 17 ^ -1 B 8 1 22 7 -9 8 ^ -1 C 7 0 11 1 22 7 5 17 ^ 一元多项式相加 typedef struct node { int coef,exp; struct node *next; }JD; 设p,q分别指向A,B中某一结点，p,q初值是第一结点 比较 p-exp与 q-exp p-exp q-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 -1 pa 7 0 3 1 9 8 5 17 ^ -1 pb 8 1 22 7 -9 8 ^ p pre q -1 pa 7 0 3 1 9 8 5 17 ^ -1 pb 8 1 22 7 -9 8 ^ p pre q -1 pa 7 0 11 1 9 8 5 17 ^ -1 pb 8 1 22 7 -9 8 ^ p pre q -1 pa 7 0 11 1 9 8 5 17 ^ -1 pb 8 1 22 7 -9 8 ^ p pre q=NULL -1 pa 7 0 11 1 9 8 5 17 ^ -1 pb 8 1 22 7 -9 8 ^ p pre q=NULL -1 pa 7 0 11 1 9 8 5 17 ^ -1 pb 8 1 22 7 -9 8 ^ p pre -1 pa 7 0 11 1 22 7 5 17 ^ Ch2_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-expq-exp) { 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