数据结构课程设计一元多项式的加法与减法

课程设计(论文)题目名称一元多项式的加法、减法、乘法的实现课程名称数据结构课程设计学生姓名郭晗学号1141303066系、专业信息工程系、信息类指导教师黄同成2012年12月23日1摘要设有一元多项式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)中无重复阶项和无零系数项，且输出结果用升幂和降幂两种排列情况。关键词：一元多项式；顺序存储；链式存储；升幂；降幂2目录1问题描述................................................................................................12需求分析................................................................................................13概要设计................................................................................................13．1抽象数据类型定义.....................................................................13．2模块划分.....................................................................................44详细设计................................................................................................34．1数据类型的定义.........................................................................34．2主要模块的算法描述.................................................................35测试分析................................................................................................76课程设计总结......................................................................................10参考文献..................................................................................................10附录（源程序清单）..............................................................................1131问题描述设有一元多项式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）用一维数组cp1[n1]和cp2[n2]存储一元多项式Am(x)和Bn(x)的系数，用for循环来计算顺序结构中的加法减法乘法的结果。（2）用指针*d,*q来存储一元多项式的内容，再利用指针计算动态链表下一元多项式的加法减法乘法的结果。（3）在用降幂升幂两种排列输出结果时，用expn和coef表示一元多项式的系数和指数，输出两种排列结果。3概要设计3．1抽象数据类型定义（1）顺序存储结构的抽象数据类型定义intn1,n2;利用一维数组cp1[n1]和cp2[n2]存储多项式的系数基本操作：voidcreatpoly1(double*a,intpt)操作结果：建立顺序结构voidaddpoly(double*a,double*b,double*c)初始条件：一维数组cp1[n1]和cp2[n2]已建立操作结果：顺序结构相加4voidsubpoly(double*a,double*b,double*c)初始条件：一维数组cp1[n1]和cp2[n2]已建立操作结果：顺序结构相减voidmulpoly(double*a,double*b,double*c)初始条件：一维数组cp1[n1]和cp2[n2]已建立操作结果：顺序结构相乘voidansprint(double*a,intn)初始条件:一维数组cp1[n1]和cp2[n2]已建立操作结果：选用升幂或降幂排列打印出结果（2）动态链表结构的抽象数据类型定义typedefstructp_pol{doublecoef;intexpn;p_pol*next；}MPP；基本操作：MPP*creatlink(MPP*p,intn,intpt)初始条件：动态链表已定义操作结果：构造动态链表结构voidaddlink(MPP*p1,MPP*p2,MPP*p3)初始条件：动态链表已定义操作结果：动态链表相加voidsublink(MPP*p1,MPP*p2,MPP*p3)初始条件：动态链表已定义操作结果：动态链表相减voidmullink(MPP*p1,MPP*p2,MPP*p3)初始条件：动态链表已定义操作结果：动态链表相乘voidprintlink(MPP*p)初始条件：动态链表已定义操作结果：选用升幂或降幂排列打印结果voiddeletelink(MPP*p)初始条件：动态链表已定义操作结果：删除结点释放内存3．2模块划分5本程序包括三个模块：（1）主程序模块voidmain(){输入第一个多项式的项数；分别输入各项的系数和指数；输入第二个多项式的项数；分别输入各项的系数和指数；请选择实现结构：1顺序结构2动态链表结构选择操作方式：1相加2相减3相乘}（2）顺序存储结构模块——实现顺序存储结构的抽象数据类型（3）动态链表结构模块——实现动态链表结构的抽象数据类型4详细设计4．1数据类型的定义（1）顺序存储结构类型intn1,n2;intcp1[n1];intcp2[n2]（2）动态链表结构类型#defineINFEX10000#defineINFCO10000doublecoef;intexpn;p_pol*next;4．2主要模块的算法描述该题可画三个流程图：（1）一元多项式的计算主流程图；（2）顺序存储结构流程图；（3）动态链表结构流程图。流程图如下：（1）一元多项式的计算主流程图：如图4.1所示6图4.1一元多项式的计算主流程图选择操作方式选择打印输出方式开始输入两个多项式各项的系数和选择实现结构顺序结构？是否为顺序结构为动态链表结构结束打印输出处理后的结果7（2）顺序存储结构流程图如图4.2所示图4.2顺序存储结构流程图是否调用减法函数调用乘法函数选择打印输出顺序升幂是否开始顺序存储结构加法调用加法函数是否减法调用升幂输出函数调用降幂输出函数打印输出处理后的结果结束8（3）动态链表结构流程图如图4.3所示图4.3动态链表结构流程图是否调用减法函数调用乘法函数选择打印输出顺序升幂是否开始动态链表存储结构加法调用加法函数是否减法调用升幂输出函数调用降幂输出函数打印输出处理后的结果结束95测试分析测试数据及结果如下：1011126课程设计总结从这次数据结构课程设计，我不仅学会了怎样编出一个一元多项式的加法、减法、乘法的实现，而且还深深的体会到编好一个程序是一件非常有意义的事。我觉得编程不仅需要信心，还需要耐心，更需要团队合作之心，有了这些还不够，我们应该从实践出发，并从实践得到检验，不懂就是不懂，虚心求教才是解决问题的好办法。最后我要感谢老师给了我这次编程的机会，让我知道了团队合作原来如此重要，并且感受到数据结构原来也很奇妙，编程之路有点苦，但有我们团队一起走过的痕迹，我最后发现这是甜的味道！两周的课程设计结束了，在这次的课程设计中不仅检验了我所学习的知识，也培养了我如何去把握一件事情，如何去做一件事情，又如何完成一件事情。在设计过程中，与同学分工设计，和同学们相互探讨，相互学习，相互监督。学会了合作，学会了运筹帷幄，学会了宽容，学会了理解，也学会了做人与处世。课程设计是我们专业课程知识综合应用的实践训练，是我们迈向社会，从事职业工作前一个必不少的过程．”千里之行始于足下”，通过这次课程设计，我深深体会到这句千古名言的真正含义．我今天认真的进行课程设计，学会脚踏实地迈开这一步，就是为明天能稳健地在社会大潮中奔跑打下坚实的基础．通过这次课程设计，本人在多方面都有所提高。提高了编程能力，绘图能力，熟悉了规范和标准，同时各科相关的课程都有了全面的复习，独立思考的能力也有了提高。在这次设计过程中，体现出自己综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，从中发现自己平时学习的不足和薄弱环节，从而加以弥补参考文献[1]黄同成，黄俊民，董建寅．数据结构[M]．北京：中国电力出版社，2008[2]董建寅，黄俊民，黄同成．数据结构实验指导与题解[M]．北京：中国电力出版社，2008[3]严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，2002[4]刘振鹏，张晓莉，郝杰．数据结构[M]．北京：中国铁道出版社，200313附录（源程序清单）#includestdio.h#includemath.h#includestdlib.h#defineINFEX10000#defineINFCO10000typedefstructpol{doublecoef;intexpn;}MPOL;MPOL*cp1,*cp2;//-----顺序结构部分-----intn1,n2;voidansprint(double*a,intn)//打印出结果{intchoose;puts(请选择输出顺序：1升幂2降幂：);scanf(%d,&choose);inti,num;if(choose!=2)//升幂打印{if(choose!=1)printf(没有%d选项，系统将默认输出升序：\nY(X)=,choose);elseprintf(Y(X)=);num=0;for(i=0;i=n;i++)14if(fabs(a[i])1e-8){if(num++)putchar('+');printf(%lfX^%d,a[i],i);}}else//降幂打印{printf(Y(X)=);num=0;for(i=n;i=0;i--)if(fabs(a[i])1e-8){if(num++)putchar('+');printf(%lfX^%d,a[i],i);}}putchar(10);}voidaddpoly(double*a,double*b,double*c)//顺序结构相加{intmin=(cp1[n1-1].expncp2[n2-1].expn?cp2[n2-1].expn:cp1[n1-1].expn);intmax=(cp1[n1-1].expncp2[n2-1].expn?cp2[n2-1].expn:cp1[n1-1].expn);inti;for(i=0;i=min;i++)c[i]=a[i]+b[i];for(;i=