一元多项式计算.doc

数据结构课内实验实验报告实验1一元多项式计算姓 名_李晓伟_学 号_13030311_班 级_13软二_ 完成时间_2014/11/17_实验1 一元多项式计算1 问题描述： 能够按照指数降序排列建立并输出多项式； 完成两个多项式的相加、相减和相乘，并将结果输出。参考教材P42页上的例2-4定义抽象数据类型，实现多项式的创建、相加、相减、相乘、打印等函数。可以采用链表或数组任意一种结构表示多项式。2 设计思想（数学模型的选择）在数学上，一个一元多项式Pn(x)可按升幂写成：Pn(x)=a 0+a1 x+a2 x2 +an xn-1 .它由n+1个系数惟一确定，因此，在计算机里，它可用一个线性表P来表示：Pn=(a0,a1,a2,an)每一项的指数i隐含在其系数ai的序号里。 多项式的乘法规则：多次运用单项式与多项式相乘的法则得到的计算时(a+b)(m+n)，先把(m+n)看成一个单项式，(a+b) 是一个多项式，运用单项式与多项式相乘的法则，得到(a+b)(m+n)=a(m+n)+b(m+n),然后再次运用单项式与多项式相乘的法则。3 数据结构定义typedef struct Polynomiafloat coef;int expn;struct Polynomial *next; *Polyn,Polynomial;4 系统功能模块介绍系统主要分为: (1 )compare(); (2 )insert() (3 )createpolyn() (4 )printpolyn() (5 )addpolyn() (6 )subtractpolyn() (7 )mulpolyn() (8) main()5 程序清单（打印清单）# include stdio.h# include malloc.htypedef struct Polynomialfloat coef;int expn;struct Polynomial *next;*Polyn,Polynomial;/int 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 if(!a&b)return -1;/a多项式已空，但b多项式非空elsereturn 1;/b多项式已空，但a多项式非空/compare /void Insert(Polyn p,Polyn h) if(p-coef=0) free(p); /系数为0的话释放结点else /如果系数不为0 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; /Insert /Polyn CreatePolyn(Polyn head) Polyn p; /定义一个p链表p=head=(Polyn)malloc(sizeof(struct Polynomial); head-next=NULL; p=(Polyn)malloc(sizeof(struct Polynomial);/建立新结点以接收数据scanf(%f %d,&p-coef,&p-expn); while(p-coef!=-100) Insert(p,head); /调用Insert函数插入结点p=(Polyn)malloc(sizeof(struct Polynomial); /建立新结点以接收数据scanf(%f%d,&p-coef,&p-expn); printf(建立成功!nn);return head; /CreatePolyn /void PrintPolyn(Polyn 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 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+; /while printf(n); /PrintPolyn /Polyn AddPolyn(Polyn pa,Polyn pb) /求解并建立多项式a+b，返回其头指针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(compare(qa,qb) case 1: qc-coef=qa-coef; qc-expn=qa-expn; qa=qa-next; / 当a-expn b-expn时，将a这个节点放进新的多项式hc中break; case 0: qc-coef=qa-coef+qb-coef; qc-expn=qa-expn; qa=qa-next; qb=qb-next; break; / 当a-expn=b-expn时，先把系数相加，指数不变，在将这个节点放进新的多项式hc中 case -1: qc-coef=qb-coef; qc-expn=qb-expn; qb=qb-next; break; / 当a-expn expn时，将b这个节点放进新的多项式hc中 /switch if(qc-coef!=0) qc-next=hc-next; hc-next=qc; hc=qc; else free(qc); /当相加系数为0时，释放该结点 /while return headc; /AddPolyn /Polyn SubtractPolyn(Polyn pa,Polyn pb) /求解并建立多项式a-b，返回其头指针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; /SubtractPolyn /Polyn MulPolyn(Polyn pa,Polyn pb) /求解并建立多项式a*b，返回其头指针(该函数实现乘法) Polyn hf,pf; 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); /调用Insert函数以合并指数相同的项 return hf; /MulPolyn /int main() Polyn pa=0,pb=0,pc,pd,pf;/定义各式的头指针，pa与pb在使用前付初值NULL /pc头指针所在的多项式用在加法中作为结果，pd用在加法中，pf乘法中int i=1; /菜单变量printf(建立第一个多项式，输入-100结束:n);pa=CreatePolyn(pa); /建立第一个多项式a printf(n);printf(建立第二个多项式,输入-100结束:n);pb=CreatePolyn(pb);printf(n); /建立第二个多项式b printf(多项式A(x)=); /多项式aPrintPolyn(pa);printf(多项式B(x)=); /多项式bPrintPolyn(pb);while(i!=0)printf(=n);printf( 选择计算公式:n);printf( 1:A(x)+B(x)n);printf( 2:A(x)-B(x)n);printf( 3:A(x)*B(x)n);printf( 0:退出程序!n);printf(=n);scanf(%d,&i);switch (i) case 1 : pc=AddPolyn(pa,pb); printf(多项式A(x)+B(x)=); /多项式a+b PrintPolyn(pc); break; case 2 : pd=SubtractPolyn(pa,pb); printf(多项式A(x)-B(x)=); /多项式a-b PrintPolyn(pd);break; case 3 :pf=MulPolyn(pa,pb); printf(多项式A(x)*B(x)=); /多项式a*b PrintPolyn(pf);break;default : return 0; 6 运行与调试分析（运行结构