二元多项式加减运算问题-数据结构与算法课程设计报告

1、合肥学院计算机科学与技术系课程设计报告20092010 学年第 2 学期课程数据结构与算法课程设计名称二元多项式加减运算问题学生姓名陈康荫学号0804012007专业班级08 计科系计本 (2)班指导教师王昆仑2010 年 5 月题目：二元多项式加减运算问题设计程序以实现降幂建立、输出、加、减任意两个二元多项式。要求：（1）所设计的数据结构应尽可能节省存储空间。（2）程序的运行时间应尽可能少。1、问题分析和任务定义此程序需要完成以下的要求：按照指数降序排列建立多项式并且输出；能够完成两个多项式的相加、相减运算，并将结果输出。在这个程序中，我采用链表的数据结构来实现二元多项式的建立和表示。 然后

2、进行降序的排列， 完成二元多项式的两个基本运算： 加法和减法。最后同样按照降序，对得到的结果多项式进行排列，测试用例设置为二组，分别为：第一组为系数不同而x 和 y 的指数各自相同；第二组为系数和指数各不相同。举一个例子如下：35x4y38x737x2y7第一组数据：6xyy第二组数据：2x7x35x24x42y2y7y5y降幂排序后的结果：7343276x y3第一组数据：8x y5x y7x y第二组数据：5x24x42x7x37y5y2y2y8x35x24x45x39x7x3两组多项式相加结果：7y7y5y4y2y2y6x y8x35x24x45x35x7x3两组多项式相减结果：7y7y

3、5y4y2y2y6x y现在，我要通过程序来实现以上的过程将其在计算机上完成运算最终成功得到这样的结果。2、数据结构的选择和概要设计为了解决这个问题， 我选择的数据结构为链表，原因是：链表中的结点可以动态生成的，用链表结构可以灵活地添加或删除结点。另外，用链表结构来存储这样的数据可以大大地减少空间复杂度， 因此本题在设计算法时使用的就是链表地结构， 存放多项式的链表结点结构如下图如示：系数coefX 的指数 xexpY 的指数图 1.存放多项式的链表结点结构yexp指针nextstruct LinkListint coef;/系数int xexp;/x指数int yexp;/y指数LinkLi

4、st *next;/指针;/定义结点这是链表的最基本的构成单元结点。在输入多项式时， 考虑到输入多项式的形式，本程序是分别输入各个多项式中每一个项的系数， x 指数 ,y 指数，然后在输出时再把多项式的各个关键字组合在一起。建立链表的时候， 通过定义MAX 的值就可以一次性地告诉计算机，本次运行程序需要开辟空间的大小。 同时可以改变相应的MAX 大小，来改变其空间的大小。由于是2 个多项式相加相减的运算， 所以设定MAX1 和 MAX2 分别来定义。 然而， 二元多项式的加减在运算中难免会遇到两种极端情况，即：没有一个是同类项或者全是同类项。如果遇到“没有一个是同类项”的情况，那么，运算后的这

5、个链表的长度就是原来的2 个多项式之和，所以直接将运算后得到的链表长度开辟的空间定义为MAX1+MAX2，已免出现溢出错误。在这一点上，链表的插入结点的操作简单的优势就体现出来了，然而对于减法的情况，同理， 合并同类项的工作对于多项式来说也就是结点的删除工作。本程序的几个重要的问题按顺序是：1、建立链表2、多项式的输入形式、显示以及显示的形式3、如何按降序排序4、多项式加法函数5、多项式减法函数6、选择菜单。以上这六个问题需要最终分别用几个函数来分别实现。 另外加上一个主函数。 这几个函数分别为：void CreateList(LinkList *&L,int a,int b,int

6、c, int n) /void sort(LinkList *&L) /降序排序void ListAdd(LinkList *&L1,LinkList *&L2,LinkList *&L3) /void ListSubtract(LinkList *&L1,LinkList *&L2,LinkList *&L3)void DisplayList(LinkList *&L) /显示多项式int menu_select()/菜单创建链表两个多项式相加这些函数连同主函数在一起构成整个程序，其中，主函数依次调用建表函数、排序函数、显示函数

7、、 菜单函数， 菜单函数提示用户选择来调用加法函数和减法函数， 加法函数和减法函数中都分别依次调用建表函数、 排序函数和显示函数， 另外菜单函数还自己调用自己， 即递归的调用。3、详细设计和编码本程序的有6 个模块，分别为1、建表 2 、排序 3 、加法 4 、减法 5 、显示 6 、选择。各模块的详细分析设计如下：1、建表多项式的存储的数据结构采用的是链表的方式：系数cofe X 的指数 xexpY 的指数 yexp 指针 next存放多项式的链表结点结构对于输入的2 个多项式， 都采用链表的存储方式，运算后的多项式也一样地采用这种方式来存储。在建立链表结构时，根据题目的情况，我选择了头插法

8、来建立链表，算法为：首先建立一个只含有头结点的空单链表，然后读入数据， 生成新结点， 并将新结点总是插入到头结点之后，直到读满之前设置的链表的长度。系数，x 指数， y 指数分别用a,x,y三个数组的形式进行读入。头插法建单链表的算法时间复杂度为O(n) 。创建链表函数为：void CreateList(LinkList *&L,int a,int x,int y, int n)/定义三个数组用于存储系数、 x 指数、 y 指数LinkList *s;int i;L=(LinkList *)malloc(sizeof(LinkList);/开辟空间存放链表L-next=NULL;for

9、(i=0;icoef=ai;s-xexp=xi;s-yexp=yi;s-next=L-next;/头插法建链表的时间复杂度是O(n)L-next=s;2、排序降序排序函数的主要算法思想： 先检查 p 结点是不是最后一个结点， 如果不是， 就向后继续查找，直到找到最后一个结点，把这个结点中的指数和前一个结点中的指数进行比较，如果这个指数比前一个结点的指数大， 说明这两个结点按升序排列， 需要改变位置， 于是执行指针的变换操作，使得两个结点改成降序排列，以此达到排序的目的。以下是排序函数：降序排序void sort(LinkList *&L)LinkList *p=L-next,*q,*r

10、;if(p!=NULL)r=p-next;p-next=NULL;p=r;while(p!=NULL)r=p-next;q=L;while(q-next!=NULL&(q-next-xexpp-xexp)|(q-next-xexp=p-xexp&q-next-yexpp-yexp)q=q-next;p-next=q-next;q-next=p;p=r;3、加法两个多项式相加的算法是：两个多项式中，具有相同指数项的，也就是同类项的对应系数相加， 若相加和不为零， 则合并成加和多项式中的一项，所有指数不相同的项均直接移动至加和多项式中的后面，至于排列，则依据排序函数进行降序排序。对

11、于两个多项式链表A 和 B，实现多项式相加时，加和多项式中的结点无需另外生成，可以看成是将多项式B 加到多项式A 中，最后的加和多项式即是新的多项式A，设 p、 q 分别指向多项式A、B 的首元素结点，则比较结点*p 、*q 的指数项，可以进行以下操作来完成多项式的加法运算：若 p-expexp ，则 *p 结点应是加和多项式的一项，并将指针p 后移。若 p-expq-exp ，则 *q 结点应是加和多项式的一项，将*q 结点插入到多项式链表 A 的 *p 结点之前，并令指针q 在多项式链表B 上后移。若 p-exp=q-exp ，则将两个结点的系数相加，若和不为零， 则修改 *p 结点的系数

12、域，释放指针q 所指向的结点空间；若和为零，则指针p、 q 分别在各自的链表上后移，同时释放原先两个指针所指向的结点空间。重复上述步骤，若q=NULL，则链表 A 即为加和多项式链表；若p=NULL，则将链表B 中指针 q 所指向的余下的链表全部插入到链表A 的表尾，形成加和多项式链表A.由于这个题目是二元多项式，要考虑 x 和 y 两个元， 故而以上四个步骤在实际写程序的时候是按照xexp 和 yexp 两个变量而不是只有一个exp，写成 exp 是为了说明的时候看得清楚一点。加法算法的时间复杂度取决于链表A 和 B 的项数，若A 有 n 项 ,B 有 m 项，那么上述算法的时间复杂度为O(

13、n+m).以下是两个多项式相加函数：两个多项式相加void ListAdd(LinkList *&L1,LinkList *&L2,LinkList *&L3)int coefMAX1+MAX2,xexpMAX1+MAX2,yexpMAX1+MAX2,i=0; /MAX1+MAX2的原因是防止两个多项式中没有任何一个相同LinkList *p=L1-next,*q=L2-next;while(p!=NULL&q!=NULL)if(p-xexpxexp) coefi=p-coef;xexpi=p-xexp;yexpi=p-yexp;i+;p=p-next;else

14、 if(p-xexpq-xexp)coefi=q-coef; xexpi=q-xexp; yexpi=q-yexp; i+; q=q-next;else if(p-xexp=q-xexp&p-yexpyexp) coefi=p-coef;xexpi=p-xexp;yexpi=p-yexp;i+;p=p-next;else if(p-xexp=q-xexp&p-yexpq-yexp)coefi=q-coef; xexpi=q-xexp;yexpi=q-yexp;i+;q=q-next;else if(p-xexp=q-xexp&p-yexp=q-yexp)coefi=p-

15、coef+q-coef;xexpi=p-xexp;yexpi=p-yexp;i+;p=p-next;q=q-next;while(p!=NULL&q=NULL)coefi=p-coef;xexpi=p-xexp;yexpi=p-yexp;i+;p=p-next;while(q!=NULL&p=NULL)coefi=q-coef;xexpi=q-xexp;yexpi=q-yexp;i+;q=q-next;CreateList(L3,coef,xexp,yexp,i);sort(L3);4、减法两个多项式的相减算法和加法函数很类似，主要思想是先将链表 B 取负，然后执行和加法算法一

16、样的步骤，最后交给排序函数做一次降序排序。5、显示显示的格式是 :a1*xb1yc1+a2*xb2yc2+a3*xb3yc3+a4*xb4yc4根据依次读入的数据进行显示6、选择菜单主要提供用户选择（包含退出功能），两个多项式的和以及两个多项式的差的运算。4、上机调试过程1、语法错误及修改由于本算法使用了链表的方式建立二元多项式，所以程序的空间是动态的生成的，而且链表可以灵活地添加或删除结点， 所以使得程序得到简化。 出现的语法问题主要在于子函数和变量的定义，降序排序，关键字和函数名称的书写，以及一些库函数的规范使用，这些问题均可以根据编译器的警告提示，对应的将其解决。2、逻辑问题及其调整编写

17、程序的过程中遇到许多问题，首先在选择数据结构的时候选择了链表，但是链表的排序比较困难， 特别是在多关键字的情况下，在一种关键字确定了顺序以后，在第一关键字相同的时候， 按某种顺序对第二关键字进行排序。 在此程序中共涉及到 3 个量数， 即：系数， x 的指数和 y 的指数，而关键字排是按 x 的指数和 y 的指数来看，由于要求是降幂排序且含有 2 个关键字， 所以我先选择 x 的指数作为第一关键字， 先按 x 的降序来排序， 当 x 的指数相同时，再以 y 为关键字，按照 y 的指数大小来进行降序排列。在加法函数的编写过程中也遇到了大量的问题，由于要同时比较多关键字，而且设计中涉及了数组和链表

18、的综合运用， 导致反复修改了很长的时间才完成一个加法的设计， 现在仍然有一个问题存在， 若以 0 为系数的项是首项则显示含有此项， 但是运算后则自动消除此项，这样是正确的。但是当其不是首项的时候，加法函数在显示的时候有0 为系数的项时，0 前边不显示符号，当然，这样也可以理解成当系数为0 时，忽略这一项。3、时间，空间性能分析链表的建立使用的是头插法建表，时间复杂度为O(n) ，本程序采用链表存储。单链表的每个结点都有一个指针空间，相当于总共增加了n 个整型变量，在空间复杂度上为O(n) 。加法函数的时间复杂度取决于多项式A 和 B 的项数， 若 A 有 n 项而 B 有 m 项，那么本算法的

19、时间复杂度为O(n+m), 空间复杂度为O(n+m), 减法函数由于与加法函数结构相同，只是符号改换，故而时间空间复杂度同加法函数，分别为时间O(n+m), 空间 O(n+m)。在设计减法函数的时候由于考虑不够充分就直接编写程序，走了很多弯路，不得不停下来仔细研究算法，后来发现由于前边的加法函数完全适用于减法，只不过是将二元多项式B的所有项取负再用加法函数即可，可见算法的重要性不低于程序本身。4、经验和体会在调试过程中，发生了许多小细节上的问题，提醒了我在以后编程的时候要注意细节，即使是一个括号的遗漏或者一个字符的误写都会造成大量的错误，浪费许多时间去寻找与修改，总结的教训就是写程序的时候要仔

20、细。还有一个体会就是格式和注释，由于平时不注意格式和注释，导致有的时候检查和调试的时候很不方便，有的时候甚至刚刚完成一部分的编辑，结果一不注意， 忘记了这一部分程序的功能， 修改的时候也有不小心误删的情况出现。如果注意格式风格和养成随手加注释的习惯， 就能减少这些不必要的反复和波折。还有就是在修改的时候，要注意修改前后的不同点在哪里，改后调试结果要在原有的基础上更加精确。5、测试结果及其分析。按照前述提供的测试用例输入程序进行结果测试。测试结果如下：这一组数据设置为系数不同而 x 和 y 的指数各自相同， 结果是程序合并同类项， 两个多项式的 x 和 y 的指数相同的项的系数相加成为新的多项式

21、，均与试验结果中的数据相同（注：程序的运行结果截图在下一页）由此，第一组指数相同的2 个多项式成功完成运算。下面，我来用第二组数据来进行测试。这一组数据设置为系数相同而x 和 y 的指数各自不相同，结果是程序找不到同类项，按两个多项式的x 和 y 的指数排列相加成为新的多项式。由于没有同类项，所以只好依次相加所有的项。（注：程序的运行结果截图在下一页）由此，第二组指数不同的2 个多项式成功完成运算。6、用户使用说明用户使用之前需要设置 MAX 的值，如果不需要改变原始的设置，直接打开“二元多项式计算 .exe ”，界面欢迎使用二元多项式加减计算器，一次性输入第一个多项式所有的系数，按 ente

22、r 输入，再一次性输入 x 的指数和 y 的指数，接着是重复前一系列步骤输入第二个多项式的所有信息，按 enter 输入。程序自动降幂排列第一个和第二个多项式，并分别为用户表示出来，然后程序提示菜单为：1、两个多项式的和2 、两个多项式的差0 、退出用户根据需要键入选项，程序将为用户分别显示这两个多项式的1、两个多项式的和或2、两个多项式的差。用户如有需要记录，可以自行记录结果。最后提醒：本程序不提供文件保存的功能。7、参考文献1王昆仑李红数据结构与算法中国铁道出版社，2007 年 6 月第 1 版2潭浩强 C 程序设计清华大学出版社， 2005 年 7 月第 3 版3潭浩强 C 程序设计题解

23、与上机指导清华大学出版社，2005 年 7 月第 3 版4郑莉 董渊张瑞丰C+语言程序设计清华大学出版社，2003 年 12 月第 3 版5严蔚敏吴伟民数据结构清华大学出版社，1997 年 4 月第 1 版6严蔚敏吴伟民米宁 数据结构题集清华大学出版社，1987 年 4 月第 1 版7徐孝凯数据结构实用教程清华大学出版社2001 年 10 月第 1 版8、附录（源程序带注释）#include #include #define MAX1 4#define MAX2 4/ 定义结点structLinkList intcoef; / int xexp;/x int yexp; /yLinkList*

24、next;/ ;系数指数指数指针/ 创建链表void CreateList(LinkList *&L,int a,int x,int y, int n)/定义三个数组用于存储系数、x 指数、 y 指数LinkList *s;int i;L=(LinkList *)malloc(sizeof(LinkList);/ 开辟空间存放链表 L-next=NULL;for(i=0;icoef=ai;s-xexp=xi;s-yexp=yi;s-next=L-next;L-next=s;降序排序void sort(LinkList *&L)LinkList *p=L-next,*q,*r;i

25、f(p!=NULL)r=p-next;p-next=NULL;p=r;while(p!=NULL)r=p-next;q=L;while(q-next!=NULL&(q-next-xexpp-xexp)|(q-next-xexp=p-xexp&q-next-yexpp-yexp)q=q-next;p-next=q-next;q-next=p;p=r;两个多项式相加void ListAdd(LinkList *&L1,LinkList *&L2,LinkList *&L3)int coefMAX1+MAX2,xexpMAX1+MAX2,yexpMAX1+MA

26、X2,i=0;LinkList *p=L1-next,*q=L2-next;while(p!=NULL&q!=NULL)if(p-xexpxexp)coefi=p-coef;xexpi=p-xexp;yexpi=p-yexp;i+;p=p-next;else if(p-xexpq-xexp)coefi=q-coef;xexpi=q-xexp;yexpi=q-yexp;i+;q=q-next;else if(p-xexp=q-xexp&p-yexpyexp)coefi=p-coef;xexpi=p-xexp;yexpi=p-yexp;i+;p=p-next;else if(p-x

27、exp=q-xexp&p-yexpq-yexp)coefi=q-coef;xexpi=q-xexp;yexpi=q-yexp;i+;q=q-next;else if(p-xexp=q-xexp&p-yexp=q-yexp)coefi=p-coef+q-coef;xexpi=p-xexp;yexpi=p-yexp;i+;p=p-next;q=q-next;while(p!=NULL&q=NULL)coefi=p-coef;xexpi=p-xexp;yexpi=p-yexp;i+;p=p-next;while(q!=NULL&p=NULL)coefi=q-coef;

28、xexpi=q-xexp;yexpi=q-yexp;i+;q=q-next;CreateList(L3,coef,xexp,yexp,i);sort(L3);两个多项式相减void ListSubtract(LinkList *&L1,LinkList *&L2,LinkList *&L3)int coefMAX1+MAX2,xexpMAX1+MAX2,yexpMAX1+MAX2,i=0;LinkList *p=L1-next,*q=L2-next;while(p!=NULL&q!=NULL)if(p-xexpxexp)coefi=p-coef;xexpi=p-

29、xexp;yexpi=p-yexp;i+;p=p-next;else if(p-xexpq-xexp)coefi=-q-coef;xexpi=q-xexp;yexpi=q-yexp;i+;q=q-next;else if(p-xexp=q-xexp&p-yexpyexp)coefi=p-coef;xexpi=p-xexp;yexpi=p-yexp;i+;p=p-next;else if(p-xexp=q-xexp&p-yexpq-yexp)coefi=-q-coef;xexpi=q-xexp;yexpi=q-yexp;i+;q=q-next;else if(p-xexp=q-x

30、exp&p-yexp=q-yexp)coefi=p-coef-q-coef;xexpi=p-xexp;yexpi=p-yexp;i+;p=p-next;q=q-next;while(p!=NULL&q=NULL)coefi=p-coef;xexpi=p-xexp;yexpi=p-yexp;i+;p=p-next;while(q!=NULL&p=NULL)coefi=-q-coef;xexpi=q-xexp;yexpi=q-yexp;i+;q=q-next;CreateList(L3,coef,xexp,yexp,i);sort(L3);显示多项式void Display

31、List(LinkList *&L)LinkList *p=L-next;printf(%dx%dy%d,p-coef,p-xexp,p-yexp);p=p-next;while(p!=NULL)if(p-coef0)printf(+%dx%dy%d,p-coef,p-xexp,p-yexp);elseprintf(%dx%dy%d,p-coef,p-xexp,p-yexp);p=p-next;菜单int menu_select()int choose;printf(ntt*n);printf(ttt1printf(ttt2printf(ttt0printf(ttt、两个多项式的和、两个多项式的差、退出 n);请选择(1 或 2 或n);n);0)n);printf(tt*n);for( ; ; )scanf(%d,&choose);if(choose2)printf(ttt输入有误 , 重新选择 n);elsebreak;return choose;主函数void main()int c