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

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