数据结构一元多项式的计算

1、项目一 一元多项式的计算问题1.1设计题目与要求1.1.1设计题目1）一元多项式计算任务：能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输入；基本要求：在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图） 、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；本程序关键点是如何将输入的两个多项式相加、相减操作。如何将输入的一元多项式按指数的降序排列如何确定要输入的多项式的项数；如何将输入的两个一元多项式显示出来。如何将输入的两个一元多项式进行相加操作。如何将输入的两个一元多项式进行相减操作。本程序是通过链表实现一元多项

2、式的相加减操作。1.1.2、任务定义此程序需要完成如下的要求：将多项式按照指数降序排列建立并输出，将两个一元多项式进行相加、相减操作，并将结果输入。a： 输入多项式的项数并建立多项式； b： 输出多项式，输出形式分别为浮点和整数序列，序列按指数升序排列； c： 多项式a和b相加，建立多项式a+b； d： 多项式a和b相减，建立多项式a-b。 e： 多项式的输出。1.2 数据结构的选择和概要设计：1.2.1数据结构的选用 A:基于链表中的节点可以动态生成的特点，以及链表可以灵活的添加或删除节点的数据结构，为了实现任意多项式的加法，减法，因此选择单链表的结构体，它有一个系数，指数，下一个指针3个元

3、属；例如，图1中的两个线性链表分别表示一元多项式和一元多项式。从图中可见，每个结点表示多项式中的一项。图1 多项式表的单链存储结构B：本设计使用了以下数据结构：typedef struct nodeint xs; /*系数*/int zs;/*指数*/struct node * next; /*next指针*/Dnode,* Dnodelist;C：设计本程序需用到八个模块，用到以下八个子函数如下：1.Dnodelist Creat_node(void) /*链表初始化*/2.int Insert_node(Dnodelist D,int xs,int zs) /*插入函数*/3.Dnodel

4、ist Creat_Dmeth(int length) /*创建多项式*/4.Dnodelist Addresult(Dnodelist D1,Dnodelist D2) /*多项式相加*/5.Dnodelist Subresult(Dnodelist D1,Dnodelist D2) /*多项式相减*/6.Dnodelist select(Dnodelist D1,Dnodelist D2) /*选择函数*/7void Show(Dnodelist D) /*显示（输出）函数*/8void main()主程序模块调用链一元多项式的各种基本操作模块。1.2.2 多项式的输入 先输入多项式的项数

5、，采用尾插法的方式，输入多项式中一个项的系数和指数，就产生一个新的节点，建立起它的右指针，并用头节点指向它；1.2.3 两个多项式的加法 “和多项式”链表中的结点无需另生成，而应该从两个多项式的链表中摘取。其运算规则如下：假设指针A和B分别指向多项式a和多项式b中当前进行比较的某个结点，则比较两个结点中的指数项，有下列3种情况：指针A所指结点的指数值<指针B所指结点的指数值，则应摘取A指针所指结点插入到“和多项式”链表中去；指针A所指结点的指数值>指针B所指结点的指数值，则应摘取指针A所指结点插入到“和多项式”链表中去；指针A所指结点的指数值=指针B所指结点的指数值，则将两个结点中

6、的系数相加，若和数不为零，则修改A所指结点的系数值，同时释放B所指结点；反之，从多项式A的链表中删除相应结点，并释放指针A和B所指结点。例如，由图2中的两个链表表示的多项式相加得到的“和多项式”链表如图2所示，图中的长方框表示已被释放的结点。图2 相加得到的和多项式    上述多项式的相加过程归并两个有序表的过程极其类似，不同之处仅在于，后者在比较数据元素时只出现两种情况。因此，多项式相加的过程也完全可以利用线性链表的基本操作来完成。1.2.4流程图 （1）在主函数中调用函数进行多项式的输入、输出，运用选择语句来选择加法、减法进行操作，流程图如图3：1输

7、入一一元多项式的项数n2YYN结束开始1：一元多项式的相加2：一元多项式的相减输入n个非零项再输入一一元多项式的项数依次输入n个非零项调用加法Dnodelist Addresult(Dnodelist D1,Dnodelist D2) /*多项式相加*/)；再输入一一元多项式的项数依次输入n个非零项调用减法Dnodelist Subresult(Dnodelist D1,Dnodelist D2)输出相加结果输出相减结果Y图3 主函数流程图1.3 系统设计1.3.1 功能算法描述与数据结构说明该多项式程序除了main()函数外，主要有以下函数：void Insert(Polyn p,Polyn

8、 h)Polyn CreatePolyn(Polyn head,int m)void DestroyPolyn(Polyn p)void PrintPolyn(Polyn P)int compare(Polyn a,Polyn b)Polyn AddPolyn(Polyn pa,Polyn pb)Polyn SubtractPolyn(Polyn pa,Polyn pb)Polyn MultiplyPolyn(Polyn pa,Polyn pb)1.3.2 系统主要功能函数的详细设计1.main（）函数main函数用来实现提示使用者输入、显示功能列表、调用其他运算函数实现运算功能。在main（

9、）函数中，定义m、n用来保存两个多项式的项数，pa、pb、pc、pd、pf定义程序所需链表的头指针。在程序开始要求输入两个多项式的项数，随后根据项数创建两个链表以保存多项式，再显示出功能列表后通过if语句来实现功能的选择，从而对整个程序流程进行控制。2. Polyn CreatePolyn(Polyn head,int m)该函数功能是创建新的多项式链表。int m保存的多项式的项数，使用for语句，控制输入多项式的每一项。当创建的链表长度为m时，将不再提示用户继续输入多项式的系数和指数。在该函数中要用到分配空间的函数malloc()为新建链表分配空间。3. void DestroyPolyn

10、(Polyn p)该函数的功能是销毁掉创建的两个链表，释放内存。以辅助退出程序。4. void Insert(Polyn p,Polyn h)该函数功能：将新的节点p插入到现有链表的后面，并确保多项式的指数exp是升序。将s节点插入到head所指向的链表。在该函数的操作中，要注意指针是如何移动的。5. Polyn AddPolyn(Polyn pa,Polyn pb)该函数功能：实现两个多项式pa、pb相加，并将计算结果存储于新建立的pc中，它的原理是将指数相同的单项式相加，系数相加后为0，则pa、pb的指针都后移。在加法计算中要求pa,与pb的幂次序都是升序，否则可能得到错误的结果。该函数调

11、用了int compare(Polyn a,Polyn b)的结果，用来判断多项式在同一指数下a、b是否有为系数为0。同样也使用了malloc()关键字，为新链表创建空间。6. int compare(Polyn a,Polyn b)该函数功能：判断两个多项式在同一指数下是否有其中一个为系数为0。用来辅助加法和乘法运算。7. Polyn SubtractPolyn(Polyn pa,Polyn pb)该函数功能：实现两个多项式pa、pb相减，其原理根加法类似，将指数相同的指数相减。与加法不同的是在送在减法中，创建了新的链表来存放结果，并返回该链表的头指针。8. void PrintPolyn(

12、Polyn P)该函数功能：显示多项式链表。在该函数中较复杂的是如何控制链表的输出，尤其是第一项的输出，同时还有符号的控制。在输出第一项时要判断是不是常数项，若是，则不要输出字符x。9. Polyn MultiplyPolyn(Polyn pa,Polyn pb)函数功能：实现两个多项式相乘，A(X) * B(x) 。计算时运用单项式与多项式相乘的法则，然后再次运用单项式与多项式相乘的法则。1.4系统实现该程序实现了多项式的创建、多项式的加法、减法、乘法运算以及多项式的清除。为完成这些功能，还用到了一些辅助函数。下面讨论重要函数具体实现过程及其参数的意义：（1）链表初始化函数Creat_nod

13、e()带有头结点的头指针指向空（NULL）。（2）多项式数据的创建函数Creat_Dmeth()当链表初始化成功后，开始创建多项式。分别循环输入两个多项式的系数和指数，其中要用到插入函数。（3）数据的插入函数Insert_node()当创建多项式时，要用到此函数，即利用插入的方式将多项式的数据连接起来。再输入一组数据后，程序自动调用此函数，插入时也进行着排序，从表头的next开始，一一比较指数大小，直到大于或等于当前指向的数据或遍历完所有数据时停止，然后开始链表中数值的插入，如果相等则直接将指数相加，如果大于就将新数据插入到当前指向的前面，否则将新数据插入到最后。（4）多项式的显示函数Show

14、()从多项式表头的next开始，直到指向空（NULL），将系数与指数一一显示。（5）选择运算方式的函数select()三种选择：1为相加，2为相减，每一种选择调用相应的运算函数。（6）多项式的运算函数：新建链表存储计算后的多项式1、多项式相加Addresult()创建两个指针分别指向两个多项式表头的next，分别使用两个while函数独自循环，遍历各自的每一组数据，每遍历一次都将系数与指数存储到新建多项式的链表中。因为存储时利用到插入函数，而插入函数中有相同指数的系数相加功能，所以直接将两个多项式的数据依次插入到新的多项式中即可完成多项式相加。2、多项式相减Subresult()创建两个指针分

15、别指向两个多项式表头的next，以两个指针同时不为空为条件循环遍历，如果当前多项式1的指数小于多项式2，则将当前多项式2的系数置负，指数不变，存入新建多项式中，指向多项式2的指针指向下一个；如果如果当前多项式1的指数大于多项式2，则将当前多项式1的系数指数不变，存入新建多项式中，指向多项式1的指针指向下一个；否则将多项式1的系数减去2的系数后存入新建多项式中，指数不变存入，再将两个指针同时指向下一个。结束循环后判断是哪一个多项式遍历完了，将未遍历完的多项式剩下的数据全部插入到新建多项式中。（7）主函数main()创建两个多项式的链表并且初始化，分别调用相应的多项式创建函数，创建成功后选择运算方

16、式，再将运算结果输出显示。5.其它函数的介绍请参见附录中详细代码1.5 调试及运行结果该程序在VC6.0中调试通过，没有错误和警告，运行结果经过检验为正确。下图即为该程序运行结果效果图。图中采用的是计算多项式2x2+3x1和3x2+2x3的加减两种运算进行演示：1.6源程序详见附录附录 一元多项式计算源代码#include<stdio.h>#include<stdlib.h>typedef struct nodeint xs;int zs;struct node * next;Dnode,* Dnodelist; /*定义结构体*/Dnodelist Creat_nod

17、e(void) /*链表初始化*/Dnodelist D;D=(Dnodelist)malloc(sizeof(Dnode);if(D)D->next=NULL;return D;int Insert_node(Dnodelist D,int xs,int zs) /*插入函数*/Dnodelist p;Dnodelist q;Dnodelist r;p=D;while(p->next) r=p;p=p->next;if(zs=p->zs) /*指数相等，系数直接相加，结束*/p->xs=p->xs+xs;return 1;else if(zs>p-&

18、gt;zs) /*指数大于当前数据的，将数据插入当前数据之前，结束*/q=Creat_node();q->xs=xs;q->zs=zs;r->next=q;q->next=p;return 1;/*while(p->next)*/q=Creat_node(); /*要插入的数据指数最小，直接插入至链表最后*/q->xs=xs;q->zs=zs;q->next=p->next;p->next=q;return 1;free(p);free(q);free(r);Dnodelist Creat_Dmeth(int length) /*创建

19、多项式*/int i,m,n;Dnodelist D;D=Creat_node();for(i=0;i<length;i+) /*以三组数据为例*/scanf("%d,%d",&m,&n);Insert_node(D,m,n); /*调用插入函数，将输入的系数指数插入链表*/return D;Dnodelist Addresult(Dnodelist D1,Dnodelist D2) /*多项式相加*/Dnodelist D;Dnodelist p,q;int x,z;D=Creat_node();p=D1->next;q=D2->next

20、;while(q)x=q->xs;z=q->zs;Insert_node(D,x,z);q=q->next;while(p)x=p->xs;z=p->zs;Insert_node(D,x,z);p=p->next; /*直接插入数据，利用插入函数可完成该功能*/return D;Dnodelist Subresult(Dnodelist D1,Dnodelist D2) /*多项式相减*/Dnodelist D;Dnodelist p,q;int x,z;D=Creat_node();p=D1->next;q=D2->next;while(p&a

21、mp;&q)if(p->zs)<(q->zs) /*指数小（1的数据在2中不存在），直接插入*/x=-(q->xs); /*由于是式1减式2，所以系数置负*/z=q->zs;Insert_node(D,x,z);q=q->next;else if(p->zs)>(q->zs) /*指数大（2的数据在1中不存在），直接插入*/ x=p->xs;z=p->zs;Insert_node(D,x,z);p=p->next;else /*指数相同的先将系数相减，再插入*/z=q->zs;x=(p->xs)-(q-

22、>xs);Insert_node(D,x,z);p=p->next;q=q->next;/*while(p&&q)*/while(p)x=p->xs;z=p->zs;Insert_node(D,x,z);p=p->next;while(q)x=-(q->zs);z=q->zs;Insert_node(D,x,z);q=q->next; /*将未遍历完的数据直接插入*/return D;Dnodelist select(Dnodelist D1,Dnodelist D2) /*选择函数*/Dnodelist D;int s; printf(" 一元多项式的计算 n"); printf("*Menu*n"); printf("* 1 多项式相加 2 多项式相减 *n"); printf("*n");scanf("%d",&s);switc