两个多项式相加实验报告

1、两个多项式相加实验报告主要实验内容：根据所学的数据结构中线性结构(线性表)的逻辑特性和物理特性及相关算法应用于求解一个具体的实际问题两个多项式相加一、运行环境：visualC+二、需求分析掌握线性结构的逻辑特性和物理特性掌握线性结构的各种相关算法掌握将算法转换成程序的方法和步骤掌握采用线性结构解决实际问题。三、概要设计1、抽象数据类型一元多项式的定义如下：数据对象：=W,中的每个元素包含一个表示系数的实数和表示指数的整数数据关系：=W,且中的指数值V中的指数值基本操作：操作结果：输入项的系数和指数，建立一元多项式P。初始条件：一元多项式P已存在。操作结果：销毁一元多项式P。初始条件：一元多项式

2、P已存在。操作结果：打印输出一元多项式P。初始条件：一元多项式P已存在。操作结果：返回一元多项式P中的项数。初始条件：一元多项式和已存在。操作结果：完成多项式相加运算，即：+a并销毁一元多项式。元多项式的实现：/用带表头结点的有序链表表示多项式结点的数据元素类型定义为:项的表示系数intexpn;指数term,/ElemType;四、详细设计线性表的应用-多项式相加问题多项式的相加操作是线性表处理的典型例子。在数学上，一个多项式可写成下列形式：P（x）=anxn+an-lxn-l+alx+aO（其中ai为xi的非零系数）在多项式相加时，至少有两个或两个以上的多项式同时并存，而且在实现运算的过程

3、中所产生的中间多项式和结果多项式的项数和次数都是难以预料的。因此计算机实现时，可采用单链表来表示。多项式中的每一项为单链表中的一个结点，每个结点包含三个域：系数域、指数域和指针域，其形式如下：coefexpne.现在设有两个多项式：A（x）=l2+3x2+5x3+8x4B（x）=5+6x5它们的链表结构见图2-5。-1图2-5-多1项式的单链表结构多项式相加的运算规则为：两个多项式中所有指数相同的项，对应系数相加，若和不为零，则构成“和多项式”中的一项；所有指数不同的项均复制到“和多项式”中。实现时，可采用另建多项式的方法，也可采用把一个多项式归并到另一个多项式中去的方法。这里介绍后一种方法。

4、下面是一个完整的C程序，包含三个算法：PolyAdd、Creat_Linkst和Print_Linkst。核心算法PolyAdd是把分别由pa和pb所指的两个多项式相加，结果为pa所指的多项式。相加时，首先设两个指针变量qa和qb分别从多项式的首项开始扫描（见图2-5-1）,比较qa和qb所指结点指数域的值，可能出现下列三种情况之一：（1）qa-exp大于qb-exp，则qa继续向后扫描。（2）qa-exp等于qb-exp,则将其系数相加。若相加结果不为零，将结果放入qa-coef中，并删除qb所指结点，否则同时删除qa和qb所指结点。然后qa、qb继续向后扫描。（3）qa-exp小于qb-e

5、xp,则将qb所指结点插入qa所指结点之前，然后qa、qb继续向后扫描。扫描过程一直进行到qa或qb有一个为空为止，然后将有剩余结点的链表接在结果链表上。所得pa指向的链表即为两个多项式之和。算法Creat_Linkst是建立表示多项式的单链表。建立链表的过程是一个动态生成的过程，即从“空表”的初始状态起，依次输入数据元素，每输入一个就生成一个新结点并插入到表尾。为了方便新结点的插入，算法中设置一个指针pre使其始终指向当前链表的表尾结点，初始指向pa（见图2-5-1）。五、测试数据及结果：六、源程序(带注释)#include#includestructlistintpower;intcoef

6、f;structlist*next;typedefstructlistnode;typedefnode*poly;voidprintPoly(polyhead)polypointer;pointer=head;while(pointer!=NULL)/*节点结构声明*/*多项式中变量的幂*/*多项式中变量的系数*/*临时指针变量*/*打印各节点*/printf(%d,%d,pointer-coeff,pointer-power);pointer=pointer-next;printf(n);/*从键盘输入一个多项式的项数和各项的幂和系数*/polycreatePoly(polyhead)pol

7、ynewNode;/*临时节点*/polypointer;intn,i;intcoeffTemp,powerTemp;/*临时变量*/head=(poly)malloc(sizeof(node);/*内存配置*/if(head=NULL)printf(MemoryallocateFailure!n);/*内存配置失败*/elseprintf(“请输入要创建的多项式的项数：n);scanf(%d,&n);if(n=0)returnNULL;printf(请按x降幕依次输入各项的系数和幕：n);scanf(%d%d,&coeffTemp,&powerTemp);/*输入多项式一项的系数和幂*/he

8、ad-coeff=coeffTemp;/*定义首节点*/head-power=powerTemp;head-next=NULL;pointer=head;for(i=1;icoeff=coeffTemp;newNode-power=powerTemp;newNode-next=NULL;pointer-next=newNode;/*将新定义的节点连接到原链表的表尾*/pointer=newNode;/*pointer指针后移*/printPoly(head);returnhead;voidfreeList(polyhead)polypointer;/*临时指针变量*/while(head!=N

9、ULL)pointer=head;head=head-next;free(pointer);polyaddPoly(polyhead1,polyhead2)polypointer1,pointer2,pointer,newNode,head;/*临时指针变量*/pointer1=head1;pointer2=head2;head=(poly)malloc(sizeof(node);pointer=head;while(pointer1!=NULL)|(pointer2!=NULL)/if(pointer1!=NULL&pointer2!=NULL&(pointer1-powerpointer2

10、-power)newNode=(poly)malloc(sizeof(node);newNode-power=pointer1-power;newNode-coeff=pointer1-coeff;newNode-next=NULL;pointer-next=newNode;pointer=newNode;pointer1=pointer1-next;if(pointer1!=NULL&pointer2!=NULL&(pointer1-powerpower)newNode=(poly)malloc(sizeof(node);newNode-power=pointer2-power;newNod

11、e-coeff=pointer2-coeff;newNode-next=NULL;pointer-next=newNode;pointer=newNode;/*指向存储结果的链表的指针后移*/pointer2=pointer2-next;if(pointer1!=NULL&pointer2!=NULL&(pointer1-power=pointer2-power)newNode=(poly)malloc(sizeof(node);newNode-power=pointer1-power;newNode-coeff=pointer1-coeff+pointer2-coeff;newNode-ne

12、xt=NULL;pointer-next=newNode;pointer=newNode;/*指向存储结果的链表的指针后移*/pointer1=pointer1-next;pointer2=pointer2-next;if(pointer1=NULL&pointer2!=NULL)newNode=(poly)malloc(sizeof(node);newNode-power=pointer2-power;newNode-coeff=pointer2-coeff;newNode-next=NULL;pointer-next=newNode;pointer=newNode;/*指向存储结果的链表的

13、指针后移*/pointer2=pointer2-next;if(pointer2=NULL&pointer1!=NULL)newNode=(poly)malloc(sizeof(node);newNode-power=pointer1-power;newNode-coeff=pointer1-coeff;newNode-next=NULL;pointer-next=newNode;pointer=newNode;pointer1=pointer1-next;pointer=head;head=head-next;free(pointer);return(head);voidmain()polyp,q,r;printf(这是多项式p:n);p=createPoly(p);printf(这是多项式q:n);q=