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

1、实验题目：一元多项式运算班级：13级数学一班 姓名： 张保昌 学号：2013433037 日期：20141009一、需求分析1问题描述；设计一个简单的一元稀疏多项式加减及求导运算器。2 基本要求的功能要求； （1）输入多项式时可以按任意次序输入各项的数据（输入并建立多项式A与B），不必按指数有序；在算法中实现建立按指数有序的多项式。 （2）计算多项式A与B的和，即建立多项式A+B。 （3）按照指数升序次序，输出多项式A、B、A+B。 （4）计算多项式A与B的差，即建立多项式AB； （5） 计算多项式A的导函数A 。3 测试数据。 （1）(x+3x68.6x11)+(63x6+21x9)=6+x

2、+21x98.6x11 （2）(3x3x+4.1x21.2x9)(3x35.1x2 +7.8x12)=xx21.2x9+7.8x12 （3）(x+x3)+(xx3)=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(

3、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()

4、; /菜单函数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

5、指数域*next指针域2 写出各模块的伪码算法；void index() /菜单函数。cout 一元多项式运算 endlendl;cout 1.一元多项式加法endl;cout 2.一元多项式减法endl;cout 3.一元多项式导数endl;cout 0. 结束 endlendlnext =NULL;/头结点cout多项式onum;for(int i=1;i=num;i+)cout请输入第i项endl;coutcoef1;coutexpo1;data=new polynode;data-coef=coef1;data-exp =expo1;data-next =NULL;temp-next

6、=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;elseq=q-next ;k=k-next;p=p-next ;k=h;q=h-next ;while(q)if( q -coef=0)r=q;q=q-

7、next ;k-next =r-next ;delete r;elseq=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;elsecout多项式ocoef ;expo1=p-exp ;if(i=0)if(expo1=0)i=1;coutcoef1;else if(expo1=1)i=1;if(coef1=1)coutX;else if(coef1=-1)cout

8、-X;elsecoutcoef1X;elsei=1;if(coef1=1)coutXexpo1;else if(coef1=-1)cout-Xexpo1;elsecoutcoef1Xexpo1;elseif(expo1=1)if(coef1=1)cout+X;else if(coef1=-1)cout0)cout+coef1X;elsecoutcoef1X;elseif(coef1=-1)cout-Xexpo1;else if(coef1=1)cout+X0)cout+coef1Xexpo1;elsecoutcoef1Xnext ;coutnext;if(!p)return h;while(p

9、-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;ha=simply_list(h

10、a);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调试中遇到的问题及对问题的解决方法； 指针指向的错误。导致程序无法正常运行，经过逐步调试

11、，发现了问题，认真分析指针指向的内存空间。并做了合理的修改。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_dis

12、play(polylink h,char o); O(n) void index(); O(1)5、 使用说明及测试结果根据提示语输入相应的信息。如下为运行结果。 1） 菜单 2）加法3）减法4）导数六、源程序#includeusing namespace std;typedef struct pnode double coef;/*系数域*/int exp;/*指数域*/struct pnode *next;/*指针域，指向下一个系数不为0的子项*/polynode, *polylink;polylink insert_list(polylink h,char o);polylink ord

13、er_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 m

14、ark=mark;cin.get();system(cls);switch(mark)case 1:A=B=C=NULL;cout 一元多项式加法endlendl;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 一元多项式加法endlendl;list_display(A,a);list_display(B,b);coutendl;cout多项式A与B相加得:endl

15、;C=add(A,B);list_display(C,c);break;case 2:A=B=C=NULL;cout 一元多项式减法endlendl;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 一元多项式减法 endlendl;cout被减数;list_display(A,a);cout减数;list_display(B,b);cout

16、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);

17、index();void index()cout 一元多项式运算 endlendl;cout 1.一元多项式加法endl;cout 2.一元多项式减法endl;cout 3.一元多项式导数endl;cout 0. 结束 endlendlnext =NULL;/头结点cout多项式onum;for(int i=1;i=num;i+)cout请输入第i项endl;coutcoef1;coutexpo1;data=new polynode;data-coef=coef1;data-exp =expo1;data-next =NULL;temp-next =data;temp=data;return

18、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;elseq=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 ;del

19、ete r;elseq=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;elsecout多项式ocoef ;expo1=p-exp ;if(i=0)if(expo1=0)i=1;coutcoef1;else if(expo1=1)i=1;if(coef1=1)coutX;else if(coef1=-1)cout-X;elsecoutcoef1X;elsei=1;if(coef1=1)coutXexpo1;else if(coef1=-1)cout-Xexpo1;elsecoutcoef1Xexpo1;elseif(expo1=1)if(coef1=1)cout+X;else if(coef1=-1)cout0)cout+coef1X;elsecoutcoef1X;elseif(coef1=-1)c