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

《一元多项式的加减求导运算算法(数据结构算法)(13页).doc》由会员分享，可在线阅读，更多相关《一元多项式的加减求导运算算法(数据结构算法)(13页).doc（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-一元多项式的加减求导运算算法(数据结构算法)-第 13 页实验题目：一元多项式运算班级：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

2、）(x+3x68.6x11)+(63x6+21x9)=6+x+21x98.6x11 （2）(3x3x+4.1x29)(3x35.1x212)=xx2912 （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 pnodedouble coef;/*系数域*/int exp;/*指数域*/struct pnode *next;/*指针域，*/polynode, *polylink;polylink in

3、sert_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); /输出显示vo

4、id index(); /菜单函数2 模块划分。 1）主函数模块。2）加法运算模块 3）减法运算模块 4）导数模块。3 主模块的流程及各子模块的主要功能；开始Mark? （2）减法运算（1）加法运算（3）求导运算输入两个多项式A 、B输入多项式A 输入两个多项式A 、B初步简化整理加法运算器初步简化整理求导运算器初步简化整理减法转化加法输出结果输出结果三、详细设计1采用c+语言定义相关的数据类型；typedef struct pnodedouble coef;/*系数域*/int exp;/*指数域*/struct pnode *next;/*指针域polynode, *polylink;Co

5、ef系数域Exp指数域*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;te

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

7、r=q;q=q-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

8、=-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)cout-Xexpo1;else if(coef1=1)cout+X0)cout+coef1Xexpo1;elsecoutcoef1Xnext ;coutnext;if(!p)return h

9、;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;ha=simpl

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

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 l

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

13、k 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)c

14、out mark=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相加得

15、:endl;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)

16、;coutendl;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(

17、cls);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;re

18、turn 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

19、 ;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-X;elsecoutcoef1X;elsei=

20、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-next)q=p-next ;r=p;whil

21、e(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(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;