程序语言课程设计任意两个高次多项式的加法和乘法运算

1、 课程设计报告设计名称： 数据结构课程设计 设计题目： 两个高次多项式的加法和乘法 学生学号： 1402120135 专业班级： 软件工程1班 软件学院课程设计任务书学生姓名 学号1402120135专业班级软件工程1班设计题目任意两个高次多项式的加法和乘法运算内容概要： 设计或开发环境：Microsoft Visual Studio 2010 关键技术：C+语言 主要功能： 1建立一元多次多项式 2高次多项式相加 3高次多项式相乘 文献资料：1谭浩强C语言程序设计（第三版） 清华大学出版社 20072姜敏芝 余健 C语言程序设计案例精编 清华大学出版社 20083李健学 余健 数据结构课程设

2、计案例精编 20074唐国民 王国均数据结构（C语言版） 清华大学出版社5韩利凯 李军 数据结构 浙江大学出版社 20136网上相关文献资料设计要求：A.功能要求1）输入并建立多项式；2）输出多项式；3）两个多项式相加，输出和多项式；4）两个多项式相乘，输出积多项式。B.文档格式*.cpp工作期限：设计工作自2014年6月16日至2014年6月27日止。指导教师： 韩利凯 院长： 日 期：2014年6月16日软件学院课程设计进度安排表 起止日期内 容备注6月16日 6月 17日下任务书；收集、阅读、整理相关参考文献，并进行归纳和概括总结，完成项目/任务背景介绍部分文字内容。6月18日11月20

3、日系统功能设计和模块设计、系统体系结构构建。6月21日6月24日各功能模块编码实现，系统各功能模块调试与维护。6月25日6月26日系统功能集成、系统调试与测试，按照模板要求撰写课程设计/项目设计报告。6月27日课程设计/项目设计分组答辩，提交课程设计/项目设计报告以及相关文档，进行成绩评定。指导教师签名： 2014年6月16日摘 要摘要：本课程设计主要解决任意两个高次多项式的乘法运算。所设计的数据结构应尽可能节省存储空间，程序的运行时间应尽可能少。从题目看出所设计的程序应能达到的功能，设计好的程序要满足以上两点。在数据输入方面可以根据一元高次多项式的特征，从左到右开始，按每一项指数、系数的顺序

4、输入。这里要留意一个问题，因为要相乘的多项式项数是未知的，所以选择什么样的存储方式在本课程设计中尤为重要，这也是本程序好坏的一个评定。程序通过调试运行，初步实现了设计目标，并且经过适当完善后，将可以应用在商业中解决实际问题。关键词：高次多项式；加法；乘法；时间复杂度；空间复杂度目 录目 录I第一章 课题背景21.1 绪论21.2 主要内容2第二章 设计简介及设计方案论述32.1 系统分析32.1.1 功能需求32.1.2 数据需求32.1.3 系统需求32.2 总体设计32.2.1 系统设计方案32.2.2 功能模块设计4第三章 详细设计53.1 主要流程图53.2 链表模块63.3 加法模块

5、83.4 乘法模块10第四章 设计结果及分析124.1 调试与测试124.1.1 调试124.1.2 测试124.1.3 运行界面134.2 结果分析13总结14参考文献15附录16第一章 课题背景1.1 绪论随着科技的进步，社会的不断发展，计算器已普遍应用于各行各业，为了帮助人们提高工作效率，节约运算时间，设计一个多功能的计算器是很有必要的，在此设计一个高次多项式计算器可以很方便的对多项式相加、相减、相乘，对提高人们的运算效率很有帮助。这样一个程序需要用到C+多方面的知识，要实现多项式的建立和输入输出等功能，必须要熟练的掌握C+，在此尤其是链表的灵活运用和结点特点。1.2 主要内容用C+语言

6、实现多项式的输入输出和多项式的加减乘等运算，其中主要用到链表和结点的相关知识,具体功能如下：1）输入并建立多项式；2）输出多项式；3）两个多项式相加，输出和多项式；4）两个多项式相减，输出差多项式。第二章 设计简介及设计方案论述2.1 系统分析2.1.1 功能需求 实现任意两个高次多项式的加法和乘法2.1.2 数据需求在输入过程中，首先要给定输入的数据，数据只能是数字，不能是字母或其他，不能连续输入数据，必须要求以空格分开要输入的数据。2.1.3 系统需求系统必须安全可靠，不会出现无故死机状态，运算速度要快。2.2 总体设计2.2.1 系统设计方案用户输入高次多项式系数和指数，用单链表储存你输

7、入的数据，输出两个多项式相加和相乘之后的结果。(1) 数据结构的选择本程序选择的数据结构是单链表，原因如下：当需要插入数据元素时，临时动态地为其申请一个存储空间，而不是将结点放在一个定义的数组中，删除数据元素时，可以释放该数据元素所占用的空间，即可以根据表的实际需要临时动态的分配存储空间以存储表中的数据元素。单链表是有限个具有相同数据类型的数据元素组成的链表且该链表的每一个结点只有一个指针域。带头结点的单链表是在单链表的第一个结点之前加一个同类型的结点，目的是为了使链表有一致的描述。本程序解决的是两多项式相乘的问题，多项式的项数本身就是不确定的，而且相乘后的多项式可能含有指数相同的问题，这时就

8、需要合并，合并后其中的一项就没有用了需要删除，不然就浪费内存空间。基于以上几点所以采用了链表。链表具有动态生成，灵活添加或删除结点的特点，尽可能节省存储空间。(2) 文件保存方式运用带头节点的单链表储存多项式。(3) 抽象数据类型定义主要定义多项式的系数和指数，系数项和指数项均用整型定义。(4) 存储结构采用链式结构，建立链表储存输入的多项式(5) 算法设计先将两个已知的多项式的指数和系数存放在指定链表中在执行乘法运算。乘法运算的过程是将A 式中的第一项与B 式的每一项相乘，在将A 式的第二项与B 式的每一项相乘，依次下去直到A 式的所有项与B 式乘完为止。将相乘后所得的指数、系数存在预先建好

9、的C 链表中。 C 链表中如果有指数相同的项就需要合并，合并时将结果放在前一个项中，将后一项删除。首先定义3个指针，x、y、z，x、y 指向首元素结点z 指向第二个结点，用z 结点中指数项与x 结点的指数项比较，如果不同指针z 向后移，若相同则将z 结点的系数加到x 上去然后将z 所在结点空间释放，并且指针z 后移。直到指针z 指向空后，将指针x 后移一项，并令z 指向x 的下一项，然后按上述步骤依次执行，直到x 指向空结束。这里指针y 是z 的前驱结点他的作用是合并后结点空间释放结点空间将此结点的前后两项链接起来。本程序核心部分全部是运用while 循环语句实现的。2.2.2 功能模块设计高

10、次多项式加法和乘法加法模块乘法模块输出模块输入模块链表模块图 2-1 功能模块第三章 详细设计多项式的建立主要需要建立新链表，并分配给这个新链表一定量的存储空间，分配的存储空间内进行运算；多项式加减乘等运算主要运用了链表的建立，链表存储空间分配，链表的查找，插入与连接进行计算。3.1 主要流程图此阶段是程序构建的思路，是本程序的结构图，同时也体现出本程序将要达到的功能，如图 3-1所示： 输入任意两个高次 多项式的系数、指数值 将输入值分别储存 在两个动态链表中 将相乘和相加的 结果存入C链表 将存放相乘多项式的各项 系数指数的链表置空 若有指数相同 的项合并 输出两个要进行 运算的多项式 输

11、出结果图 3-1 主流程图3.2 链表模块此阶段是程序中链表的主要流程，如图 3-2所示： Start list<term> Poly_add(list<term>&poly_list_first, list<term>&poly_list_second) list<term>:iterator iter_first = poly_list_first.begin();list<term>:iterator iter_second = poly_list_second.begin(); iter_first!=poly

12、_list_first.end() && iter_second != poly_list_second.end() term t_first = (term)*iter_first; term t_second = (term)*iter_second; t_first.exp>t_second.exp poly_list_result.push_back(t_first); iter_first+; t_second.exp> t_first.exp poly_list_result.push_back (t_second);iter_second+; t_te

13、mp.coef=t_first.coef +t_second.coef;t_temp. exp=t_first.coef;End图 3-2 链表结构图主要代码如下：list<term> Poly_add(list<term>&poly_list_first,list<term>&poly_list_second) list<term> poly_list_result;/用以存储运算结果 list<term>:iterator iter_first = poly_list_first.begin(); list<

14、term>:iterator iter_second = poly_list_second.begin(); /*该while循环针对两个链表迭代器都没有指到结尾的情形*/ while (iter_first != poly_list_first.end() && iter_second != poly_list_second.end() term t_temp; term t_first = (term)*iter_first; term t_second = (term)*iter_second; if (t_first.exp>t_second.exp) po

15、ly_list_result.push_back(t_first); iter_first+; else if (t_second.exp>t_first.exp) poly_list_result.push_back(t_second); iter_second+; else t_temp.coef = t_first.coef + t_second.coef; t_temp.exp = t_first.coef; poly_list_result.push_back(t_temp); iter_first+; iter_second+; /该for循环针对第一个多项式的迭代器没有指到

16、结尾 for (;iter_first != poly_list_first.end();iter_first+) poly_list_result.push_back(*iter_first); /该for循环针对第二个多项式的迭代器没有指到结尾 for (; iter_second != poly_list_second.end(); iter_second+) poly_list_result.push_back(*iter_second); return poly_list_result; 3.3 加法模块此阶段是程序中加法模块的主要流程，如图 3-3所示： Start list<

17、;term>:iterator iter_first = m_poly_list_first.begin();list<term>:iterator iter_second = m_poly_list_second.begin(); iter_first != m_poly_list_ first.end()&&iter_second!=m_poly_list_ second.end() term t_first = (term)*iter_first; term t_second = (term)*iter_second; t_first.exp>t_

18、second.exp m_poly_list_result.push_back(t_first); iter_first+; t_second.exp>t_first.exp m_poly_list_result.push_back (t_second);iter_second+; t_temp.coef=t_first.coef+t_second.coef; t_temp.exp=t_first.exp; m_poly_list_result.push_back(t_temp); iter_first+;iter_second+;iter_first!=m_poly_list_firs

19、t.end()m_poly_list_result.push_back(*iter_first);iter_first+;iter_second!=m_poly_list_second.end()m_poly_list_result.push_back(*iter_second);iter_second+;End图 3-3 加法模块结构主要代码如下：void Poly_add()list<term>:iterator iter_first = m_poly_list_first.begin();list<term>:iterator iter_second = m_po

20、ly_list_second.begin();while (iter_first != m_poly_list_first.end() && iter_second != m_poly_list_second.end()term t_temp;term t_first = (term)*iter_first;term t_second = (term)*iter_second;if(t_first.exp>t_second.exp)m_poly_list_result.push_back(t_first);iter_first+;else if(t_second.exp&

21、gt;t_first.exp)m_poly_list_result.push_back(t_second);iter_second+;elset_temp.coef = t_first.coef + t_second.coef;t_temp.exp = t_first.exp;m_poly_list_result.push_back(t_temp);iter_first+;iter_second+;for(;iter_first != m_poly_list_first.end(); iter_first+)m_poly_list_result.push_back(*iter_first);f

22、or (;iter_second != m_poly_list_second.end(); iter_second+)m_poly_list_result.push_back(*iter_second);3.4 乘法模块此阶段是程序中乘法模块的主要流程，如图 3-4所示：Startlist<term> poly_list_result;list<term>:iterator iter_first = m_poly_list_first.begin();iter_first != m_poly_list_first.end()list<term> poly_l

23、ist_temp;list<term>:iterator iter_second=m_poly_list_second.begin();iter_first+iter_second != m_poly_list_second.end();term t_first = (term)*iter_first;term t_second = (term)*iter_second;t_temp.coef = t_first.coef*t_second.coef;t_temp.exp = t_first.exp + t_second.exp;poly_list_temp.push_back(t

24、_temp);poly_list_result = Poly_add(poly_list_temp, poly_list_result);m_poly_list_result = poly_list_result;End图3-4 乘法模块结构主要代码如下：void Poly_multi()list<term> poly_list_result;list<term>:iterator iter_first = m_poly_list_first.begin();for (; iter_first != m_poly_list_first.end(); iter_first

25、+)list<term> poly_list_temp; /用以存储多项式的中间运算结果 list<term>:iterator iter_second=m_poly_list_second.begin();for (;iter_second != m_poly_list_second.end();iter_second+)term t_temp; /用以存储项的中间运算结果 term t_first = (term)*iter_first;term t_second = (term)*iter_second;/此处实现多项式项的相乘 t_temp.coef = t_f

26、irst.coef*t_second.coef; /系数相乘 t_temp.exp = t_first.exp + t_second.exp; /指数相加 poly_list_temp.push_back(t_temp);/此处调用私有成员函数Poly_add()poly_list_result = Poly_add(poly_list_temp, poly_list_result);/将运算结果赋值给私有数据成员,用以输出 m_poly_list_result = poly_list_result;第四章 设计结果及分析4.1 调试与测试4.1.1 调试调试过程主要是运行编制好的程序，然后遇

27、到错误后根据系统的提示，找到相关的问题所在。本系统调试过程中遇到的主要问题、原因和解决方法如下面介绍。Error C2065:coef:undeclared identifierCoef没有明确被定义回到程序中查找并改正，发现调用的变量没有在同一类中4.1.2 测试软件测试是软件生存期中的一个重要阶段，是软件质量保证的关键步骤从用户的角度来看，普遍希望通过软件测试暴露软件中隐藏的错误和缺陷，所以软件测试应该是“为了发现错误而执行程序的过程”。或者说，软件测试应该根据软件开发各阶段的规格说明和程序的内部结构而精心设计一批测试用例（即输入数据及其预期的输出结果），并利用这些测试用例去运行程序，以发

28、现程序错误或缺陷。过度测试则会浪费许多宝贵的资源。到测试后期，即使找到了错误，然而付出了过高的代价。测试数据过程如下：第一个多项式的项数：3第1项系数：2指数：9第2项系数：8指数：4第3项系数：6 指数：6第二个多项式的项数:2第1项系数：4指数：6第2项系数：4指数：1运行结果：第一个多项式为:2x9+8x4+6x6第二个多项式为:4x6+4x1多项式加法的运算结果:2x9+4x6+8x4+6x6+4x1多项式乘法的运算结果:8x15+40x32+24x12+24x7+32x54.1.3 运行界面图 4-1 运行界面4.2 结果分析经过一段时间的设计，我的程序大体完成，任务书中所要求实现多

29、项式的输入输出、多项式的加法、多项式的乘法都实现了，而但程序还存在一些缺点，例如，系数输入负数会加减号重复，无法输入字母计算，无法进行多项连续计算，以后还需进一步改进。总结数据结构体现的是解决问题的一种思想，怎样把这种思想体现出来，需要我们对每个方面的系统了解。并发现了许多自己的不足，平时没掌握的的知识在实践中暴露，经过不断的思考，查阅书籍和上网查资料及上机运行，解决了大部分的问题，还有一些小问题。但是，我相信在今后的学习中，一定能把它解决好。当今计算机应用在生活中可以说是无处不在。因此作为二十一世纪的大学生来说掌握程序开发技术是十分重要的，而C+语言又是最常见，功能最强大的一种高级语言，因此

30、做好C+语言版数据结构课程设计是十分必要的。我不仅巩固了数据结构程序设计的内容，掌握设计的基本方法，强化了上机动手能力，还进一步掌握了以下知识：数据类型，链表，结点，分支控制，循环控制，结构体及数组，指针，文件操作，编译预处理等；通过课程设计，掌握了程序的局部测试，调试方法，建立程序系统调试，测试的基本概念和思想，学会较大程序的系统测试和调试方法。当我选择这个多项式计算器系统时，首先系统分析主要思路和框架哦，与同学讨论，联系所学的知识。我知道书上和老师讲的有限，所以上网搜也是一种利用资源的表现。在编程中，特别是结构体，指针的部分，几乎是一片空白。不过经过几天的努力，大体把课本上的知识点看了一遍

31、，知识点也基本上掌握了，所以下一步就是开始正式的编程序了。当读懂了C+语言编程的基本过程和方法，经过一波三折，终于开始正式编程。 编译过程中，算法至关重要，多项式加法：系数相同时指数相加，不同时两项做加法；多项式乘法：指数相乘，系数相加，当然在设计过程中还要注意一些特殊值，如0,1等。通过这次课程设计，我感觉到要自己动手真正做出一个程序并不很容易,但只要用心去做，总会有收获,特别是当我遇到问题,问老师，问同学，想尽办法去解决,最后终于找到方法时,心里的那份喜悦之情真是难以形容.编写程序中遇到问题再所难免,应耐心探究其中的原因,从出现问题的地方起,并联系前后程序,仔细推敲,逐个排查.直到最终搞清

32、为止。在课程设计过程中，收获知识，提高能力的同时，我也学到了很多的人生哲理，懂得了怎么去制定计划，怎么去实现这个计划，并掌握了在执行的过程中怎样去克服心理上的不良情绪。因此在以后的生活和学习的过程中，我一定把课程设计的精神带到生活中，使生活变得更好。参考文献1 谭浩强. C语言程序设计(第三版)M. 清华大学出版社, 2007.2 姜敏芝,余健. C语言程序设计案例精编M. 清华大学出版社, 2008.3 李健学,余健. 数据结构课程设计案例精编M. 2007.4 唐国民,王国均. 数据结构(C语言版)M. 北京:清华大学出版社.5 王路明. C语言程序设计教程M. 北京:北京邮电大学出版社,

33、2005年5月.6 谭浩强. C+程序设计M. 北京:清华大学出版社.2004.7 范策. 算法与数据结构（C语言版)M. 北京:机械工业出版社，2004.8 詹春华,杨沙. C语言程序设计教程M. 科学出版社,2011年8月.9 韩利凯,李军,高寅. 数据结构M. 浙江大学出版社，2013年8月.附录/*程序功能:实现任意两个高次多项式的加法和乘法运算*/* 多项式加法和乘法 */#include<list>#include<iostream>#include<cassert>using namespace std; /定义多项式的项类 class ter

34、mpublic:int coef; /多项式系数 int exp; /多项式指数 /初始化项的系数和指数 term(int c=0,int e=0):coef(c),exp(e);/定义多项式类 class PolyArithprivate:list<term> m_poly_list_first; /存储第一个多项式 list<term> m_poly_list_second; /存储第二个多项式 list<term> m_poly_list_result; /用以存储运算结果/*多项式私有成员函数,用以乘法时的调用*/ list<term>

35、Poly_add(list<term>&poly_list_first,list<term>&poly_list_second) list<term> poly_list_result;/用以存储运算结果 list<term>:iterator iter_first = poly_list_first.begin(); list<term>:iterator iter_second = poly_list_second.begin(); /*该while循环针对两个链表迭代器都没有指到结尾的情形*/ while (it

36、er_first != poly_list_first.end() && iter_second != poly_list_second.end() term t_temp; term t_first = (term)*iter_first; term t_second = (term)*iter_second; if (t_first.exp>t_second.exp) poly_list_result.push_back(t_first); iter_first+; else if (t_second.exp>t_first.exp) poly_list_res

37、ult.push_back(t_second); iter_second+; else t_temp.coef = t_first.coef + t_second.coef; t_temp.exp = t_first.coef; poly_list_result.push_back(t_temp); iter_first+; iter_second+; /该for循环针对第一个多项式的迭代器没有指到结尾 /第二个指到结尾的情形 for (;iter_first != poly_list_first.end();iter_first+) poly_list_result.push_back(*i

38、ter_first); /该for循环针对第二个多项式的迭代器没有指到结尾 /第一个指到结尾的情形 for (; iter_second != poly_list_second.end(); iter_second+) poly_list_result.push_back(*iter_second); return poly_list_result; public: /输入函数,用以输入多项式 void Poly_input()int n;cout << "请输入第一个多项式的项数:" << endl;cin >> n;cout <

39、< "按降幂输入第一个多项式的每一项的系数和指数:"cout << endl;for (int i = 1; i <= n; i+)term t_temp;cout << "请输入第" << i << "项系数和指数:"cout << endl;cin >> t_temp.coef;cin >> t_temp.exp;m_poly_list_first.push_back(t_temp);n = 0;cout << "

40、请输入第二个多项式的项数:" << endl;cin >> n;cout << "按降幂输入第二个多项式的每一项的系数和指数:"cout << endl;for (int j = 1; j <= n; j+)term t_temp;cout << "请输入第" << j << "项系数和指数:"cout << endl;cin >> t_temp.coef;cin >> t_temp.exp;m_po

41、ly_list_second.push_back(t_temp);/输出函数,用以输出多项式 void Poly_output()list<term>:iterator iter = m_poly_list_first.begin(); /输出第一个多项式的每一项 cout<<"第一个多项式为:"for (;iter != m_poly_list_first.end();)term t_temp = *iter;cout << t_temp.coef << "x" << t_temp.exp;i

42、f (+iter != m_poly_list_first.end()cout << "+"cout << endl;list<term>:iterator iter1 = m_poly_list_second.begin(); /输出第二个多项式的每一项 cout<<"第二个多项式为:"for (;iter1 != m_poly_list_second.end();)term t_temp = *iter1;cout << t_temp.coef << "x"

43、<< t_temp.exp;if (+iter1 != m_poly_list_second.end()cout << "+"cout << endl;void Poly_output_result()list<term>:iterator iter = m_poly_list_result.begin(); /输出多项式结果 for (;iter != m_poly_list_result.end();)term t_temp = *iter;cout << t_temp.coef << "

44、x" << t_temp.exp;if (+iter != m_poly_list_result.end()cout << "+"cout << endl;/加法函数,其基本思想同上边的私有成员函数Poly_add()/此处不带参数,多项式运算对象为私有数据成员void Poly_add()list<term>:iterator iter_first = m_poly_list_first.begin();list<term>:iterator iter_second = m_poly_list_seco

45、nd.begin();while (iter_first != m_poly_list_first.end() && iter_second != m_poly_list_second.end()term t_temp;term t_first = (term)*iter_first;term t_second = (term)*iter_second;if(t_first.exp>t_second.exp)m_poly_list_result.push_back(t_first);iter_first+;else if(t_second.exp>t_first.exp)m_poly_list_result.push_back(t_second);iter_second+;elset_temp.coef = t_first.coef + t_second.coef;t_temp.exp = t_first.ex