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

課程設(shè)計(論文)題 目 名 稱 一元多項式的加法、減法、乘法的實現(xiàn) 課 程 名 稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 學(xué) 生 姓 名 學(xué) 號 系 、專 業(yè) 信息工程系、通信工程 指 導(dǎo) 教 師 設(shè)有一元多項式Am(x)和Bn(x)：Am(x)=A0+A1x+A2x2+A3x3+ +AmxmBn(x)=B0+B1x1+B2x2+B3x3+ +Bnxn分別采用順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)：M(x)=Am(x)+Bn(x)、M(x)=Am(x)-Bn(x)和M(x)=Am(x)Bn(x)。并要結(jié)果M(x)中無重復(fù)階項和無零系數(shù)項，且輸出結(jié)果用升冪和降冪兩種排列情況。關(guān)鍵詞：一元多項式；順序存儲；鏈?zhǔn)酱鎯?；升冪；降冪?錄1 問題描述12 需求分析13 概要設(shè)計131抽象數(shù)據(jù)類型定義132模塊劃分24 詳細(xì)設(shè)計341數(shù)據(jù)類型的定義342主要模塊的算法描述35 測試分析76 課程設(shè)計總結(jié)10參考文獻10附錄（源程序清單）111 問題描述設(shè)有一元多項式Am(x)和Bn(x)：Am(x)=A0+A1x+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）分別采用順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)實現(xiàn)；（2）結(jié)果M(x)中無重復(fù)階項和無零系數(shù)項；（3）要求輸出結(jié)果用升冪和降冪兩種排列情況。2 需求分析（1）用一維數(shù)組cp1n1和cp2n2存儲一元多項式Am(x)和Bn(x)的系數(shù)，用for循環(huán)來計算順序結(jié)構(gòu)中的加法、減法、乘法的結(jié)果。（2）用指針*d,*q來存儲一元多項式的內(nèi)容，再利用指針計算動態(tài)鏈表下一元多項式的加法、減法、乘法的結(jié)果。（3）在用降冪升冪兩種排列輸出結(jié)果時，用expn和coef表示一元多項式的系數(shù)和指數(shù)，輸出兩種排列結(jié)果。3 概要設(shè)計31抽象數(shù)據(jù)類型定義（1）順序存儲結(jié)構(gòu)的抽象數(shù)據(jù)類型定義int n1,n2;利用一維數(shù)組cp1n1和cp2n2存儲多項式的系數(shù)基本操作：void creatpoly1(double *a,int pt)操作結(jié)果：建立順序結(jié)構(gòu)void addpoly(double *a,double *b,double *c)初始條件：一維數(shù)組cp1n1和cp2n2已建立操作結(jié)果：順序結(jié)構(gòu)相加void subpoly(double *a,double *b,double *c)初始條件：一維數(shù)組cp1n1和cp2n2已建立操作結(jié)果：順序結(jié)構(gòu)相減 void mulpoly(double *a,double *b,double *c) 初始條件：一維數(shù)組cp1n1和cp2n2已建立操作結(jié)果：順序結(jié)構(gòu)相乘void ansprint(double *a,int n) 初始條件: 一維數(shù)組cp1n1和cp2n2已建立操作結(jié)果：選用升冪或降冪排列打印出結(jié)果（2）動態(tài)鏈表結(jié)構(gòu)的抽象數(shù)據(jù)類型定義typedef struct p_pol double coef; int expn; p_pol *next；MPP；基本操作：MPP * creatlink(MPP *p,int n,int pt)初始條件：動態(tài)鏈表已定義操作結(jié)果：構(gòu)造動態(tài)鏈表結(jié)構(gòu)void addlink(MPP *p1,MPP *p2,MPP *p3)初始條件：動態(tài)鏈表已定義操作結(jié)果：動態(tài)鏈表相加void sublink(MPP *p1,MPP *p2,MPP *p3)初始條件：動態(tài)鏈表已定義操作結(jié)果：動態(tài)鏈表相減void mullink(MPP *p1,MPP *p2,MPP *p3)初始條件：動態(tài)鏈表已定義操作結(jié)果：動態(tài)鏈表相乘void printlink(MPP * p)初始條件：動態(tài)鏈表已定義操作結(jié)果：選用升冪或降冪排列打印結(jié)果void deletelink(MPP *p)初始條件：動態(tài)鏈表已定義操作結(jié)果：刪除結(jié)點釋放內(nèi)存32模塊劃分本程序包括三個模塊：（1）主程序模塊void main()輸入第一個多項式的項數(shù)；分別輸入各項的系數(shù)和指數(shù)；輸入第二個多項式的項數(shù)；分別輸入各項的系數(shù)和指數(shù)；請選擇實現(xiàn)結(jié)構(gòu)：1 順序結(jié)構(gòu) 2 動態(tài)鏈表結(jié)構(gòu)選擇操作方式：1 相加 2 相減 3 相乘（2）順序存儲結(jié)構(gòu)模塊實現(xiàn)順序存儲結(jié)構(gòu)的抽象數(shù)據(jù)類型（3）動態(tài)鏈表結(jié)構(gòu)模塊實現(xiàn)動態(tài)鏈表結(jié)構(gòu)的抽象數(shù)據(jù)類型4 詳細(xì)設(shè)計41數(shù)據(jù)類型的定義（1）順序存儲結(jié)構(gòu)類型int n1,n2;int cp1n1; intcp2n2（2）動態(tài)鏈表結(jié)構(gòu)類型#define INFEX 10000#define INFCO 10000double coef;int expn;p_pol *next;42主要模塊的算法描述該題可畫三個流程圖：（1）一元多項式的計算主流程圖；（2）順序存儲結(jié)構(gòu)流程圖；（3）動態(tài)鏈表結(jié)構(gòu)流程圖。流程圖如下：（1）一元多項式的計算主流程圖：如圖4.1所示為動態(tài)鏈表結(jié)構(gòu)為順序結(jié)構(gòu)開始輸入兩個多項式各項的系數(shù)選擇實現(xiàn)結(jié)構(gòu)順序結(jié)構(gòu)？YN選擇打印輸出結(jié)果的方式升冪？YN升冪輸出結(jié)果降冪輸出結(jié)果打印輸出處理后的結(jié)果結(jié)束圖4.1一元多項式的計算主流程圖（2）順序存儲結(jié)構(gòu)流程圖如圖4.2所示減法？開始采用順序存儲結(jié)構(gòu)調(diào)用加法函數(shù)YN加法？調(diào)用降冪輸出函數(shù)調(diào)用升冪輸出函數(shù)YN調(diào)用減法函數(shù)調(diào)用乘法函數(shù)選擇打印輸出結(jié)果的順序升冪？YN打印輸出處理后的結(jié)果結(jié)束圖4.2順序存儲結(jié)構(gòu)流程圖（3）動態(tài)鏈表結(jié)構(gòu)流程圖如圖4.3所示減法？開始采用動態(tài)鏈表存儲結(jié)構(gòu)調(diào)用加法函數(shù)YN加法？調(diào)用降冪輸出函數(shù)調(diào)用升冪輸出函數(shù)YN調(diào)用減法函數(shù)調(diào)用乘法函數(shù)選擇打印輸出結(jié)果的順序升冪？YN打印輸出處理后的結(jié)果結(jié)束圖4.3動態(tài)鏈表結(jié)構(gòu)流程圖5 測試分析測試數(shù)據(jù)及結(jié)果如下：6 課程設(shè)計總結(jié)通過這次課程設(shè)計使我了解到編寫的程序不但要拿來使用，還要讓人看得懂。所以，代碼編寫的風(fēng)格要盡量規(guī)范，清晰。變量要盡量少定義，結(jié)構(gòu)體采用簡單的。另外，對指針的使用要小心，盡量在定義的時候就進行初始化，避免出現(xiàn)沒有被定義的指針。該程序主要實現(xiàn)了順序結(jié)構(gòu)、動態(tài)鏈表結(jié)構(gòu)下的一元多項式的加法、減法、乘法等運算功能。同時，也應(yīng)用了升冪和降冪的輸出方法，輸出程序的結(jié)果。雖然此次的程序不是很完備，但是總體還是一個比較能體現(xiàn)數(shù)據(jù)結(jié)構(gòu)知識點的程序了，當(dāng)然只是相對于我這個初學(xué)者來說。這次設(shè)計中我發(fā)現(xiàn)了自己的許多不足，如對指針的機制掌握的還不是很透徹，有的時候會出現(xiàn)指針指向錯誤以及空指針的錯誤,還有不能很好地分析自己算法地復(fù)雜度以及不能很好地使用控制機制使自己的程序流暢地運行。因此，在今后我會更加努力地。在此我要非常感謝的是我的指導(dǎo)老師黃同成老師，感謝老師的細(xì)心認(rèn)真的輔導(dǎo)，讓我對數(shù)據(jù)結(jié)構(gòu)這門課程有了更多的了解，也讓我對這門課程產(chǎn)生了濃厚的興趣。在這次課程設(shè)計中我又進一步地了解了數(shù)據(jù)結(jié)構(gòu)中算法的核心思想的重要性，懂得了一個程序地好壞關(guān)鍵在于算法是否優(yōu)秀，一個好的優(yōu)秀的算法可以使我們的程序更加完善，安全性更高以及有更高的效率。參考文獻1 黃同成，黃俊民，董建寅數(shù)據(jù)結(jié)構(gòu)M北京：中國電力出版社，20082 董建寅，黃俊民，黃同成數(shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)與題解M北京：中國電力出版社，20083 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語言版）M. 北京：清華大學(xué)出版社，20024 劉振鵬，張曉莉，郝杰數(shù)據(jù)結(jié)構(gòu)M北京：中國鐵道出版社，2003附錄（源程序清單）#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)將默認(rèn)輸出升序：nM(X)=,choose);elseprintf(M(X)=);num=0;for(i=0;i1e-8)if(num+)putchar(+);printf(%lfX%d,ai,i);else /降冪打印printf(M(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:cp1n1-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.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 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.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.coef;d-expn=cp1i.expn;elsed-coef=cp2i.coef;d-expn=cp2i.expn;q-next=d;q=d;return p;void printlink1(MPP * p) /打印結(jié)果Am(x)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+;p=p-next;if(choose=2) /降冪打印count=0;printf(Am(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)將默認(rèn)輸出升序：nAm(X)=,choose);elseprintf(Am(X)=);for(i=0;inext;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+;p=p-next;if(choose=2) /降冪打印count=0;printf(Bn(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)將默認(rèn)輸出升序：nBn(X)=,choose);elseprintf(Bn(X)=);for(i=0;inext;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+;p=p-next;if(choose=2) /降冪打印count=0;printf(M(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)將默認(rèn)輸出升序：nM(X)=,choose);elseprintf(M(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!=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;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 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=-INFEX;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;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,*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-coef=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é)果為：);printlink(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);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);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=