一元多项式的加减求导运算算法(数据结构算法).doc

实验题目：一元多项式运算
班级：13级数学一班 姓名： 张保昌 学号：2013433037 日期：2014—10—09
一、需求分析
1．问题描述；
设计一个简单的一元稀疏多项式加减及求导运算器。
2． 基本要求的功能要求；
（1）输入多项式时可以按任意次序输入各项的数据（输入并建立多项式A与B），不必按指数有序；在算法中实现建立按指数有序的多项式。
（2）计算多项式A与B的和，即建立多项式A+B。
（3）按照指数升序次序，输出多项式A、B、A+B。
（4）计算多项式A与B的差，即建立多项式A－B；
（5） 计算多项式A的导函数Aˊ 。
3． 测试数据。
（1）(x+3x6－8.6x11)+(6－3x6+21x9)=6+x+21x9－8.6x11
（2）(3x－3－x+4.1x2－1.2x9)＋(―3x―3－5.1x2 +7.8x12)=－x－x2－1.2x9+7.8x12
（3）(x+x3)+(―x―x3)=0
（4）(x+x2+x3)+0=x+x2+x3
（5）(x+x2+x3)—(x+x2+x3)=0
(6) (x+x2+x3)ˊ=1+2x+3x2
二、概要设计
1．本程序所用的抽象数据类型的定义；
typedef struct pnode
{
double coef; /*系数域*/
int exp; /*指数域*/
struct pnode *next; /*指针域，*/
}polynode, *polylink;
polylink insert_list(polylink h,char o); //输入多项式。
polylink order_list(polylink h); //按指数升序排列
polylink simply_list(polylink h); //初步整理（合并多项式，并删除系数为零的式子）
polylink add(polylink a,polylink b); //加法运算
polylink opposite(polylink b); //将减法统归为加法
polylink derivative(polylink a); //求导函数
void list_display(polylink h,char o); //输出显示
void index(); //菜单函数
2． 模块划分。
1）主函数模块。2）加法运算模块 3）减法运算模块 4）导数模块。

3． 主模块的流程及各子模块的主要功能；

开始
Mark?

（2）

减法
运算

（1）

加法
运算
（3）

求导
运算

输入
两个
多项式
A 、B

输入
多项式
A
输入
两个
多项式
A 、B

初步简化整理

加法
运算器

初步简化整理

求导
运算器

初步简化整理
减法转化加法

输出结果
输出结果

三、详细设计
1．采用c++语言定义相关的数据类型；
typedef struct pnode
{
double coef; /*系数域*/
int exp; /*指数域*/
struct pnode *next; /*指针域
}polynode, *polylink;

Coef
系数域
Exp
指数域
*next
指针域

2． 写出各模块的伪码算法；
void index() //菜单函数。
{
cout<<" 一元多项式运算 "<<endl<<endl;
cout<<" 1.一元多项式加法"<<endl;
cout<<" 2.一元多项式减法"<<endl;
cout<<" 3.一元多项式导数"<<endl;
cout<<" 0. 结束 "<<endl<<endl<<endl;
}
polylink insert_list(polylink h,char o) //输入多项式
{
h=new polynode;
double coef1;
int num,expo1;
polylink temp;
polynode *data;
temp=h;
h->next =NULL;//头结点
cout<<"多项式"<<o<<"的项数 : ";
cin>>num;
for(int i=1;i<=num;i++)
{
cout<<"请输入第"<<i<<"项"<<endl;
cout<<"系数 :";
cin>>coef1;
cout<<"指数 :";
cin>>expo1;
data=new polynode;
data->coef=coef1;
data->exp =expo1;
data->next =NULL;
temp->next =data;
temp=data;
}
return h;
}
polylink simply_list(polylink h) //初步化简，系数无0，无重复指数
{
polylink p,q,r,k;
p=h->next ;
if(!p)
return h; //空表
while(p)
{
k=p;
q=k->next ;
while(q)
{
if(q->exp==p->exp )
{
r=q;
q=q->next ;
p->coef +=r->coef ;
k->next =r->next ;
delete r;
}
else
{
q=q->next ;
k=k->next;
}

}
p=p->next ;
}
k=h;
q=h->next ;
while(q)
{
if( q ->coef==0)
{
r=q;
q=q->next ;
k->next =r->next ;
delete r;
}
else
{
q=q->next ;
k=k->next ;
}

}
return h;
}
void list_display(polylink h,char o) //显示多项式
{
polylink p;
double coef1;
int expo1,i=0;
p=h->next ;
if(!p)
{
cout<<"多项式"<<o<<" : 0 "<<endl;
}
else
cout<<"多项式"<<o<<" : ";
while(p)
{
coef1=p->coef ;
expo1=p->exp ;
if(i==0)
{
if(expo1==0)
{
i=1;
cout<<coef1;
}
else if(expo1==1)
{
i=1;
if(coef1==1)
cout<<"X";
else if(coef1==-1)
cout<<"-X";
else
cout<<coef1<<"X";
}
else
{
i=1;
if(coef1==1)
cout<<"X^"<<expo1;
else if(coef1==-1)
cout<<"-X^"<<expo1;
else
cout<<coef1<<"X^"<<expo1;
}
}
else
{
if(expo1==1)
{
if(coef1==1)
cout<<"+X";
else if(coef1==-1)
cout<<"-X";
else if(coef1>0)
cout<<"+"<<coef1<<"X";
else
cout<<coef1<<"X";
}
else
{
if(coef1==-1)
cout<<"-X^"<<expo1;
else if(coef1==1)
cout<<"+X^"<<expo1;
else if(coef1>0)
cout<<"+"<<coef1<<"X^"<<expo1;
else
cout<<coef1<<"X^"<<expo1;
}
}
p=p->next ;
}
cout<<endl;
}
polylink order_list(polylink h) //升序排列
{
polynode temp;
polylink p,q,r;
p=h->next;
if(!p)return h;
while(p->next)
{
q=p->next ;
r=p;
while(q)
{
if(q->exp <r->exp )
r=q;
q=q->next ;
}
temp.coef =r->coef ;
temp.exp =r->exp ;
r->coef =p->coef ;
r->exp =p->exp ;
p->coef =temp.coef ;
p->exp =temp.exp ;
p=p->next ;
}
return h;
}

polylink add(polylink ha,polylink hb)//加法
{
polylink a;
a=ha;
while(a->next )
a=a->next ;
a->next =hb->next ;
delete hb;
ha=simply_list(ha);
ha=order_list(ha);
return ha;
}
polylink opposite(polylink b)
{
polylink hb;
hb=b->next;
while(hb)
{
hb->coef =(-1)*hb->coef;
hb=hb->next ;
}
return b;
}
polylink derivative(polylink a)//求导
{
polylink ha;
ha=a->next ;
while(ha)
{
ha->coef *=ha->exp ;
ha->exp --;
ha=ha->next ;
}
return a;
}

四、调试分析
1．调试中遇到的问题及对问题的解决方法；
指针指向的错误。导致程序无法正常运行，经过逐步调试，发现了问题，认真分析指针指向的内存空间。并做了合理的修改。
2．算法的时间复杂度和空间复杂度。
polylink order_list(polylink h); O(n²)
polylink simply_list(polylink h); O(n²)
polylink add(polylink a,polylink b); O(n²)
polylink opposite(polylink b);// O(n)
polylink insert_list(polylink h,char o) O(n)
polylink derivative(polylink a); //O(n)
void list_display(polylink h,char o); O(n)
void index(); O(1)

五、 使用说明及测试结果

根据提示语输入相应的信息。
如下为运行结果。 1） 菜单

2）加法

3）减法

4）导数

六、源程序
#include<iostream>
using namespace std;
typedef struct pnode
{
double coef; /*系数域*/
int exp; /*指数域*/
struct pnode *next; /*指针域，指向下一个系数不为0的子项*/
}polynode, *polylink;
polylink insert_list(polylink h,char o);
polylink order_list(polylink h);
polylink simply_list(polylink h);
polylink add(polylink a,polylink b);
polylink opposite(polylink b);
polylink derivative(polylink a);
void list_display(polylink h,char o);
void index();
void main()
{
index();
int mark=1;
polylink A=NULL,B=NULL,C=NULL;
char a='A',b='B',c='C',Da='d';
while(mark)
{
cout<<"请选择 --> mark="<<" ";
cin>>mark;
cin.get();
system("cls");
switch(mark)
{
case 1:
A=B=C=NULL;
cout<<" 一元多项式加法"<<endl<<endl;
cout<<"请输入";
A=insert_list(A,a);
B=insert_list(B,b);
A=simply_list(A);
A=order_list(A);
B=simply_list(B);
B=order_list(B);
cin.get();
system("cls");
cout<<" 一元多项式加法"<<endl<<endl;
list_display(A,a);
list_display(B,b);
cout<<endl;
cout<<"多项式A与B相加得:"<<endl;
C=add(A,B);
list_display(C,c);
break;
case 2:
A=B=C=NULL;
cout<<" 一元多项式减法"<<endl<<endl;
cout<<"请输入被减数";
A=insert_list(A,a);
cout<<"请输入要减数";
B=insert_list(B,b);
A=simply_list(A);
A=order_list(A);
B=simply_list(B);
B=order_list(B);
cin.get();
system("cls");
cout<<" 一元多项式减法 "<<endl<<endl;
cout<<"被减数";
list_display(A,a);
cout<<"减数";
list_display(B,b);
cout<<endl;
cout<<"多项式(A-B)得:"<<endl;
B=opposite(B);
C=add(A,B);
list_display(C,c);
break;
case 3:
A=NULL;
cout<<" 一元多项式求导运算"<<endl;
A=insert_list(A,a);
A=simply_list(A);
A=order_list(A);
list_display(A,a);
cout<<"其导数为:"<<endl;
A=derivative(A);
list_display(A,Da);
system(“pause”)
break;
default:
break;

}
if(mark==0)
break;
cin.get();
system("cls");
index();
}
}
void index()
{
cout<<" 一元多项式运算 "<<endl<<endl;
cout<<" 1.一元多项式加法"<<endl;
cout<<" 2.一元多项式减法"<<endl;
cout<<" 3.一元多项式导数"<<endl;
cout<<" 0. 结束 "<<endl<<endl<<endl;
}
polylink insert_list(polylink h,char o)//输入多项式
{
h=new polynode;
double coef1;
int num,expo1;
polylink temp;
polynode *data;
temp=h;
h->next =NULL;//头结点
cout<<"多项式"<<o<<"的项数 : ";
cin>>num;
for(int i=1;i<=num;i++)
{
cout<<"请输入第"<<i<<"项"<<endl;
cout<<"系数 :";
cin>>coef1;
cout<<"指数 :";
cin>>expo1;
data=new polynode;
data->coef=coef1;
data->exp =expo1;
data->next =NULL;
temp->next =data;
temp=data;
}
return h;
}
polylink simply_list(polylink h)//初步化简，系数无0，无重复指数
{
polylink p,q,r,k;
p=h->next ;
if(!p)
return h;//空表
while(p)
{
k=p;
q=k->next ;
while(q)
{
if(q->exp==p->exp )
{
r=q;
q=q->next ;
p->coef +=r->coef ;
k->next =r->next ;
delete r;
}
else
{
q=q->next ;
k=k->next;
}
}
p=p->next ;
}
k=h;
q=h->next ;
while(q)
{
if( q ->coef==0)
{
r=q;
q=q->next ;
k->next =r->next ;
delete r;
}
else
{
q=q->next ;
k=k->next ;
}
}
return h;
}
void list_display(polylink h,char o)//显示
{
polylink p;
double coef1;
int expo1,i=0;
p=h->next ;
if(!p)
{
cout<<"多项式"<<o<<" : 0 "<<endl;
}
else
cout<<"多项式"<<o<<" : ";
while(p)
{
coef1=p->coef ;
expo1=p->exp ;
if(i==0)
{
if(expo1==0)
{
i=1;
cout<<coef1;
}
else if(expo1==1)
{
i=1;
if(coef1==1)
cout<<"X";
else if(coef1==-1)
cout<<"-X";
else
cout<<coef1<<"X";
}
else
{
i=1;
if(coef1==1)
cout<<"X^"<<expo1;
else if(coef1==-1)
cout<<"-X^"<<expo1;
else
cout<<coef1<<"X^"<<expo1;
}
}
else
{
if(expo1==1)
{
if(coef1==1)
cout<<"+X";
else if(coef1==-1)
cout<<"-X";
else if(coef1>0)
cout<<"+"<<coef1<<"X";
else
cout<<coef1<<"X";
}
else
{
if(coef1==-1)
cout<<"-X^"<<expo1;
else if(coef1==1)
cout<<"+X^"<<expo1;
else if(coef1>0)
cout<<"+"<<coef1<<"X^"<<expo1;
else
cout<<coef1<<"X^"<<expo1;
}
}
p=p->next ;
}
cout<<endl;
}
polylink order_list(polylink h)//升序排列
{
polynode temp;
polylink p,q,r;
p=h->next;
if(!p)return h;
while(p->next)
{
q=p->next ;
r=p;
while(q)
{
if(q->exp <r->exp )
r=q;
q=q->next ;
}
temp.coef =r->coef ;
temp.exp =r->exp ;
r->coef =p->coef ;
r->exp =p->exp ;
p->coef =temp.coef ;
p->exp =temp.exp ;
p=p->next ;
}
return h;
}

polylink add(polylink ha,polylink hb)//加法
{
polylink a;
a=ha;
while(a->next )
a=a->next ;
a->next =hb->next ;
delete hb;
ha=simply_list(ha);
ha=order_list(ha);
return ha;
}
polylink opposite(polylink b)
{
polylink hb;
hb=b->next;
while(hb)
{
hb->coef =(-1)*hb->coef;
hb=hb->next ;
}
return b;
}
polylink derivative(polylink a)//求导
{
polylink ha;
ha=a->next ;
while(ha)
{
ha->coef *=ha->exp ;
ha->exp --;
ha=ha->next ;
}
return a;
}