一元多项式加减乘除运算(7页).doc

《一元多项式加减乘除运算(7页).doc》由会员分享，可在线阅读，更多相关《一元多项式加减乘除运算(7页).doc（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-一元多项式加减乘除运算-第 1 页中国计量学院实验报告实验课程：算法与数据结构实验名称：一元二项式班 级：学 号：姓 名：实验日期： 2013-5-7一 实验题目： 创建2个一元多项式 实现2个多项式相加 实现2个多项式相减 实现2个多项式相乘 实现2个多项式相除 销毁一元多项式实验成绩： 指导教师：二 算法说明 存储结构：一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况进行

2、分析，实现一元多项式的相加、相减操作。 加法算法开始定义存储结果的空链 r是 否输出存储多项式的和的链r结束是否同指数项系数相加后存入r中直接把p中各项存入r中直接把q中各项存入r存储多项式2的空链Q是否为空存储多项式1的空链P是否为空合并同类项三 测试结果四 分析与探讨实验数据正确，部分代码过于赘余，可以精简。五 附录：源代码#include#include#includetypedef struct Polynomialfloat coef;int expn;struct Polynomial *next;*Polyn,Polynomial; /Insertvoid Insert(Poly

3、n p,Polyn h) if(p-coef=0) free(p); /系数为0的话释放结点 else Polyn q1,q2; q1=h;q2=h-next; while(q2&p-expnexpn) /查找插入位置 q1=q2; q2=q2-next; if(q2&p-expn=q2-expn) /将指数相同相合并 q2-coef+=p-coef; free(p); if(!q2-coef)/系数为0的话释放结点 q1-next=q2-next; free(q2); else /指数为新时将结点插入 p-next=q2; q1-next=p;/CreatePolynPolyn Create

4、Polyn(Polyn head,int m) int i; Polyn p; p=head=(Polyn)malloc(sizeof( Polynomial); head-next=NULL; for(i=0;icoef,&p-expn); Insert(p,head); return head;/DestroyPolynvoid DestroyPolyn(Polyn head) Polyn q1,q2; q1=head; while(q1!=NULL) q2=q1-next; free(q1); q1=q2; return;/PrintPolynvoid PrintPolyn(Polyn

5、P) Polyn q=P-next; int flag=1; if(!q) /若多项式为空，输出0 putchar(0); printf(n); return; while (q) if(q-coef0&flag!=1) putchar(+);/系数大于0且不是第一项 if(q-coef!=1&q-coef!=-1)/系数非1或-1的普通情况 printf(%g,q-coef); if(q-expn=1) putchar(X); else if(q-expn) printf(X%d,q-expn); else if(q-coef=1) if(!q-expn) putchar(1); else

6、if(q-expn=1) putchar(X); else printf(X%d,q-expn); if(q-coef=-1) if(!q-expn) printf(-1); else if(q-expn=1) printf(-X); else printf(-X%d,q-expn); q=q-next; flag+; printf(n);/compareint compare(Polyn a,Polyn b) if(a&b) if(!b|a-expnb-expn) return 1; else if(!a|a-expnexpn) return -1; else return 0; else

7、if(!a&b) return -1;/a多项式已空，但b多项式非空 else return 1;/b多项式已空，但a多项式非空/AddPolynPolyn AddPolyn(Polyn pa,Polyn pb) Polyn qa=pa-next; Polyn qb=pb-next; Polyn headc,hc,qc; hc=(Polyn)malloc(sizeof(struct Polynomial);/建立头结点 hc-next=NULL; headc=hc; while(qa|qb) qc=(Polyn)malloc(sizeof(struct Polynomial); switch(

8、compare(qa,qb) case 1: qc-coef=qa-coef; qc-expn=qa-expn; qa=qa-next; break; case 0: qc-coef=qa-coef+qb-coef; qc-expn=qa-expn; qa=qa-next; qb=qb-next; break; case -1: qc-coef=qb-coef; qc-expn=qb-expn; qb=qb-next; break; /switch if(qc-coef!=0) qc-next=hc-next; hc-next=qc; hc=qc; else free(qc);/当相加系数为0

9、时，释放该结点 /while return headc;/SubtractPolynPolyn SubtractPolyn(Polyn pa,Polyn pb) Polyn h=pb; Polyn p=pb-next; Polyn pd; while(p)/将pb的系数取反 p-coef*=-1; p=p-next; pd=AddPolyn(pa,h); for(p=h-next;p;p=p-next) /恢复pb的系数 p-coef*=-1; return pd;/MultiplyPolynPolyn MultiplyPolyn(Polyn pa,Polyn pb) Polyn hf,pf;

10、 Polyn qa=pa-next; Polyn qb=pb-next; hf=(Polyn)malloc(sizeof(struct Polynomial);/建立头结点 hf-next=NULL; for(;qa;qa=qa-next) for(qb=pb-next;qb;qb=qb-next) pf=(Polyn)malloc(sizeof(struct Polynomial); pf-coef=qa-coef*qb-coef; pf-expn=qa-expn+qb-expn; Insert(pf,hf); return hf;/DevicePolynvoid DevicePolyn(P

11、olyn pa,Polyn pb) Polyn hf,pf,temp1,temp2; Polyn qa=pa-next; Polyn qb=pb-next; hf=(Polyn)malloc(sizeof(struct Polynomial);/建立头结点,存储商 hf-next=NULL; pf=(Polyn)malloc(sizeof(struct Polynomial);/建立头结点，存储余数 pf-next=NULL; temp1=(Polyn)malloc(sizeof(struct Polynomial); temp1-next=NULL; temp2=(Polyn)malloc(

12、sizeof(struct Polynomial); temp2-next=NULL; temp1=AddPolyn(temp1,pa); while(qa!=NULL&qa-expn=qb-expn) temp2-next=(Polyn)malloc(sizeof(struct Polynomial); temp2-next-coef=(qa-coef)/(qb-coef); temp2-next-expn=(qa-expn)-(qb-expn); Insert(temp2-next,hf); pa=SubtractPolyn(pa,MultiplyPolyn(pb,temp2); qa=p

13、a-next; temp2-next=NULL; pf=SubtractPolyn(temp1,MultiplyPolyn(hf,pb); pb=temp1; printf(商是：); PrintPolyn(hf); printf(余数是：); PrintPolyn(pf);int main() int m,n,flag=0,i,k; Polyn pa=0,pb=0,pc,pd,pf;/定义各式的头指针，pa与pb在使用前付初值NULL printf(请输入a的项数:); scanf(%d,&m); pa=CreatePolyn(pa,m);/建立多项式a printf(请输入b的项数:);

14、scanf(%d,&n); pb=CreatePolyn(pb,n);/建立多项式b /输出菜单 for ( k=1 ;k=1 ; ) printf(操作提示：nt1.输出多项式a和bnt2.多项式相加a+bnt3.多项式相减a-bn); printf(t4.多项式相除a*bnt5.多项式相除a/bnt6.销毁多项式n); printf(t7.退出n*n); printf(执行:); scanf(%d,&flag); switch(flag) case(1): printf(多项式a：);PrintPolyn(pa); printf(多项式b：);PrintPolyn(pb);break; c

15、ase(2): pc=AddPolyn(pa,pb); printf(多项式a+b：);PrintPolyn(pc); DestroyPolyn(pc);break; case(3): pd=SubtractPolyn(pa,pb); printf(多项式a-b：);PrintPolyn(pd); DestroyPolyn(pd);break; case(4): pf=MultiplyPolyn(pa,pb); printf(多项式a*b：);PrintPolyn(pf); DestroyPolyn(pf);break; case(5): DevicePolyn(pa,pb); break;

16、case(6): DestroyPolyn(pa); DestroyPolyn(pb);printf(成功销毁2个一元二项式n); printf(n接下来要执行的操作:n1 重新创建2个一元二项式 n2 退出程序n);printf(执行:);scanf(%d,&i);if(i=1)/ Polyn pa=0,pb=0,pc,pd,pf;/定义各式的头指针，pa与pb在使用前付初值NULL printf(请输入a的项数:); scanf(%d,&m); pa=CreatePolyn(pa,m);/建立多项式a printf(请输入b的项数:); scanf(%d,&n); pb=CreatePolyn(pb,n);/建立多项式b break;if(i=2)return 0; case(7): return 0;