数据结构课程设计实验报告专业班级：学号：姓名：2011年1月1日题目：一元多项式的运算1、题目描述一元多项式的运算在此题中实现加、减法的运算，而多项式的减法可以通过加法来实现（只需在减法运算时系数前加负号）。

在数学上，一个一元n次多项式P n(X)可按降序写成：P n(X)= P n X^n+ P(n-1)X^(n-1)+......+ P1X+P0它由n+1个系数惟一确定，因此，在计算机里它可以用一个线性表P来表示：P=(P n，P(n-1)，......，P1，P0)每一项的指数i隐含在其系数P i的序号里。

假设Q m(X)是一元m次多项式，同样可以用一个线性表Q来表示：Q=(q m,q(m-1)，.....，q1，q0)不是一般性，假设吗吗m<n，则两个多想是相加的结果：R n(X)= P n(X)+ Q m(X)很显然，可以对P,Q和R采用顺序存储结构，使得多项式相加的算法定义和实现简单化。

然而，在通常的应用中，多项式的次数可能变化很大而且很高，使得顺序存储结构的最大长度很难确定。

特别是在处理项数少且次数特别高的情况下，对内存空间的浪费是相当大的。

因此，一般情况下，都采用链式存储结构来处理多项式的运算，使得两个线性链表分别表示一元多项式P n(X)和Q m(X)，每个结点表示多项式中的一项。

通过分析多项式的特征，不难看出多项式是由单项式构成的，而每个单项式都具有系数和指数，当系数为0时，该项就是去了意义，在计算机内要表示一个多项式，至少具有以下数据信息：系数信息、指数信息和指向下一个单项式的指针。

通过指针，我们就可以把多个单项式连接起来，形成一个多项式。

2、任务要求系数定义的是float型，范围是3.4*10^-38~3.4*10^38;指数定义的是int型，范围是-2147483648~+2147483647；输入多项式系数及指数，系统会自动将系数转化为浮点型。

功能：（1）．提示输入数据。

要求先输入多项式的项数。

（2）．创建多项式。

接收输入的数据，并保存到链表中。

（3）．显示已经创建好的多项式。

（4）．实现加、减法运算。

（5）.退出程序3、概要设计(1)链表结点的类型定义(2)建立有序链表void CreatPolyn(LinkList &L,int n)(3)多项式链表的相加void AddPolyn(LinkList La,LinkList Lb,LinkList &Lc)(4)多项式链表的输出void printList(LinkList L)4、详细设计(1)链表结点的类型定义typedef struct //在struct前使用关键字typedef，表示是声明新类型{float coef; //系数int expn; //指数}DataType; //DataType是新类型typedef struct node //单链表的存储{DataType data; //数据域struct node *next; //指向下一个结点}ListNode,*LinkList; //ListNode是结点的新类型，LinkList是指向ListNode类型的结点的指针类型(2)建立有序链表要实现多项式的加法运算，首先要建立多项式的存储结构，每一个一元多项式的存储结构就是一个有序单链表。

有序链表的基本操作定义与线性链表有两处不同，一个是结点的查找定位操作LocateNode有所不同，二是结点的插入操作InsertNode不同，这两个操作算法分别如下：//结点的查找定位int LocateNode(LinkList L,DataType e,int &q){ListNode *p=L->next;q=0;//记录结点位置序号while(p&&e.expn<p->data.expn){p=p->next;q++;}if(p==NULL||e.expn!=p->data.expn)return 0;elsereturn 1;}void InsertNode(LinkList &L,DataType e,int q)函数功能：将新的节点p插入到现有链表的后面，并确保多项式的指数expn是升序。

将s节点插入到e所指向的链表。

在该函数的操作中，要注意指针是如何移动的。

//有序链表结点的插入void InsertNode(LinkList &L,DataType e,int q){ListNode *s,*p;int i=0;p=L;while(p->next && i<q){p=p->next;i++;}//查找插入位置s=(ListNode*)malloc(sizeof(ListNode));s->data.coef=e.coef;s->data.expn=e.expn;s->next=p->next;p->next=s;}有了上述两个“结点的查找定位算法”和“有序链表结点的插入算法”，int n保存的多项式的项数，使用for语句，控制输入多项式的每一项。

当创建的链表长度为n时，将不再提示用户继续输入多项式的系数和指数。

建立一个一元多项式的单链表的具体算法如下：//多项式链表的建立void CreatPolyn(LinkList &L,int n){LinkList pa; //定义一个头指针为pa链表int i,q; //i用来计输入的项数，q指结点的位置序号DataType e; //插入的值epa=(ListNode*)malloc(sizeof(ListNode)); //生成链表头结点pa->next=NULL;for(i=1;i<=n;i++){scanf("%f,%d",&e.coef,&e.expn);if(!LocateNode(pa,e,q)) //当前链表中不存在该指数项InsertNode(pa,e,q); //调用InsertNode函数插入结点}L=pa;}(3)多项式链表的相加根据一元多项式相加的运算规则：对于一元多项式中所有指数相同的项，对应系数相加，若其和不为零，则构成“和多项式”中的一项；对于两个一元多项式中所有指数不相同的项，则分别复制到“和多项式”中相应的位置。

根据以上运算规则，其实现算法思路如下：假设pc为指向“和多项式链表”当前尾结点的指针，指针pa和pb分别指向两个多项式中当前进行比较的某个结点，则比较两个结点中的指数项值，有下面三种情况：1.若指针pa所指结点的指数值大于指针pb所指结点的指数值，则取pa指针所指向的结点插入到pc指针所指结点之后，分别修改指针pa和pc，使之指向链表的下一个结点；2.若指针pa所指结点的指数值小于指针pb所指结点的指数值，则取pb指针所指向的结点插入到pc指针所指结点之后，分别修改指针pb和pc，使之指向链表的下一个结点；3.若指针pa所指结点的指数值等于指针pb所指结点的指数值，则将两结点中的系数相加，如果其和数不为零，则修改pa指针所指结点中的系数值，将其结点插入到pc指针所指结点之后，分别修改pa、pb和pc，使之指向各自链表的下一个结点，同时删除并释放指针pb原先指向各自链表的下一个结点；如果和数为零，保存pa和pb所指向的结点，修改pa和pb指针使之指向各自链表的下一个结点，然后释放保存的两个结点。

再比较指针pa 和pb指向节点中的指数项值，分3种情况进行处理…..这样的操作一直继续到pa或pb等于NULL为止。

最后将未结束的链表后面剩余的节点连接到pc指针所指向结点之后。

上述多项式的相加过程和两个有序链表合并的过程类似，不同之处仅在于多项式的比较多了相等比较后的操作。

因此，多项式相加的过程完全可以利用线性链表的基本操作来实现。

具体实现多项式相加的算法如下：//多项式链表的相加void AddPolyn(LinkList La,LinkList Lb,LinkList &Lc){ //两个有序链表La和Lb表示的多项式相加ListNode *pa,*pb,*pc,*s;float sum;pa=La->next;pb=Lb->next; //pa和pb分别指向两个链表的开始结点Lc=pc=La; //用La的头结点作为Lc的头结点while (pa&&pb){if(pa->data.expn > pb->data.expn){pc->next=pa;pc=pa;pa=pa->next;}else if(pa->data.expn < pb->data.expn){pc->next=pb;pc=pb;pb=pb->next;}else {sum=pa->data.coef+pb->data.coef;if(fabs(sum)>0){ //系数和不为零pa->data.coef=sum;pc->next=pa;pc=pa;pa=pa->next;s=pb;pb=pb->next;free(s);}else{s=pa;pa=pa->next;free(s);s=pb;pb=pb->next;free(s);}}}pc->next=pa?pa:pb;//插入链表剩余部分free(Lb);//释放Lb的头结点}(4) 多项式链表的输出void printList(LinkList L)函数功能：显示多项式链表。

在输出项中使用了条件表达式，当系数项为正数时，在系数前输出一个“+”号，否则输出一个空格，而负数的负号还照常输出，使得输出结果尽量与原多项式的表示形式类似。

因此，输出多项式链表的算法实现如下：//多项式链表的输出void printList(LinkList L){ListNode *p;p=L->next;while(p){printf("%c %fx^ %d",(p->data.coef>0? '+':' '),p->data.coef,p->data.expn);p=p->next;}printf("\n");}源程序代码：#include <stdio.h>#include <stdlib.h>#include <math.h>//多项式链表结点类型定义typedef struct //在struct前使用关键字typedef，表示是声明新类型{float coef; //系数int expn; //指数}DataType; //DataType是新类型typedef struct node //单链表的存储{DataType data; //数据域struct node *next; //指向下一个结点}ListNode,*LinkList; //ListNode是结点的新类型，LinkList是指向ListNode类型的结点的指针类型//结点的查找定位int LocateNode(LinkList L,DataType e,int &q){ListNode *p=L->next;q=0;//记录结点位置序号while(p&&e.expn<p->data.expn){p=p->next;q++;}if(p==NULL||e.expn!=p->data.expn)return 0;elsereturn 1;}//有序链表结点的插入void InsertNode(LinkList &L,DataType e,int q){ListNode *s,*p;int i=0;p=L;while(p->next && i<q){p=p->next;i++;}s=(ListNode*)malloc(sizeof(ListNode));s->data.coef=e.coef;s->data.expn=e.expn;s->next=p->next;p->next=s;}//多项式链表的建立void CreatPolyn(LinkList &L,int n){LinkList pa; //定义一个头指针为pa链表int i,q; //i用来计输入的项数，q指结点的位置序号DataType e; //插入的值epa=(ListNode*)malloc(sizeof(ListNode)); //生成链表头结点pa->next=NULL;for(i=1;i<=n;i++){scanf("%f,%d",&e.coef,&e.expn);if(!LocateNode(pa,e,q)) //当前链表中不存在该指数项InsertNode(pa,e,q); //调用InsertNode函数插入结点}L=pa;}//多项式链表的输出void printList(LinkList L){ListNode *p;p=L->next;while(p){printf("%c %fx^ %d",(p->data.coef>0? '+':' '),p->data.coef,p->data.expn);p=p->next;}printf("\n");}//多项式链表的相加void AddPolyn(LinkList La,LinkList Lb,LinkList &Lc){ //两个有序链表La和Lb表示的多项式相加ListNode *pa,*pb,*pc,*s;float sum;pa=La->next;pb=Lb->next;//pa和pb分别指向两个链表的开始结点Lc=pc=La;//用La的头结点作为Lc的头结点while (pa&&pb){if(pa->data.expn > pb->data.expn){pc->next=pa;pc=pa;pa=pa->next;}else if(pa->data.expn < pb->data.expn){pc->next=pb;pc=pb;pb=pb->next;}else {sum=pa->data.coef+pb->data.coef;if(fabs(sum)>0){//系数和不为零pa->data.coef=sum;pc->next=pa;pc=pa;pa=pa->next;s=pb;pb=pb->next;free(s);}else{s=pa;pa=pa->next;free(s);s=pb;pb=pb->next;free(s);}}}pc->next=pa?pa:pb;//插入链表剩余部分free(Lb);//释放Lb的头结点}//主控函数void main(){LinkList La,Lb,Lc;int n;printf("输入第一个多项式的项数:");scanf("%d",&n);printf("输入第一个多项式的每一项的系数,指数:\n");CreatPolyn(La,n);printf("第一个多项式为:");printList(La);printf("输入第二个多项式的项数:");scanf("%d",&n);printf("输入第二个多项式的每一项的系数,指数:");CreatPolyn(Lb,n);printf("第二个多项式为:");printList(Lb);AddPolyn(La,Lb,Lc);printf("\n相加后的和多项式为:");printList(Lc);}5、调试分析此一元多项式的运算程序，只能实现一元多项式的加、减法，不能实现一元多项式的乘法，而且若想计数多个多项式的和或者差的话，必须退出界面重新开始计算。