一元多项式相加问题实验报告.doc
文本预览下载声明
一元多项式相加问题
一．问题描述
设计算法实现一元多项式的简单运算。
二．数据结构设计
分析任意一元多项式的描述方法可知，一个一元多项式的每一个子项都由“系数---指数”两部分组成，所以可以将它抽象成一个由“系数----指数对”构成的线性表。基于这样的分析，可以采用一个带有头结点的单链表来表示一个一元多项式。具体数据类型定义为：
typedef struct node{
float cofe; //系数域
int exp; //指数域
struct node* next; //指针域 指向下一个子项
}*polynode,poly;
Polynode head_a,head_b,head_c;
这三个指针分别作为链表A，B和C的头指针。
三．功能设计
1.输入并建立多项式的功能模块
此模块要求按照“系数---指数对”的输入格式输入各个子项，输入一个子项，通过遍历链表比较指数的大小，将新结点插在合适的位置，使多项式的指数按递增的顺序存储。当遇到输入结束标志是停止输入，而转去执行程序下面的部分。具体函数构造为：
polynode creat_polynode(){
polynode A ,p,q,s; //建立这种类型的头指针，尾指针，遍历指针和动态指针
float a;
int b;
A=new poly;
A-next=NULL;
q=A;
p=A;
cina;
cinb;
while(a!=0||b!=0)
{
s=new poly;
s-cofe=a;
s-exp=b;
while(q-next)
{
if(q-next-expb)
q=q-next; //遍历链表，若指数大于原链表指数，指针后移一个
else{
s-next=q-next;
q-next=s;
break; //若不是，将结点插入指针后面
}
}
if(q-next==NULL)
{
s-next=p-next;
p-next=s;
p=s; //q遍历到链表尾仍未插入，将结点插入最后，改变尾指针使其指向新结点
}
q=A; //让q返回头指针处，以便下一次遍历链表
cina;
cinb;
}
if(p!=NULL)
p-next=NULL;
return A;
}
2.多项式相加的功能模块
此模块根据在1中建立的两个多项式进行相加运算，并存放在以C为头指针的一个新链表中。可以采用如下方法进行设计：
设指针p,q,r分别指向描述多项式的链表A,B,C头部，比较p-exp与q-exp；若p-exp小，则做如下操作：
while(p!=NULLq!=NULL) //在两个指针不为空的情况下
{
r=new poly;
if(p-expq-exp)
{
r-cofe=p-cofe;
if(r-cofe==0)
{
delete r;
p=p-next;
continue; //若r指向的系数为，则p前进，释放r并强制执行下一次循环
}
r-exp=p-exp;
r-next=s-next;
s-next=r;
s=r;
p=p-next; //p指针指向的指数小，将此结点赋给r，p指针前进
}
若p-exp=q-exp，则：
else
if(p-exp==q-exp)
{
r-cofe=p-cofe+q-cofe; //若两指针指数部分相等，则系数相加赋给r
if(r-cofe==0)
{
delete r;
p=p-next;
q=q-next;
continue;
}
r-exp=p-exp;
r-next=s-next;
s-next=r;
s=r;
p=p-next;
q=q-next; //两指针均前进
}
若p-expq-exp,则：
else
if(p-expq-exp)
{
r-cofe=q-cofe;
if(r-cofe==0)
{
delete r;
q=q-next;
continue;
}
r-exp=q-exp;
r-next=s-next;
s-next=r;
s=r;
q=q-next;
}
}
在两个指针中有一个为空以后，可以进行如下操作将多项式中剩余项赋到C中：
while(p==NU
显示全部