二元多项式加减运算.docx

《二元多项式加减运算.docx》由会员分享，可在线阅读，更多相关《二元多项式加减运算.docx（15页珍藏版）》请在三一办公上搜索。

1、系数/x指数/y指数LinkList *next; ;/指针/定义结点题目：二元多项式加减运算问题设计程序以实现降幂建立、输出、加、减任意两个二元多项式。要求：（1）所设计的 数据结构应尽可能节省存储空间。（2）程序的运行时间应尽可能少。1、问题分析和任务定义此程序需要完成以下的要求：按照指数降序排列建立多项式并且输出；能够完成两个多 项式的相加、相减运算，并将结果输出。在这个程序中，我采用链表的数据结构来实现二元 多项式的建立和表示。然后进行降序的排列，完成二元多项式的两个基本运算：加法和减法。 最后同样按照降序，对得到的结果多项式进行排列，测试用例设置为二组，分别为：第一组 为系数不同而x

2、和y的指数各自相同；第二组为系数和指数各不相同。举一个例子如下：第一组数据：6% y3+5%4y3+8x7y3+7x2y7第二组数据：2%2 y7+x2 y3+5x7 y 2+4x5 y4降幂排序后的结果：第一组数据：8x7 y3+5x4 y3+7x2 y7+6x y3第二组数据：5x7y2+4x5y4+2x2y7+x2y3两组多项式相加结果：8x7y3+5x7y2+4x5y4+5x4y3+9x2y7+x2y3+6x y3 两组多项式相减结果：8x7y3 - 5x7y2 - 4x5y4+5x4y3+5x2y7 - x2y3+6x y3现在，我要通过程序来实现以上的过程将其在计算机上完成运算最终

3、成功得到这样的结果。2、数据结构的选择和概要设计为了解决这个问题，我选择的数据结构为链表，原因是：链表中的结点可以动态生成的， 用链表结构可以灵活地添加或删除结点。另外，用链表结构来存储这样的数据可以大大地减 少空间复杂度，因此本题在设计算法时使用的就是链表地结构，存放多项式的链表结点结构 如下图如示：系数 coef X 的指数 xexp Y 的指数 yexp 指针 next图1.存放多项式的链表结点结构struct LinkListint coef;int xexp;int yexp;这是链表的最基本的构成单元一一结点。在输入多项式时，考虑到输入多项式的形式，本程序是分别输入各个多项式中每一

4、个项 的系数，x指数,y指数，然后在输出时再把多项式的各个关键字组合在一起。建立链表的时候，通过定义MAX的值就可以一次性地告诉计算机，本次运行程序需要开 辟空间的大小。同时可以改变相应的MAX大小，来改变其空间的大小。由于是2个多项式相 加相减的运算，所以设定MAX 1和MAX2分别来定义。然而，二元多项式的加减在运算中难免 会遇到两种极端情况，即：没有一个是同类项或者全是同类项。如果遇到“没有一个是同类 项”的情况，那么，运算后的这个链表的长度就是原来的2个多项式之和，所以直接将运算 后得到的链表长度开辟的空间定义为MAX1+MAX2，已免出现溢出错误。在这一点上，链表的 插入结点的操作简

5、单的优势就体现出来了，然而对于减法的情况，同理，合并同类项的工作 对于多项式来说也就是结点的删除工作。本程序的几个重要的问题按顺序是：1、建立链表2、多项式的输入形式、显示以及显示的形式3、如何按降序排序4、多项式加法函数5、多项式减法函数6、选择菜单。以上这六个问题需要最终分别用几个函数来分别实现。另外加上一个主函数。这几个函 数分别为：void CreateList(LinkList *&L,int a,int b,int c, int n) /创建链表void sort(LinkList *&L) /降序排序void ListAdd(LinkList *&L1,LinkList *&L2

6、,LinkList *&L3) /两个多项式相加void ListSubtract(LinkList *&L1,LinkList *&L2,LinkList *&L3)void DisplayList(LinkList *&L) /显示多项式int menu_select()/菜单这些函数连同主函数在一起构成整个程序，其中，主函数依次调用建表函数、排序函数、 显示函数、菜单函数，菜单函数提示用户选择来调用加法函数和减法函数，加法函数和减法 函数中都分别依次调用建表函数、排序函数和显示函数，另外菜单函数还自己调用自己，即 递归的调用。3、详细设计和编码本程序的有6个模块，分别为1、建表2、排序3

7、、加法4、减法5、显示6、选择。各模块的详细分析设计如下：1、建表多项式的存储的数据结构采用的是链表的方式：系数cofeX的指数xexpY的指数yexp指针next存放多项式的链表结点结构对于输入的2个多项式，都采用链表的存储方式，运算后的多项式也一样地采用这种方 式来存储。在建立链表结构时，根据题目的情况，我选择了头插法来建立链表，算法为：首 先建立一个只含有头结点的空单链表，然后读入数据，生成新结点，并将新结点总是插入到 头结点之后，直到读满之前设置的链表的长度。系数，x指数，y指数分别用a,x,y口 三个数组的形式进行读入。头插法建单链表的算法时间复杂度为O(n)。创建链表函数为：voi

8、d 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;/头插法建链表的时间复杂度是O(n)L-next=s;2、排序降序排序函数的主要算法思想：先检查p结点是不是最后一个结点，如果不是，就向后 继续查找，直到找到最后一个结点，把这个结点中的指数和前一

9、个结点中的指数进行比较， 如果这个指数比前一个结点的指数大，说明这两个结点按升序排列，需要改变位置，于是执 行指针的变换操作，使得两个结点改成降序排列，以此达到排序的目的。以下是排序函数：/降序排序void sort(LinkList *&L)LinkList *p=L-next,*q,*r;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-n

10、ext=q-next;q-next=p;p=r;3、加法两个多项式相加的算法是：两个多项式中，具有相同指数项的，也就是同类项的对应系 数相加，若相加和不为零，则合并成加和多项式中的一项，所有指数不相同的项均直接移动 至加和多项式中的后面，至于排列，则依据排序函数进行降序排序。对于两个多项式链表A和B，实现多项式相加时，加和多项式中的结点无需另外生成， 可以看成是将多项式B加到多项式A中，最后的加和多项式即是新的多项式A，设p、q分 别指向多项式A、B的首元素结点，则比较结点*p、*4的指数项，可以进行以下操作来完成 多项式的加法运算： 若p-expexp，则*?结点应是加和多项式的一项，并将指

11、针p后移。 若p-expq-exp，则*4结点应是加和多项式的一项，将*q结点插入到多项式链 表A的*p结点之前，并令指针q在多项式链表B上后移。 若p-exp=q-exp，则将两个结点的系数相加，若和不为零，则修改*p结点的系数 域，释放指针q所指向的结点空间；若和为零，则指针p、q分别在各自的链表上后移，同 时释放原先两个指针所指向的结点空间。 重复上述步骤，若q=NULL，则链表A即为加和多项式链表；若p=NULL，则将链表 B中指针q所指向的余下的链表全部插入到链表A的表尾，形成加和多项式链表A. 由于这个题目是二元多项式，要考虑X和y两个元，故而以上四个步骤在实际写程 序的时候是按照

12、xexp和yexp两个变量而不是只有一个exp，写成exp是为了说明的时候看 得清楚一点。加法算法的时间复杂度取决于链表A和B的项数，若A有n项,B有m项，那 么上述算法的时间复杂度为O(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!=NUL

13、L&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-xexp=q-xexp&p-yexpq-yexp) coefi=q-coef;xexpi=q-xexp;yexp

14、i=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;xexpi=q-xexp;yexpi=q-yexp;i+;q=q-next;CreateList(L3,coef,xexp,yexp,i);

15、sort(L3); 4、减法两个多项式的相减算法和加法函数很类似，主要思想是先将链表B取负，然后执行和加 法算法一样的步骤，最后交给排序函数做一次降序排序。5、显示显示的格式是:a1*xb1yc1+a2*xb2yc2+a3*xb3yc3+a4*xb4yc4根据依次读入的数据进行显示 6、选择菜单主要提供用户选择（包含退出功能），两个多项式的和以及两个多项式的差的运算。1、两个多项式的和 酉人多项式的差 0.退出请选择或2或跄4、上机调试过程1、语法错误及修改由于本算法使用了链表的方式建立二元多项式，所以程序的空间是动态的生成的，而且 链表可以灵活地添加或删除结点，所以使得程序得到简化。出现的语

16、法问题主要在于子函数 和变量的定义，降序排序，关键字和函数名称的书写，以及一些库函数的规范使用，这些问 题均可以根据编译器的警告提示，对应的将其解决。2、逻辑问题及其调整编写程序的过程中遇到许多问题，首先在选择数据结构的时候选择了链表，但是链表的 排序比较困难，特别是在多关键字的情况下，在一种关键字确定了顺序以后，在第一关键字 相同的时候，按某种顺序对第二关键字进行排序。在此程序中共涉及到3个量数，即：系数， x的指数和y的指数，而关键字排是按x的指数和y的指数来看，由于要求是降幂排序且含 有2个关键字，所以我先选择x的指数作为第一关键字，先按x的降序来排序，当x的指数 相同时，再以y为关键字

17、，按照y的指数大小来进行降序排列。在加法函数的编写过程中也遇到了大量的问题，由于要同时比较多关键字，而且设计中 涉及了数组和链表的综合运用，导致反复修改了很长的时间才完成一个加法的设计，现在仍 然有一个问题存在，若以0为系数的项是首项则显示含有此项，但是运算后则自动消除此项， 这样是正确的。但是当其不是首项的时候，加法函数在显示的时候有0为系数的项时，0前 边不显示符号，当然，这样也可以理解成当系数为0时，忽略这一项。3、时间，空间性能分析链表的建立使用的是头插法建表，时间复杂度为O(n)，本程序采用链表存储。单链表 的每个结点都有一个指针空间，相当于总共增加7n个整型变量，在空间复杂度上为O

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

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

20、是程序合并同类项，两个多 项式的x和y的指数相同的项的系数相加成为新的多项式，均与试验结果中的数据相同(注：程序的运行结果截图在下一页)由此，第一组指数相同的2个多项式成功完成运算。下面，我来用第二组数据来进行测试。这一组数据设置为系数相同而x和y的指数各自 不相同，结果是程序找不到同类项，按两个多项式的x和y的指数排列相加成为新的多项式。 由于没有同类项，所以只好依次相加所有的项。（注：程序的运行结果截图在下一页）e. * J- By Do cu*ent s D ebug; T ext 1. exe 便入算一穆*式的所有系数S个）: *入第一个多项式所有的X色s个: 5 ? 8 3航v第一个

21、多项式所有的y色S个:4 2 7 9前入第二八多项式钓所有系敖（4个）:4 5 4 5扁入剪二八多项式听有钓扁4个:3 4 6 8扁入剪二八多项式听有的儒4个:5 19 7陪晶显示第一八多项式：4x A8 y 7 +5 x a?sj A2 +5 x A3 A9 +奴华 广4 整晶显示第二八多项舟57+4k%9+5 广4 8 人1 +奴35.S 的的 顼顼 多多 个个出 两两退由此，第二组指数不同的2个多项式成功完成运算。6、用户使用说明用户使用之前需要设置MAX的值，如果不需要改变原始的设置，直接打开“二元多项式 计算.exe”，界面欢迎使用二元多项式加减计算器，一次性输入第一个多项式所有的系

22、数， 按 enter输入，再一次性输入乂的指数和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/定义结点struct LinkListint coef; /系数int xexp; /x 指数int yexp; /y 指数LinkList *next;/指针;/创建链表void Cr

24、eateList(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;if(p!=NULL)r=p-next;p-next=NULL;p=r;w

25、hile(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+MAX2,i=0;LinkList *p=L1-next,*q=L2-next;while(p!=NULL&q!=N

26、ULL)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-xexp=q-xexp&p-yexpq-yexp)coefi=q-coef;xexpi=q-xexp;yexpi=q-yexp;i

27、+;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;xexpi=q-xexp;yexpi=q-yexp;i+;q=q-next;CreateList(L3,coef,xexp,yexp,i);sort(L3);两

28、个多项式相减void ListSubtract(LinkList *&L1, LinkList *&L2, LinkList *&L3) int coefMAX1+MAX2, xexpMAXl+MAX2, yexpMAXl+MAX2, i=0;LinkList *p=Ll-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(pxexpqxexp)coefi=-q-coef;xexp i=q-xexp;yexpi=q-ye

29、xp;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-coef-q-coef;xexpi=p-xexp;yexpi=p-yexp;i+；p=p-next;q=q-next;while(p!=NU

30、LL&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 DisplayList(LinkList *&L)LinkList *p=L-next;printf(%dx”%dy”%d”,p-coef,p-xexp,p-yexp);p=p-next;while(p!=NULL)if(p-co

31、ef0)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(ttt1、两个多项式的和n);printf(ttt2、两个多项式的差n);printf(ttt0、退出n);printf(ttt 请选择(1 或 2 或 0)n);printf(tt*n);for( ; ; )scanf(%d”,&choose);if(choose2)printf(ttt输入有

32、误，重新选择n);elsebreak;return choose;/主函数void main()int coefMAX1,xexpMAX1,yexpMAX1,i=0;LinkList *L1,*L2,*LSum;printf (-输入第一个多项式的所有系数(%d个)：n”,MAX1); /输入第一个多项式的系数 for(i=0;iMAX1;i+) scanf(%d”,&coefi);printf(输入第一个多项式所有的x幂(%d个)：n”,MAX1); /输入第一个多项式的x幂 for(i=0;iMAX1;i+) scanf(%d”,&xexpi);printf(输入第一个多项式所有的y幂(%

33、d个)：n”,MAX1); /输入第一个多项式的y幂 for(i=0;iMAX1;i+) scanf(%d”,&yexpi);CreateList(L1,coef,xexp,yexp,MAX1);printf (-n输入第二个多项式的所有系数(%d个)：n”,MAX2); /输入第二个多项式的系数 for(i=0;iMAX2;i+) scanf(%d”,&coefi);printf(输入第二个多项式所有的x幂(%d个)：n”,MAX2); /输入第二个多项式的x幂for(i=0;iMAX2;i+)scanf(%d”,&xexpi);printf(输入第二个多项式所有的y幂(%d个)：n”,MA

34、X2); /输入第二个多项式的y幂 for(i=0;iMAX2;i+)scanf(%d”,&yexpi);CreateList(L2,coef,xexp,yexp,MAX2);printf(nn降幂显示第一个多项式:n); /降幂显示第一个多项式 sort(L1);DisplayList(L1);printf(nn降幂显示第二个多项式:n); /降幂显示第二个多项式 sort(L2);DisplayList(L2);printf(n)；for(; ;)switch(menu_select()case 1:printf(n求两个多项式的和并显示:n); /求两个多项式的和并显示 ListAdd(L1,L2,LSum);DisplayList(LSum);printf(n)；break;case 2:printf (-n求两个多项式的差并显示:n); 求两个多项式的差并显示ListSubtract(L1,L2,LSum);DisplayList(LSum);printf(n); break;case 0:default :printf(退出！ n);break;