數(shù)據(jù)結(jié)構(gòu)課程設(shè)計_一元多項式的加法、減法、乘法的實現(xiàn)

1、hunan city university 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 報 告設(shè)計題目：一元多項式的加法、減法、乘法的實現(xiàn)專 業(yè)： 計算機科學與技術(shù)（嵌入式） 學生姓名： 班級學號： 分組成員： 指導教師： 陳強老師 2012 年 6月 8日1006402數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告一、 設(shè)計時間2011年6月4日6月8日二、 設(shè)計地點湖南城市學院實驗樓計算機房407三、 設(shè)計目的數(shù)據(jù)結(jié)構(gòu)主要介紹最常用的數(shù)據(jù)結(jié)構(gòu)，闡明各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論其在計算機中的存儲表示，以及在其上進行各種運算時的實現(xiàn)算法，并對算法的效率進行簡單的分析和討論，是介于數(shù)學、計算機軟件和計算機硬件之間的一門計算機專業(yè)的核心課程，它

2、是計算機程序設(shè)計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應用于信息學、系統(tǒng)工程等各種領(lǐng)域。該課程的特點是實踐性較強，為了學好這門課程，需要在掌握理論知識的同時，加強上機實踐。本課程設(shè)計的目的就是要達到理論與實際應用相結(jié)合，使同學們能夠根據(jù)數(shù)據(jù)對象的特性，學會數(shù)據(jù)組織的方法，能把現(xiàn)實世界中的實際問題在計算機內(nèi)部表示出來，并培養(yǎng)基本的、良好的程序設(shè)計技能。具體要求如下：1.了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力；2.初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼測試等基本方法和技能;3.提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力;4.訓

3、練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應具備的科學的工作方法和作風。四、 設(shè)計小組成員五、 指導教師：六、 設(shè)計課題：順序結(jié)構(gòu)、動態(tài)鏈表結(jié)構(gòu)下的一元多項式的加法、減法、乘法的實現(xiàn)設(shè)有一元多項式am(x)和bn(x).am(x)=a0+a1x1+a2x2+a3x3+amxmbn(x)=b0+b1x1+b2x2+b3x3+bnxn請實現(xiàn)求m(x)=am(x)+bn(x)、m(x)=am(x)-bn(x)和m(x)=am(x)bn(x)。要求：1)首先判定多項式是否稀疏2)分別采用順序和動態(tài)存儲結(jié)構(gòu)實現(xiàn)；3)結(jié)果m(x)中無重復階項和無零系數(shù)項；4)要求輸出結(jié)果的升冪和降冪兩

4、種排列情況七、 基本思路及關(guān)鍵問題的解決方法輸入多項式各項的系數(shù)和指數(shù)并對其進行稀疏判斷，然后選擇實現(xiàn)結(jié)構(gòu)，判斷為順序結(jié)構(gòu)或動態(tài)鏈表結(jié)構(gòu)，分別進行處理，再選定計算方法（進行加法、減法和乘法判斷），然后用相應的計算方法對多項式進行計算，最后判斷升冪或降冪的輸出方式進行輸出。八、 算法及流程圖;流程圖：開始輸入兩個多項式各項的系數(shù)和指數(shù)是判斷是否稠密？否為稀疏多項式為稠密多項式選擇實現(xiàn)結(jié)構(gòu) 順序結(jié)構(gòu)？ 是否 為順序結(jié)構(gòu)為動態(tài)鏈表結(jié)構(gòu)選擇操作方式選擇操作方式 加法？ 加法？調(diào)用加法函數(shù)是否 是否 減法？ 減法？調(diào)用加法函數(shù)否是否調(diào)用乘法函數(shù)調(diào)用減法函數(shù)調(diào)用減法函數(shù)調(diào)用乘法函數(shù)是否選擇打印輸出順序選擇

5、打印輸出順序 升冪？ 升冪？ 是否是否調(diào)用降冪輸出函數(shù)調(diào)用升冪輸出函數(shù)調(diào)用降冪輸出函數(shù)調(diào)用升冪輸出函數(shù)打印輸出處理后的結(jié)果結(jié)束 運行如圖： 運算操作方式：1 加法：兩多項式指數(shù)相同項指數(shù)不變系數(shù)相加2 減法：兩多項式指數(shù)相同項指數(shù)不變系數(shù)相減3 相乘：第一個多項式的各項和第二個多項式的各項分別相乘再相加，其中系數(shù)相乘指數(shù)相加，具體表達式如下：假設(shè)a(x)和b(x)為一元多項式，則m(x) = a(x) * b(x)= a(x) * b1xe1+b2xe2+bnxen= bia(x)xei 九、 調(diào)試過程中出現(xiàn)的問題及相應解決辦法； 獨立測試各個模塊的功能時發(fā)現(xiàn)在創(chuàng)建鏈表后和另一個進行運算后多余

6、的存儲單元沒有釋放而造成內(nèi)存的泄漏，還有對于鏈表的運算時結(jié)束條件掌握不透徹導致沒有按計劃地去結(jié)束，比如在用for循環(huán)及while循環(huán)時沒有正確地判斷指針的移動與結(jié)束條件而得不到自己想要的結(jié)果。進入函數(shù)內(nèi)部調(diào)試時發(fā)現(xiàn)有誤用沒有初始化的變量，還有贅余的語句擾亂了代碼的健壯性。 在主函數(shù)中對各個函數(shù)的調(diào)用時沒有一個清晰的思路，使程序顯得很混亂，給調(diào)試造成了很大困難。 對非法操作控制的不夠完善，例如缺少對越界訪問及其非法數(shù)據(jù)的控制機制，使程序的安全性下降。對于每創(chuàng)建一個鏈表，每次在進行完相應操作之后應該對其鏈表進行刪除釋放，并且要做到在適當?shù)臅r間進行刪除，對于運算結(jié)束的條件的意識不是很清楚，運算結(jié)束的

7、標識是當結(jié)點指針移動并且為空時結(jié)束，還有在用指針和變量的時候注意初始化問題，并且盡量使得程序保持良好的可讀性。十、 課程設(shè)計心得體會；編寫的程序不但要拿來使用，還要給別人查看，以便代碼的維護。所以代碼編寫的風格盡量規(guī)范，清晰。變量要盡量少定義，結(jié)構(gòu)夜采用簡單的。另外，對指針的使用要小心，盡量在定義的時候就進行初始化，避免野指針，指針的使用涉及到內(nèi)存的分配。該程序基本實現(xiàn)了要求的順序結(jié)構(gòu)、動態(tài)鏈表結(jié)構(gòu)下的一元多項式的加法、減法、乘法等功能。代碼較為冗余，可讀性較差，可以多添加一些提示語句以及注釋。在這次課程設(shè)計中我又進一步地了解了數(shù)據(jù)結(jié)構(gòu)中算法的核心思想的重要性，懂得了一個程序地好壞關(guān)鍵在于算法

8、是否優(yōu)秀，一個好的優(yōu)秀的算法可以使我們的程序更加完善，安全性更高以及有更高的效率。這次設(shè)計中我發(fā)現(xiàn)了自己的許多不足，如對指針的機制掌握的還不是很透徹，有的時候會出現(xiàn)指針指向錯誤以及空指針的錯誤,還有不能很好地分析自己算法地復雜度以及不能很好地使用控制機制使自己的程序流暢地運行。十一、 部分源程序(核心代碼)void mulpoly(double *a,double *b,double *c) /一元多項式順序結(jié)構(gòu)乘法實現(xiàn)int max=cp1n1-1.expn+cp2n2-1.expn+2;int i,j;for(i=0;imax;i+)ci=0;for(i=0;i=cp1n1-1.expn;

9、i+)for(j=0;j=cp2n2-1.expn;j+)ci+j+=ai*bj;puts(相乘結(jié)果為：);ansprint(c,max-1);void ansprint(double *a,int n) /結(jié)果打印函數(shù)int choose;puts(請選擇輸出順序：1 升冪 2 降冪：);scanf(%d,&choose);int i,num;if(choose!=2) /升冪打印if(choose!=1)printf(沒有%d選項，系統(tǒng)將默認輸出升序：ny(x)=,choose);elseprintf(y(x)=);num=0;for(i=0;i1e-8)if(num+)putchar(+

10、);printf(%lfx%d,ai,i);else /降冪打印printf(y(x)=);num=0;for(i=n;i=0;i-)if(fabs(ai)1e-8)if(num+)putchar(+); printf(%lfx%d,ai,i);putchar(10);動態(tài)鏈表的建立和構(gòu)造：typedef struct p_pol /結(jié)構(gòu)結(jié)點定義double coef;int expn;p_pol *next;mpp;mpp * creatlink(mpp *p,int n,int pt) /構(gòu)造動態(tài)鏈表結(jié)構(gòu)mpp *d,*q;int i;q=(mpp *)malloc(sizeof(mpp)

11、; /頭結(jié)點if(q=null)exit(0);q-next=null;q-coef=infco;q-expn=-infex;p=q;for(i=0;inext=null;if(pt=1)d-coef=cp1i.coef;d-expn=cp1i.expn;elsed-coef=cp2i.coef;d-expn=cp2i.expn;q-next=d;q=d;return p; /返回頭指針動態(tài)鏈表結(jié)構(gòu)實現(xiàn)加法：void addlink(mpp *p1,mpp *p2,mpp *p3) /動態(tài)鏈表相加mpp * p,*head;p=(mpp *)malloc(sizeof(mpp); /頭結(jié)點if

12、(p=null)exit(0);p-coef=infco;p-expn=-infex;p-next=null;head=p3=p;p1=p1-next;p2=p2-next;while(p1!=null|p2!=null)if(fabs(head-coef)1e-8) /如果系數(shù)不為0p=(mpp *)malloc(sizeof(mpp);if(p=null)exit(0);head-next=p;head=p;head-next=null;if(p1=null)head-coef=p2-coef;head-expn=p2-expn;p2=p2-next;continue;if(p2=null

13、)head-coef=p1-coef;head-expn=p1-expn;p1=p1-next;continue;if(p1-expn=p2-expn) /如果系數(shù)相同head-coef=p1-coef+p2-coef;head-expn=p1-expn;p1=p1-next;p2=p2-next;else if(p1-expnexpn)head-coef=p1-coef;head-expn=p1-expn;p1=p1-next;elsehead-coef=p2-coef;head-expn=p2-expn;p2=p2-next;puts(相加結(jié)果為：);printlink(p3);源程序：#

14、include#include#include#define infex 10000#define infco 10000typedef struct poldouble coef;int expn;mpol;mpol *cp1,*cp2;/-順序結(jié)構(gòu)部分-int n1,n2;void ansprint(double *a,int n) /打印出結(jié)果int choose;puts(請選擇輸出順序：1 升冪 2 降冪：);scanf(%d,&choose);int i,num;if(choose!=2) /升冪打印if(choose!=1)printf(沒有%d選項，系統(tǒng)將默認輸出升序：ny(x

15、)=,choose);elseprintf(y(x)=);num=0;for(i=0;i1e-8)if(num+)putchar(+);printf(%lfx%d,ai,i);else /降冪打印printf(y(x)=);num=0;for(i=n;i=0;i-)if(fabs(ai)1e-8)if(num+)putchar(+); printf(%lfx%d,ai,i);putchar(10);void addpoly(double *a,double *b,double *c) /順序結(jié)構(gòu)相加int min=(cp1n1-1.expncp2n2-1.expn?cp2n2-1.expn:c

16、p1n1-1.expn);int max=(cp1n1-1.expncp2n2-1.expn?cp2n2-1.expn:cp1n1-1.expn);int i;for(i=0;i=min;i+)ci=ai+bi;for(;icp2n2-1.expn)ci=ai;elseci=bi;puts(相加結(jié)果為：);ansprint(c,max);void subpoly(double *a,double *b,double *c) /順序結(jié)構(gòu)相減int min=(cp1n1-1.expncp2n2-1.expn?cp2n2-1.expn:cp1n1-1.expn);int max=(cp1n1-1.e

17、xpncp2n2-1.expn?cp2n2-1.expn:cp1n1-1.expn);int i;for(i=0;i=min;i+)ci=ai-bi;for(;icp2n2-1.expn)ci=ai;elseci=-bi;puts(相減結(jié)果為：);ansprint(c,max);void mulpoly(double *a,double *b,double *c) /順序結(jié)構(gòu)相乘int max=cp1n1-1.expn+cp2n2-1.expn+2;int i,j;for(i=0;imax;i+)ci=0;for(i=0;i=cp1n1-1.expn;i+)for(j=0;j=cp2n2-1.

18、expn;j+)ci+j+=ai*bj;puts(相乘結(jié)果為：);ansprint(c,max-1);void creatpoly1(double *a,int pt) /建立順序結(jié)構(gòu)int i;if(pt=1)for(i=0;i=cp1n1-1.expn;i+)ai=0;for(i=0;in1;i+)acp1i.expn=cp1i.coef;elsefor(i=0;i=cp2n2-1.expn;i+)ai=0;for(i=0;inext=null;q-coef=infco;q-expn=-infex;p=q;for(i=0;inext=null;if(pt=1)d-coef=cp1i.coe

19、f;d-expn=cp1i.expn;elsed-coef=cp2i.coef;d-expn=cp2i.expn;q-next=d;q=d;return p;void printlink(mpp * p) /打印結(jié)果int num=0,i=0,choose,count;puts(請選擇輸出順序：1 升冪 2 降冪：);scanf(%d,&choose);mpp *tp=p;p=p-next;while(p!=null)num+;p=p-next;mpol *d=new mpolnum;p=tp-next;while(p!=null)di.coef=p-coef;di.expn=p-expn;i

20、+;p=p-next;if(choose=2) /降冪打印count=0;printf(y(x)=);for(i=num-1;i=0;i-)if(count+)putchar(+);printf(%lfx%d,di.coef,di.expn);else /升冪打印if(choose!=1)printf(沒有%d選項，系統(tǒng)將默認輸出升序：ny(x)=,choose);elseprintf(y(x)=);for(i=0;icoef=infco;p-expn=-infex;p-next=null;head=p3=p;p1=p1-next;p2=p2-next;while(p1!=null|p2!=n

21、ull)if(fabs(head-coef)1e-8)p=(mpp *)malloc(sizeof(mpp);if(p=null)exit(0);head-next=p;head=p;head-next=null;if(p1=null)head-coef=p2-coef;head-expn=p2-expn;p2=p2-next;continue;if(p2=null)head-coef=p1-coef;head-expn=p1-expn;p1=p1-next;continue;if(p1-expn=p2-expn)head-coef=p1-coef+p2-coef;head-expn=p1-e

22、xpn;p1=p1-next;p2=p2-next;else if(p1-expnexpn)head-coef=p1-coef;head-expn=p1-expn;p1=p1-next;elsehead-coef=p2-coef;head-expn=p2-expn;p2=p2-next;puts(相加結(jié)果為：);printlink(p3);void sublink(mpp *p1,mpp *p2,mpp *p3) /動態(tài)鏈表相減mpp * p,*head;p=(mpp *)malloc(sizeof(mpp);if(p=null)exit(0);p-coef=infco;p-expn=-inf

23、ex;p-next=null;head=p3=p;p1=p1-next;p2=p2-next;while(p1!=null|p2!=null)if(fabs(head-coef)1e-8)p=(mpp *)malloc(sizeof(mpp);if(p=null)exit(0);head-next=p;head=p;head-next=null;if(p1=null)head-coef=-p2-coef;head-expn=p2-expn;p2=p2-next;continue;if(p2=null)head-coef=p1-coef;head-expn=p1-expn;p1=p1-next;

24、continue;if(p1-expn=p2-expn)head-coef=p1-coef-p2-coef;head-expn=p1-expn;p1=p1-next;p2=p2-next;else if(p1-expnexpn)head-coef=p1-coef;head-expn=p1-expn;p1=p1-next;elsehead-coef=-p2-coef;head-expn=p2-expn;p2=p2-next;puts(相減結(jié)果為：);printlink(p3);void mullink(mpp *p1,mpp *p2,mpp *p3) /動態(tài)鏈表相乘mpp *p,*head,*d

25、,*tp;int i,j;p=(mpp *)malloc(sizeof(mpp);if(p=null)exit(0);p-coef=infco;p-expn=-infex;p-next=null;tp=head=p3=p;p=(mpp *)malloc(sizeof(mpp);if(p=null)exit(0);p-coef=infco;p-expn=infex;p-next=null;tp-next=p;for(i=0;inext;d=p2;for(j=0;jnext;p=(mpp *)malloc(sizeof(mpp);if(p=null)exit(0);p-next=null;p-co

26、ef=p1-coef*d-coef;p-expn=p1-expn+d-expn;tp=p3;while(tp-next!=null)if(tp-expn=p-expn)tp-coef+=p-coef;free(p);break;if(tp-expnexpn&tp-next-expnp-expn)p-next=tp-next;tp-next=p;break;tp=tp-next;tp=p3;while(tp-next!=null)if(tp-next-expn=infex)free(tp-next);tp-next=null;break;tp=tp-next;puts(相乘結(jié)果為：);print

27、link(p3);void deletelink(mpp *p) /刪除結(jié)點釋放內(nèi)存mpp *d;while(p!=null)d=p;p=p-next;free(d);int main()int i,choose,choose2;puts(輸入第一個多項式的項數(shù)：);scanf(%d,&n1);cp1=(mpol *)malloc(n1*sizeof(mpol);puts(分別輸入各項的系數(shù)和指數(shù)：);for(i=0;in1;i+)scanf(%lf%d,&cp1i.coef,&cp1i.expn);if(n1(cp1n1-1.expn+1)/2)puts(此多項式稀疏！);elseputs(

28、此多項式稠密！);puts(輸入第二個多項式的項數(shù)：);scanf(%d,&n2);cp2=(mpol *)malloc(n2*sizeof(mpol);puts(分別輸入各項的系數(shù)和指數(shù)：);for(i=0;in2;i+)scanf(%lf%d,&cp2i.coef,&cp2i.expn);if(n2(cp2n2-1.expn+1)/2)puts(此多項式稀疏！);elseputs(此多項式稠密！);puts(請選擇實現(xiàn)結(jié)構(gòu)：1 順序結(jié)構(gòu) 2 動態(tài)鏈表結(jié)構(gòu)！);scanf(%d,&choose);double *c1,*c2,*c3;mpp *p1=null,*p2=null,*p3=null;switch(choose)case 1:c1=(double *)malloc(cp1n1-1.expn+1)*sizeof(double);c2=(double *)malloc(cp1n2-1.expn+1)*sizeof(double);creatpoly1(c1,1);creatpoly1(c2,2);break;case 2:p1=creatlink(p1,n1,1);p2=creatlink(p2,n2,2);break;defau