一元多项式的加法、减法、乘法的实现数据结构课程设计.doc

课程设计(论文)题 目 名 称 一元多项式的加法、减法、乘法的实现 课 程 名 称 数据结构课程设计 学 生 姓 名 学 号 系 、专 业 信息工程系、通信工程 指 导 教 师 2012年 12 月 23 日摘 要设有一元多项式Am(x)和Bn(x)：Am(x)=A0+A1x+A2x2+A3x3+ +AmxmBn(x)=B0+B1x1+B2x2+B3x3+ +Bnxn分别采用顺序和链式存储结构实现：M(x)=Am(x)+Bn(x)、M(x)=Am(x)-Bn(x)和M(x)=Am(x)Bn(x)。并要结果M(x)中无重复阶项和无零系数项，且输出结果用升幂和降幂两种排列情况。关键词：一元多项式；顺序存储；链式存储；升幂；降幂目 录1 问题描述12 需求分析13 概要设计131抽象数据类型定义132模块划分24 详细设计341数据类型的定义342主要模块的算法描述35 测试分析76 课程设计总结10参考文献10附录（源程序清单）111 问题描述设有一元多项式Am(x)和Bn(x)：Am(x)=A0+A1x+A2x2+A3x3+ +AmxmBn(x)=B0+B1x1+B2x2+B3x3+ +Bnxn实现M(x)=Am(x)+Bn(x)、M(x)=Am(x)-Bn(x)、M(x)=Am(x)Bn(x)。要求： （1）分别采用顺序和链式存储结构实现；（2）结果M(x)中无重复阶项和无零系数项；（3）要求输出结果用升幂和降幂两种排列情况。2 需求分析（1）用一维数组cp1n1和cp2n2存储一元多项式Am(x)和Bn(x)的系数，用for循环来计算顺序结构中的加法、减法、乘法的结果。（2）用指针*d,*q来存储一元多项式的内容，再利用指针计算动态链表下一元多项式的加法、减法、乘法的结果。（3）在用降幂升幂两种排列输出结果时，用expn和coef表示一元多项式的系数和指数，输出两种排列结果。3 概要设计31抽象数据类型定义（1）顺序存储结构的抽象数据类型定义int n1,n2;利用一维数组cp1n1和cp2n2存储多项式的系数基本操作：void creatpoly1(double *a,int pt)操作结果：建立顺序结构void addpoly(double *a,double *b,double *c)初始条件：一维数组cp1n1和cp2n2已建立操作结果：顺序结构相加void subpoly(double *a,double *b,double *c)初始条件：一维数组cp1n1和cp2n2已建立操作结果：顺序结构相减 void mulpoly(double *a,double *b,double *c) 初始条件：一维数组cp1n1和cp2n2已建立操作结果：顺序结构相乘void ansprint(double *a,int n) 初始条件: 一维数组cp1n1和cp2n2已建立操作结果：选用升幂或降幂排列打印出结果（2）动态链表结构的抽象数据类型定义typedef struct p_pol double coef; int expn; p_pol *next；MPP；基本操作：MPP * creatlink(MPP *p,int n,int pt)初始条件：动态链表已定义操作结果：构造动态链表结构void addlink(MPP *p1,MPP *p2,MPP *p3)初始条件：动态链表已定义操作结果：动态链表相加void sublink(MPP *p1,MPP *p2,MPP *p3)初始条件：动态链表已定义操作结果：动态链表相减void mullink(MPP *p1,MPP *p2,MPP *p3)初始条件：动态链表已定义操作结果：动态链表相乘void printlink(MPP * p)初始条件：动态链表已定义操作结果：选用升幂或降幂排列打印结果void deletelink(MPP *p)初始条件：动态链表已定义操作结果：删除结点释放内存32模块划分本程序包括三个模块：（1）主程序模块void main()输入第一个多项式的项数；分别输入各项的系数和指数；输入第二个多项式的项数；分别输入各项的系数和指数；请选择实现结构：1 顺序结构 2 动态链表结构选择操作方式：1 相加 2 相减 3 相乘（2）顺序存储结构模块实现顺序存储结构的抽象数据类型（3）动态链表结构模块实现动态链表结构的抽象数据类型4 详细设计41数据类型的定义（1）顺序存储结构类型int n1,n2;int cp1n1; intcp2n2（2）动态链表结构类型#define INFEX 10000#define INFCO 10000double coef;int expn;p_pol *next;42主要模块的算法描述该题可画三个流程图：（1）一元多项式的计算主流程图；（2）顺序存储结构流程图；（3）动态链表结构流程图。流程图如下：（1）一元多项式的计算主流程图：如图4.1所示为动态链表结构为顺序结构开始输入两个多项式各项的系数选择实现结构顺序结构？YN选择打印输出结果的方式升幂？YN升幂输出结果降幂输出结果打印输出处理后的结果结束图4.1一元多项式的计算主流程图（2）顺序存储结构流程图如图4.2所示减法？开始采用顺序存储结构调用加法函数YN加法？调用降幂输出函数调用升幂输出函数YN调用减法函数调用乘法函数选择打印输出结果的顺序升幂？YN打印输出处理后的结果结束图4.2顺序存储结构流程图（3）动态链表结构流程图如图4.3所示减法？开始采用动态链表存储结构调用加法函数YN加法？调用降幂输出函数调用升幂输出函数YN调用减法函数调用乘法函数选择打印输出结果的顺序升幂？YN打印输出处理后的结果结束图4.3动态链表结构流程图5 测试分析测试数据及结果如下：6 课程设计总结通过这次课程设计使我了解到编写的程序不但要拿来使用，还要让人看得懂。所以，代码编写的风格要尽量规范，清晰。变量要尽量少定义，结构体采用简单的。另外，对指针的使用要小心，尽量在定义的时候就进行初始化，避免出现没有被定义的指针。该程序主要实现了顺序结构、动态链表结构下的一元多项式的加法、减法、乘法等运算功能。同时，也应用了升幂和降幂的输出方法，输出程序的结果。虽然此次的程序不是很完备，但是总体还是一个比较能体现数据结构知识点的程序了，当然只是相对于我这个初学者来说。这次设计中我发现了自己的许多不足，如对指针的机制掌握的还不是很透彻，有的时候会出现指针指向错误以及空指针的错误,还有不能很好地分析自己算法地复杂度以及不能很好地使用控制机制使自己的程序流畅地运行。因此，在今后我会更加努力地。在此我要非常感谢的是我的指导老师黄同成老师，感谢老师的细心认真的辅导，让我对数据结构这门课程有了更多的了解，也让我对这门课程产生了浓厚的兴趣。在这次课程设计中我又进一步地了解了数据结构中算法的核心思想的重要性，懂得了一个程序地好坏关键在于算法是否优秀，一个好的优秀的算法可以使我们的程序更加完善，安全性更高以及有更高的效率。参考文献1 黄同成，黄俊民，董建寅数据结构M北京：中国电力出版社，20082 董建寅，黄俊民，黄同成数据结构实验指导与题解M北京：中国电力出版社，20083 严蔚敏，吴伟民. 数据结构（C语言版）M. 北京：清华大学出版社，20024 刘振鹏，张晓莉，郝杰数据结构M北京：中国铁道出版社，2003附录（源程序清单）#include#include#include#define INFEX 10000#define INFCO 10000typedef struct poldouble coef;int expn;MPOL;MPOL *cp1,*cp2;/-顺序结构部分-int n1,n2;void ansprint(double *a,int n) /打印出结果int choose;puts(请选择输出顺序：1 升幂 2 降幂：);scanf(%d,&choose);int i,num;if(choose!=2) /升幂打印if(choose!=1)printf(没有%d选项，系统将默认输出升序：nM(X)=,choose);elseprintf(M(X)=);num=0;for(i=0;i1e-8)if(num+)putchar(+);printf(%lfX%d,ai,i);else /降幂打印printf(M(X)=);num=0;for(i=n;i=0;i-)if(fabs(ai)1e-8)if(num+)putchar(+); printf(%lfX%d,ai,i);putchar(10);void addpoly(double *a,double *b,double *c) /顺序结构相加int min=(cp1n1-1.expncp2n2-1.expn?cp2n2-1.expn:cp1n1-1.expn);int max=(cp1n1-1.expncp2n2-1.expn?cp2n2-1.expn:cp1n1-1.expn);int i;for(i=0;i=min;i+)ci=ai+bi;for(;icp2n2-1.expn)ci=ai;elseci=bi;puts(相加结果为：);ansprint(c,max);void subpoly(double *a,double *b,double *c) /顺序结构相减int min=(cp1n1-1.expncp2n2-1.expn?cp2n2-1.expn:cp1n1-1.expn);int max=(cp1n1-1.expncp2n2-1.expn?cp2n2-1.expn:cp1n1-1.expn);int i;for(i=0;i=min;i+)ci=ai-bi;for(;icp2n2-1.expn)ci=ai;elseci=-bi;puts(相减结果为：);ansprint(c,max);void mulpoly(double *a,double *b,double *c) /顺序结构相乘int max=cp1n1-1.expn+cp2n2-1.expn+2;int i,j;for(i=0;imax;i+)ci=0;for(i=0;i=cp1n1-1.expn;i+)for(j=0;j=cp2n2-1.expn;j+)ci+j+=ai*bj;puts(相乘结果为：);ansprint(c,max-1);void creatpoly1(double *a,int pt) /建立顺序结构int i;if(pt=1)for(i=0;i=cp1n1-1.expn;i+)ai=0;for(i=0;in1;i+)acp1i.expn=cp1i.coef;elsefor(i=0;i=cp2n2-1.expn;i+)ai=0;for(i=0;inext=NULL;q-coef=INFCO;q-expn=-INFEX;p=q;for(i=0;inext=NULL;if(pt=1)d-coef=cp1i.coef;d-expn=cp1i.expn;elsed-coef=cp2i.coef;d-expn=cp2i.expn;q-next=d;q=d;return p;void printlink1(MPP * p) /打印结果Am(x)int num=0,i=0,choose,count;puts(请选择输出顺序：1 升幂 2 降幂：);scanf(%d,&choose);MPP *tp=p;p=p-next;while(p!=NULL)num+;p=p-next;MPOL *d=new MPOLnum;p=tp-next;while(p!=NULL)di.coef=p-coef;di.expn=p-expn;i+;p=p-next;if(choose=2) /降幂打印count=0;printf(Am(X)=);for(i=num-1;i=0;i-)if(count+)putchar(+);printf(%lfX%d,di.coef,di.expn);else /升幂打印if(choose!=1)printf(没有%d选项，系统将默认输出升序：nAm(X)=,choose);elseprintf(Am(X)=);for(i=0;inext;while(p!=NULL)num+;p=p-next;MPOL *d=new MPOLnum;p=tp-next;while(p!=NULL)di.coef=p-coef;di.expn=p-expn;i+;p=p-next;if(choose=2) /降幂打印count=0;printf(Bn(X)=);for(i=num-1;i=0;i-)if(count+)putchar(+);printf(%lfX%d,di.coef,di.expn);else /升幂打印if(choose!=1)printf(没有%d选项，系统将默认输出升序：nBn(X)=,choose);elseprintf(Bn(X)=);for(i=0;inext;while(p!=NULL)num+;p=p-next;MPOL *d=new MPOLnum;p=tp-next;while(p!=NULL)di.coef=p-coef;di.expn=p-expn;i+;p=p-next;if(choose=2) /降幂打印count=0;printf(M(X)=);for(i=num-1;i=0;i-)if(count+)putchar(+);printf(%lfX%d,di.coef,di.expn);else /升幂打印if(choose!=1)printf(没有%d选项，系统将默认输出升序：nM(X)=,choose);elseprintf(M(X)=);for(i=0;icoef=INFCO;p-expn=-INFEX;p-next=NULL;head=p3=p;p1=p1-next;p2=p2-next;while(p1!=NULL|p2!=NULL)if(fabs(head-coef)1e-8)p=(MPP *)malloc(sizeof(MPP);if(p=NULL)exit(0);head-next=p;head=p;head-next=NULL;if(p1=NULL)head-coef=p2-coef;head-expn=p2-expn;p2=p2-next;continue;if(p2=NULL)head-coef=p1-coef;head-expn=p1-expn;p1=p1-next;continue;if(p1-expn=p2-expn)head-coef=p1-coef+p2-coef;head-expn=p1-expn;p1=p1-next;p2=p2-next;else if(p1-expnexpn)head-coef=p1-coef;head-expn=p1-expn;p1=p1-next;elsehead-coef=p2-coef;head-expn=p2-expn;p2=p2-next;puts(相加结果为：);printlink(p3);void sublink(MPP *p1,MPP *p2,MPP *p3) /动态链表相减MPP * p,*head;p=(MPP *)malloc(sizeof(MPP);if(p=NULL)exit(0);p-coef=INFCO;p-expn=-INFEX;p-next=NULL;head=p3=p;p1=p1-next;p2=p2-next;while(p1!=NULL|p2!=NULL)if(fabs(head-coef)1e-8)p=(MPP *)malloc(sizeof(MPP);if(p=NULL)exit(0);head-next=p;head=p;head-next=NULL;if(p1=NULL)head-coef=-p2-coef;head-expn=p2-expn;p2=p2-next;continue;if(p2=NULL)head-coef=p1-coef;head-expn=p1-expn;p1=p1-next;continue;if(p1-expn=p2-expn)head-coef=p1-coef-p2-coef;head-expn=p1-expn;p1=p1-next;p2=p2-next;else if(p1-expnexpn)head-coef=p1-coef;head-expn=p1-expn;p1=p1-next;elsehead-coef=-p2-coef;head-expn=p2-expn;p2=p2-next;puts(相减结果为：);printlink(p3);void mullink(MPP *p1,MPP *p2,MPP *p3) /动态链表相乘MPP *p,*head,*d,*tp;int i,j;p=(MPP *)malloc(sizeof(MPP);if(p=NULL)exit(0);p-coef=INFCO;p-expn=-INFEX;p-next=NULL;tp=head=p3=p;p=(MPP *)malloc(sizeof(MPP);if(p=NULL)exit(0);p-coef=INFCO;p-expn=INFEX;p-next=NULL;tp-next=p;for(i=0;inext;d=p2;for(j=0;jnext;p=(MPP *)malloc(sizeof(MPP);if(p=NULL)exit(0);p-next=NULL;p-coef=p1-coef*d-coef;p-expn=p1-expn+d-expn;tp=p3;while(tp-next!=NULL)if(tp-expn=p-expn)tp-coef+=p-coef;free(p);break;if(tp-expnexpn&tp-next-expnp-expn)p-next=tp-next;tp-next=p;break;tp=tp-next;tp=p3;while(tp-next!=NULL)if(tp-next-expn=INFEX)free(tp-next);tp-next=NULL;break;tp=tp-next;puts(相乘结果为：);printlink(p3);void deletelink(MPP *p) /删除结点释放内存MPP *d;while(p!=NULL)d=p;p=p-next;free(d);int main()int i,choose,choose2;puts(输入第一个多项式的项数：);scanf(%d,&n1);cp1=(MPOL *)malloc(n1*sizeof(MPOL);puts(分别输入各项的系数和指数：);for(i=0;in1;i+)scanf(%lf%d,&cp1i.coef,&cp1i.expn);puts(输入第二个多项式的项数：);scanf(%d,&n2);cp2=(MPOL *)malloc(n2*sizeof(MPOL);puts(分别输入各项的系数和指数：);for(i=0;in2;i+)scanf(%lf%d,&cp2i.coef,&cp2i.expn);puts(请选择实现结构：1 顺序结构 2 动态链表结构);scanf(%d,&choose);double *c1,*c2,*c3;MPP *p1=NULL,*p2=NULL,*p3=NULL;switch(choose)case 1:c1=(double *)malloc(cp1n1-1.expn+1)*sizeof(double);c2