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

西安文理学院软件学院课程设计报告设计名称：数据结构课程设计设计题目：任意两个高次多项式的加法和乘法运算学生学号：1402120433专业班级：软件工程12级4班学生姓名：学生成绩：指导教师（职称）：课题工作时间：2014.6.16至2014.6.27说明：1、报告中的任务书、进度表由指导教师在课程设计开始前填写并发给每个学生。2、学生成绩由指导教师根据学生的设计情况给出各项分值及总评成绩。3、所有学生必须参加课程设计的答辩环节，凡不参加答辩者，其成绩一律按不及格处理。答辩由指导教师实施。4、报告正文字数一般应不少于3000字，也可由指导教师根据本门综合设计的情况另行规定。5、平时表现成绩低于6分的学生，取消答辩资格，其本项综合设计成绩按不及格处理。软件学院课程设计任务书学生姓名学号专业班级设计题目任意两个高次多项式的加法和乘法运算内容概要：用c++语言及数据结构的思想解决任意两个高次多项式的加法和乘法运算。数据输入方面可以根据一元高次多项式的特征，从左到右开始，按每一项指数、系数的顺序输入。运用单链表、动态链表等关键技术，实现所设计的数据结构应尽可能节省存储空间、程序的运行时间应尽可能的少的功能。开发环境：VisualC++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需求分析我们日常生活的开支，大额数字或者多倍小数的计算都需要计算器的帮助。小学时，你可能拿的是简单的计算器，而高中，这简单的计算器已经满足不了你的需求。虽然现在的计算器价格比较便宜，各种功能不同，操作不便。有时你需要的那种功能计算器还不能实现，所以能够通过自己的手设计开发出你所需要的计算程序是非常有意义的。为方便让你算出任意两个高次多项式的加法和乘法，特编写此程序。使用该程序之后，所设计的数据结构应尽可能节省存储空间，程序的运行时间应尽可能少。1.2程序的目的设计程序以实现任意两个高次多项式的加法和乘法运算。所设计的数据结构应尽可能节省存储空间，程序的运行时间应尽可能少。1.3要解决的问题1.怎样实现两个多项式的乘法？2.相乘后若有指数相同的项用什么方法合并？3.使用什么数据结构来满足尽可能节省存储空间的要求？4.用什么方法来输出表达式？1.4设计思路从题目看出所设计的程序应能达到的功能，设计好的程序要满足以上两点。在数据输入方面可以根据一元高次多项式的特征，从左到右开始，按每一项指数、系数的顺序输入。这里要留意一个问题，因为要相乘的多项式项数是未知的，所以选择什么样的存储方式在课程设计中尤为重要，这也是本程序好坏的一个评定。1.5程序运行平台该程序是用VisualC++6.0制做的，使用VisualC++6.0运行该程序，具体操作是：打开VisualC++6.0，菜单栏里点文件→打开工作区→找到西安文理学院软件学院课程设计报告-2-“cpp1.dsw”这个文件→打开，或者在资源管理器中双击该文件，此时，VC++6.0会自动打开，并载入该系统相关资源。1.6性能要求1.系统易操作性所开发的系统应操作简单，使学生不受电脑水平的限制。2.系统具有可维护性由于系统设计的范围较广，数据库中的信息需定期修改，为了使系统运作的更好，可以对系统数据及简单的功能进行简单的维护及调整。3.该系统能够在开发的硬件系统中运行不会因外部系统的不同面做不同的修改。西安文理学院软件学院课程设计报告-3-第二章设计简介及设计方案论述2.1设计简介设计题目:设计程序以实现任意两个高次多项式的加法和乘法运算目的：要求熟练掌握C++语言的基本知识和编辑技能；基本掌握结构化程序设计的基本思路和方法；以及数据结构的使用。要求：1.所设计的数据结构应尽可能节省存储空间。2.程序的运行时间应尽可能少。2.2数据结构的选择本程序选择的数据结构是单链表，原因如下：链表的定义：（1）链表是有限个具有相同数据类型的数据元素的集合，D={ai/i=1,2,…，n};ai为数据元素。（2）数据元素之间的关系R={ai,ai+1/ai,ai+1∈D}。（3）数据元素ai在存储器中占用任意的、连续或不连续的物理存储区域。动态链表：当需要插入数据元素时，临时动态地为其申请一个存储空间，而不是将结点放在一个定义的数组中，删除数据元素时，可以释放该数据元素所占用的空间，即可以根据表的实际需要临时动态的分配存储空间以存储表中的数据元素。单链表是有限个具有相同数据类型的数据元素组成的链表且该链表的每一个结点只有一个指针域。带头结点的单链表是在单链表的第一个结点之前加一个同类型的结点，目的是为了使链表有一致的描述。本程序解决的是两多项式相加和相乘的问题，多项式的项数本身就是不确定的，而且相乘后的多项式可能含有指数相同的问题，这时就需要合并，合并后其中的一项就没有用了需要删除，不然就浪费内存空间。基于以上几点所以采用了链表。链表具有动态