任意两个高次多项式的加法和乘法运算

《任意两个高次多项式的加法和乘法运算》由会员分享，可在线阅读，更多相关《任意两个高次多项式的加法和乘法运算（28页珍藏版）》请在装配图网上搜索。

1、西安文理学院软件学院课程设计报告设计名称：数据结构课程设计设计题目：任意两个高次多项式的加法和乘法运算学生学号：33专业班级：软件工程12级4班学生姓名：学生成绩：指导教师（职称）：课题工作时间：至说明：1、报告中的任务书、进度表由指导教师在课程设计开始前填写并发给每个学生。2、学生成绩由指导教师根据学生的设计情况给出各项分值及总评成绩。3、所有学生必须参加课程设计的答辩环节，凡不参加答辩者，其成绩一律按不及格处理。答辩由指导教师实施。4、报告正文字数一般应不少3000字，也可由指导教师根据本门综合设计的情况另行规定。5、平时表现成绩低6分的学生，取消答辩资格，其本项综合设计成绩按不及格处理。

2、软件学院课程设计任务书指导教师：院长：学生姓名学号专业班级设计题目任意两个局次多项式的加法和乘法运算内容概要：用C+语言及数据结构的思想解决任意两个高次多项式的加法和乘法运算。数据输入方面可以根据一元高次多项式的特征，从左到右开始，按每一项指数、系数的顺序输入。运用单链表、动态链表等关键技术，实现所设计的数据结构应尽可能节省存储空间、程序的运行时间应尽可能的少的功能。开发环境：VisualC+让同学深入了解C+,掌握C+的功能和数据结构的功能。文献资料：1韩利凯，李军.数据Z构M.浙江：浙江大学出版社，2013.2苏仕华.数据结构课程设计M.北京：机械工业出版社，2009.3耿国华.数据Z勾-

3、用可言描述M.北京：高等教育出版社,2011.4严蔚敏，陈文博.数据结构及算法教程M.北京：清华大学出版社,2010.设计要求：设计程序以实现任意两个高次多项式的加法和乘法运算。(1)所设计的数据结构应尽可能节省存储空间。(2)程序的运行时间应尽可能的少。工作期限：设计工作自2014年6月16日至2014年6月27日止。日期：2014年6月16日软件学院课程设计进度安排表学生姓名：学号：专业：软件工程班级:2012级4班起止日期内容备注6月16日6月17日下任务书；收集、阅读、整理相关参考文献，并进行归纳和概括总结，完成项目/任务背景介绍部分文字内容。6月18日11月20日系统功能设计和模块设

4、计、系统体系结构构建。6月21日6月24日各功能模块编码实现，系统各功能模块调试与维护。6月25日6月26日系统功能集成、系统调试与测试，按照模板要求撰写课程设计/项目设计报告。6月27日课程设计/项目设计分组答辩，提交课程设计/项目设计报告以及相关文档，进行成绩评定。指导教师签名:2014年6月16日成绩评定表学生姓名：学号：专业：软件工程班级:2012级4班类别合计分值各项分值评分标准实际得分合计得分平时表现1010按时参加设计指导，无违反纪律情况。完成情况3020按设计任务书的要求完成了全部任务，能完整演示其设计内容，符合要求。10能对其设计内容进行详细、完整的介绍，并能就指导教师提出的

5、问题进行正确的回答。报告X3510报告文字通顺，内容翔实，论述充分、完整，立论正确，结构严谨合理；报告字数符合相关要求，工整规范，整齐划一。5课题背景介绍清楚，综述分析充分。5设计方案合理、可行，论证严谨，逻辑性强，具有说服力。5符号统一；图表完备、符合规范要求。5能对整个设计过程进行全面的总结，得出有价值的结论或结果。5参考文献数量在2篇以上，格式符合要求，在正文中正确引用。答辩情况2510在规定时间内能就所设计的内容进行阐述，言简意明，重点突出，论点正确，条理清晰。15在规定时间内能准确、完整、流利地回答教师所提出的问题。总评成绩：分指导教师：（签字）日期：2014年6月27日摘要摘要：任

6、意两个高次多项式的加法和乘法运算。所设计的数据结构应尽可能节省存储空间，程序的运行时间应尽可能少。在数据输入方面可以根据一元高次多项式的特征，从左到右开始，按每一项指数、系数的顺序输入。但是相乘的多项式项数是未知的，所以选择什么样的存储方式在本课程设计中尤为重要。程序通过调试运行，初步实现了设计目标，并且经过适当完善后，将可以应用在商业中解决实际问题。关键词：高次多项式;加法;乘法;存储方式摘要VI第一章课题背景1需求分析1程序的目的1要解决的问题1设计思路1程序运行平台1性能要求2第二章设计简介及设计方案论述3设计简介3数据结构的选择3解决方案3各程序模块之间的层次（调用）关系4用户使用说明

7、4第三章详细设计5算法思想5下面是针对本程序专门定义的数据结构类型5结构图5算法描述5第四章设计结果及分析6程序调试6时间空间复杂度的计算7错误分析8存在的不足与对策、编程体会8总结9参考文献10附录：程序源代码11第一章课题背景需求分析我们日常生活的开支，大额数字或者多倍小数的计算都需要计算器的帮助。小学时，你可能拿的是简单的计算器，而高中，这简单的计算器已经满足不了你的需求。虽然现在的计算器价格比较便宜，各种功能不同，操作不便。有时你需要的那种功能计算器还不能实现，所以能够通过自己的手设计开发出你所需要的计算程序是非常有意义的。为方便让你算出任意两个高次多项式的加法和乘法，特编写此程序。使

8、用该程序之后，所设计的数据结构应尽可能节省存储空间，程序的运行时间应尽可能少。程序的目的设计程序以实现任意两个高次多项式的加法和乘法运算。所设计的数据结构应尽可能节省存储空间，程序的运行时间应尽可能少。要解决的问题1. 怎样实现两个多项式的乘法2. 相乘后若有指数相同的项用什么方法合并3. 使用什么数据结构来满足尽可能节省存储空间的要求4. 用什么方法来输出表达式设计思路从题目看出所设计的程序应能达到的功能，设计好的程序要满足以上两点。在数据输入方面可以根据一元高次多项式的特征，从左到右开始，按每一项指数、系数的顺序输入。这里要留意一个问题，因为要相乘的多项式项数是未知的，所以选择什么样的存储

9、方式在课程设计中尤为重要，这也是本程序好坏的一个评定。程序运行平台该程序是用VisualC+哧1做的，使用VisualC+运行该程序，具体操作是：打开VisualC+,菜单栏里点文件打开工作区找到“”这个文件打开,或者在资源管理器中双击该文件，此时，VC+会自动打开，并载入该系统相关资源。性能要求1. 系统易操作性所开发的系统应操作简单，使学生不受电脑水平的限制。2. 系统具有可维护性由于系统设计的范围较广，数据库中的信息需定期修改，为了使系统运作的更好，可以对系统数据及简单的功能进行简单的维护及调整。3. 该系统能够在开发的硬件系统中运行不会因外部系统的不同面做不同的修改。第二章设计简介及设

10、计方案论述设计简介设计题目：设计程序以实现任意两个高次多项式的加法和乘法运算目的：要求熟练掌握C+语言的基本知识和编辑技能；基本掌握结构化程序设计的基本思路和方法；以及数据结构的使用。要求：1 .所设计的数据结构应尽可能节省存储空间。2 .程序的运行时间应尽可能少。数据结构的选择本程序选择的数据结构是单链表，原因如下：链表的定义：(1)链表是有限个具有相同数据类型的数据元素的集合，D=ai/i=1,2,n;ai为数据元素。(2) 数据元素之间的关系R=/ai,ai+1CD。(3)数据元素ai在存储器中占用任意的、连续或不连续的物理存储区域。动态链表：当需要插入数据元素时，临时动态地为其中请一个

11、存储空间，而不是将结点放在一个定义的数组中，删除数据元素时，可以释放该数据元素所占用的空间，即可以根据表的实际需要临时动态的分配存储空间以存储表中的数据元素。单链表是有限个具有相同数据类型的数据元素组成的链表且该链表的每一个结点只有一个指针域。带头结点的单链表是在单链表的第一个结点之前加一个同类型的结点，目的是为了使链表有一致的描述。本程序解决的是两多项式相加和相乘的问题，多项式的项数本身就是不确定的，而且相乘后的多项式可能含有指数相同的问题，这时就需要合并，合并后其中的一项就没有用了需要删除，不然就浪费内存空间。基于以上几点所以采用了链表。尽可能节省存储空间链表具有动态生成，灵活添加或删除结

12、点的特点，解决方案1、首先进行需求分析，搞清楚系统功能和任务；2、然后在总体设计中确定模块结构、划分功能模块，将软件功能需求分配给所划分的最单元模块。确定模块间的联系，确定数据结构、文件结构、数据库模式，确定测试方法与策略；3、在详细设计中，为每个模块确定采用的算法，选择适当的工具表达算法的过程（流程图）来描述模块的详细过程。确定每一模块采用的数据结构和模块接口的细节，对系统内部其他模块的接口4、根据分析编写C+叫言代码。各程序模块之间的层次（调用）关系在执行主函数时先调用creat生成要相乘的多项式，存储在两个动态链表中，然后调用print函数输出两个多项式，继续执行相乘函数，相乘后调用置空

13、函数将相乘的链表删除。然后，检验是否有指数相同的项，如果没有则调用print函数输出结果，否则调执行合并函数将指数项相同的合并，调用print函数输出结果。用户使用说明（1）给出任意两个高次多项式，只需按照多项式从左到右依次输入系数值、指数值，当输入指数值为-1时结束。（由于程序设计的缺陷系数指数都要输入所以结束之前系数值可随便输入不影响运算结果。）（2）程序中指数、系数定义的是整型，所以表达式中系数值、指数值不能超出整型范围。3）输入是正数直接输入，负数要加负号。指数不能选择-1。第三章详细设计算法思想算法思想如下：(1):首先将两个已知的多项式的指数和系数存放在指定链表中在执行乘法运算。乘

14、法运算的过程是将f(x)式中的第一项与g(x)式的每一项相乘，在将f(x)式的第二项与g(x)式的每一项相乘，依次下去直到f(x)式的所有项与g(x)式乘完为止。将相乘后所得的指数、系数存在刚开始建好的F(x)链表中。(2):F(x)链表中如果有指数相同的项就需要合并，合并时将结果放在前一个项中，将后一项删除。这里需要将F(x)链表中的每一项都要对比一遍，这里就要发挥指针的作用了。首先定义3个指车+,x、v、z,x、y指向首元素结点z指向第二个结点，用z结点中指数项与x结点的指数项比较，如果不同指针z向后移，若相同则将z结点的系数加到x上去然后将z所在结点空间释放，并且指针z后移。直到指针z指

15、向空后，将指针x后移一项，并令z指向x的下一项，然后按上述步骤依次执行，直到x指向空结束。这里指针y是z的前驱结点他的作用是合并后结点空间释放结点空间将此结点的前后两项链接起来。本程序核心部分全部是运用while循环语句实现的。界面通过switch、case等语句来控制的。下面是针对本程序专门定义的数据结构类型结点的数据类型如下：typedefstructnode(3)重复(1)、(2)步，直到p-next为空后，结束。将乘出结果存入C链表。合并时用两个指针指向C链表，一个指针跟随另一个当作后一个指针前驱指针，这样合并后释放就容易将前后结点链接上。综合以上分析，两个高次多项式相乘的算法如下：P

16、LOY*byPLOY(PLOYhead1,PLOY*head2)在VC的环境下,调试程序,进入界面,如下图4-1所示：图4-1进入界面2 .按降幕输入第一个多项式数据，如下图4-2所示:*C:U sersl enovoXDes kto pDe b u gM-exe-任音两卜型网式小M自加且冢二)退巾L-两个率项苴相加 一网上翦图式相集 k-4-44_4_4_4_4_全输人多项式干，1格式是:事蛾 4131211100m渊人半独式r的下一I页：以。o 靠前人在项式工的下一项mUq o 手输入爵项TV的下一项：(UAo Q 品拓入委项宜工的下一项：吆口 口 宇输入参场式士,的K1即 以口 o Cx

17、J-*-4-Hi F+x_ 2-hx 1+1 转项人多项钛门(格式是：系的指敷m以口 CI结束!)I J !) !) !) !)以。o结束！，图4-2按升降幕输入数据3 .按开幕输入第二个多项式数据，如下图4-3所示:4.运行结果正确如下图4-4所示：g(x)=s 机防 2惶 1+1图4-4运行结果图4-3按升降幕输入数据请献务财通下一项：以。赫！)请附咨项*的下一项:取0。造束!)谙献嬲式加下一顼：以。给刘)输期赋曲下一哧以)0辕!)(x)=fW+j(k)=2.000000/4+2.000000s3+2,0000002+2,OOOOOQk+2,000000时间空间复杂度的计算若多项式A有n项

18、，多项式B有m项，则两多项式相乘时为m*n，接下来检验是否有同类项检查方法是每一项都要对比所以为(m*n)!,时间复杂度为O(m*n+(m*n)!)由于各个算法是基于动态链表而建成的，所以各算法的空间性能均较好。错误分析（1）语句后面漏分号，或者在不该加分号的地方加了分号，或者忘记后括号。通过编译时的指出，改正了这些错误。（2）当程序执行到合并指数相同项时出现了错误。调试后发现执行完第一次while循环后指向c链表的指针e不在存储空间中，导致无法判断while循环，仔细检查后，发现合并时将e指针所指结点释放后，没有给他指定新的结点。把指针e后移一位，这样就解决了问题。（3）关于时间空间复杂度的

19、计算不太会用，最后经过问同学和在互联网上查资料解决了这个问题。存在的不足与对策、编程体会因为掌握的知识有限，所以程序编起来有点难。通过编写这个系统，我体会到了一个系统应该作为一个整体来看待，系统具有牵一发而动全身的特性，某一个模块的一个小小错误都可能导致系统其他模块功能的丧失甚至是崩溃，同时在编程时应该按照模块来编写，一个模块实现一个功能，这样在调试的时候就方便检查，还有一个程序写完了，不是真正的结束，还需要不断地调试不断地修改程序中的错误。在编程中出现了一个致命的错误：我在程序中定义了几个函数但是忘记了使用引用导致了最后编译是出现了重大错误，经过好几个小时的仔细排查终于找到了问题所在。所以此

20、次编程我最大的一个收获是：仔细研究每一个函数的定义，不要出现定义中形参缺少或者实参形参形式不符出现的错误总结本系统实现了以任意两个高次多项式的加法和乘法运算。所设计的数据结构应尽可能节省存储空间，程序的运行时间应尽可能少。通过本设计实验又将数据结构中的链表的知识重新温习了一遍，并且自己能够独立设计一些东西，学会了在设计实验过程时的基本步骤。基本上能够有条理的解决这些问题。在课程设计中，我使用了数据结构中学到的链表，因为链表具有动态生成，灵活添加或删除结点的特点，尽可能节省存储空间。正好符合题目的要求，自己不仅灵活的使用了链表，而且弄清楚了很多关于链表的作用，受益非浅。在课程设计中遇到了很多的问

21、题，都是以前没有发现的，这些问题涉及的方面很多，有的是c语言基础的，也有最近学习的数据结构的知识。在实习中，我们可以把这学期所学的理论知识和实践联系起来，在所要开发的项目中渐渐成长。虽然我们对这些知识运用得还不是很熟练，但是相信我们也在滴水穿石地成长起来。发现问题，提出问题，解决问题，使我们从不足之处出发，寻找新的学习方向。通过本次课程设计，让我发现了自己的不足。自己在学习知识上面的漏洞。希望通过弥补这些发现的漏洞，提高自己的专业知识水平。设计过程中的解决问题的方法，让我明白了如何学习会更有效。如何学习才不会耽误太多的时间。也学会了解决问题的一般方法：向老师、同学请教，借助网络等等。我要感谢学

22、校给我提供的良好的环境，让我们可以在机房好好的学习。同时感谢老师对我的指导和帮助，感谢高年级哥哥姐姐给我的鼓励让我逐渐有了信心，也感谢帮助我的同学们。是你们对我的帮助和耐心指导，让我有信心完成这次作业，是你们给了我信心，也给了我无尽的希望。大家要互相帮助，共同进步，才能更好的学习，让自己的知识更加丰富，让自己在编程生涯得到提升。参考文献1 韩利凯，李军.数据结构M.浙江：浙江大学出版社,2013.2 苏仕华.数据结构课程设计M.北京：机械工业出版社,2009.3耿国华.数据结构-用C言描述M.北京：高等教育出版社，2011.4 严蔚敏,陈文博.数据结构及算法教程M.北京:清华大学出版社,201

23、0.附录：程序源代码#include#includetypedefstructnode个高次多项式相加n);printf(2.两个高次多项式相乘n);printf(0.退出n);voidinsert(PLOY*head,PLOY*inpt)/查找位置插入新链节程序PLOY*pre,*now;intsignal=0;pre=head;/pre定义为现在的前一个链节if(pre-next=NULL)pre-next=inpt;elsenow=pre-next;while(signal=0)if(inpt-expnexpn)/当新链节小于现在的连接时向后移一个链节if(now-next=NULL)n

24、ow-next=inpt;signal=1;elsepre=now;now=pre-next;elseif(inpt-expnnow-expn)/如果发现比现在的链节大了就插入到这个连接的前面inpt-next=now;pre-next=inpt;signal=1;elsenow-coef=now-coef+inpt-coef;signal=1;free(inpt);/与当前链节相等指数if(now-coef=0)pre-next=now-next;free(now);PLOY*creat(charch)/输入多项式PLOY*head,*inpt;floatx;inty;head=(PLOY*

25、)malloc(sizeof(PLOY);/创建链表头head-next=NULL;printf(”请输入高次多项式c:(格式是：系数指数；以00结束！)n,ch);scanf(%f%d,&x,&y);while(x!=0)inpt=(PLOY*)malloc(sizeof(PLOY);/创建新链节inpt-coef=x;inpt-expn=y;inpt-next=NULL;insert(head,inpt);/不然就查找位置并且插入新链节printf(请输入高次多项式c的下一项:(以00结束！)n,ch);scanf(%f%d,&x,&y);returnhead;PLOY*addPLOY(P

26、LOY*head,PLOY*pre)/多项式相加PLOY*inpt;intflag=0;while(flag=0)if(pre-next=NULL)flag=1;/当现在指向空时跳出循环elsepre=pre-next;inpt=(PLOY*)malloc(sizeof(PLOY);/创建新链节inpt-coef=pre-coef;inpt-expn=pre-expn;inpt-next=NULL;insert(head,inpt);/否则把当前g(x)的链节插入到y(x)中returnhead;PLOY*byPLOY(PLOY*head1,PLOY*head2)多项式相乘PLOY*inpt,

27、*res,*pre;intflag=0;res=(PLOY*)malloc(sizeof(PLOY);/创建链表头res-next=NULL;head1=head1-next;pre=head2;while(flag=0)if(pre-next=NULL)pre=head2;/当现在指向空时跳出循环head1=head1-next;continue;if(head1=NULL)flag=1;/当现在指向空时跳出循环continue;pre=pre-next;创建新链节inpt=(PLOY*)malloc(sizeof(PLOY);/inpt-coef=pre-coef*head1-coef;i

28、npt-expn=pre-expn+head1-expn;inpt-next=NULL;insert(res,inpt);/把当前g(x)的链节插入到y(x)中returnres;voidprint(PLOY*fun)/PLOY*printing;intflag=0;printing=fun-next;/if(fun-next=NULL)/printf(0n);输出多项式正在被打印的链节如果函数为空打印0return;while(flag=0)if(printing-coef0&fun-next!=printing)printf(+);/if(printing-coef=1);/elseif(

29、printing-coef=-1)printf(-);/elseprintf(%f,printing-coef);/为正数时打印+号如果为1就不用打印系数了如果为-1就打印-号就行了其余情况都得打印if(printing-expn!=0)printf(xA%d,printing-expn);如果指数为0不打印指数项elseif(printing-coef=1)|(printing-coef=-1)printf(1);if(printing-next=NULL)flag=1;/如果现在的链节没有下一个就结束elseprinting=printing-next;printf(n);voidmain

30、()PLOY*f,*g;intsign=-1;/操作选择start();/界面函数while(sign!=0)scanf(%d,&sign);switch(sign)case0:break;/退出case 1:printf(你选择的操作是多项式相加:n);f=creat(f);/输入多项式f(x)printf(f(x)=);print(f);g=creat(g);/输入多项式g(x)printf(g(x)=);print(g);printf(F(x)=f(x)+g(x)=);f=addPLOY(f,g);/两个多项式相加print(f);sign=-1;/复位标志start();/回复用户选择界面break;case 2:printf(你选择的操作是多项式相乘:n);f=creat(f);/输入多项式f(x)printf(f(x)=);print(f);g=creat(g);/输入多项式g(x)printf(g(x)=);print(g);printf(F(x)=f(x)*g(x)=);f=byPLOY(f,g);/两个多项式相加print(f);sign=-1;/复位标志start();/回复用户选择界面break;default:printf(输入有误!请重新选择操作!n);/选择错误,返回选择界面start();break;