一元多項式的加減求導運算算法(數據結構算法)

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、，發(fā)現了問題，認真分析指針指向的內存空間。并做了合理的修改。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