一元多项式相加问题的实验报告.doc
一元多项式相加问题一、 问题描述通过键盘输入两个形如P0+P1X1+P2X2+PnX的多项式，经过程序运后在屏幕上输出它们的相加和。二、数据结构设计一个一元多项式的每一个子项都由“系数-指数两局部组成，因此可将其抽象为包含系数coef、指数exp、指针域next构成的链式线性表。将两个多项式分别存放在两个线性表中，然后经过相加后将所得多项式存放在一个新的线性表中，但是不用再开辟新的存储空间，只依靠结点的移动来构成新的线性表，期间可以将某些不需要的空间回收。基于这样的分析，可以采用不带头结点的单链表来表示一个一元多项式。具体数据类型定义为：struct nodefloat coef; /系数域int exp; /指数域 struct node *next;三、 功能函数设计1、 输入多项式的系数和指数初始化多项式的功能模块具体函数为node *in_fun()此函数的处理较为全面，要求用户按照指数递增的顺序和一定的输入格式输入各个系数不为0的子项，输入一个子项建立一个相关结点，当遇到输入完毕标志时停止输入。关键步骤具体如下：控制用户按照指数递增的顺序输入r=a;while(r!=q->next)if(y<=r->exp) cout<<"请按照指数递增顺序输入,请重新输入"cin>>x>>y;break;r=r->next;从头开始遍历，假设遇到目前输入的指数不是最大时，就跳出循环，让用户重新输入。当输入的系数为零时，不为其分配存储空间存储while(x=0) cin>>x>>y; continue;即假设系数为0，不再进展动态分配并新建结点，而是重新提取用户输入的下一个子项的系数和指数，利用continue进入下一次循环。初始化完成后将最后一个结点的指针域置为空，并返回该新建链表的首地址。if(q!=NULL) q->next=NULL;return a;动态分配空间新建结点存储系数和指数的代码如下：p=new node;p->coef=x;p->exp=y;if(a=NULL) a=p;else q->next=p;q=p;2、 多项式显示功能函数由于系数有正有负，故采取如下处理：对于正数，输出时在前面加“+，头指针除外；对于负数，直接将系数输出即可，即：p=a;while(p)if(p=a) cout<<p->coef<<"*x"<<p->exp;else if(p->coef<0) cout<<p->coef<<"*x"<<p->exp;else if(p->coef>0) cout<<"+"<<p->coef<<"*x"<<p->exp;p=p->next;输出的多项式的形式形如：P1X1+P2X2+PnXn3、 多项式相加的功能函数函数为：node *plus_fun(node *a,node *b)此函数根据在1中初始化的两个多项式进展相加运算，并存放在以c为头指针的一个新链表中。设指针p,q,r分别指向描述多项式的链表a,b,c的头部，其中将a也赋给c。p,q两个指针同时移动，并根据p,q两结点对应的指数的大小采取不同的操作。当(p->exp)<(q->exp)时，操作如下：w=p;p=p->next;r->next=w;r=w;即定义一个结点w，将结点p赋给它，然后将p结点后移，指向a中下一个待处理结点，然后将w移动到新生成链表c的尾结点的后面，最后将w赋给r,使得r仍指向链表c的尾结点。当p->exp>q->exp时，采取如下操作：w=q;q=q->next;r->next=w;r=w;即此时将q赋给w,然后使q结点指向链表b中下一个待处理结点，然后将w移动到新生成链表c的尾结点的后面，最后将w赋给r,使得r仍指向链表c的尾结点。当p->exp=q->exp时，定义一个float类型的变量x，当x不为0时，采取如下操作：p->coef=x;w=p;p=p->next;r->next=w;r=w;w=q;q=q->next;delete w;即将x的值赋给p的系数域，之后将结点p赋给w，然后将p结点后移，指向a中下一个待处理结点，然后将w移动到新生成链表c的尾结点的后面，最后将w赋给r,使得r仍指向链表c的尾结点。同时，将q的存空间释放，并使得q指向b中下一个待处理结点。当x为0时，采取如下操作：w=p;p=p->next;delete w;w=q;q=q->next;delete w;即将pq的空间释放，并分别使其指向各自链表中下一个待处理结点。当上面的循环进展完后，至少有一个链表已被遍历完，然后只需将另一个链表剩余的所有结点都移动到c中即可。if(p!=NULL)while(p)w=p;p=p->next;r->next=w;r=w;if(q!=NULL)while(q)w=q;q=q->next;r->next=w;r=w;最后将c中的最后一个结点的指针域置为空,并返回c的地址。r->next=NULL;return c;4、 主函数功能设计采用循环的形式可以屡次进展两个多项式的初始化和求和。四、 界面设计提示用户进展每一步操作以与每一步输出的容，界面简明清晰。五、 运行与调试六、 源代码#include<iostream.h>struct nodefloat coef; /系数域int exp; /指数域 struct node *next;node *in_fun()node *p,*a,*q,*r;a=q=NULL;float x;int y;cin>>x>>y;while(x!=0|y!=0)while(x=0) cin>>x>>y;if(x=0&&y=0) break;else continue;if(x=0&&y=0) break;p=new node;p->coef=x;p->exp=y;if(a=NULL) a=p;else q->next=p;q=p;cin>>x>>y;if(x=0&&y=0) break;r=a;while(r!=q->next)if(y<=r->exp) cout<<"请按照指数递增顺序输入,请重新输入"cin>>x>>y;break;r=r->next;if(x=0&&y=0) break; if(q!=NULL) q->next=NULL;return a;void out_fun(node *a)node *p;p=a;while(p)if(p=a) cout<<p->coef<<"*x"<<p->exp;else if(p->coef<0) cout<<p->coef<<"*x"<<p->exp;else if(p->coef>0) cout<<"+"<<p->coef<<"*x"<<p->exp;p=p->next;cout<<endl;node *plus_fun(node *a,node *b)node *c,*p,*q,*r,*w;float x;p=a;q=b;c=a;r=c;while(p&&q)if(p->exp)<(q->exp)w=p;p=p->next;r->next=w;r=w;else if(p->exp=q->exp)x=p->coef+q->coef;if(x!=0)p->coef=x;w=p;p=p->next;r->next=w;r=w;w=q;q=q->next;delete w;else if(x=0)w=p;p=p->next;delete w;w=q;q=q->next;delete w;else if(p->exp>q->exp)w=q;q=q->next;r->next=w;r=w;if(p!=NULL)while(p)w=p;p=p->next;r->next=w;r=w;if(q!=NULL)while(q)w=q;q=q->next;r->next=w;r=w;r->next=NULL;return c;int main()node *a,*b,*c;int n=1;while(n)cout<<endl<<"-一元多项式相加问题-"<<endl;cout<<endl<<"请输入第一个多项式的系数和指数"<<endl;a=in_fun();cout<<endl<<"您所输入的多项式为"<<endl;out_fun(a);cout<<endl<<"请输入第二个多项式的系数和指数"<<endl;b=in_fun();cout<<endl<<"您所输入的多项式为"<<endl;out_fun(b);cout<<endl<<"初始化完毕，两多项式相加得"<<endl;c=plus_fun(a,b);out_fun(c);cout<<"继续初始化多项式请输入1，停止请输入0 "cin>>n;cout<<endl;while(n!=1&&n!=0)cout<<"输入错误，请重新输入:"cin>>n;cout<<endl;return 0;12 / 12
