1、#大学数据结构课程设计报告 题目：顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现院（系）：计算机工程学院 学生姓名: 班级： 学号: 起迄日期: 2011.06.20-06.30指导教师: 指导教师评语： 成绩： 签名： 年 月 日20102011年度 第 2 学期 一、需求分析1、顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。可以分为几个模块：输入模块、输出模块（升幂降幂）、数据处理模块（多项式的加减乘）、主程序模块。2、在程序过程中加入汉字提示符，让读者清楚明白的操作该程序。运行程序时看起来简洁有序，操作简单明了3、程序执行时的命令：选择创建两个一元多项式输入
2、第一个一元多项式的项数依次输入一元多项式的系数和指数以相同方式输入第二个一元多项式选择操作方式选择降幂或升幂排序输出结果是否退出。4、测试数据。输入的一元多项式系数指数分别为7 0,3 1,9 8,5 17和8 1,22 7，-9 8。加法结果为；升幂 降幂减法结果为：升幂 降幂乘法结果为：升幂 降幂二、 概要设计1、设计思路： 在该程序中分别分为顺序存储和链式存储结构。2、数据结构设计：一元多项式抽象数据类型的定义：ADT Polynomial数据对象：D=ai|aiTermSet,i=1,2,m,m=0TermSet中的每一个元素包含一个表示系数的实数和表示指数的整数数据关系:R1=|ai
3、-1,aiD, 且ai-1中的指数值ai中的指数值，i=2,n基本操作：CreatPolyn(&P,m)操作结果：输入m项的系数和指数，建立一元多项式P.DesteoyPolyn(&P)初始条件：一元多项式P已存在。操作结果：销毁一元多项式P。PrintfPolyn(P)初始条件：一元多项式P已存在。操作结果：打印输出一元多项式P。PolynLength(P)初始条件：一元多项式P已存在。操作结果：返回一元多项式P的项数。AddPolyn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已存在。操作结果：完成一元多项式的加法运算，即：Pa=Pa+Pb,并销毁一元多项式Pb。SubtractPol
4、yn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已存在。操作结果：完成一元多项式的减法运算，即：Pa=Pa-Pb,并销毁一元多项式Pb。MultiplyPolyn(&Pa,&Pb)初始条件：一元多项式Pa和Pb已存在。操作结果：完成一元多项式的乘法运算，即：Pa=PaPb,并销毁一元多项式Pb。ADT Polynomial3.软件结构设计：本程序主要分为四大模块：主程序模块输入模块：通过Getpolyn函数输入输出模块（升幂降幂）：PrintPolyn函数实现输出数据处理模块（多项式的加减乘）：通过一元多项式的Polynomial基本操作实现三、 详细设计 1.定义程序中所有用到的数据及其
5、数据结构，及其基本操作的实现typedef struct float coef; /系数 int expn; /指数term;/*1、创建并初始化多项式链表*/polynomail creatpolyn(polynomail P,int m) polynomail 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-nex
6、t!=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; return P;2主函数和其他函数的伪码算法int cmp(term a,term b) if(a.expnb.expn) return 1; if(a.expn=b.expn) return 0; if(a.expnnext!=NUL
7、L;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-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指向参与比较的最后一个，不断向前移动 /*从大到小排序*/void arrange2(polynomail pa) polynomail h=pa,p,q,r; if(pa=NULL) exit(-2); for(p=pa;p-nex
8、t!=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指向参与比较的最后一个，不断向前移动 /*打印多项式,求项数*/int printpolyn(polynomail P) int i; polynomail q; if(P=NULL) printf(无项！n); else
9、 if(P-next=NULL) printf(Y=0n); else printf(该多项式为Y=);q=P-next;i=1; if(q-data.coef!=0&q-data.expn!=0) printf(%.2fX%d,q-data.coef,q-data.expn); i+; if(q-data.expn=0&q-data.coef!=0) printf(%.2f,q-data.coef);/打印第一项 q=q-next; if(q=NULL) printf(n);return 1; while(1)/while中，打印剩下项中系数非零的项， if(q-data.coef!=0&q
10、-data.expn!=0) if(q-data.coef0) printf(+); printf(%.2fX%d,q-data.coef,q-data.expn); i+; if(q-data.expn=0&q-data.coef!=0) if(q-data.coef0) printf(+); printf(%f,q-data.coef); q=q-next; if(q=NULL) printf(n); break; return 1;/*2、两多项式相加*/polynomail addpolyn(polynomail pa,polynomail pb) polynomail s,newp,
11、q,p,r;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-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.
12、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; break; /switch /while while(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)
13、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; 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-ne
14、xt-next; free(r); printf(升序 1 , 降序 2n); printf(选择:); scanf(%d,&j); if(j=1) arrange1(newp); else arrange2(newp); return newp;/*3、两多项式相减*/polynomail subpolyn(polynomail pa,polynomail pb) polynomail 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=(LNo
15、de*)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=q-next; break; case 1: s-data.coef=-q-d
16、ata.coef; s-data.expn=q-data.expn; r-next=s; r=s; q=q-next; break; /switch /while while(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;
17、r=s; q=q-next; r-next=NULL; if(newp-next!=NULL&newp-next-next!=NULL)/合并同类项 for(q=newp-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(选择:); s
18、canf(%d,&j); if(j=1) arrange1(newp); else arrange2(newp); return newp;/*4两多项式相乘*/polynomail mulpolyn(polynomail pa,polynomail pb) polynomail s,newp,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(LN
19、ode); 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(选择:); scanf(%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)
20、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;/*5、销毁已建立的两个多项式*/void delpolyn(polynomail pa,polynomail pb) polynomail p,q; p=pa; while(p!=NULL) q=p; p=p-next; free(q); p=pb; while(p!=NULL) q=p; p=p-next; free(q); printf(两
21、个多项式已经销毁n);void main()system(color 4c); polynomail pa=NULL,pb=NULL; polynomail p,q; polynomail addp=NULL,subp=NULL,mulp=NULL; int n,m; int sign=y; printf(1、创建两个一元多项式n); printf(2、两多项式相加得一新多项式n); printf(3、两多项式相减得一新多项式n); printf(4、两多项式相乘得一新多项式n); printf(5、销毁已建立的两个多项式n); printf(6、退出n); printf(n); while(
22、sign!=n) printf(请选择：); 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); printpolyn(pa); printf(请输入第二个多项式：n); printf(要输入几项：); scanf(%d,&m); pb=creatp
23、olyn(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=subpolyn(pa,pb); printpolyn(subp); break; case 4: if(pa=NULL) printf(请先创建两个一元多项式！n); break; mulp=mulpolyn(pa,pb);
24、 printpolyn(mulp); break; case 5: if(pa=NULL) printf(请先创建两个一元多项式！n); break; delpolyn(pa,pb); pa=pb=NULL; 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); exit(-2); /switch /while3.主要函数的程序流程图，实现设计中主程序和其他子模块的算法，以流程图的形式表示。（包含函数之间调用的关系图）1、2、四、 调试分析 1. 实际完成的情况说明（完成的功能，支持
