實(shí)驗(yàn)一-一元多項(xiàng)式運(yùn)算

1、實(shí)驗(yàn)一 - 一元多項(xiàng)式運(yùn)算實(shí)驗(yàn)一 一元多項(xiàng)式的運(yùn)算1. 問題定義及需求分析1.1 課題目的和任務(wù)問題描述：設(shè)計(jì)一個一元多項(xiàng)式簡單計(jì)算器。實(shí)驗(yàn)要求：1) 采用順序表或鏈表等數(shù)據(jù)結(jié)構(gòu)。2) 輸入并建立多項(xiàng)式。3) 輸出運(yùn)算結(jié)果的多項(xiàng)式。1.2 數(shù)據(jù)形式輸入數(shù)據(jù)形式：通過鍵盤輸入。輸入值的范圍：多項(xiàng)式的項(xiàng)數(shù)和指數(shù)的輸入數(shù)據(jù)為 int 型，輸入值范圍 為-32768 至 32767；多項(xiàng)式系數(shù)的輸入值范圍為 float 型，范圍為 1.2e-38 至 3.4e+38 。輸出數(shù)據(jù)形式：輸出到顯示器。1.3 程序功能實(shí)現(xiàn)兩個一元多項(xiàng)式之間的加法、減法和乘法運(yùn)算。1.4 測試數(shù)據(jù)4/第一個多項(xiàng)式的項(xiàng)數(shù)1 4

2、/第一項(xiàng)的系數(shù)和指數(shù)3 3/第二項(xiàng)的系數(shù)和指數(shù)-2 2/第三項(xiàng)的系數(shù)和指數(shù)6 0/第四項(xiàng)的系數(shù)和指數(shù)5/第二個多項(xiàng)式的項(xiàng)數(shù)-3 5/第一項(xiàng)的系數(shù)和指數(shù)2 2/第二項(xiàng)的系數(shù)和指數(shù)-6 0/第三項(xiàng)的系數(shù)和指數(shù)-1 -1/第四項(xiàng)的系數(shù)和指數(shù)1.2 -2/第五項(xiàng)的系數(shù)和指數(shù)2. 概要設(shè)計(jì)2.1 抽象數(shù)據(jù)類型需要定義一個多項(xiàng)式類型的數(shù)據(jù)類型，里面包含一個 int 型的指數(shù) 和一個 float 型的系數(shù)，再定義一個多項(xiàng)式節(jié)點(diǎn)，里面包含一個多項(xiàng)式 類型的數(shù)據(jù)， 和一個指向下一個節(jié)點(diǎn)的指針。 通過對多項(xiàng)式節(jié)點(diǎn)的操作， 實(shí)現(xiàn)對輸入數(shù)據(jù)的運(yùn)算。開始1加法運(yùn)算3乘法運(yùn)算結(jié)束輸出運(yùn)算后 的多項(xiàng)式 PrintPolyn

3、()2.2 主程序流程及各模塊之間的調(diào)用關(guān)系輸出第一個 多項(xiàng)式PrintPolyn()輸入第一個 多項(xiàng)式的項(xiàng) 數(shù)創(chuàng)建多項(xiàng)式CreatPolyn()輸出第一個 多項(xiàng)式PrintPolyn()創(chuàng)建多項(xiàng)式CreatPolyn()輸入第二個 多項(xiàng)式的項(xiàng) 數(shù)Menu()2減法運(yùn)算選擇操作加法運(yùn)算AddPolyn()減法運(yùn)算SubtractPolyn()乘法運(yùn)算MultiplyPolyn()3. 詳細(xì)設(shè)計(jì)3.1 存儲結(jié)構(gòu)實(shí)現(xiàn)多項(xiàng)式結(jié)構(gòu)體： typedef struct float coef; int expn;Poly;typedef struct LNodePoly data; struct LNode

4、* next;LNode,*LinkList; 多項(xiàng)式類型的定義： typedef LinkList polynomial;3.2 負(fù)責(zé)模塊的偽碼算法1)int MultiplyPolyn(polynomial& a,polynomial& b)/多項(xiàng)式相乘if(a,b 中均沒有項(xiàng) )return 0; c=(polynomial)malloc(sizeof(LNode);/ 開辟一個 c 儲存相乘結(jié)果 c-next=NULL;ha=a-next;/ha 為 a 中的項(xiàng)hb=b-next;/hb 為 b 中的項(xiàng)for( ； hb 不空；下一項(xiàng) )/ 將 a 中第一項(xiàng)與 b 中所有項(xiàng)相乘 ha

5、的系數(shù) *hb 的系數(shù)； ha 的指數(shù) *hb 的指數(shù)；開辟一個新節(jié)點(diǎn) E，將數(shù)據(jù)存入，并把 E 連到 c 后Sort(c);/ 對 c 中多項(xiàng)式排序 ha=ha-next;/ha 指向下一個項(xiàng) while(ha!=NULL)/將 a 中第二項(xiàng)與 b 中所有項(xiàng)相乘，存入 d，然后將c 和 d相加得到新的 c，再以此對 a中其余各項(xiàng)做相同操作，最終得到乘法 運(yùn)算后的 chb=b-next;/hb為 b 的第一項(xiàng)d=(polynomial)malloc(sizeof(LNode);/ 開辟一個 d 儲存 相乘結(jié)果d-next=NULL;for(； hb 不空；下一項(xiàng) )/ 將 a 中第一項(xiàng)與 b

6、中所有項(xiàng)相乘ha的系數(shù) *hb 的系數(shù) ;ha的指數(shù) *hb 的指數(shù) ;開辟一個新節(jié)點(diǎn) E，將數(shù)據(jù)存入，并把 E連到 d 后;Sort(d);/ 對 d 中多項(xiàng)式排序ha=ha-next;/ha指向下一項(xiàng)AddPolyn(c,d);/將 c ， d 相加得到新的 ct=a;a=c;/a 指向運(yùn)算結(jié)果DestroyPolyn(b);/ 銷毀初始的兩個多項(xiàng)式DestroyPolyn(t);(2)void DestroyPolyn(polynomial& L)/銷毀多項(xiàng)式while(L!=NULL)p=L;L=L-next;/ 指向后一項(xiàng)free(p);( 3) void Sort(polynomi

7、al& L)/對多項(xiàng)式的指數(shù)進(jìn)行冒泡排序for( 多項(xiàng)式長度 )for(j=L;j-next-next!=NULL;j=j-next)if(j-next 指數(shù) next-next 指數(shù) )/ 將大的冒到前面 p=j-next;q=j-next-next;p-next=q-next;q-next=p;j-next=q;4. 調(diào)試分析4.1 問題分析與解決方法(1) 多項(xiàng)式相乘對于多項(xiàng)式相乘， 考慮到兩個一元多項(xiàng)式的相乘， 可以利用兩個一元多 項(xiàng)式相加的算法來實(shí)現(xiàn)， 因?yàn)槌朔ㄟ\(yùn)算可以分解為一系列的加法運(yùn)算， 所以 只需循環(huán)執(zhí)行加法運(yùn)算，就可以完成多項(xiàng)式的相乘。例如A(x)和 B( x)為一元多項(xiàng)式

8、，則有：M x A x B xA x b1xe1 b2xe1 L bnxennbi A x xeii1其中，每一項(xiàng)都是一個一元多項(xiàng)式。（2）銷毀多項(xiàng)式銷毀多項(xiàng)式只需要判斷多項(xiàng)式中的項(xiàng)是否為空，不為空就將指針后移， 然后釋放剛才的儲存空間，當(dāng)為空時結(jié)束循環(huán)。（3）對多項(xiàng)式各項(xiàng)進(jìn)行排序 通過冒泡排序?qū)崿F(xiàn)多現(xiàn)實(shí)各項(xiàng)的指數(shù)的排序，冒泡排序的實(shí)現(xiàn)過程為： 多項(xiàng)式中有多少項(xiàng)就進(jìn)行多少次的排序， 第一次排序遍歷一遍所有項(xiàng)， 進(jìn)行 比較大小，將最大的項(xiàng)調(diào)整到鏈表最前端，然后依次遍歷，排完所有項(xiàng)。4.2 算法的時空分析（1）多項(xiàng)式相乘假設(shè)多項(xiàng)式 a 長度為 m，多項(xiàng)式 b長度為 n，因?yàn)樾枰獙蓚€表中的所 有元

9、素進(jìn)行操作，所以時間復(fù)雜度為 O mn ， 需要建立兩個臨時表 c，d 來存儲運(yùn)算數(shù)據(jù)，因此空間復(fù)雜度為 O n 。（2）銷毀多項(xiàng)式時間復(fù)雜度為 O n ， 空間復(fù)雜度為 O 1 。（3）冒泡排序時間復(fù)雜度為 O n2 ， 空間復(fù)雜度為 O 1 。4.3 算法的改進(jìn)設(shè)想對于多項(xiàng)式中項(xiàng)的排序， 可以采用更高效的排序算法來實(shí)現(xiàn)， 因?yàn)檩斎?多項(xiàng)式中不含有指數(shù)相同的項(xiàng)（指數(shù)相同的項(xiàng)在運(yùn)算中會被合并） ，因此可 以采用時間性能更好的快速排序來實(shí)現(xiàn)。4.4 經(jīng)驗(yàn)和體會在算法設(shè)計(jì)中，有很多問題是可以相互轉(zhuǎn)化的，例如對于乘法運(yùn)算 的算法設(shè)計(jì)，因?yàn)槌朔ㄔ醋杂诩臃ǎ钥梢詫⑶蟪朔ǖ膯栴}轉(zhuǎn)化為求 一系列加法的問

10、題，從而使問題得到簡化，更有利于解決。因此，在編 程過程中，應(yīng)當(dāng)多注意事物之間的內(nèi)在聯(lián)系，從而抽絲剝繭，簡化問題， 有利于問題的求解。5. 使用說明按照屏幕提示，通過鍵盤輸入數(shù)據(jù)，數(shù)據(jù)與數(shù)據(jù)之間用空格隔開，一組數(shù) 據(jù)輸入完畢后，回車結(jié)束。6. 測試結(jié)果（截屏）（1） 多項(xiàng)式相乘2) 多項(xiàng)式排序(冒泡排序)7. 附錄7.1 個人負(fù)責(zé)模塊的程序代碼int MultiplyPolyn(polynomial& a,polynomial& b)/ 多項(xiàng)式相乘/ 將 a 的每項(xiàng)分別和 b 所有項(xiàng)相乘，再將它們 相加void Sort(polynomial& L);/ 函數(shù)聲明 void DestroyPo

11、lyn(polynomial& ); polynomial ha=NULL,hb=NULL,c=NULL; Poly e;if(a-next=NULL|b-next=NULL)return0;/ 若多項(xiàng)式中無項(xiàng)，則返回c=(polynomial)malloc(sizeof(LNode);/開辟 c，存儲第一次運(yùn)算結(jié)果c-next=NULL;ha=a-next;hb=b-next;for(;hb!=NULL;hb=hb-next)/ 將 b 中 每項(xiàng)都與 a 的第一項(xiàng)相乘e.coef=(ha-data.coef)*(hb-data.coef);e.expn=(ha-data.expn)+(hb-

12、data.expn); polynomial E=NULL;E=(polynomial)malloc(sizeof(LNode);E-data.coef=e.coef;E-data.expn=e.expn;E-next=c-next;c-next=E;/ 將每項(xiàng)結(jié)果保存在 c中Sort(c);/ 序處理ha=ha-next;/ while(ha!=NULL)/ 別與 b 中各項(xiàng)相乘 hb=b-next; polynomial d;對 c 中項(xiàng)的指數(shù)進(jìn)行排指向下一項(xiàng)將 a 中其余各項(xiàng)分d=(polynomial)malloc(sizeof(LNode);d-next=NULL;for(;hb!=

13、NULL;hb=hb-next)/ 用 d 儲存 a 中后一項(xiàng)和 b 中所有項(xiàng)的乘積e.coef=(ha-data.coef)*(hb-data.coef);e.expn=(ha-data.expn)+(hb-data.expn); polynomial E=NULL;E=(polynomial)malloc(sizeof(LNode);E-data.coef=e.coef;E-data.expn=e.expn;E-next=d-next;d-next=E;Sort(d);ha=ha-next;AddPolyn(c,d);/ 將 c， d 兩項(xiàng)相加，得到合并后的 cpolynomial t=a

14、;a=c;DestroyPolyn(b);/ 銷毀臨時存儲空間DestroyPolyn(t);return 1;void DestroyPolyn(polynomial& L)/銷毀線性表while(L!=NULL) polynomial p; p=L; L=L-next; free(p);void Sort(polynomial& L)/ 冒泡排序 polynomial i,j; for(i=L;i-next!=NULL;i=i-next)/ 總次數(shù)for(j=L;j-next-next!=NULL;j=j-next) / 第一趟if(j-next-data.expnnext-next-da

15、 ta.expn)/ 比較大小，將大的冒到前面 polynomial p,q;p=j-next; q=j-next-next; p-next=q-next; q-next=p; j-next=q;7.2 程序全部代碼 #include #include #include #define TRUE 1; #define FALSE 0; using namespace std; typedef structfloat coef;int expn;Poly; typedef struct LNodePoly data;struct LNode* next;LNode,*LinkList;typed

16、ef LinkList polynomial;int main()/ 主函數(shù)/ 函數(shù)聲明void CreatPolyn(polynomial& ,int );void DestroyPolyn(polynomial& );void const PrintPolyn(polynomial );intAddPloyn(polynomial& ,polynomial& );intSubtractPloyn(polynomial& ,polynomial&);intMultiplyPloyn(polynomial& ,polynomial& );voidMenu(polynomial& ,polyno

17、mial& );/ 定義int n=1;while(n=0)polynomial a;polynomial b;system(cls);printf( 請輸入第一個多項(xiàng)式的項(xiàng)數(shù) ( 輸 入負(fù)數(shù)退出)：);scanf(%d,&n);if(n0)exit(0);CreatPolyn(a,n);PrintPolyn(a);printf( 請輸入第二個多項(xiàng)式的項(xiàng)數(shù) (輸 入負(fù)數(shù)退出)：);scanf(%d,&n);if(nnext=NULL;Poly e;int i=1;for(;n0;n-,i+) printf(請輸入第 %d,i);printf(項(xiàng)的系數(shù)和指數(shù) :);scanf(%f%d,&e.c

18、oef,&e.expn); polynomial E=NULL;E=(polynomial)malloc(sizeof(LNode); E-data.coef=e.coef;E-data.expn=e.expn; E-next=L-next;L-next=E;Sort(L);intSubtractPolyn(polynomial&Pa,polynomial &Pb)/ 多 項(xiàng) 式 減 法 ： Pa=Pa-Pbpolynomial ha=NULL,hb=NULL,p=NULL; ha=Pa;hb=Pb; if(ha-next=NULL)Pa=Pb; free(ha); return 0; els

19、e while(hb-next!=NULL) if(ha-next-data.expnnext-data.e xpn)polynomial p,q; p=hb-next; q=p-next;p-data.coef=0-p-data.coef; p-next=ha-next;ha-next=p;hb-next=q;ha=ha-next;else if(ha-next-data.expn=hb-next-data. expn)ha-next-data.coef=ha-next-data.coef -hb-next-data.coef;p=hb-next; hb-next=hb-next-next;

20、 free(p);elseha=ha-next;if(ha-next=NULL)hb-next-data.coef=0-hb-next-data.co ef;ha-next=hb-next; hb-next=NULL;free(hb);return 0;void const PrintPolyn(polynomial P)/ 輸出多項(xiàng)式polynomial a;a=P-next;/ 開始輸出while(a-next)printf(%gx%d+,a-data.coef,a-data.expn); a=a-next;/ 輸出最后一個printf(%gx%dn,a-data.coef,a-data.

21、 expn);int AddPolyn(polynomial &Pa,polynomial &Pb)/ 多項(xiàng)式加法： Pa=Pa+Pbpolynomial ha=NULL,hb=NULL,p=NULL;ha=Pa;hb=Pb;if(ha-next=NULL)Pa=Pb; free(ha); return 0; else while(hb-next!=NULL)if(ha-next-data.expnnext-data.e xpn)polynomial p,q;p=hb-next;q=p-next;p-next=ha-next;ha-next=p;hb-next=q;ha=ha-next;els

22、e if(ha-next-data.expn=hb-next-data. expn)ha-next-data.coef=ha-next-data.coef +hb-next-data.coef;p=hb-next; hb-next=hb-next-next; free(p);elseha=ha-next; if(ha-next=NULL) ha-next=hb-next;hb-next=NULL;free(hb);return 0;int MultiplyPolyn(polynomial& a,polynomial& b)/多項(xiàng)式相乘void Sort(polynomial& L);void

23、DestroyPolyn(polynomial& ); polynomial ha=NULL,hb=NULL,c=NULL; Poly e;if(a-next=NULL|b-next=NULL)return 0;c=(polynomial)malloc(sizeof(LNode); c-next=NULL;ha=a-next;hb=b-next;for(;hb!=NULL;hb=hb-next)e.coef=(ha-data.coef)*(hb-data.coef);e.expn=(ha-data.expn)+(hb-data.expn); polynomial E=NULL;E=(polynomial)malloc(sizeof(LNode);E-data.coef=e.