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

实验题目：一元多项式运算

班级：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）(3x3－x+4.1x2－1.2x9)＋(―3x3－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）导数模块。

页脚内容1

第二章 解一元二次方程

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

开始 Mark? （2） （1） 减法 加法 运算 运算 输入 输入 两个 两个 多项式 多项式 A 、B A 、B 加法 初步简 运算器 化整理

初步简减法转

化整理 化加法

输出结果 （3） 求导 运算 输入 多项式 A 初步简化整理 求导 运算器 输出结果 三、详细设计

1．采用c++语言定义相关的数据类型； typedef struct pnode {

double coef; /*系数域*/ int exp; /*指数域*/ struct pnode *next; /*指针域 }polynode, *polylink;

页脚内容2

第二章 解一元二次方程

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

2．写出各模块的伪码算法； void index() //菜单函数。 { cout<<\" 一元多项式运算 \"<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<<\"多项式\"<>num; for(int i=1;i<=num;i++) { cout<<\"请输入第\"<>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，无重复指数 {

页脚内容3

第二章 解一元二次方程

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

页脚内容4

第二章 解一元二次方程

} return h; }

void list_display(polylink h,char o) //显示多项式 { polylink p; double coef1; int expo1,i=0; p=h->next ; if(!p) { cout<<\"多项式\"<cout<<\"多项式\"<coef ; expo1=p->exp ; if(i==0) { if(expo1==0) { i=1; cout<页脚内容5

第二章 解一元二次方程

}

cout<0) cout<<\"+\"<0) cout<<\"+\"<next ; }

cout<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) {

页脚内容6

第二章 解一元二次方程

}

if(q->exp 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) {

页脚内容7

第二章 解一元二次方程

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） 菜单

页脚内容8

第二章 解一元二次方程

2）加法

页脚内容9

第二章 解一元二次方程

3）减法

页脚内容10

第二章 解一元二次方程

4）导数

六、源程序

#include 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) {

页脚内容11

第二章 解一元二次方程

cout<<\"请选择 --> mark=\"<<\" \"; cin>>mark; cin.get(); system(\"cls\"); switch(mark) {

case 1: A=B=C=NULL;

cout<<\" 一元多项式加法\"<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<<\" \"<cout<<\" cout<<\"被减数\"; list_display(A,a);

cout<<\"减数\";

页脚内容12

一元多项式加法 一元多项式减法\"<list_display(B,b); cout<cout<<\" 一元多项式求导运算\"<cout<<\"其导数为:\"<void index() {

cout<<\" 一元多项式运算 \"<polylink insert_list(polylink h,char o)//输入多项式 { h=new polynode; double coef1; int num,expo1; polylink temp;

页脚内容13

第二章 解一元二次方程

polynode *data; temp=h;

h->next =NULL;//头结点

cout<<\"多项式\"<>num;

for(int i=1;i<=num;i++) { cout<<\"请输入第\"<>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 ;

页脚内容14

第二章 解一元二次方程

}

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<<\"多项式\"<cout<<\"多项式\"<coef ; expo1=p->exp ; if(i==0) { if(expo1==0) {

页脚内容15

第二章 解一元二次方程

i=1; cout<0) cout<<\"+\"<0)

页脚内容16

第二章 解一元二次方程

}

cout<<\"+\"<next ; }

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

页脚内容17

第二章 解一元二次方程

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

页脚内容18