一元多项式的计算课程设计报告

合肥学院计算机科学与技术系课程设计报告2008～2009学年第二学期课程程序设计语言Ⅱ课程设计课程设计名称多项式的计算学生姓名王建敏学号0804013029专业班级计算机科学与技术（3）班指导教师张贯虹汪彩梅2009年6月一、课程设计题目：多项式（单项链表的应用）二、分析与设计1．程序的基本功能（1）建立多项式（2）输出多项式（3）删除多项式以释放空间（4）删除多项式中的某一项（5）将多项式合并同类项（6）拷贝多项式（7）将多项式按指数升序排列（8）判断两多项式是否相等（9）两个多项式相加，建立并输出和多项式（10）两个多项式相减，建立并输出差多项式（11）两个多项式相乘，建立并输出积多项式（12）两个多项式相除，建立并输出商多项式2．算法设计本程序主要应用了链表，结构体和类模板。用结构体来定义多项式的结点（即每一项），它包含三个域，分别存放该项的系数、指数以及指向下一项结点的指针；用链表来存储多项式，为了节省空间，只存储多项式中系数非0的项，用多项式链表类来实现设定的程序的基本功能。涉及的主要算法有：（1）使用尾插法创建多项式，即从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表尾上,直到读入结束标志（某一项的系数为零）为止。（2）输出一个非空的多项式链表，不要输出最后一项，即输入系数为零的结束项，用if……else语句判断。（3）删除整个多项式是一项一项的删，使用链表删除其结点的方法，使用free（）函数释放存储空间。在删除非空的多项式的某一项时，定义k来找到要删除的那一项的位置，再使用delete将其删除。（4）在对多项式合并同类项时，主要有两点，一是看两项指数是否相等，若相等则合并成一项，二是看两项系数和是否为零，若为零则去掉这两项。在对多项式排序时，先合并同类项，再按指数值从小到大排序。（5）在拷贝多项式时使用重载函数，将系数和指数都拷贝给新的多项式。（6）在判断两多项式是否相等时，先分别对两多项式进行排序，再从头项开始，一项一项的比较其系数和指数，一旦有一个不相等就结束，即这两多项式不相等，否则相等。（7）计算多项式加减，其算法思想是相同的。以多项式加法为例，先对两多项式排序，再将两多项式的每一项逐项相加，在相加之前，先比较两项的指数是否相等，若相等则将系数相加，再判断系数是否为零，若为零则删除，否则存储在和多项式中。若两项指数不相等，当多项式pa指数大于多项式pb指数时，则将pa结点副本插入到和多项式PolyC尾部；当pa指数小于pb指数时，则将pb结点副本插入到和多项式PolyC尾部，最后插入剩余结点。（8）计算多项式乘法时，先判断两多项式是否为空，若为空，则返回乘多项式，否则要先对两多项式进行合并排序，先将两多项式的第一项相乘，即系数相乘，指数相加，其值作为乘多项式的第一结点，其后使用双重循环将一多项式的每一项与另一多项式的每一项分别相乘，结果存到乘多项式中。（9）计算多项式除法时，同样要判断两多项式是否为空，只要有一为空，则直接返回空，否则将一多项式整个除以另一多项式，系数相除，指数相减，结果存到商多项式中。3．系统总框图4．定义的主要函数及说明CreatePoly()-------创建多项式链表OutputPoly()-------输出多项式DestroyPoly()------完全删除多项式DelPoly()-----------删除多项式中的某一项EqualPoly()---------判断两多项式是否相等MergePoly()--------将多项式和并同类项SortPoly()-----------将多项式按升序排列PolyAdd()-----------多项式和的计算PolySub()----------多项式差的计算PolyMutiply()-------多项式积的计算PolyDivide()---------多项式商的计算三、系统实施1．源程序代码（见后附录）2．上机调试过程1）调试中遇到的主要问题问题一：开始用类来定义多项式链表的结点，即typedefstructPolyNode{}PolyNode,*PolyList，并将三个数据域设为私有成员，系统报错。问题二：将多项式类的析构函数体写为：~Polynomial(){deletehead;deleterear;deleteLength;}，用户菜单结构体结点各函数退出多项式链表类模板主函数系统报错。问题三：在记录多项式项数Length时，在创建多项式的函数体内，写成：Length=n-1，编译通过，可运行结果不正确，多了一项。问题四：在多项式类中所定义的两个多项式的加减乘除及判断是否相等这些功能函数本来用的是友元函数（也应该用友元函数），例对多项式的加法用的是函数friendPolyListPolyAdd(PolyList&PolyA,PolyList&PolyB)，系统报错。问题五：在程序运行过程中出现错误errorC2955:'Polynomial':useofclasstemplaterequirestemplateargumentlist。2）解决问题解决题一：根据错误提示发现多项式类成员函数的实现不能访问结点类的私有成员，在结点类里添加一个友元类friendclassPolynomial，运行后还是有错误，经过反复修改，根据提示意识到自己不能解决typedef在类模板中的正确使用，导致反复不能运行，最后将多项式链表的结点用结构体来定义，即用typedefstructPolyNode{}PolyNode,*PolyList，运行最终正确。解决题二：根据错误提示将析构函数改为：~Polynomial(){deletehead;deleterear;}，运行对。解决题三：根据运行的错误结果将错误代码改为：Length=n-2，运行正确。解决题四：据错误提示应该是PolyA本是指针成员，在前加上地址运算符&会出错，且PolyList非类名，故系统报错。将&全部去掉，运行仍错误，反复对其修改，都不能运行，最后将友元函数改为普通函数，如上面的加法函数改为PolyListPolyAdd(PolyListPolyA,PolyListPolyB)，运行正确（虽然不该在多项式类中定义这样的函数，因为这些功能并非多项式的基本行为，但毕竟个人能力有限，只希望以后掌握更多的知识来进行弥补）。解决题五：根据错误指示位置发现在使用类模板的地方出现了问题，误将voidPolynomialT::MergePoly(PolyListPoly)写为voidPolynomial::MergePoly(PolyListPoly)，了解到在实现模板类的成员函数时，要加上T来限制。3）算法改进设想自己的课程设计还不够完善，有些功能未设计到，有很多需要改进的地方，现列举以下几个改进设想：设想一：希望可以对某一个多项式进行插入一项或插入另一个多项式。设想二：用类来定义多项式链表的结点，添加构造函数、拷贝构造函数和析构函数等基本类函数，使用友元类访问结点的私有成员。设想三：对两个多项式间的加减乘除及判断是否相等使用友元函数来实现，因为这些功能并非多项式的行为。设想四：希望可以用磁盘文件输入数据，并完整的清晰的将运行结果进行保存。设想五：希望自己做的系统界面更加美观、实用，令读者运行快乐。设想六：可以用重载函数来实现多项式间的加减乘除运算，重载运算符“+、—、×、\”，但也必须使用友元函数来写。4）经验与体会虽然课程设计做的不够完善，但在设计的过程中受益匪浅，通过查资料等学到了很多以前不知道或不太会应用的知识，主要包括以下几点：a．对typedef的应用有了新的认识。如typedefint*bom将int另命名为*bom，则用bom定义的类型为int指针类型的指针，例如bomn，则n为int型的指针。typedef有利于程序的通用和移植。b．最主要的是对单向链表的使用有了更深刻的了解和掌握，因为多项式的计算要求用单向链表来实现，所以在做课程设计之前通过网上找资料，查参考书及问辅导老师等对单向链表的使用比以前掌握的更加到位，并且能够灵活运用，通篇几乎用的都是单向链表，这是受益的一大重点。c．更正了对运算符delete的使用，以前一直以为delete可以删除一切基本数据类型的数据，以释放它们的空间，可运行报错。通过查看课本发现delete是用来删除由new建立的对象，释放指针所指向的内存空间，格式为：delete指针名，这可以与运算符new一起记忆，new的功能是动态分配内存。d．对重载运算符的使用也比以前更加深入，本程序是使用了重载赋值运算符“=”，来实现对多项式的拷贝，深记重载函数的一般语法形式为：函数类型operator运算符（形参表）{函数体}。e．由于课程设计中要求使用模板，为了正确使用模板，学习了很多关于模板使用的方法及注意事项，促使我对类模板的使用有了更深一步的理解，牢记在类模板以外定义成员函数，需采用以下的形式：（模板参数表用classT或typenameT，常用前者。）template模板参数表类型名类名T：：函数名（参数表）5）不足之处本程序最大的不足便在于计算多项式的加减乘除和判断两多项式是否相等未使用友元函数，虽然程序仍能正确运行，但从本质上讲，不用友元函数是不正确的，因为这些功能并非单个多项式所具有的行为。本程序另一不足之处在于对磁盘文件的处理不规范，它只能存储程序运行结果所输出的多项式，而不能存储多项式前的说明文字，如对某一多项式进行合并同类项，屏幕上显示的是“合并后的PolyA为：6x^3+3.5x^7”，但文件里保存的只是“6x^3+3.5x^7”，让旁观者不清楚这是什么函数功能运行的结果。这些不足主要是因为自己对知识的掌握不是很牢固，不能正确灵活运用所学知识。针对这些不足，我以后要认真学习这些不足的知识，深刻理解并掌握它们。3．测试结果及其分析运行说明：运行程序后，先出现以下主菜单：（说明：界面缩小了）上面有提示语句，分别按照这些提示语句进行选择，就会出现相应的菜单。3）进入帮助菜单4）创建PolyA多项式5）先输出PolyA并记录项数，再删除PolyA4）对刚未删除的PolyA修改，进入修改菜单5）拷贝PolyA，再创建一个PolyB多项式并输出6）进入多项式运算菜单（加减乘除及判断两多项式是否相等）7）当输入错误时系统给出错误提示8）系统结束时界面如下四、参考书目【1】杨正宏《数据结构（C/C++版）》北京：清华大学出版社，2004年11月【2】王睿伯《面向对象程序设计》北京：科学出版社，2003年7月【3】傅仕星《C++语言程序设计习题与实验指导》北京：清华大学出版社，2000年7月【4】张基温《c++程序开发例题与习题》北京：清华大学出版社，2001年9月【5】王昆仑《数据结构与算法》中国：中国铁道出版社，2007年5月【6】郑莉《C++语言程序设计（第三版）》北京：清华大学出版社【7】郑莉《C++语言程序设计（第三版）学生用书》北京：清华大学出版社【8】刘振安《C++程序设计课程设计》中国：机械工业出版社【9】吴乃陵《C++程序设计》北京：高等教育出版社【10】李春葆《C++程序设计学习与上机实验指导》北京：清华大学出版社【11】范辉《VisualC++6.0程序设计简明教程》北京：高等教育出版社【12】李龙澍《C++程序设计实训教程》北京：清华大学出版社【13】洪国胜《C++Builder程序设计轻松上手》北京：清华大学出版社【14】宁正元《数据结构（c语言）》南京：东南大学出版社，2000年6月第1版【15】严蔚敏《数据结构（c语言版）》北京：清华大学出版社，1997年4月第1版。【16】胡学钢《数据结构算法设计指导》北京：清华大学出版社，1999年第1版。