一元多項式的加減求導(dǎo)運算算法(數(shù)據(jù)結(jié)構(gòu)算法)

1、實驗題目：一元多項式運算班級：13級數(shù)學(xué)一班 姓名： 張保昌 學(xué)號：2013433037 日期：20141009一、需求分析1問題描述；設(shè)計一個簡單的一元稀疏多項式加減及求導(dǎo)運算器。2 基本要求的功能要求； （1）輸入多項式時可以按任意次序輸入各項的數(shù)據(jù)（輸入并建立多項式A與B），不必按指數(shù)有序；在算法中實現(xiàn)建立按指數(shù)有序的多項式。 （2）計算多項式A與B的和，即建立多項式A+B。 （3）按照指數(shù)升序次序，輸出多項式A、B、A+B。 （4）計算多項式A與B的差，即建立多項式AB； （5） 計算多項式A的導(dǎo)函數(shù)A 。3 測試數(shù)據(jù)。 （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二、概要設(shè)計1本程序所用的抽象數(shù)據(jù)類型的定義；typedef struct pnode double coef;/*系數(shù)域*/int exp;/*指數(shù)域*/struct pnode *next;/*指針域，*/polynode, *polylink;polylink insert_list(

3、polylink h,char o); /輸入多項式。polylink order_list(polylink h); /按指數(shù)升序排列polylink simply_list(polylink h); /初步整理（合并多項式，并刪除系數(shù)為零的式子）polylink add(polylink a,polylink b); /加法運算polylink opposite(polylink b); /將減法統(tǒng)歸為加法polylink derivative(polylink a); /求導(dǎo)函數(shù)void list_display(polylink h,char o); /輸出顯示void index()

4、; /菜單函數(shù)2 模塊劃分。 1）主函數(shù)模塊。2）加法運算模塊 3）減法運算模塊 4）導(dǎo)數(shù)模塊。3 主模塊的流程及各子模塊的主要功能； 開始Mark? （2）減法運算（1）加法運算（3）求導(dǎo)運算輸入兩個多項式A 、B輸入多項式A 輸入兩個多項式A 、B初步簡化整理加法運算器初步簡化整理求導(dǎo)運算器初步簡化整理減法轉(zhuǎn)化加法輸出結(jié)果輸出結(jié)果三、詳細設(shè)計1采用c+語言定義相關(guān)的數(shù)據(jù)類型；typedef struct pnode double coef;/*系數(shù)域*/int exp;/*指數(shù)域*/struct pnode *next;/*指針域polynode, *polylink;Coef系數(shù)域Exp

5、指數(shù)域*next指針域2 寫出各模塊的偽碼算法；void index() /菜單函數(shù)。cout 一元多項式運算 endlendl;cout 1.一元多項式加法endl;cout 2.一元多項式減法endl;cout 3.一元多項式導(dǎo)數(shù)endl;cout 0. 結(jié)束 endlendlnext =NULL;/頭結(jié)點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) /初步化簡，系數(shù)無0，無重復(fù)指數(shù)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)/求導(dǎo)polylink ha;ha=a-next ;while(ha)ha-coef *=ha-exp ;ha-exp -;ha=ha-next ;return a; 四、調(diào)試分析1調(diào)試中遇到的問題及對問題的解決方法； 指針指向的錯誤。導(dǎo)致程序無法正常運行，經(jīng)過逐步調(diào)試

11、，發(fā)現(xiàn)了問題，認真分析指針指向的內(nèi)存空間。并做了合理的修改。2算法的時間復(fù)雜度和空間復(fù)雜度。 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、 使用說明及測試結(jié)果根據(jù)提示語輸入相應(yīng)的信息。如下為運行結(jié)果。 1） 菜單 2）加法3）減法4）導(dǎo)數(shù)六、源程序#includeusing namespace std;typedef struct pnode double coef;/*系數(shù)域*/int exp;/*指數(shù)域*/struct pnode *next;/*指針域，指向下一個系數(shù)不為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請輸入被減數(shù);A=insert_list(A,a);cout請輸入要減數(shù);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被減數(shù);list_display(A,a);cout減數(shù);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 一元多項式求導(dǎo)運算endl;A=insert_list(A,a);A=simply_list(A);A=order_list(A);list_display(A,a);cout其導(dǎo)數(shù)為: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.一元多項式導(dǎo)數(shù)endl;cout 0. 結(jié)束 endlendlnext =NULL;/頭結(jié)點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)/初步化簡，系數(shù)無0，無重復(fù)指數(shù)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