一元多项式计算.doc

xx学院数据结构与算法课程设计报 告 书课程设计题目 一元多项式计算院系名称计算机科学与技术系 专 业 （班 级） 姓 名 （学 号） 指 导 教 师 完 成 时 间 一问题分析和任务定义1问题分析设计要求是对于从键盘输入的任意两个一元多项式，能够分别按照指数降序排列建立并输出多项式，实现对此两个多项式的进行相加、相减，并将结果输出。在具体实现时，可采用链式存储结构将多项式中的每一项连接起来，表达出整个多项式，其中的每一项是一个单项式。通过每一项变元的系数与指数的输入设置，完成对于整个多项式的设定，通过建立单链表，建立结点存储每一项变元的系数与指数，最后整个链表便完成了整个多项式的存储。两个多项式对应建立两个链表，通过两链表按照数学上多项式之间的加、减运算规则进行合并，最后实现计算，将其输出，便得到最终的计算结果。2任务定义若干个单项式（不含加法或减法运算的整式）的代数和称做多项式。一元多项式就是只含一个变元的多项式。根据多项式的定义可知，对于一元多项式来说，由n个同一变元的单项式组成。其运算满足交换率。对其进行降幂排列，只需要将它的所有的指数值相比较，指数大的放在前面，小的放在后面。对于两个一元多项式的加法和减法来说，只需将指数值相同的单项式的系数值相加减即可。程序所能达到的功能：对于任意输入的两个多项式不但可以分别进行降幂排列，还可以对其相互间进行加减运算并输出两式运算后的降幂排列的结果。据此，对于输入的变元的系数与指数值的范围为任意的整数均可。输入的形式按照运行时界面的提示，变元的系数和指数交替输入即可，当其中一个单项式变元的系数值为0时，表示该一元多项式的输入到此结束。多项式输出的形式采用数学上习惯的表达方式，即：系数+变元+指数，一个多项式的结构由形如axb的数个单项式的和组成。其中a为系数，x为变元，b表示变元x的指数。3测试数据设计测试数据时，应充分考虑到测试数据的完备性，做到全面地对算法程序进行测试，以验证整个程序在处理具体问题时对不同情况的处理能力。据此，设计测试数据表一所示：表一：序号测试数据对象名称测试数据内容第一组第一个一元多项式 a（6，1）（-4，5）（12，-5）（-5，-2）（0，1）第二个一元多项式 b（15，4）（8，-3）（-9，5）（-11，-1）（0，2）第二组第一个一元多项式 c（5，6）（-13，-2）（-25，2）（15，-4）（0，4）第二个一元多项式 d（0，255）第三组第一个一元多项式 e（17，2）（-10，5）（23，14）（0，-14）第二个一元多项式 f（31，2）（-12，-4）（0，0）测试数据特点：1） 第一组完成两组一元多项式正常计算，系数与指数的关系包含有多种，有同为正、同为负、正负交替，后面分别以（0，1）（0，2）表示本次输入结束。2） 第二组的情况是第一个多项式正常设置，第二个多项式不设置，内容为空，直接以（0，255）退出，这样是为了测试程序是否能针对一个多项式进行处理。3） 第三组的情况是第一个多项式内容正常设置，以（0，-14）结束，在第二个多项式设置时，假设遇到突发事件，用户不能或不愿继续完成后面的操作而想要从中途退出，于是采用（0，0）强制退出程序运行，结束整个计算。二概要设计和数据结构的选择在算法程序的设计与编写过程中，根据以上对相关问题及设计要求的分析，结合设计对象的特点，实现一元多项式的相加、相减、降幂和输出。根据一元多项式的结构特点与运算规则，采用链表来存储和实现，之所以选用链表，是因为对于链表中的结点可以很方便地实现插入和删除，通过两个链表的合并即可完成两个多项式的计算。定义一个结构体类型结点来存放多项式各项变元的系数和幂。typedef struct node/结构体类型定义结点 int coef; /系数coefficientint power; /幂node *next;/指向结点的指针，连接后项构成多项式链表node;具体流程是：首先调用建表函数create()依次建立两个单链表，分别表示待处理的两个一元多项式，然后对两个多项式按指数大小进行降幂排列，由sort()函数实现，接下来便是调用计算函数calculate()将二者进行计算，这是整个算法的核心，最后通过输出函数output()输出，据此思想算法，程序流程图如下：开始建表create()建表结束？计算calculate()输出output()结束N输出output()输出结束？YNY图 1. 建表三详细设计和编码在本次设计的程序中，共使用了四个子函数，其详细设计和编码如下：当用户从键盘输入系数和幂以后，建立链表，存储该一元多项式。node *create() /根据用户输入的数据建立一个多项式链表int co,po,i=1; node *head,*s,*pre; /head是头结点指针,s为在建结点指针,pre是在建结点的前一结点的指针 printf(请输入一元多项式,以(0，n)的形式结束本次输入(n为任意非零整数):n);head=(node*)malloc(size); /申请头结点空间head-next=NULL; /将head的next域置为空 pre=head; do /运用do-while循环建立一元多项式链表printf(第%d次-系数,幂:,i+); scanf(%d,%d,&co,&po); if(co=0&po=0)/判断是结束标志时， exit(0);/则跳出 if (co!=0) /输入的系数值非空，用于判断该结点是否建立s=(node*)malloc(size); /建立一个新结点，表示多项式的一项 s-coef=co; /分别将系数、 s-power=po;/指数赋值 s-next=NULL;/将s的next域置为空 pre-next=s;/前项与后项链接 pre=s;/pre前项指针后移至s上，以便下一项的建立 while (co!=0); /当系数不为零时，继续循环 printf(n); return(head); /返回头结点指针，即表头，标识整个多项式2由于多项式系数和幂是随机输入的，根据要求，需要对其按指数进行降幂排列，在这个程序模块中，使用链表，根据指数大小的比较，对各种情况进行处理。此处由于反复使用指针对各个结点先定位，找到合适位置，再进行链接插入，实现时很不容易，投入了很多的时间和精力。void sort(item * T) /对任意输入的一元多项式进行降幂排列item *p=T-next; /p指向待处理的第一个结点，初始指向原表头结点T-next=NULL; /T仍为待建立的有序表的表头指针，初始值为空while(p!=NULL) /把原单链表中的结点依次进行有序链接item *q=p; /q指向待处理的结点p=p-next; /p指向下一个待处理的结点item *ap=NULL,*cp=T-next; /cp指向有序表中待比较的结点，ap指向其前驱结点while(cp!=NULL) /为插入q结点寻找插入位置if(q-powercp-power)break;elseap=cp;cp=cp-next; /将q结点插入到ap和cp结点之间q-next=cp;3在该程序中，最关键的一步是实现两个一元多项式的加减运算并输出。由于加减算法原理是一样的，减法可通过系数为负的加法实现，故只按运算规则编写加法函数，便可实现计算。若读者需要进行减法运算，只需将被减多项式的系数全部取反输入通过加法即可实现。该段程序要对于指数的多种不同情况分别进行展开处理，因而显得有点烦琐，至于有无更简洁的实现方式，尚在思索之中，有待进一步简化。node * calculate(node * pa,node * pb)/两个一元多项式进行计算int n;node *ph,*s,*pres;/ph是头结点指针,pres是在建结点的前一结点的指针 pa=pa-next; pb=pb-next; ph=(node *)malloc(size); /申请空间，存放附加的表头结点 ph-next=NULL; pres=ph; /p总是指向ph链表的最后一个结点 while (pa!=NULL & pb!=NULL) if (pa-powerpb-power)/a的幂高 s=(node *)malloc(size); /建立一个结点s s-coef=pa-coef;/将较大的幂对应的项pa放在s结点中 s-power=pa-power; s-next=NULL; pres-next=s; pres=s;/指针后移 pa=pa-next;/pa指针后移将pa后面的项继续和pb比较 else if (pa-powerpower)/b的幂高 s=(node *)malloc(size); /建立一个结点s s-coef=pb-coef;/将较大的幂对应的项pb放在s结点中 s-power=pb-power; s-next=NULL; pres-next=s; pres=s; pb=pb-next;/pb指针后移将pb后面的项继续和pa比较 else /两者的幂相等时 n=pa-coef+pb-coef;/系数相加 if (n!=0) /系数不为0时添加该结点 s=(node *)malloc(size); /建立一个结点 s-coef=n; s-power=pb-power; s-next=NULL; pres-next=s;pres=s; pa=pa-next;pb=pb-next; while (pa!=NULL)/当pa未结束，pb结束时，将pa剩下的项链接着放入s中 s=(node *)malloc(size); /建立一个结点 s-coef=pa-coef;s-power=pa-power; s-next=NULL;pres-next=s; pres=s;pa=pa-next;/指针后移继续将pa中的剩余项链接到s后面 while (pb!=NULL)/当pb未结束，pa结束时，将pb剩下的项链接着放入s中 s=(node *)malloc(size); /建立一个结点 s-coef=pb-coef; s-power=pb-power; s-next=NULL; pres-next=s; pres=s;pb=pb-next;/指针后移继续将pb中的剩余项链接到s后面 return(ph); /返回头结点指针4最后一个子函数是输出函数output()，输出最终的结果，同时体现出程序的价值，算法是将最后计算合并的链表逐个结点依次输出，便得到整个链表，也就是最后的多项式计算结果。由于考虑各个结点的指数情况不同，分别进行了判断处理，因而整个函数略显冗余，这一点可进一步研习并优化。void output(node *T)/输出多项式(符号表幂运算,例如m 2表示) node *p=T-next; while(p-next!=NULL)/当不为空，即链表未结束时，循环if(p-power=1)/判断p-power的值得范围，以相应的形式输出printf(%dx,p-coef);else if(p-power=0)/指数为零时printf(%d,p-coef); /直接输出系数else if(p-powercoef,p-power);/加括号输出elseprintf(%dx%d,p-coef,p-power);if(p-next-coef0)/后面的项系数大于零printf(+); /则用加号连接p=p-next;/指针后移if(p-power=1)/最后一个一元多项式单链表结点的输出printf(%dx,p-coef);else if(p-power=0)printf(%d,p-coef); else if(p-powercoef,p-power);elseprintf(%dx%d,p-coef,p-power);四上机调试遇到的问题及解决在该程序的完成过程中，虽然总体的思想很简单，但实现起来才发现实践与理论之间是有很大距离的，特别是对于多种情况的不同处理，由于指针的灵活性，需要特别留心细节，时刻把握住指针的指向，否则会引起很大的混乱，而自己却理不出丝毫的头绪。调试中，遇到的主要问题如下所列：（1）在排序函数中，开始对各种情况的考虑欠全面，只是一味地对多项式链表中的结点项指数进行比较，把比较结果按指数降幂放入另外开辟的新空间里，这样做程序不仅冗长，而且显得笨拙，由于指针的不断变换，最后的结果也是错误百出，后仔细分析老师上课课件中类似的一道例题，将程序改正，在原链表内将非序的，采用while嵌套循环并比较if(q-powercomp-power)将非序的结点插入到合适的新位置。（2）在计算函数中，对于指数比较的三种情况处理时，将后项结点直接连接于后结点pa-next=pb并返回，结果破坏了原来的链表结构，无法完成后面的比较，引起错误，后来改用新申请结点s并把对象的相关数据赋给s, s-coef=pa-coef; s-power=pa-power;后面的也都是如此处理，虽然方式单一，但实现的结果是正确的。（3）在输出函数中，通过链表中指针的连接关系逐个输出，条件是while(p-next!=NULL)，但这样输出的结果是把最后一项遗漏了，后只好对其另加处理，接在后面讨论并输出。（4）在后面的测试中，加入了适当的提示与输入要求，使界面更加友好，操作时在以（0，n）（n为任意非零整数）结束本次输入的基础上，又加了以（0，0）跳出整个程序，显得更加贴近现实。但就在实现时自己犯了一个很不应该的粗心错误，自己原以（#，#）形式作为退出方式，但在运行时出现看不同懂的死循环，费了好大的劲也无能为力，最后请同学帮忙测试分析，发现是简单的类型不匹配，即#属于字符型，而输入数据定义是整形，故导致错误，恍然大捂，后改为（0，0），感慨果然是当局者迷，此处一提，以示警醒。2时间与空间性能分析由于本算法使用的是单链表，对于其时间和空间的消耗计算同单链表一样.在该算法中时间主要消耗在对单链表进行降幂排列。最好的情况是：一元多项式本身是按降幂排列的，此时总的移动次数为N-1；最坏情况是：待排序的一元多项式本身是按升幂排列，此时总的比较次数为N-i+1;则其时间复杂度为：T(N)=O(n*n); 对于其消耗空间而言，单链表中每个结点都要增加一个指针空间，相当于总共增加了n 个整型变量，空间复杂度为 O(n)。 3经验和体会整个设计的最大体会便是做比说难，刚开始抽到题目时，觉得很简单，但具体动手做时发现情况相当复杂，对于指针的知识掌握是一次很大的考验，终觉眼高手低之深刻。对于任何事情都不应该轻视大意，而要深刻思考并着手认真的做。对于炎炎烈日，每天坐在空调机房内，将所学的理论知识应用于实践，不懂的地方有老师随时给予指导解答，虽忙碌，但不失仍为一种享受。 对于具体的设计而言，让我收获了许多。特别是指针的相关知识与应用，同时对于单链表也有了更为透彻的把握。整个设计学习的过程中，不仅仅是知识的深化与累积，更是一种做事严谨与端正的态度。五用户使用说明在该程序执行过程中，用户只需要按照提示要求逐一输入数据即可。输入一元多项式时，输入一次系数和幂以后，敲回车键进行下一次输入，直至输入（0，n）结束。实现减法运算时，将被减的多项式系数全部取反输入，即可得到正确的计算结果。需特别说明的是，一定要按要求输入，每次按系数和幂值依次输入，系数和幂值之间以逗号隔开，(0，n)的形式有两个功能：当n为非零整数时，表示结束本次输入工作，当n为0时，表示结束整个程序，完成用户所需要的强制退出。六测试结果对应测试数据的各个结果与说明如下所示：第一组测试结果：第一组测试结果（图二）： 说明：如运行结果所示，先建立第一个一元多项式，输出原始状态，然后按指数降幂排列，并输出。第二个一元多项式同样如此。最后二者计算合并，得出结果，容易验证，结果是正确的，此即完成了正常的两个一元多项式计算。第二组测试结果（图三）： 说明：本组数据检测当第一个一元多项式正常设置，而第二个多项式为空，不设置任何数据，结果出错。原因是在建表时程序是空操作，而在排序时，头指针地址后移，此时的指针地址已不在程序所能左右的范围内，地址随机得到，出现混乱，导致错误。当然这种情况在实际操作时意义不大，此处之所以列出是为了验明程序的健壮性，完全是出于务实的态度。第三组测试结果（图四）：说明：本组测试是针对于一种意外情况的处理，第一个多项式正常输入，在设置第二个多项式时，采用强制退出，结束整个程序，如图成功实现。这一点是模拟实际，具有一定现实意义。七参考书目徐孝凯，数据结构实用教程，清华大学出版社，1999年12月第1版。胡学钢，数据结构（c语言版），高等教育出版社，2004年1月第1版。严蔚敏等，数据结构（c语言版），清华大学出版社，1997年4月第1版。谭浩强，c语言程序设计教程（第二版），高等教育出版社，1998年7月第2版。八带注释的源程序#includestdio.h#includestdlib.htypedef struct node/结构体类型定义结点 int coef; /系数coefficientint power; /幂node *next;/指向结点的指针，连接后项构成多项式链表node;int size=sizeof(node);/定义m标量结点空间，用于空间申请node *create() /根据用户输入的数据建立一个多项式链表int co,po,i=1; node *head,*s,*pre; /head是头结点指针,s为在建结点指针,pre是在建结点的前一结点的指针 printf(请输入一元多项式,以(0，n)的形式结束本次输入(n为任意非零整数):n);head=(node*)malloc(size); /申请头结点空间head-next=NULL; /将head的next域置为空 pre=head; do /运用do-while循环建立一元多项式链表printf(第%d次-系数,幂:,i+); scanf(%d,%d,&co,&po); if(co=0&po=0)/判断是结束标志时， exit(0);/则跳出 if (co!=0) /输入的系数值非空，用于判断该结点是否建立s=(node*)malloc(size); /建立一个新结点，表示多项式的一项 s-coef=co; /分别将系数、 s-power=po;/指数赋值 s-next=NULL;/将s的next域置为空 pre-next=s;/前项与后项链接 pre=s;/pre前项指针后移至s上，以便下一项的建立 while (co!=0); /当系数不为零时，继续循环 printf(n); return(head); /返回头结点指针，即表头，标识整个多项式void sort(node * T) /对多项式进行降幂排列，T为表头指针node *p=T-next; /p指向待处理的第一个结点，初始指向原表头结点T-next=NULL; /T仍用做待建有序表的表头指针，初始值为空，while(p!=NULL) /把原单链表中的结点依次进行有序链接，构成有序表node *q=p; /q指向待处理的结点p=p-next; /p指针后移，指向下一个待处理的结点node *prep=NULL,*comp=T-next; /comp指向有序表中待比较的结点，prep指向其前驱结点while(comp!=NULL) /为插入q结点寻找插入位置if(q-powercomp-power) break;/有序时，跳出，不作处理elseprep=comp;comp=comp-next; /将q结点插入到prep和comp结点之间q-next=comp; /对有序表中下一项进行比较if(prep=NULL) /有序表为空T-next=q; /头结点直接链接当前结点elseprep-next=q;/否则连接到前驱接点后，按正常处理node * calculate(node * pa,node * pb)/两个一元多项式进行计算int n;node *ph,*s,*pres;/ph是头结点指针,pres是在建结点的前一结点的指针 pa=pa-next; pb=pb-next; ph=(node *)malloc(size); /申请空间，存放附加的表头结点 ph-next=NULL; pres=ph; /p总是指向ph链表的最后一个结点 while (pa!=NULL & pb!=NULL) if (pa-powerpb-power)/a的幂高 s=(node *)malloc(size); /建立一个结点s s-coef=pa-coef;/将较大的幂对应的项pa放在s结点中 s-power=pa-power; s-next=NULL; pres-next=s; pres=s;/指针后移 pa=pa-next;/pa指针后移将pa后面的项继续和pb比较 else if (pa-powerpower)/b的幂高 s=(node *)malloc(size); /建立一个结点s s-coef=pb-coef;/将较大的幂对应的项pb放在s结点中 s-power=pb-power; s-next=NULL; pres-next=s; pres=s; pb=pb-next;/pb指针后移将pb后面的项继续和pa比较 else /两者的幂相等时 n=pa-coef+pb-coef;/系数相加 if (n!=0) /系数不为0时添加该结点 s=(node *)malloc(size); /建立一个结点 s-coef=n; s-power=pb-power; s-next=NULL; pres-next=s;pres=s; pa=pa-next;pb=pb-next; while (pa!=NULL)/当pa未结束，pb结束时，将pa剩下的项链接着放入s中 s=(node *)malloc(size); /建立一个结点 s-coef=pa-coef;s-power=pa-power; s-next=NULL;pres-next=s; pres=s;pa=pa-next;/指针后移继续将pa中的剩余项链接到s后面 while (pb!=NULL)/当pb未结束，pa结束时，将pb剩下的项链接着放入s中 s=(node *)malloc(size); /建立一个结点 s-coef=pb-coef; s-power=pb-power; s-next=NULL; pres-next=s; pres=s;pb=pb-next;/指针后移继续将pb中的剩余项链接到s后面 return(ph); /返回头结点指针void output(node *T)/输出多项式(符号表幂运算,例如m 2表示) node *p=T-next; while(p-next!=NULL)/当不为空，即链表未结束时，循环if(p-power=1)/判断p-powe