一元多项式相加问题实验报告

　一元多项式相加问题 一、 问题描述 通过键盘输入两个形如 P 0 +P 1 X 1 +P 2 X 2 +…+P n X 的多项式，经过程序运后在屏幕上输出它们的相加和。

　二、数据结构设计 一个一元多项式的每一个子项都由“系数-指数”两部分组成，因此可将其抽象为包含系数 coef、指数 exp、指针域 next 构成的链式线性表。将两个多项式分别存放在两个线性表中，然后经过相加后将所得多项式存放在一个新的线性表中，但是不用再开辟新的存储空间，只依靠结点的移动来构成新的线性表，期间可以将某些不需要的空间回收。基于这样的分析，可以采用不带头结点的单链表来表示一个一元多项式。具体数据类型定义为：

　struct node {

　float 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;

　} 输出的多项式的形式形如：P 1 X^1+P 2 X^2+…+P n X^n 3、 多项式相加的功能函数 函数为：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 node {

　float 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; }

推荐访问： 多项式 相加 实验