数据结构课程设计报告一元多项式加减乘除(精)

1、PAGE PAGE 31多项式想加减与乘与升降序学 院 计算机科学与技术 专 业 信 息 安 全 学 号 201312070 学 生 姓 名 陶宝中 辅导教师姓名 2014年12月 22 日设计目的与内容 了解数据结构的与算法的设计方法，独立分析和设计一元多项式加减与乘除的程序编码，通过程序编写掌握软件开发过程的问题分析，系统设计，程序编码，测试等基本方法和技能，提高综合运用所学理论知识和方法独立分析和解决问题的能力，通过这次实践将实验问题中的所涉及的对象在计算机中表示出来并对他们进行处理，掌握线除 。 任务与分析 本课题主要的目的是分别采用顺序和动态存储结构实现一元多项式的加法、减法和乘法。

2、并将操作结果分别按升序和降序输出程序的主要功能一元多项式创建建立一元多项式的顺序表和链式表，按程序提示输入每个项数据结束创建。借助元素在存储器中的相对位置来表示数据元素之间的关系，顺序表中第i个位置表示一元多项式的第i项的系数为第i个位置存放的内容，指数为i-1。创建一个一元多项式顺序表，对一元多项式的运算中会出现的各种情况进行分析，实现一元多项式的相加、相减、相乘操作。用链表来表示只存储多项式中系数非零的项。链表中的每一个结点存放多项式的一个term项结构和指向下一个节点的指针域，term又包括系数和指数两个域分别存放该项的系数、。创建一元多项式链表，对一元多项式的运算中会出现的各种可能情况

3、进行分析，实现一元多项式的相加、相减、相乘操作。一元多项式的加法 对于两个一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；对于两个一元多项式中所有指数不相同的项，则分别复抄到和多项式中去。一元多项式的减法对于两个一元多项式中所有指数相同的项，对应系数相减，若其差不为零，则构成“和多项式”中的一项；对于两个一元多项式中所有指数不相同的项，将其按减法规则复抄到差多项式中去。一元多项式的乘法将乘法运算分解为一系列的加法运算利用两个一元多项式相加的算法实现。一元多项式项的指数比较比较相邻两项的指数的大小。按升序排列时，前面项的指数大于后面项的指数就交换其项的位置。

4、按降序序排列时，后面项的指数大于前面项的指数就交换其项的位置。一元多项式运算结果升降排序一元多项式运算结果选择调用降序或升序排序函数。一元多项式的输出将选择的运算操作结果输出。一元多项式的销毁销毁已建立的两个多项式，释放空间。3 程序运行平台VC+6.0。 编译，链接，执行。 Windows XP。4 总体设计 图4。1 系统总体框架图主 函 数创建多项式多项式加法多项式减法多项式乘法多项式升降序 多项式输出5 程序类的说明 （1）Ploy结构声明typedef struct /顺序表结构声明 int aN;/记录多项式 int len;/记录多项式的长度Ploy; （2）term结构声明 t

5、ypedef struct /项的表示 float coef; /系数 int expn; /指数term;（3）LNode结构声明typedef struct LNode term data; /term多项式值 struct LNode *next;LNode,*LinkList; /两个类型名typedef LinkList polynomail; /用带头结点的有序链表表示多项式6 模块分析 整个流程图如图所示：图16.1 创建模块6.1.1、链式存储结构的一元多项式的创建程序源代码：polynomail creatpolyn(polynomail P,int m) /输入m项的系数和

6、指数，建立表示一元多项式的有序链表Ppolynomail r,q,p,s,Q;int i; P=(LNode*)malloc(sizeof(LNode); r=P;for(i=0;idata.coef,&s-data.expn); r-next=s;r=s;r-next=NULL;if(P-next-next!=NULL) for(q=P-next;q!=NULL/*&q-next!=NULL*/;q=q-next)/合并同类项for(p=q-next,r=q;p!=NULL;)if(q-data.expn=p-data.expn)q-data.coef=q-data.coef+p-data.

7、coef;r-next=p-next;Q=p;p=p-next;free(Q);else r=r-next;p=p-next;return P;6.1.2、顺序存储结构一元多项式的创建程序源代码：void GetPloy(Ploy *A)int i,coef,ex,maxe=0; char ch; printf(请输入每个项的系数及对应的指数，指数为负数时标志输入结束！n); for(i=0;iai=0;scanf(%d%d,&coef,&ex); while(ex=0) if(exmaxe) maxe=ex;if(A-aex!=0)printf(你输入的项已经存在，是否更新原数据？（Y/N）

8、);cinch; if(ch=Y|ch=y) A-aex=coef;printf(更新成功，请继续输入！n); elseprintf(请继续输入！n);else A-aex=coef;scanf(%d%d,&coef,&ex); A-len=maxe; return ;6.2 一元多项式的加法6.2.1 链式存储两多项式相加程序源代码：polynomail addpolyn(polynomail pa,polynomail pb) /完成多项式相加运算，即：Pa=Pa+Pbpolynomail s,newp,q,p,r;int j;p=pa-next;q=pb-next; newp=(LNod

9、e*)malloc(sizeof(LNode); r=newp; while(p&q) s=(LNode*)malloc(sizeof(LNode); switch(cmp(p-data,q-data)case -1: s-data.coef=p-data.coef;s-data.expn=p-data.expn;r-next=s; r=s;p=p-next;break;case 0: s-data.coef=p-data.coef+q-data.coef;if(s-data.coef!=0.0) s-data.expn=p-data.expn;r-next=s;r=s;p=p-next; q

10、=q-next; break;case 1: s-data.coef=q-data.coef; s-data.expn=q-data.expn; r-next=s; r=s; q=q-next; break;/switch/while6.2.2 顺序存储的多项式相加程序源代码：void ADD(Ploy A,Ploy B,Ploy *M)/*多项式A与多项式B相加，得到多项式M*/int la=A.len,lb=B.len,i; M-len=lalb?la:lb; for(i=0;i=la&iai=A.ai+B.ai;while(iai=A.ai;i+; while(iai=B.ai;i+;

11、return;6.3 一元多项式相减6.3.1链式存储的多项式相减程序源代码：/*3、两多项式相减*/polynomail subpolyn(polynomail pa,polynomail pb) /完成多项式相减运算，即：Pa=Pa-Pbpolynomail s,newp,q,p,r,Q; int j; p=pa-next;q=pb-next; newp=(LNode*)malloc(sizeof(LNode); r=newp; while(p&q) s=(LNode*)malloc(sizeof(LNode); switch(cmp(p-data,q-data)case -1: s-da

12、ta.coef=p-data.coef;s-data.expn=p-data.expn; r-next=s; r=s; p=p-next; break; case 0: s-data.coef=p-data.coef-q-data.coef;if(s-data.coef!=0.0) s-data.expn=p-data.expn; r-next=s; r=s;p=p-next; q=q-next; break;case 1: s-data.coef=-q-data.coef;s-data.expn=q-data.expn; r-next=s; r=s;q=q-next;/switch/whil

13、ewhile(p) s=(LNode*)malloc(sizeof(LNode); s-data.coef=p-data.coef; s-data.expn=p-data.expn; r-next=s; r=s; p=p-next;while(q) s=(LNode*)malloc(sizeof(LNode); s-data.coef=-q-data.coef; s-data.expn=q-data.expn; r-next=s; r=s; q=q-next; r-next=NULL;if(newp-next!=NULL&newp-next-next!=NULL)/合并同类项 for(q=ne

14、wp-next;q!=NULL;q=q-next)for(p=q-next,r=q;p!=NULL;)if(q-data.expn=p-data.expn) q-data.coef=q-data.coef+p-data.coef; r-next=p-next; Q=p;p=p-next; free(Q); else r=r-next;p=p-next; printf(升序 1 , 降序 2n); printf(选择:); scanf(%d,&j); if(j=1) arrange1(newp); else arrange2(newp); return newp;6.3.2顺序存储的多项式相减程

15、序源代码：void SUB(Ploy A,Ploy B,Ploy *M)/*多项式A与多项式B相减（A-B），得到多项式M*/ int la=A.len,lb=B.len,i; M-len=lalb?la:lb; for(i=0;i=la&iai=A.ai-B.ai; while(iai=A.ai;i+; while(iai=0-B.ai;i+; return ; 6.4 一元多项式相乘6.4.1链式存储的多项式相乘程序源代码：polynomail mulpolyn(polynomail pa,polynomail pb) /完成多项式相乘运算，即：Pa=Pa*Pbpolynomail s,n

16、ewp,q,p,r; int i=20,j; newp=(LNode*)malloc(sizeof(LNode); r=newp; for(p=pa-next;p!=NULL;p=p-next)for(q=pb-next;q!=NULL;q=q-next) s=(LNode*)malloc(sizeof(LNode); s-data.coef=p-data.coef*q-data.coef; s-data.expn=p-data.expn+q-data.expn; r-next=s; r=s; r-next=NULL; printf(升序 1 , 降序 2n); printf(选择:); sc

17、anf(%d,&j); if(j=1) arrange1(newp); else arrange2(newp);for(;i!=0;i-)for(q=newp-next;q-next!=NULL;q=q-next)/合并同类项for(p=q;p!=NULL&p-next!=NULL;p=p-next)if(q-data.expn=p-next-data.expn)q-data.coef=q-data.coef+p-next-data.coef;r=p-next;p-next=p-next-next; free(r);return newp;6.4.2顺序存储多项式相乘程序源代码：void MU

18、L(Ploy A,Ploy B,Ploy *M)/*多项式A与多项式B相乘，得到多项式M*/int i,j; for(i=0;iai=0; for(i=0;i=A.len;i+)for(j=0;jai+j+=A.ai*B.aj; M-len=A.len+B.len; return ; 6.5一元多项式输出结果按项的指数排序6.5.1链式由小到大排序图6.6.1链式升序流程图void arrange1(polynomail pa) polynomail h=pa,p,q,r; if(pa=NULL) exit(-2); for(p=pa;p-next!=NULL;p=p-next); r=p;

19、for(h=pa;h-next!=r;)/大的沉底 for(p=h;p-next!=r&p!=r;p=p-next) if(cmp(p-next-data,p-next-next-data)=1) q=p-next-next; p-next-next=q-next; q-next=p-next; p-next=q; r=p;/r指向参与比较的最后一个，不断向前移动 6.5.2链式由大到小排序图6.6.2链式降序流程图程序源代码：void arrange2(polynomail pa) polynomail h=pa,p,q,r; if(pa=NULL) exit(-2); for(p=pa;p

20、-next!=NULL;p=p-next); r=p; for(h=pa;h-next!=r;)/小的沉底 for(p=h;p-next!=r&p!=r;p=p-next) if(cmp(p-next-next-data,p-next-data)=1) q=p-next-next; p-next-next=q-next; q-next=p-next; p-next=q; r=p;/r指向参与比较的最后一个，不断向前移动6.5.3顺序由大到小排序程序源代码：void PrintPloy1(Ploy A) /降序输出顺序一元多项式int i; printf( %dx%d ,A.aA.len,A.l

21、en); for(i=A.len-1;i=1;i-) if(A.ai=0) ;else if(A.ai=1) printf( + x%d ,i);else if(A.ai=-1) printf( - x%d ,i);else if(A.ai0) printf(+ %dx%d ,A.ai,i); else printf(- %dx%d ,-A.ai,i); if(A.a0=0) ;else if(A.a00) printf( + %d,A.a0);/打印x的0次项 elseprintf( - %d,-A.a0);printf(n); return ;6.5.4顺序由小到大排序程序源代码：void

22、 PrintPloy2(Ploy A) /升序输出顺序一元多项式int i=0; while(A.ai=0) +i; if(i=0) printf(%d,A.ai); else if(A.ai=1) printf(x%d,i);else if(A.ai=-1) printf(-x%d,i); else printf(%dx%d,A.ai,i);for(+i;i1) printf( + %dx%d,A.ai,i); else if(A.aim;while(mm)printf(你输入的输出新创一元多项式的操作号不合法，请重新输入n);cinm;switch(m)case 1:if(m=1) pri

23、ntf(A降=); PrintPloy1(A); printf(n); printf(B降=); PrintPloy1(B);break;case 2:if(m=2)printf(A升=);PrintPloy1(A);printf(n);printf(B升=);PrintPloy1(B);break;Menushunxu();while(1) printf(请选择你想进行的顺序存储运算操作：n);cinn;while(n6)printf(输入的顺序操作号不对，请重新输入n);cinn; switch(n)case 1:if(n=1) printf(更新两个多项式：n);printf(请输入多项

24、式A：n); GetPloy(&A); printf(请输入多项式B：n); GetPloy(&B);printf(输出两个更新的一元多项式A、B，降幂输出请按1，升幂输出请按2！n);cinm; while(m2) printf(你输入的输出排序操作号不合法，请重新输入n); cinm; switch(m)case 1:if(m=1) printf(A降=);PrintPloy1(A);printf(n);printf(B降=);PrintPloy1(B);break;case 2:if(m=2) printf(A升=);PrintPloy1(A);printf(n);printf(B升=)

25、;PrintPloy1(B);break;break;case 2:if(n=2)ADD(A,B,&M); printf(降幂输出请按1，升幂输出请按2！n); cinm; while(m2) printf(你输入的输出排序操作号不合法，请重新输入n); cinm; switch(m)case 1:if(m=1) printf(ADD降=);PrintPloy1(M);printf(n);break;case 2:if(m=2)printf(ADD升=);PrintPloy2(M);printf(n);break;break;case 3: if(n=3)SUB(A,B,&M);printf(

26、降幂输出请按1，升幂输出请2！n);cinm;while(m2) printf(你输入的输出排序操作号不合法，请重新输入n); cinm; switch(m)case 1:if(m=1) printf(SUB降=);PrintPloy1(M);printf(n);break;case 2:if(m=2)printf(SUB升=);PrintPloy2(M);printf(n);break;break;case 4: if(n=4)MUL(A,B,&M);printf(降幂输出请按1，升幂输出请2！n);cinm;while(m3) printf(你输入输出排序操作号不合法，请重新输入n); c

27、inm;switch(m)case 1:if(m=1) printf(MUL降=);PrintPloy1(M);printf(n);break;case 2:if(m=2)printf(MUL升=);PrintPloy2(M);printf(n);break;break;case 5:if(n=5)printf(返回主菜单n);Menu(); break; case 6:if(n=6)printf(已成功退出该系统，谢谢你的使用！n);exit(-2); break; 6.6.3链式子系统程序源代码：void Menulink()printf(n); printf( *一元多项式链式存储的基本

28、运算*n); printf( 1、创建两个一元多项式请按1n); printf( 2、两多项式相加得一新多项式请按2n); printf( 3、两多项式相减得一新多项式请按3n); printf( 4、两多项式相乘得一新多项式请按4n); printf( 5、销毁已建立的两个多项式请按5n); printf( 6、退出该子系统返回主菜单请按6n);printf( 7、退出该系统请按7n); printf( *n);printf(n);void link() /一元多项式链式存储的实现polynomail pa=NULL,pb=NULL;polynomail p,q;polynomail add

29、p=NULL,subp=NULL,mulp=NULL;int n,m;printf(已进入链式存储一元多项式运算的子系统n);Menulink();while(1)printf(请选择你想进行的链式存储运算操作：n); scanf(%d,&n); switch(n)case 1:if(pa!=NULL) printf(已建立两个一元多项式，请选择其他操作!);break;printf(请输入第一个多项式：n);printf(要输入几项：);scanf(%d,&m);while(m=0) printf(m不能为0，请重新输入m：);scanf(%d,&m);pa=creatpolyn(pa,m)

30、;printpolyn(pa);printf(请输入第二个多项式：n); printf(要输入几项：); scanf(%d,&m);while(m=0) printf(m不能为0，请重新输入m：);scanf(%d,&m); pb=creatpolyn(pb,m); printpolyn(pb);break;case 2:if(pa=NULL) printf(请先创建两个一元多项式!n);break;addp=addpolyn(pa,pb);printpolyn(addp);break;case 3:if(pa=NULL) printf(请先创建两个一元多项式!n);break;subp=su

31、bpolyn(pa,pb);printpolyn(subp);break;case 4:if(pa=NULL) printf(请先创建两个一元多项式!n);break; mulp=mulpolyn(pa,pb);printpolyn(mulp);break;case 5: if(pa=NULL)printf(请先创建两个一元多项式!n);break;delpolyn(pa,pb);pa=pb=NULL;printf(两个一元多项式的销毁成功!n);break;case 6:if(addp!=NULL) p=addp;while(p!=NULL)q=p;p=p-next;free(q);if(subp!=NULL)p=subp;while(p!=NULL) q=p; p=p-next; free(q);printf(返回主菜单n);Menu();break;case 7:if(addp!=NULL) p=addp;while(p!=NULL)q=p;p=p-next;free(q);if(subp!=NULL)p=subp;while(p!=NULL) q=p; p=p-next; free(q);printf(已成功退出该系统，谢谢你的使用！n);exit(-2);break;/swit