試驗一-一元多項式運(yùn)算

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

2、項的系數(shù)和指數(shù)-2 2/第三項的系數(shù)和指數(shù)6 0/第四項的系數(shù)和指數(shù)5/第二個多項式的項數(shù)-3 5/第一項的系數(shù)和指數(shù)2 2/第二項的系數(shù)和指數(shù)-6 0/第三項的系數(shù)和指數(shù)-1 -1/第四項的系數(shù)和指數(shù)1.2 -2/第五項的系數(shù)和指數(shù)2概要設(shè)計2.1抽象數(shù)據(jù)類型需要定義一個多項式類型的數(shù)據(jù)類型，里面包含一個int型的指數(shù)和一個float型的系數(shù)，再定義一個多項式節(jié)點，里面包含一個多項式 類型的數(shù)據(jù)，和一個指向下一個節(jié)點的指針。 通過對多項式節(jié)點的操作， 實現(xiàn)對輸入數(shù)據(jù)的運(yùn)算。開始1加法運(yùn)算3乘法運(yùn)算結(jié)束2.2主程序流程及各模塊之間的調(diào)用關(guān)系輸出第一個 多項式Prin tPoly n()輸入第一

3、個 多項式的項 數(shù)1創(chuàng)建多項式CreatPoly n()1r輸出第一個 多項式Prin tPoly n()1r創(chuàng)建多項式CreatPoly n()輸入第二個 多項式的項 數(shù)V12減法運(yùn)算1選擇操作加法運(yùn)算AddPoly n()減法運(yùn)算SubtractPoly n()乘法運(yùn)算MultiplyPoly n()輸出運(yùn)算后 的多項式Prin tPoly n()3詳細(xì)設(shè)計3.1存儲結(jié)構(gòu)實現(xiàn)多項式結(jié)構(gòu)體：typedef structfloat coef;int exp n;Poly;typedef struct LNodePoly data;struct LNode* n ext;LNode,*Li nk

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

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

6、節(jié)點E,將數(shù)據(jù)存入，并把E連到d后；Sort(d);/對d中多項式排序ha=ha->n ext;/ha指向下一項AddPolyn(c,d);將c, d相加得到新的ct=a;a=c;/a指向運(yùn)算結(jié)果DestroyPoly n(b);銷毀初始的兩個多項式DestroyPoly n( t);(2) void DestroyPolyn(polynomial& L)/銷毀多項式 while(L!=NULL)P=L;L=L-> next;/指向后一項free(p); (3) void Sort(polynomial& L)/ 對多項式的指數(shù)進(jìn)行冒泡排序 for( 多項式長度)f

7、or(j=L;j->n ext- >n ext!=NULL;j=j->n ext)if(j->next指數(shù)<j->next->next指數(shù))/將大的冒到前面p=j->n ext;q=j->n ext- >n ext; p->n ext=q->n ext;q->n ext=p; j->n ext=q; 4. 調(diào)試分析4.1問題分析與解決方法(1) 多項式相乘對于多項式相乘，考慮到兩個一元多項式的相乘，可以利用兩個一元多 項式相加的算法來實現(xiàn)，因為乘法運(yùn)算可以分解為一系列的加法運(yùn)算， 所以 只需循環(huán)執(zhí)行加法運(yùn)算，就

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

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

10、使問題得到簡化，更有利于解決。因此，在編 程過程中，應(yīng)當(dāng)多注意事物之間的內(nèi)在聯(lián)系，從而抽絲剝繭，簡化問題， 有利于問題的求解。5. 使用說明按照屏幕提示，通過鍵盤輸入數(shù)據(jù)，數(shù)據(jù)與數(shù)據(jù)之間用空格隔開，一組數(shù) 據(jù)輸入完畢后，回車結(jié)束。6. 測試結(jié)果（截屏）（1）多項式相乘潔轍丄岸誠的系樹諸就1 4：請嫡入第的系聶和娥心3請輸片寡3頊的系剪和韋罰;-2 2請輸入第口貝的系數(shù)和奮數(shù)瀉 . . .M2 *1x"4 2x2 +Isk' J請輸入男二個英項武的項故(輸.扎負(fù)數(shù)退出) 5請輸入篦1頂?shù)南禂?shù)和獪數(shù):壬5譜輸人第頁他系擁Q看覲盤2情輸入第頑的系數(shù)和猶數(shù)T 0諳輸人舅妙的累蟻杓冷荻

11、：-1 -1請輸入鴿河的系數(shù)和指竝：1上-2-Gt Q +2k 2 +-3s 5 Is - +L.辦-21.多項我相如云多項式北偏農(nóng)參項式相奉：1 , Answer = Tx"9 廠9*"8 的k"7 吃u飛 +-L2k'5 +-10x4 +-'''3 +22. 2k2 十仏 +-38.x 0 +-6i -1 +7- 2x -2歯按社意縫蝕擴(kuò)，一一(2)多項式排序(冒泡排序)101 51 31 61 -21 -41 01 -11 11 21 4lx 6 +lx 5 +lx 4 +1k 3 +lx"2 +lx 1 +lx&q

12、uot;0 +lx"-l +lx -2 +lx -4Process returned 0 （0x0） eKecuticn time : 40. 138 s Press any key to continue.7附錄7.1個人負(fù)責(zé)模塊的程序代碼intMultiplyPoly n(poly nomia l&a,pol yno mial & b)多項式相乘/將a的每項分別和b所有項相乘，再將它們 相加void Sort(poly nomia l& L);函數(shù)聲明void DestroyPoly n(poly nomial& );poly nomial ha=

13、NULL,hb=NULL,c=NULL;Poly e;if(a-> next=NULL|b-> next=NULL)retur n0;/若多項式中無項，則返回c=(poly no mial)malloc(sizeof(LNode);開辟c,存儲第一次運(yùn)算結(jié)果c->n ext=NULL;ha=a->n ex t;hb=b->n ex t;for(;hb!=NULL;hb=hb->next)/將 b 中每項都與a的第一項相乘e.coef=(ha->data.coef)*(hb->data.coef);e.exp n=(ha->data.exp

14、n)+(hb->data.exp n); polyn omial E=NULL;E=(poly nomial)malloc(sizeof(LNode);E->data.coef=e.coef;E->data.exp n=e.exp n;E->n ext=c- >next;c->n ext=E;將每項結(jié)果保存在c中Sort(c);/序處理ha=ha->next; / while(ha!=NULL) 別與b中各項相乘 hb=b->n ex t; polyn omial d;對c中項的指數(shù)進(jìn)行排指向下一項將a中其余各項分d=(poly no mial)

15、malloc(sizeof(LNode); d->n ext=NULL;for(;hb!=NULL;hb=hb->next)用 d 儲存 a中后一項和b中所有項的乘積e.coef=(ha->data.coef)*(hb->data.coef);e.exp n=(ha->data.exp n)+(hb->data.exp n); polyn omial E=NULL;E=(poly nomial)malloc(sizeof(LNode); E->data.coef=e.coef;E->data.exp n=e.exp n;E->n ext=d

16、->next;d->n ext=E;Sort(d);ha=ha->n ex t;AddPolyn(c,d);將 c, d 兩項相加，得到合并后的cpolyn omial t=a;a=c;DestroyPoly n(b);銷毀臨時存儲空間DestroyPoly n( t);return 1;void DestroyPoly n(poly nomia l& L)銷毀線性表while(L!=NULL)polyn omial p;P=L;L=L->n ex t;free(p);void Sort(poly nomia l& L)/冒泡排序polyn omial

17、i,j;for(i=L;i-> next!=NULL;i=i-> next)總次數(shù)for(j=L;j->n ext->n ext!=NULL;j=j->n ext)/第一趟if(j- >n ext->data.exp nvj->n ext->n ext->da ta.exp n)/比較大小，將大的冒到前面polyn omial p,q;p=j->n ex t; q=j->n ext->next; p->n ext=q->n ex t;q->n ext=p; j->n ext=q;7.2程序全部

18、代碼#in clude<stdio.h>#in clude<iostream>#in clude<stdlib.h>#defi ne TRUE 1;#defi ne FALSE 0; using n amespace std;typedef structfloat coef;int exp n;Poly;typedef struct LNodePoly data;struct LNode* n ex t;LNode,*Li nkLis t;typedef Lin kList polyno mial;int mai n() / 主函數(shù)/ 函數(shù)聲明void Cr

19、eatPo lyn(polyn omial& ,int );void DestroyPoly n(poly nomial& );void const Prin tPo lyn( polyn omial );intAddPlo yn (poly nomial& ,poly nomial& );intSubtractPlo yn (poly nomial&,poly nomial&);intMultiplyPlo yn(polyn omial&,poly nomial&);voidMenu (poly no mial& ,po

20、ly no mial& );/ 定義int n=1;while (n >=0)polyn omial a;polyn omial b;system("cls");printf(-請輸入第一個多項式的項數(shù)(輸入負(fù)數(shù)退出)：")；sca nf("%d",&n);if(n vO)exit(O);CreatPoly n(a, n);Prin tPoly n(a);printf(-請輸入第二個多項式的項數(shù)(輸入負(fù)數(shù)退出)：")；sca nf("%d",&n);if(n vO)exit(O);Cr

21、eatPoly n(b, n);Prin tPoly n(b);/ 菜單Me nu(a,b);/銷毀線性表DestroyPo lyn( a);return 0;voidMenu (poly no mial&a,pol yn omia l&b)菜單intAddPoly n(poly nomial& ,poly nomial& );intSubtractPoly n(poly nomial&,poly nomial&);intMultiplyPoly n( pol yn omia l&,pol yn omia l&);void con

22、st Prin tPo lyn( polyn omial );int n=0;printf("1.多項式相加n2.多項式相減n3.多項式相乘n");sca nf("%d",&n);switch( n)case 1:AddPoly n(a,b);prin tf("A nswer=");Prin tPoly n(a); system("pause");break;case 2:SubtractPoly n(a,b); prin tf("A nswer="); Prin tPoly n(a);

23、 system("pause");break;case 3:if(MultiplyPoly n(a,b)prin tf("A nswer=");Prin tPoly n(a);elseprin tf("A nswer=0n");system("pause");break;defaultbreak; void CreatPo lyn(polyn omial& L,i nt n)創(chuàng)建多項式void Sort(po lyn omial& L);L=(poly no mial)malloc(sizeof(L

24、Node); L->n ext=NULL;Poly e;int i=1;for(; n>0;n-+)printf("請輸入第 d",i);printf(”項的系數(shù)和指數(shù)：");sca nf("%f%d", &e.coef, &e.exp n); polyn omial E=NULL;E=(poly nomial)malloc(sizeof(LNode); E->data.coef=e.coef;E->data.exp n=e.exp n;E->n ext=L->next;L->n ext

25、=E;Sort(L);intSubtractPoly n(poly no mial&Pa,polynomial&Pb) 多項式減法：Pa=Pa-Pbpoly nomial ha=NULL,hb=NULL,p=NULL; ha=Pa;hb=Pb;if(ha->n ext=NULL)Pa=Pb;free(ha);return 0;elsewhile(hb-> next!=NULL)if(ha->n ext->data.exp n<hb->n ext->data.e xpn)polyn omial p,q;p=hb->n ex t;q=

26、p->n ex t;p->data.coef=O-p->data.coef;p->n ext=ha->next;ha->n ext=p;hb->n ext=q;ha=ha->n ex t;elseif(ha->n ext->data.exp n=hb->n ext->data. exp n)ha->n ext->data.coef=ha->n ext->data.coef-hb->n ext->data.coef;p=hb->n ex t;hb->n ext=hb->n

27、 ext- >next;free(p);elseha=ha->n ex t;if(ha->n ext=NULL)hb->n ext->data.coef=0-hb->n ext->data.coef;ha->n ext=hb->next;hb->n ext=NULL;free(hb);return 0;void const Prin tPo lyn(polyno mial P)/輸出多項式polyn omial a;a=P->n ex t;/開始輸出while(a->n ext)prin tf("%gxA%d+&

28、quot;,a->data.coef,a->data.exp n); a=a->n ex t;/輸出最后一個prin tf("%gx%dn",a->data.coef,a->data.exp n);int AddPo lyn(polyn omial& Pa,poly nomial& Pb)/多項式加法：Pa=Pa+Pbpoly nomial ha=NULL,hb=NULL,p=NULL; ha=Pa;hb=Pb;if(ha->n ext=NULL)Pa=Pb;free(ha);return 0;elsewhile(hb-&

29、gt; next!=NULL)if(ha->n ext->data.exp n<hb->n ext->data.e xpn)polyn omial p,q; p=hb->n ex t;q=p->n ex t;p->n ext=ha->next; ha->n ext=p; hb->n ext=q;ha=ha->n ex t;elseif(ha->n ext->data.exp n=hb->n ext->data. exp n)ha->n ext->data.coef=ha->n ex

30、t->data.coef +hb->n ext->data.coef;p=hb->n ex t;hb->n ext=hb->n ext- >next; free(p);elseha=ha->n ex t;if(ha->n ext=NULL)ha->n ext=hb->next;hb->n ext=NULL; free(hb);return 0;intMultiplyPoly n( poly nomial&a,pol yno mial & b)多項式相乘void Sort(po lyn omial&

31、L);void DestroyPoly n(poly nomial& );pol yn omial ha=NULL,hb=NULL,c=NULL; Poly e;if(a-> next=NULL|b-> next=NULL)return 0;c=(poly no mial)malloc(sizeof(LNode);c->n ext=NULL;ha=a->n ex t;hb=b->n ex t; for(;hb!=NULL;hb=hb-> next)e.coef=(ha->data.coef)*(hb->data.coef);e.exp n=(ha->data.exp n)+(hb->data.exp n); polyn omial E=NULL