一元多项式相加问题的实验报告.doc
文本预览下载声明
一元多项式相加问题
问题描述
通过键盘输入两个形如P0+P1X1+P2X2+…+PnX
的多项式，经过程序运后在屏幕上输出它们的相加和。
二、数据结构设计
一个一元多项式的每一个子项都由“系数-指数”两部分组成，因此可将其抽象为包含系数coef、指数exp、指针域next构成的链式线性表。将两个多项式分别存放在两个线性表中，然后经过相加后将所得多项式存放在一个新的线性表中，但是不用再开辟新的存储空间，只依靠结点的移动来构成新的线性表，期间可以将某些不需要的空间回收。基于这样的分析，可以采用不带头结点的单链表来表示一个一元多项式。具体数据类型定义为：
struct node
{
float coef; //系数域
int exp; //指数域
struct node *next;
};
功能函数设计
输入多项式的系数和指数初始化多项式的功能模块
具体函数为node *in_fun()
此函数的处理较为全面，要求用户按照指数递增的顺序和一定的输入格式输入各个系数不为0的子项，输入一个子项建立一个相关结点，当遇到输入结束标志时停止输入。关键步骤具体如下：
⑴控制用户按照指数递增的顺序输入
r=a;
while(r!=q-next)
{
if(y=r-exp)
{
cout请按照指数递增顺序输入,请重新输入;
cinxy;
break;
}
r=r-next;
}
从头开始遍历，若遇到目前输入的指数不是最大时，就跳出循环，让用户重新输入。
⑵当输入的系数为零时，不为其分配存储空间存储
while(x==0) { cinxy; 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;
多项式显示功能函数
由于系数有正有负，故采取如下处理：
对于正数，输出时在前面加“+”，头指针除外；对于负数，直接将系数输出即可，即：
p=a;
while(p)
{
if(p==a) coutp-coef*x^p-exp;
else if(p-coef0) coutp-coef*x^p-exp;
else if(p-coef0) cout+p-coef*x^p-exp;
p=p-next;
}
输出的多项式的形式形如：P1X^1+P2X^2+…+PnX^n
多项式相加的功能函数
函数为：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-expq-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;
delet
显示全部