一元多项式基本运算操作

数据结构 课程设计报告 课题名称： 一元多项式基本运算操作 专 业： 计算机科学与技术 班 级： 学 号： 20090230118 姓 名： 吴 卿 指导教师： 马春江、梅 琴 成 绩： 2011 年 06 月 29 日 目 录 1 前言 3 2 需求分析 5 3 概要设计（特殊功能） 6 4 详细设计 9 5 源代码及调试 24 6 特殊问题解决方法 24 7 使用说明及 测试结果 26 8 结论 31 9 总结与体会 34 10 参考文献 38 附录 . 致谢 . 老师意见 . 1 前言 数据结构课程设计是理解和掌握数据结构的重要环节，主要任务是实现各种数据组织中的数据逻辑结构，存储结 构以及有关操作的算法。目的是使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法。另一方面，通过团队合作、文档编制、主页设计等环节对学生进行全方位的训练，最终达到培养学生的数据抽象能力和软件设计的能力。通过全部过程 培养和锻炼学生的钻研能力、动手能力、分析问题和解决问题的实际能力 。 题简介 题目名称： 一元多项式基本运算操作 课设目的： 巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知 识写程序。 课设意义： （ 1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操 作 （ 2）能针对给定题目，选择相应的数据结构，分析并设计算法， 进而给出问题的正确求解过程并编写代码实现。 （ 3）为数据结构的后续课程，诸如算法分析与设计，编 译原理等打下坚实的基础 具体内容： （ 1）输入并分别建立多项式 (2)输入输出多项式，输出形式为整数序列 ,含有系数，底数，指数， 以及正负号，序列按指数降序排列。 (3)完成两个多项式的相加、相减， 相乘， 将结果输 出，并将结果存 入文本中。 自己创新： （ 1） （ 2）设计帮助菜单 特别细节： (1)当系数为 1时，不予显示系数 1 (2)当指数为 0时，不予显示 X0字符串 (3)当指数为 1时，不予显示指数 1 预期效果： （ 1） 实现手动输入 和文本输入两种方式 （ 2） 实现两个多项式的相加，相减，相乘的运算 （ 3） 实现单个多项式的求导运算 (4)对于输入有误问题，能实现判断和处理的功能 案及其论证 实验平台： 题原因 ;自己的编程能力有限，然而深知数据结构课程的重要性以及课设的重要意义，不能去复制他人的代码，只能通过自己独立地编写，只有这样，才能够有所提高。即使自己编写的功能很少，代码量也很少，但是只要是通过自己独立地的完成，那么自己就会在编程上有真正的有所提高，有所进步。而相比于其他课题，一元多项式的计算 这一题目，相对来说较为简单，思路也是较为清晰与明朗的，所以综上所述，选择了题目 1 编写语言： C + + 可行性分析： 对于多项式的加减乘的计算，可以使用结构体链表，类模板，其中结构体中有底数，指数和指针三个数据元素。对于加运算，使用循环，将指数相等的项，进行系数的相加减；对于减法运算是加法的另外的一种形式而已，只需将多项式 2 乘以（ 然后调用加法运算函数即可；而对于乘法运算，先将两个多项式做乘法运算，对于指数相等的项，进行系数加法运算。 时间安排： 2011 选题 2011 思考规划程序设计思路 2011 编程 2011 编程 2011 调试，程序细节优化 2011 ,验收程序，撰写报告，细节优化 2011 提交报告 2 需求分析 (1)本演示程序中，多项式的系数和指数可以是整型，也可以是浮点型，所以在实际的 程序设计师采用的是的类模板。输入多项式时，a）手动输入时，依次输入多项式的项数，然后依次输入各个项的系数和指数 b）若是文本读入，直接读出。而多项式的输出形式为数学表达式且按指数降序排列，对于指数为 0的项加以处理 . (2)演示程序以用户和计算机程序对话的方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入程序中相应的选择，相应的输入数据和运算结果就会依次显示在其后。 (3)程序命令包括： a）输入多项式 b）多项式显示 c）多项式加法 d）多项式减法 e）多项式乘法 f）对多项式求导 g）显示帮助菜单 h）退出程序 (4)使用者方面：任何人都可以运行本程序，只要点击 着相应的提示操作即可，不会出现什么大的问题，而对于实际使用中出现的问题，只需查看帮助菜单即可加以解决。 (5)测试数据： 多项式 1： f(x)=100*X50+88*X3020+2*X6+3 多项式 2： f(x)=50+50*X20+X106 3 概要设计 （特殊功能） (1)数据结构：多项式的数据结构可以使用线性表来实现，具体来讲就是链表结构 (2)节点结构： (3)项目 框图： 系数 指数 *针 功能界面 输入 多项式 多项式相加 多项式相减 多项式 相乘 多项式求导 显示多项式 显示帮助菜单 退出此程序 文本输入 手动输入 退出 返回功能界面 (4)类之间的关系示意图： 多项式的各种 说明： a） 在本次课设程序中，共建立了 2 各类，分别是 中 友元。 b） 公有属性是对于多项式的各种操作 ,而私有属性就是多项式的每一项的记录信息：系数，指数和 *针。 c） 对于多项式的各种操作包括：输入多项式 ，多项式显示，多项式加法 ，多项式减法，多项式乘法，对多项式求导，也就是项目L i s t N o d e 类 公有属性 构造函数和析构函数 私有属性 系数，指数， *元类 有属性 *有属性 即：对于多项式的各种操作 框图中功能界面下的所有操作。 设计顺序： a)定义 b)定义 c）编写主函数，测试运行，细节优化 4 详细 设计 （ 1）类模板的定义 ： /向前定义 /定义友元 ; /构造新结点 ; T /单项式系数 T /未知数指数 ; ; ; ; ; ; h); ; （ 2） 各个函数分析 （ a）建立多项式函数 创建多项式有手动输入和文本读入两种方式，在具体地创建多项式时，应该选择是采用哪一种方式加以创建，不论是采用何种方式，在具体的实现上是分别去调用 者是 数。 建立多项式的存储结构，每一个一元多项式的存储结构就是一个有序单链表。有序链表的基本操作定义与线性链表有两处不同，一个是结点的查找定位操作 所不同，二是结点的插入操作 （ b）显示多项式函数 示多项式链表。在输出项中使用了条件表达式，当系数项为正数时，在系数前输出一个“ +”号，否则输出一个空格，而负数的负号还照常输出，使得输出结果尽量与原多项式的表示形式类似。需要对系数为 +1， 指数为 0 的情况加以考虑 具体代码为： p; p = /显示头结点休息，需要说明的是：指数已经排序完成 if(p-1) /对于头结点的系数为 1 的处理 if(p- /对于头结点的系数为 处理 p=p!=p=p- /利用循环，显示头结点以后节点的信息 if(p-1) /使用 句对于系数的各种情况加以考虑输出 if(p-0) /对于指数为 0 情况的考虑 /对于治顺不为 0 情况的考虑 if(p-1) /系数为 1 情况输出的考虑， if(p-0) p- 0) if(p-0) p-0) /系数为 0 情况输出的考虑， if(p-0) if(p-0) if(p- /系数为 况输出的考虑， if(p-0) if(p-0) * ( p = q = = ，系数相加 p = q = q = p = /一般情况 p != & q != p- q- ; p- p- /指针前移 p = p- p-= q- ; p- q- p- p = p-q = q- ; q- q- q = q-/ / /多项式加未完成 p!= ; p- p- p = p-/ q != ; q- q- q = q-/ (d)/多项式减法 多 项式的减法只是加法的另外的一种形式而已，多项式 2 的各个系数乘以 后再做加法运算即可，在这里不予以详述 （ e） /多项式的乘法运算 多项式的乘法运算规则： 用第一个的多项式的每一项去乘以第二个多项式的各个项，将得到的所有项进行合并同类项，然后按照指数从高到底的顺序加以排序显示 根据上述运算规则，其编程思路具体如下 假设第一个多项式的首指针为 *p,第二个多项式的首指针为 *q 1)采用双重循环算法，首先用 *p 去乘以 *q,然后 *q+，指针后移，这样做就可以实现多项式 1 的第一项与多项式 2 的每一项相乘，直到*q=止操作将相乘的结果存入新创建的链表之中。 2)采用同样的方法，这时，将 *p 指针后移，重复 1）的操作。就会得到一个完整的链表结构，这个链表结构存放了所有的成绩的结构，这个链表是没有结果任何的处理的 3） 对链表的处理，合并同类项，对于系数为 0 的节点加以删除。 4） 采用冒泡排序显示 p, *q, * /用于判断头结点赋值与否 (p=p; p=p- q=q; q=q-= /给头结点赋值 p- q- p- q- ; p- q- p- q- / / /合并次方相同的项 p=p; p=p-q=p; q; q=q- q- /指向将要判断的结点 /点不能为空 = p- p-= q- /多项式按次方降序排列 p=p; p=p- p; q=p; q; q=q- /交换 结点 p- ; q- q-q- p-q- p- p- p- f）多项式求导运算 多项式的求导思路： 首先对于指数相同的情况加以处理，然后计算新系数和新指数，其中新系数 =旧系数 *指数；新指数 =旧指数 有一定的次序相关性）。 h) g)菜单 使用 句即可加以实现，但是亮点在功能菜单使用指针数组加以定义用于显示，有一点的好处。 =显示内容的代码 ；菜单界面在此次实验中编写的较好，看起来有耳目一新的感觉。 5 源代码及调试 见报告末页（附录） 6 特殊问题解决方法 多 项式乘法的编程部分：在此部分中主要是思路不清晰，在实际地编程处理中，出现了乘的的顺序不正确，比如说我将第一个多项式的第一项乘以第二个多项式的第二项，然后是第一个多项式的第二项乘以第二个多项式的第一项，着样看似正确但是实际上，不能够得到正确的结果，而且执行的效率很低，原因是乘法的顺序混乱，自己在编程上存在思维上的漏洞。仔细分析之后，调整乘法顺序，首先是用第一项的第一项乘以第二个多项式的各个项，将结果存入链表之中，接着是用第一个多项式的第二项乘以第二个多项式的各个项，也将结果存入链表之中，对于之后的项，依次类推 。正确的语句为： /双重循环实现多项式相乘 p=p; p=p- q=q; q=q- = /给头结点赋值 p- q- p- q- ; p- q- p- q- 最后将指数相同的项，系数进行相加减，若出现系数为 0 的情况，那么应该将该节点删除。（按指数从大到小的顺序加以排序显示） 文本读入部分：事实上，对于文本读入操作的编程操作，我一直存在着极大的困难，掌握的不熟悉，在这次编程时无法将结果读入。为了解决这个问题，首先我将大二上的 C+语言关于文件的知识复习了一遍，编写了 C+几个关于文件的操作；然后进行实际的编程操作，但是实际运行时出现了很多出错的提示信息，信心有一丝受挫，但是得到了刘彬，黄伟强同学的帮助，指出了在读入数据时，没有及时地申请空间去存放要读入的数据，而且对于没有将读入的数据存入链表之中。听了两位同学的讲解后，我又将书本重新看了一遍，最后我加入了这段代码： p = q = !) p = ; p- p-q- p; q = p; ; 运行得到正确的结果（在文本中存放的即是测试数据的系数和指数，并且按照一定顺序）。 7 使用说明及 测试结果 （ 1） 使用说明： 方法 1：打开文件中 击编辑，运行 ，即可 方法 2：打开 击 行即可 弹出窗口。 （ 2）测试结果 ： a)运行该程序后出现此 说明性窗口 b）按任意键进入主菜单 c）文件读入方式输入数据 （以下结果均是建立在此数据的基础上） d）输入数字 2，进行显示操作 e）输入数字 3，进行相加运算 f)输入数字 4，进行相减运算 g）输入数字 5，进行相乘运算 h）输入数字 6，进行求导运算 i）输入数字 7，显示帮助菜单 j）输入 78，检查出错功能 k）进行手工输入的界面与方法（项数 指数） l）输入数字 0，退出界面 说明：上述加，减，乘，求导结果，均以验证，正确无误。 (3)功 能详述 ： （ 4）应用价值： 可以实现两个多项式的相加，相减，相乘以及相乘的功能。 (5) 特别说明： 当在使用程序时，建议仔细阅读说明性文件，说明性文件，仅仅在程序运行中出现一次。若想重新查看说明性文件，需要关闭程序，然后重新运行方可。而对于帮助菜单，在显示主菜单后，只需输入数字 7即可查看帮助菜单。说明性文件和帮助菜单仅仅是文字，不会有任何实质性地操作。 8 结论 在此次课程设计中，对于题目 1，主要使用的是线性，链接数据结构。在两个数相加减运算中，依次加以比较，对于指数相同的项，只是将系数进行相加减，但需要 将相同项中的一项删去，而当产生系数为 0 的情况时，需要将对应的两项都加以删除，这两点中都使用到了删除操作语句。在多项式乘法运算中，每两项相乘的结果都必须存入新的节点中；在多项式的相加减时，对于系数不同的项，两项都必须加以保存，这两点都涉及到新建并插入节点的语句。按照题目的意思，结果需要按照指数的降序排序加以显示，用到了冒泡排序的算法。为了使程序具有通用性，在此次程序算法中使用了类模板的知识，使得对于浮点型，整型的系数，指数都可以加以处理。 仔细地阅读程序代码后，使用的数据结构的概念有：线性表，冒泡排 序，链接存储，类模板，友元；细节操作有：新建节点，删除节点，增加节点，插入节点，文件读出写入；程序结构方面：总体上是循环结构（），当输入值不为是便一直执行主菜单中的程序代码，在主菜单程序中使用的是选择结构，使用了语句加以实现；在各个语句内部使用的是顺序结构，如建立多项式代码段部分 1) /对于头结点的系数为 1的处理 if(p- /对于头结点的系数为 p=p!=p=p- /利用循环，显示头结点以后 节点的信息 if(p-1) /使用 if(p-0) /对于指数为 0情况的考虑 /对于治顺不为 0情况的考虑 if(p-1) /系数为 1情况输出的考虑， if(p-0) p- 0) if(p-0) p-0) /系数为 0情况输出的考虑， if(p-0) if(p-0) if(p- /系数为 if(p-0) if(p-0) 最终将这个问题加以解决。 通过此次课程设计，我深深地感受到了数据结构课程在具体的编程中的地位，从小的方面上讲，如果没有学习数据结构这门课程，我是不可能将多项式的基本运算操作的程序拿下的；而从大的方面上讲，没有数据结构的理论学习，就仅仅是学习了语言或者语言的学生或者是工作者，他是不能从事计算机专业的。不管是现在还是以后，我都要加强数据结构的学习，不仅仅是理论知识的学习，更重要地是落实到实际的编程操作中。只有 这样，自己的编程能力才可能有实质性的突破。 9 总结与体会 经过一个星期的课程设计， 一元多项式基本运算操作的程序终于完成了。在这短短的一周时间里，整天或是对着电脑，或是翻阅资料。在此期间我失落过，伤心过，自责过，当然，也曾一度热情高涨。失落是因为自己选择的课题毫无疑问是最简单的；伤心因为自己在这种地编程过程中，遇到困难时就想着放弃，似乎心中有一个声音对我说：“你不行的”；自责是因为自己确确实实地，在实际中编程量很少很少。然而 这次课程设计使我深深地体会到：（ 1） 只有做到细心，耐心，恒心才能做好事情（ 2）平时的 日积月累，就会有很大的收获。 这次的课程设计，加强了我的动手、思考和解决问题的能力， 加深了对数据结构的理解，提高综合运用本课程所学知识的能力。培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。而且 做课程设计同时也是对课本知识的巩固和加强，平时看课本时，有些问题就不是很能理解，做完课程设计，那些问题就迎刃而解了。而且还可以记住很多东西。 认识来源于实践，实践是认识的动力和最终目的，所以这个期 末测试之后的课程设计在、对我的实际的编程能力有非常大的提高。 这次的课程设计使我懂得了理论与实际相结合是很非常重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。 在整个设计过程中，构思是很花费时间的。调试时经常会遇到这样那样的错误，有的是因为粗心造成的语法错误。当然，很多也时用错了方法，总是实现不了。 同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固。 根据我在课程设计 中遇到得问题，我将在以后的学习过程中注意以下几点： 1、认真上好专业实验课，多在实践中锻炼自己。 2、写程序的过程中要考虑周到，严密。 3、在做设计的时候要有信心，有耐心，切勿浮躁。 4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。 5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。 每个实验通常都要花费很久的时间才能理清一个程序的思路，而且要不断的调试程序才能把程序调试正确，同时还要做到界面的输出也是需要美化的。这次课程设计终 于顺利完成了，在设计中遇到了很多专业知识问题，最后在老师的辛勤指导下，也完成了课程设计。 通过这次的课程设计，让我更加了解到数据结构的重要性。可以这样讲，没有数据结构，就没有程序软件。对我们而言，知识上的收获很重要，但精神上的丰收更加可喜。 让我知道了学无止境的道理。我们每一个人永远不能满足于现有的成就，人生就像在爬山，一座山峰的后面还有更高的山峰在等着你。挫折是一份财富，经历是一份拥有。这次课程设计必将成为我人生旅途上一个非常美好的回忆！同时在 做课程设计时要能够从多方面去考虑，去研究，用多种算法去实现要 求。此次课程设计，学到了很多课内学不到的东西，比如独立思考解决问题，出现差错的随机应变，这些都让我受益非浅，今后的制作应该能够更轻松，自己也都能够解决并高质量的完成项目。 10 参考文献 【 1】杨正宏 数据结构（ C/C+版） 北京：清华大学出版社， 2004 年 11 月 【 2】傅仕星 C+语言程序设计习题与实验指导 北京：清华大学出版社， 2000年 7 月 【 3】 王昆仑 数据结构与算法 中国：中国铁道出版社， 2007年 5月 【 4】 郑莉 C+语言程序设计（第三版） 北京：清华大学出版社 【 5】 刘振安 C+程序设计课程设计 中国：机械工业出版社 【 6】 吴乃陵 C+程序设计 北京：高等教育出版社 【 7】 范辉 + 北京：高等教育出版社 【 8】 李龙澍 C+程序设计实训教程 北京：清华大学出版社 【 9】 洪国胜 C+ 序设计轻松上手 北京：清华大学出版社 【 10】 宁正元 数据结构（ 南京：东南大学出版社， 2000年 6月第 1版 【 11】 严蔚敏 数据结构（ 北京：清华大学出版社， 1997年 4月第 1版。 【 12】 胡学钢 数据结构算法设计指导北京：清华大学出版社， 1999 年 第 1版 致 谢 在本次课程设计的设计研究和设计报告的撰写过程中，我还是遇到了相当多的困难的。但是在老师耐心的指导和同学的帮助之下，我终于还