数据结构课程设计第PAGE\*MERGEFORMAT13页共NUMPAGES\*MERGEFORMAT13页信息工程学院软件工程系课程设计报告2012~2013学年第一学期课程数据结构课程设计名称多项式的运算学生姓名学号专业班级课程设计题目要求：一元多项式计算器的基本功能定位(1)建立多项式(2)输出多项式(3)两个多项式相加，建立并输出和多项式(4)两个多项式相减，建立并输出差多项式(5)两个多项式相乘，建立并输出积多项式(6)两个多项式相除，建立并输出商和余数多项式实现提示：可选择带头结点的单链表存储多项式，头结点可存放多项式的参数，如项数等分析与设计1.程序的基本功能（1）建立多项式（2）输出多项式（3）删除多项式以释放空间（4）将多项式按指数升序排列（5）两个多项式相加，建立并输出和多项式（6）两个多项式相减，建立并输出差多项式（7）两个多项式相乘，建立并输出积多项式（8）两个多项式相除，建立并输出商和余数多项式2．算法设计本程序主要应用了链表，结构体。用结构体来定义多项式的结点（即每一项），它包含三个域，分别存放该项的系数、指数以及指向下一项结点的指针；用链表来存储多项式，为了节省空间，只存储多项式中系数非0的项，用多项式链表类来实现设定的程序的基本功能。涉及的主要算法有：（1）使用尾插法创建多项式，即从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表尾上,直到读入结束标志（某一项的系数为零）为止。（2）输出一个非空的多项式链表，不要输出最后一项，即输入系数为零的结束项，用if……else语句判断。（3）删除整个多项式是一项一项的删，使用链表删除其结点的方法，使用free（）函数释放存储空间。在删除非空的多项式的某一项时，定义k来找到要删除的那一项的位置，再使用delete将其删除。（4）计算多项式加减，其算法思想是相同的。以多项式加法为例，先对两多项式排序，再将两多项式的每一项逐项相加，在相加之前，先比较两项的指数是否相等，若相等则将系数相加，再判断系数是否为零，若为零则删除，否则存储在和多项式中。若两项指数不相等，当多项式pa指数大于多项式pb指数时，则将pa结点副本插入到和多项式PolyC尾部；当pa指数小于pb指数时，则将pb结点副本插入到和多项式PolyC尾部，最后插入剩余结点。（5）计算多项式乘法时，先判断两多项式是否为空，若为空，则返回乘多项式，否则要先对两多项式进行合并排序，先将两多项式的第一项相乘，即系数相乘，指数相加，其值作为乘多项式的第一结点，其后使用双重循环将一多项式的每一项与另一多项式的每一项分别相乘，结果存到乘多项式中。（6）计算多项式除法时，同样要判断两多项式是否为空，只要有一为空，则直接返回空，否则将一多项式整个除以另一多项式，系数相除，指数相减，结果存到商多项式中。3.系统总框图4.定义的主要函数及说明voidInsert(Polynp,Polynh)------插入多项式结点PolynCreatePolyn(Polynhead,intm)------建立多项式voidDestroyPolyn(Polynp)------销毁多项式voidPrintPolyn(PolynP)------输出多项式PolynAddPolyn(Polynpa,Polynpb)------求解并建立多项式a+b，返回其头指针PolynSubtractPolyn(Polynpa,Polynpb)------求解并建立多项式a+b，返回其头指针floatValuePolyn(Polynhead,floatx)------输入x值，计算并返回多项式的值PolynDerivative(Polynhead)------求解并建立a的导函数多项式，并返回其头指针PolynMultiplyPolyn(Polynpa,Polynpb)------求解并建立多项式a*b，返回其头指针voidDevicePolyn(Polynpa,Polynpb)------求解并建立多项式a/b，返回其头指针5.各主要函数的流程图voidInsert(Polynp,Polynh)//多项式的插入开始p的系数是否为0Y释放p结点While循环查找插入的位置根据具体情况插入结点结束PolynAddPolyn(Polynpa,Polynpb)//多项式的加法PolynSubtractPolyn(Polynpa,Polynpb)//多项式的减