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

一元多项式相加问题一、问题描述通过键盘输入两个形如 P 0 +P 1X 1 +P 2X 2+…+P nX 的多项式,经过程序运后在屏幕上输出它们的相加和。二、数据结构设计一个一元多项式的每一个子项都由“系数- 指数”两部分组成, 因此可将其抽象为包含系数 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 中下一