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

西安文理学院软件学院课程设计报告设计名称： 数据结构课程设计 设计题目： 任意两个高次多项式的加法和乘法运算学生学号： 1402120433 专业班级： 软件工程12级4班 学生姓名： 学生成绩： 指导教师（职称）： 课题工作时间： 2014.6.16 至 2014.6.27 说明：1、报告中的任务书、进度表由指导教师在课程设计开始前填写并发给每个学生。2、学生成绩由指导教师根据学生的设计情况给出各项分值及总评成绩。3、所有学生必须参加课程设计的答辩环节，凡不参加答辩者，其成绩一律按不及格处理。答辩由指导教师实施。4、报告正文字数一般应不少于3000字，也可由指导教师根据本门综合设计的情况另行规定。5、平时表现成绩低于6分的学生，取消答辩资格，其本项综合设计成绩按不及格处理。软件学院课程设计任务书学生姓名学号专业班级设计题目任意两个高次多项式的加法和乘法运算内容概要： 用c+语言及数据结构的思想解决任意两个高次多项式的加法和乘法运算。数据输入方面可以根据一元高次多项式的特征，从左到右开始，按每一项指数、系数的顺序输入。运用单链表、动态链表等关键技术，实现所设计的数据结构应尽可能节省存储空间、程序的运行时间应尽可能的少的功能。开发环境：Visual C+ 6.0让同学深入了解C+，掌握C+的功能和数据结构的功能。文献资料：1 韩利凯，李军. 数据结构M. 浙江：浙江大学出版社,2013.2 苏仕华. 数据结构课程设计M. 北京：机械工业出版社 ,2009.3 耿国华. 数据结构-用C语言描述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日系统功能设计和模块设计、系统体系结构构建。6月21日6月24日各功能模块编码实现，系统各功能模块调试与维护。6月25日6月26日系统功能集成、系统调试与测试，按照模板要求撰写课程设计/项目设计报告。6月27日课程设计/项目设计分组答辩，提交课程设计/项目设计报告以及相关文档，进行成绩评定。指导教师签名： 2014年6月16日成绩评定表学生姓名： 学号： 专业： 软件工程 班级： 2012级4班 类别合计分值各项分值评分标准实际得分合计得分平时表现1010按时参加设计指导，无违反纪律情况。完成情况3020按设计任务书的要求完成了全部任务，能完整演示其设计内容，符合要求。10能对其设计内容进行详细、完整的介绍，并能就指导教师提出的问题进行正确的回答。报告质量3510报告文字通顺，内容翔实，论述充分、完整，立论正确，结构严谨合理；报告字数符合相关要求，工整规范，整齐划一。5课题背景介绍清楚，综述分析充分。5设计方案合理、可行，论证严谨，逻辑性强，具有说服力。5符号统一；图表完备、符合规范要求。5能对整个设计过程进行全面的总结，得出有价值的结论或结果。5参考文献数量在2篇以上，格式符合要求，在正文中正确引用。答辩情况2510在规定时间内能就所设计的内容进行阐述，言简意明，重点突出，论点正确，条理清晰。15在规定时间内能准确、完整、流利地回答教师所提出的问题。总评成绩： 分 指导教师： （签字） 日期：2014 年6月 27 日摘 要摘要：任意两个高次多项式的加法和乘法运算。所设计的数据结构应尽可能节省存储空间，程序的运行时间应尽可能少。在数据输入方面可以根据一元高次多项式的特征，从左到右开始，按每一项指数、系数的顺序输入。但是相乘的多项式项数是未知的，所以选择什么样的存储方式在本课程设计中尤为重要。程序通过调试运行，初步实现了设计目标，并且经过适当完善后，将可以应用在商业中解决实际问题。关键词：高次多项式; 加法; 乘法; 存储方式西安文理学院软件学院 课程设计报告目 录摘 要VI第一章 课题背景11.1 需求分析11.2 程序的目的11.3 要解决的问题11.4 设计思路11.5 程序运行平台11.6 性能要求2第二章 设计简介及设计方案论述32.1设计简介32.2 数据结构的选择32.3解决方案32.4 各程序模块之间的层次（调用）关系42.5 用户使用说明4第三章 详细设计53.1 算法思想53.2 下面是针对本程序专门定义的数据结构类型53.3 结构图63.4 算法描述6第四章 设计结果及分析114.1 程序调试114.2 时间空间复杂度的计算124.3 错误分析134.4 存在的不足与对策、编程体会13总结14参考文献15附录：程序源代码16第一章 课题背景1.1 需求分析我们日常生活的开支，大额数字或者多倍小数的计算都需要计算器的帮助。小学时，你可能拿的是简单的计算器，而高中，这简单的计算器已经满足不了你的需求。虽然现在的计算器价格比较便宜，各种功能不同，操作不便。有时你需要的那种功能计算器还不能实现，所以能够通过自己的手设计开发出你所需要的计算程序是非常有意义的。为方便让你算出任意两个高次多项式的加法和乘法，特编写此程序。使用该程序之后，所设计的数据结构应尽可能节省存储空间，程序的运行时间应尽可能少。 1.2 程序的目的设计程序以实现任意两个高次多项式的加法和乘法运算。所设计的数据结构应尽可能节省存储空间，程序的运行时间应尽可能少。 1.3 要解决的问题1. 怎样实现两个多项式的乘法？2. 相乘后若有指数相同的项用什么方法合并？3. 使用什么数据结构来满足尽可能节省存储空间的要求？4. 用什么方法来输出表达式？1.4 设计思路从题目看出所设计的程序应能达到的功能，设计好的程序要满足以上两点。在数据输入方面可以根据一元高次多项式的特征，从左到右开始，按每一项指数、系数的顺序输入。这里要留意一个问题，因为要相乘的多项式项数是未知的，所以选择什么样的存储方式在 课程设计中尤为重要，这也是本程序好坏的一个评定。1.5 程序运行平台该程序是用Visual C+6.0制做的，使用Visual C+ 6.0运行该程序，具体操作是：打开Visual C+ 6.0，菜单栏里点文件打开工作区找到“cpp1.dsw”这个文件打开，或者在资源管理器中双击该文件，此时，VC+6.0会自动打开，并载入该系统相关资源。 1.6 性能要求1.系统易操作性所开发的系统应操作简单，使学生不受电脑水平的限制。2.系统具有可维护性由于系统设计的范围较广，数据库中的信息需定期修改，为了使系统运作的更好，可以对系统数据及简单的功能进行简单的维护及调整。3.该系统能够在开发的硬件系统中运行不会因外部系统的不同面做不同的修改。第二章 设计简介及设计方案论述2.1设计简介设计题目: 设计程序以实现任意两个高次多项式的加法和乘法运算 目的：要求熟练掌握C+语言的基本知识和编辑技能；基本掌握结构化程序设计的基本思路和方法；以及数据结构的使用。 要求：1.所设计的数据结构应尽可能节省存储空间。2.程序的运行时间应尽可能少。2.2 数据结构的选择本程序选择的数据结构是单链表，原因如下：链表的定义：（1） 链表是有限个具有相同数据类型的数据元素的集合，D=ai/i=1,2,，n;ai为数据元素。（2） 数据元素之间的关系R=/ai,ai+1D。（3） 数据元素ai 在存储器中占用任意的、连续或不连续的物理存储区域。动态链表：当需要插入数据元素时，临时动态地为其申请一个存储空间，而不是将结点放在一个定义的数组中，删除数据元素时，可以释放该数据元素所占用的空间，即可以根据表的实际需要临时动态的分配存储空间以存储表中的数据元素。单链表是有限个具有相同数据类型的数据元素组成的链表且该链表的每一个结点只有一个指针域。带头结点的单链表是在单链表的第一个结点之前加一个同类型的结点，目的是为了使链表有一致的描述。本程序解决的是两多项式相加和相乘的问题，多项式的项数本身就是不确定的，而且相乘后的多项式可能含有指数相同的问题，这时就需要合并，合并后其中的一项就没有用了需要删除，不然就浪费内存空间。基于以上几点所以采用了链表。链表具有动态生成，灵活添加或删除结点的特点，尽可能节省存储空间。2.3解决方案 1、首先进行需求分析，搞清楚系统功能和任务；2、然后在总体设计中确定模块结构、划分功能模块，将软件功能需求分配给所划分的最单元模块。确定模块间的联系，确定数据结构、文件结构、数据库模式，确定测试方法与策略；3、在详细设计中，为每个模块确定采用的算法，选择适当的工具表达算法的过程（流程图）来描述模块的详细过程。确定每一模块采用的数据结构和模块接口的细节，对系统内部其他模块的接口 4、根据分析编写C+语言代码。 2.4 各程序模块之间的层次（调用）关系在执行主函数时先调用creat 生成要相乘的多项式，存储在两个动态链表中，然后调用print 函数输出两个多项式，继续执行相乘函数，相乘后调用置空函数将相乘的链表删除。然后，检验是否有指数相同的项，如果没有则调用print函数输出结果，否则调执行合并函数将指数项相同的合并，调用print函数输出结果。2.5 用户使用说明（1）给出任意两个高次多项式，只需按照多项式从左到右依次输入系数值、指数值，当输入指数值为-1 时结束。（由于程序设计的缺陷系数指数都要输入所以结束之前系数值可随便输入不影响运算结果。）（2）程序中指数、系数定义的是整型，所以表达式中系数值、指数值不能超出整型范围。（3）输入是正数直接输入，负数要加负号。指数不能选择-1。第三章 详细设计3.1 算法思想算法思想如下：（1）：首先将两个已知的多项式的指数和系数存放在指定链表中在执行乘法运算。乘法运算的过程是将f（x）式中的第一项与g（x）式的每一项相乘，在将f（x）式的第二项与g（x） 式的每一项相乘，依次下去直到f（x）式的所有项与g（x） 式乘完为止。将相乘后所得的指数、系数存在刚开始建好的F(x)链表中。（2）：F（x） 链表中如果有指数相同的项就需要合并，合并时将结果放在前一个项中，将后一项删除。这里需要将F（x） 链表中的每一项都要对比一遍，这里就要发挥指针的作用了。首先定义3个指针，x、y、z，x、y 指向首元素结点z 指向第二个结点，用z 结点中指数项与x 结点的指数项比较，如果不同指针z 向后移，若相同则将z 结点的系数加到x 上去然后将z 所在结点空间释放，并且指针z 后移。直到指针z 指向空后，将指针x 后移一项，并令z 指向x 的下一项，然后按上述步骤依次执行，直到x 指向空结束。这里指针y 是z 的前驱结点他的作用是合并后结点空间释放结点空间将此结点的前后两项链接起来。本程序核心部分全部是运用while 循环语句实现的。界面通过switch、case等语句来控制的。3.2 下面是针对本程序专门定义的数据结构类型结点的数据类型如下：typedef struct node /定义节点类型 float coef; int expn; struct node * next; PLOY; 数据结构的设计思想：链表中的每一个结点存放多项式的一个系数非0 项。它包含三个域,分别存放该项的系数、指数以及指向下一个多项式结点的指针。多项式链表结点的结构如下图3-1所示：系数 指数 指针coefexpnnext图 3-1 链表结点例如：多项式4x8+7x23-5x的单链表表示如下图3-2所示: 图3-2 单链表表示3.3 结构图整体的结构图如下图3-3所示：输入任意两个高次多项式的系数、指数值将输入值分别存储在两个动态链表中输出两个要相乘的多项式相乘将结果存入F(x)链表将存放相乘的多项式各项系数、指数的链表置空若有指数相同的项合并输出结果 图 3-3 整体结构图3.4 算法描述（1） 设指针p、q 分别为指向A、B 的首元素结点，用p-coef 乘q-coef,p-exp+q-exp,并令指针p 后移。（2）当q-next 为空时，指针p 向后移一位，指针q 继续从B 链表的第一项开始，执行p-coef 乘q-coef,p-exp 加q-exp.每执行一次指针p 后移。（3）重复（1）、（2）步，直到p-next 为空后，结束。将乘出结果存入C 链表。合并时用两个指针指向C 链表，一个指针跟随另一个当作后一个指针前驱指针，这样合并后释放就容易将前后结点链接上。综合以上分析，两个高次多项式相乘的算法如下：PLOY *byPLOY(PLOY *head1,PLOY *head2) /多项式相乘 PLOY *inpt,*res,*pre; int flag=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; inpt-expn=pre-expn+head1-expn; inpt-next=NULL; insert(res,inpt);/把当前g(x)的链节插入到y(x)中 return res; 用尾插法生成多项式链表的算法如下：PLOY *creat(char ch)/输入多项式 PLOY *head,*inpt; float x; int y; head=(PLOY *)malloc(sizeof(PLOY); /创建链表头 head-next=NULL; printf(请输入多项式%c:(格式是：系数 指数；以0 0 结束！)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的下一项:(以0 0 结束！)n,ch); scanf(%f %d,&x,&y); return head; 输出函数：void print(PLOY *fun) /输出多项式 PLOY *printing; int flag=0; printing=fun-next; /正在被打印的链节 if(fun-next=NULL) /如果函数为空打印0 printf(0n); return; while(flag=0) if(printing-coef0&fun-next!=printing) printf(+); /为正数时打印+号 if(printing-coef=1);/如果为1就不用打印系数了 else if(printing-coef=-1) printf(-); /如果为-1就打印-号就行了 else printf(%f,printing-coef);/其余情况都得打印 if(printing-expn!=0) printf(x%d,printing-expn);/如果指数为0不打印指数项 else if(printing-coef=1)|(printing-coef=-1) printf(1); if(printing-next=NULL) flag=1; /如果现在的链节没有下一个就结束 else printing=printing-next; printf(n); 以上就是按照题目功能要求和数据结构要求，编写算法和各程序模块代码。第四章 设计结果及分析4.1 程序调试1. 在VC的环境下,调试程序,进入界面，如下图4-1所示： 图4-1进入界面2. 按降幂输入第一个多项式数据,如下图4-2所示： 图4-2按升降幂输入数据 3. 按升幂输入第二个多项式数据，如下图4-3所示： 图4-3按升降幂输入数据4. 运行结果正确如下图4-4所示：图4-4 运行结果4.2 时间空间复杂度的计算若多项式A 有n 项,多项式B 有m 项，则两多项式相乘时为m*n ,接下来检验是否有同类项检查方法是每一项都要对比所以为(m*n)!,时间复杂度为O（m*n+(m*n）!)由于各个算法是基于动态链表而建成的，所以各算法的空间性能均较好。4.3 错误分析（1） 语句后面漏分号，或者在不该加分号的地方加了分号，或者忘记后括号。通过编译时的指出，改正了这些错误。（2）当程序执行到合并指数相同项时出现了错误。调试后发现执行完第一次while 循环后指向c 链表的指针e 不在存储空间中，导致无法判断while 循环，仔细检查后，发现合并时将e 指针所指结点释放后，没有给他指定新的结点。把指针e 后移一位，这样就解决了问题。（3）关于时间空间复杂度的计算不太会用，最后经过问同学和在互联网上查资料解决了这个问题。4.4 存在的不足与对策、编程体会因为掌握的知识有限，所以程序编起来有点难。通过编写这个系统，我体会到了一个系统应该作为一个整体来看待，系统具有牵一发而动全身的特性，某一个模块的一个小小错误都可能导致系统其他模块功能的丧失甚至是崩溃，同时在编程时应该按照模块来编写，一个模块实现一个功能，这样在调试的时候就方便检查，还有一个程序写完了，不是真正的结束，还需要不断地调试不断地修改程序中的错误。在编程中出现了一个致命的错误：我在程序中定义了几个函数但是忘记了使用引用导致了最后编译是出现了重大错误，经过好几个小时的仔细排查终于找到了问题所在。所以此次编程我最大的一个收获是：仔细研究每一个函数的定义，不要出现定义中形参缺少或者实参形参形式不符出现的错误总结本系统实现了以任意两个高次多项式的加法和乘法运算。所设计的数据结构应尽可能节省存储空间，程序的运行时间应尽可能少。通过本设计实验又将数据结构中的链表的知识重新温习了一遍，并且自己能够独立设计一些东西，学会了在设计实验过程时的基本步骤。基本上能够有条理的解决这些问题。在课程设计中，我使用了数据结构中学到的链表，因为链表具有动态生成，灵活添加或删除结点的特点，尽可能节省存储空间。正好符合题目的要求，自己不仅灵活的使用了链表，而且弄清楚了很多关于链表的作用，受益非浅。在课程设计中遇到了很多的问题，都是以前没有发现的，这些问题涉及的方面很多，有的是c 语言基础的，也有最近学习的数据结构的知识。在实习中，我们可以把这学期所学的理论知识和实践联系起来，在所要开发的项目中渐渐成长。虽然我们对这些知识运用得还不是很熟练，但是相信我们也在滴水穿石地成长起来。发现问题，提出问题，解决问题，使我们从不足之处出发，寻找新的学习方向。通过本次课程设计，让我发现了自己的不足。自己在学习知识上面的漏洞。希望通过弥补这些发现的漏洞，提高自己的专业知识水平。设计过程中的解决问题的方法，让我明白了如何学习会更有效。如何学习才不会耽误太多的时间。也学会了解决问题的一般方法：向老师、同学请教，借助网络等等。我要感谢学校给我提供的良好的环境，让我们可以在机房好好的学习。同时感谢老师对我的指导和帮助，感谢高年级哥哥姐姐给我的鼓励让我逐渐有了信心，也感谢帮助我的同学们。是你们对我的帮助和耐心指导，让我有信心完成这次作业，是你们给了我信心，也给了我无尽的希望。大家要互相帮助，共同进步，才能更好的学习，让自己的知识更加丰富，让自己在编程生涯得到提升。参考文献1 韩利凯，李军. 数据结构M. 浙江：浙江大学出版社,2013.2 苏仕华. 数据结构课程设计M. 北京：机械工业出版社 ,2009.3 耿国华. 数据结构-用C语言描述M. 北京：高等教育出版社,2011.4 严蔚敏,陈文博. 数据结构及算法教程M. 北京: 清华大学出版社,2010.附录：程序源代码#include #include typedef struct node /定义节点类型 float coef; int expn; struct node * next; PLOY; void start()/用户选择界面 printf(*n); printf( 任意两个高次多项式的相加/相乘:n); printf(*n); printf(请选择操作:n); printf(1.两个高次多项式相加n); printf(2.两个高次多项式相乘n); printf(0.退出n); void insert(PLOY *head,PLOY *inpt) /查找位置插入新链节程序 PLOY *pre,*now; int signal=0; pre=head; /pre定义为现在的前一个链节 if(pre-next=NULL) pre-next=inpt; else now=pre-next; while(signal=0) if(inpt-expnexpn) /当新链节小于现在的连接时向后移一个链节 if(now-next=NULL) now-next=inpt; signal=1; else pre=now; now=pre-next; else if(inpt-expnnow-expn) /如果发现比现在的链节大了就插入到这个连接的前面 inpt-next=now; pre-next=inpt; signal=1; else now-coef=now-coef+inpt-coef; signal=1; free(inpt); /与当前链节相等指数 if(now-coef=0) pre-next=now-next; free(now); PLOY *creat(char ch)/输入多项式 PLOY *head,*inpt; float x; int y; head=(PLOY *)malloc(sizeof(PLOY); /创建链表头 head-next=NULL; printf(请输入高次多项式%c:(格式是：系数 指数；以0 0 结束！)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的下一项:(以0 0 结束！)n,ch); scanf(%f %d,&x,&y); return head; PLOY *addPLOY(PLOY *head,PLOY *pre)/多项式相加 PLOY *inpt; int flag=0; while(flag=0) if(pre-next=NULL) flag=1;/当现在指向空时跳出循环 else pre=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)中 return head; PLOY *byPLOY(PLOY *head1,PLOY *head2)/多项式相乘 PLOY *inpt,*res,*pre; int flag=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; inpt-expn=pre-expn+head1-expn; inpt-next=NULL; insert(res,inpt);/把当前g(x)的链节插入到y(x)中 return res; void print(PLOY *fun) /输出多项式 PLOY *printing; int flag=0; printing=fun-next; /正在被打印的链节 if(fun-next=NULL) /如果函数为空打印0 printf(0n); return; while(flag=0) if(printing-coef0&fun-next!=printing) printf(+); /为正数时打印+号 if(printing-coef=1);/如果为1就不用打印系数了 else if(printing-coef=-1) printf(-); /如果为-1就打印-号就行了 else printf(%f,printing-coef);/其余情况都得打印 if(printing-expn!=0) printf(x%d,printing-expn);/如果指数为0不打印指数项 else if(printing-coef=1)|(printing-coef=-1) printf(1); if(printing-next=NULL) flag=1; /如果现在的链节没有下一个就结束 else printing=printing-next; printf(n); void main() PLOY *f,*g; int sign=-1; /操作选择 start(); /界面函数 while(sign!=0) scanf(%d,&sign); switch(sign) case 0: break;/退出 case 1: printf(你选择的操作是多项式相加:n); f=creat(f); /输入多项式f(x) printf(f(x)=); print(