順序結(jié)構(gòu)、動(dòng)態(tài)鏈表結(jié)構(gòu)下的一元多項(xiàng)式的加法、減法、乘法的實(shí)現(xiàn)。

課 程 設(shè) 計(jì) （ 數(shù)據(jù)結(jié)構(gòu) ） 班 級(jí) 姓 名 學(xué) 號(hào) 指導(dǎo)教師 二 一 年 七 月十日 課程設(shè)計(jì)任務(wù)書(shū)及成績(jī)?cè)u(píng)定 課題名稱 順序結(jié)構(gòu)、動(dòng)態(tài)鏈表結(jié)構(gòu)下的一元多項(xiàng)式的加法、減法、乘法的實(shí)現(xiàn)。 、題目的目的和要求 1、設(shè)計(jì)目的 鞏固和加深對(duì)數(shù)據(jù)結(jié)構(gòu)的理解，通過(guò)上機(jī)實(shí)驗(yàn)、調(diào)試程序，加深對(duì)課本知識(shí)的理解，最終使學(xué)生能夠熟練應(yīng)用數(shù)據(jù)結(jié)構(gòu)的知識(shí)寫程序。 （ 1）通過(guò)本課程的學(xué)習(xí)，能熟練掌握幾種基本數(shù)據(jù)結(jié)構(gòu)的基本操作。 （ 2）能針對(duì)給定題目，選擇 相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，分析并設(shè)計(jì)算法，進(jìn)而給出問(wèn)題的正確求解過(guò)程并編寫代碼實(shí)現(xiàn)。 2、設(shè)計(jì)題目要求 （給出你所選擇的題目 的要求 描述） 1) 首先判定多項(xiàng)式是否稀疏 2) 分別采用順序和動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)； 3) 結(jié)果 M(x)中無(wú)重復(fù)階項(xiàng)和無(wú)零系數(shù)項(xiàng)； 4) 要求輸出結(jié)果的升冪和降冪兩種排列情況； 、設(shè)計(jì)進(jìn)度及完成情況 日 期 內(nèi) 容 2010.6.28-6.30 選取參考書(shū)，查閱有關(guān)文獻(xiàn)資料，完成 資料搜集和系統(tǒng)分析工作。 2010.7.17.3 創(chuàng)建相關(guān)數(shù)據(jù)結(jié)構(gòu) ,錄入源程序 。 2010.7.57.7 調(diào)試程序并記錄調(diào)試中的問(wèn)題 ，初步完成課程設(shè)計(jì)報(bào)告。 2009.7.87.9 上交 課程設(shè)計(jì)報(bào)告 打印版 并進(jìn)行課程設(shè)計(jì)答辯，要求每個(gè)同學(xué)針對(duì)自己的設(shè)計(jì)回答指導(dǎo)教師 3-4 個(gè)問(wèn)題 。 考核結(jié)束后將課程設(shè)計(jì)報(bào)告和源程序的電子版交班長(zhǎng)統(tǒng)一刻光盤上交。 、主要參考文獻(xiàn)及資料 1 嚴(yán)蔚敏 數(shù)據(jù)結(jié)構(gòu)（ C 語(yǔ)言版） 清華大學(xué)出版社 ， 2007 2 嚴(yán)蔚敏 數(shù)據(jù)結(jié)構(gòu)題集（ C 語(yǔ)言版） 清華大學(xué)出版社 ， 2007 3 譚浩強(qiáng) C 語(yǔ)言程序設(shè)計(jì) 清華大學(xué)出版社 ， 2005 4 與所用編程環(huán)境相 配套的 C 語(yǔ)言或 C+相關(guān)的資料 、成績(jī)?cè)u(píng)定 設(shè)計(jì)成績(jī)： （教師填寫） 指導(dǎo)老師： （簽字） 二 一 年 七 月 十 日 目 錄 第一章 概述 . 1 第二章 系統(tǒng)分析 . 1 第三章 概要設(shè)計(jì) . 2 第四章 詳細(xì)設(shè)計(jì) . 3 第五章 運(yùn)行與測(cè)試 . 13 第六章 總結(jié)與心得 . 16 參考文獻(xiàn) . 17 本目錄是根據(jù) 正文 文檔自動(dòng)生成的， 請(qǐng)?jiān)?報(bào)告完成后， 更新目錄的頁(yè)碼，更新方法如下： 1.鼠標(biāo)單擊目錄任意部分選中目錄； 2.單擊鼠標(biāo)右鍵選擇“更新域”； 3.在出現(xiàn)的“更新目錄 ”的對(duì)話框中選擇“只更新頁(yè)碼”， 見(jiàn)圖 1-3， 單擊“確定”按鈕，目錄頁(yè)碼將被更新。 更新完成后，最好再核對(duì)一下。 圖 1-3 更新目錄頁(yè)碼示意圖 1 第一章 概述 課程設(shè)計(jì)是實(shí)踐性教學(xué)中的一個(gè)重要環(huán)節(jié)，它以某一課程為基礎(chǔ)，可以涉及和課程相關(guān)的各個(gè)方面，是一門獨(dú)立于課程之外的特殊課程。課程設(shè)計(jì)是讓同學(xué)們對(duì)所學(xué)的課程更全面的學(xué)習(xí)和應(yīng)用，理解和掌握課程的相關(guān)知識(shí)。數(shù)據(jù)結(jié)構(gòu)是一門重要的專業(yè)基礎(chǔ)課，是計(jì)算機(jī)理論和應(yīng)用的核心基礎(chǔ)課程。 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，要求學(xué)生在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇和應(yīng)用 、算法的設(shè)計(jì)及其實(shí)現(xiàn)等方面，加深對(duì)課程基本內(nèi)容的理解。同時(shí)，在程序設(shè)計(jì)方法以及上機(jī)操作等基本技能和科學(xué)作風(fēng)方面受到比較系統(tǒng)和嚴(yán)格的訓(xùn)練。 在這次的課程設(shè)計(jì)中我選擇的題目是 順序結(jié)構(gòu)、動(dòng)態(tài)鏈表結(jié)構(gòu)下的一元多項(xiàng)式的加法、減法、乘法的實(shí)現(xiàn) 。分別采用順序結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，利用多項(xiàng)得結(jié)果，最后得多項(xiàng)式中不含有重復(fù)階項(xiàng)和零系數(shù)得項(xiàng)。除此之外，還得分為降冪和升冪 兩種排序方式。 第二章 系統(tǒng)分析 1 順序結(jié)構(gòu)、動(dòng)態(tài)鏈表結(jié)構(gòu)下的一元多項(xiàng)式的加法、減法、乘法的實(shí)現(xiàn) 。可以分為幾個(gè)模塊：輸入模塊、輸出模塊（升冪降冪）、數(shù) 據(jù)處理模塊（多項(xiàng)式的加減乘）、主程序模塊。 2 在程序過(guò)程中加入漢字提示符，讓讀者清楚明白的操作該程序。運(yùn)行程序時(shí)看起來(lái)簡(jiǎn)潔有序 ，操作簡(jiǎn)單明了。 3 程序執(zhí)行時(shí)的命令： 選擇創(chuàng)建兩個(gè)一元多項(xiàng)式 輸入第一個(gè)一元多項(xiàng)式的項(xiàng)數(shù) 依次輸入一元多項(xiàng)式的系數(shù)和指數(shù) 以相同方式輸入第二個(gè)一元多項(xiàng)式 選擇操作方式 選擇降冪或升冪排序 輸出結(jié)果 是否退出 2 4.測(cè)試數(shù)據(jù)。 輸入的一元多項(xiàng)式 系數(shù)指數(shù)分別為 7 0,3 1,9 8,5 17 和 8 1,22 7， -9 8。加法結(jié)果為 ；升冪 降冪 減法結(jié)果為 ：升冪 降冪 乘法結(jié)果為：升冪 降冪 第三章 概要設(shè)計(jì) 1、數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì) 在該程序中分別分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 2、算法的設(shè)計(jì) 本程序主要分為四大模塊 主程序模塊 輸入模塊：通過(guò) Getpolyn 函數(shù)輸入 輸出模塊（升冪降冪）： PrintPolyn 函數(shù)實(shí)現(xiàn)輸出 數(shù)據(jù)處理模塊（多項(xiàng)式的加減乘）： 通過(guò)一元多項(xiàng)式的 Polynomial 基本操作實(shí)現(xiàn) 3 3、 抽象數(shù)據(jù)類型的設(shè)計(jì) 一元多 項(xiàng)式抽象數(shù)據(jù)類型的定義 ： 抽象數(shù)據(jù)類型 Polynomial 的定義： 第四章 詳細(xì)設(shè)計(jì) #include #include typedef struct float coef; /系數(shù) int expn; /指數(shù) term; typedef struct LNode 4 term data; /term 多項(xiàng)式值 struct LNode *next; LNode,*LinkList; typedef LinkList polynomail; /*比較指數(shù) */ int cmp(term a,term b) if(a.expnb.expn) return 1; if(a.expn=b.expn) return 0; if(a.expnnext!=NULL;p=p-next); r=p; for(h=pa;h-next!=r;)/大的沉底 for(p=h;p-next!=r&p!=r;p=p-next) if(cmp(p-next-data,p-next-next-data)=1) q=p-next-next; p-next-next=q-next; q-next=p-next; p-next=q; r=p;/r 指向參與比較的最后一個(gè)，不斷向前移動(dòng) /*由大到小排序 */ void arrange2(polynomail pa) polynomail h=pa,p,q,r; if(pa=NULL) exit(-2); for(p=pa;p-next!=NULL;p=p-next); r=p; for(h=pa;h-next!=r;)/小的沉底 for(p=h;p-next!=r&p!=r;p=p-next) if(cmp(p-next-next-data,p-next-data)=1) q=p-next-next; p-next-next=q-next; q-next=p-next; p-next=q; r=p;/r 指向參與比較的最后一個(gè)，不斷向前移動(dòng) /*打印多項(xiàng)式 ,求項(xiàng)數(shù) */ 5 int printpolyn(polynomail P) int i; polynomail q; if(P=NULL) printf(無(wú)項(xiàng)！ n); else if(P-next=NULL) printf(Y=0n); else printf(該多項(xiàng)式為 Y=);q=P-next;i=1; if(q-data.coef!=0&q-data.expn!=0) printf(%.2fX%d,q-data.coef,q-data.expn); i+; if(q-data.expn=0&q-data.coef!=0) printf(%.2f,q-data.coef);/打印第一項(xiàng) q=q-next; if(q=NULL) printf(n);return 1; while(1)/while 中，打印剩下項(xiàng)中系數(shù)非零的項(xiàng)， if(q-data.coef!=0&q-data.expn!=0) if(q-data.coef0) printf(+); printf(%.2fX%d,q-data.coef,q-data.expn); i+; if(q-data.expn=0&q-data.coef!=0) if(q-data.coef0) printf(+); printf(%f,q-data.coef); q=q-next; if(q=NULL) printf(n); break; return 1; /*1、創(chuàng)建并初始化多項(xiàng)式鏈表 */ polynomail creatpolyn(polynomail P,int m) polynomail r,q,p,s,Q; int i; P=(LNode*)malloc(sizeof(LNode); r=P; for(i=0;idata.coef,&s-data.expn); r-next=s; r=s; 6 r-next=NULL; if(P-next-next!=NULL) for(q=P-next;q!=NULL/*&q-next!=NULL*/;q=q-next)/合并同類項(xiàng) for(p=q-next,r=q;p!=NULL;) if(q-data.expn=p-data.expn) q-data.coef=q-data.coef+p-data.coef; r-next=p-next; Q=p;p=p-next; free(Q); else r=r-next; p=p-next; return P; /*2、兩多項(xiàng)式相加 */ polynomail addpolyn(polynomail pa,polynomail pb) polynomail s,newp,q,p,r;int j; p=pa-next;q=pb-next; newp=(LNode*)malloc(sizeof(LNode); r=newp; while(p&q) s=(LNode*)malloc(sizeof(LNode); switch(cmp(p-data,q-data) case -1: s-data.coef=p-data.coef; s-data.expn=p-data.expn; r-next=s; r=s; p=p-next; break; case 0: s-data.coef=p-data.coef+q-data.coef; if(s-data.coef!=0.0) s-data.expn=p-data.expn; r-next=s; r=s; p=p-next; q=q-next; break; case 1: s-data.coef=q-data.coef; s-data.expn=q-data.expn; 7 r-next=s; r=s; q=q-next; break; /switch /while while(p) s=(LNode*)malloc(sizeof(LNode); s-data.coef=p-data.coef; s-data.expn=p-data.expn; r-next=s; r=s; p=p-next; while(q) s=(LNode*)malloc(sizeof(LNode); s-data.coef=q-data.coef; s-data.expn=q-data.expn; r-next=s; r=s; q=q-next; r-next=NULL; for(q=newp-next;q-next!=NULL;q=q-next)/合并同類項(xiàng) for(p=q;p!=NULL&p-next!=NULL;p=p-next) if(q-data.expn=p-next-data.expn) q-data.coef=q-data.coef+p-next-data.coef; r=p-next; p-next=p-next-next; free(r); printf(升序 1 , 降序 2n); printf(選擇 :); scanf(%d,&j); if(j=1) arrange1(newp); else arrange2(newp); return newp; /*3、兩多項(xiàng)式相減 */ polynomail subpolyn(polynomail pa,polynomail pb) polynomail s,newp,q,p,r,Q; int j; p=pa-next;q=pb-next; newp=(LNode*)malloc(sizeof(LNode); r=newp; while(p&q) 8 s=(LNode*)malloc(sizeof(LNode); switch(cmp(p-data,q-data) case -1: s-data.coef=p-data.coef; s-data.expn=p-data.expn; r-next=s; r=s; p=p-next; break; case 0: s-data.coef=p-data.coef-q-data.coef; if(s-data.coef!=0.0) s-data.expn=p-data.expn; r-next=s; r=s; p=p-next; q=q-next; break; case 1: s-data.coef=-q-data.coef; s-data.expn=q-data.expn; r-next=s; r=s; q=q-next; break; /switch /while while(p) s=(LNode*)malloc(sizeof(LNode); s-data.coef=p-data.coef; s-data.expn=p-data.expn; r-next=s; r=s; p=p-next; while(q) s=(LNode*)malloc(sizeof(LNode); s-data.coef=-q-data.coef; s-data.expn=q-data.expn; r-next=s; r=s; q=q-next; r-next=NULL; if(newp-next!=NULL&newp-next-next!=NULL)/合并同類項(xiàng) for(q=newp-next;q!=NULL;q=q-next) for(p=q-next,r=q;p!=NULL;) if(q-data.expn=p-data.expn) 9 q-data.coef=q-data.coef+p-data.coef; r-next=p-next; Q=p;p=p-next; free(Q); else r=r-next; p=p-next; printf(升序 1 , 降序 2n); printf(選擇 :); scanf(%d,&j); if(j=1) arrange1(newp); else arrange2(newp); return newp; /*4 兩多項(xiàng)式相乘 */ polynomail mulpolyn(polynomail pa,polynomail pb) polynomail s,newp,q,p,r; int i=20,j; newp=(LNode*)malloc(sizeof(LNode); r=newp; for(p=pa-next;p!=NULL;p=p-next) for(q=pb-next;q!=NULL;q=q-next) s=(LNode*)malloc(sizeof(LNode); s-data.coef=p-data.coef*q-data.coef; s-data.expn=p-data.expn+q-data.expn; r-next=s; r=s; r-next=NULL; printf(升序 1 , 降序 2n); printf(選擇 :); scanf(%d,&j); if(j=1) arrange1(newp); else arrange2(newp); for(;i!=0;i-) for(q=newp-next;q-next!=NULL;q=q-next)/合并同類項(xiàng) for(p=q;p!=NULL&p-next!=NULL;p=p-next) if(q-data.expn=p-next-data.expn) q-data.coef=q-data.coef+p-next-data.coef; r=p-next; p-next=p-next-next; free(r); return newp; 10 /*5、銷毀已建立的兩個(gè)多項(xiàng)式 */ void delpolyn(polynomail pa,polynomail pb) polynomail p,q; p=pa; while(p!=NULL) q=p; p=p-next; free(q); p=pb; while(p!=NULL) q=p; p=p-next; free(q); printf(兩個(gè)多項(xiàng)式已經(jīng)銷毀 n); void main() polynomail pa=NULL,pb=NULL; polynomail p,q; polynomail addp=NULL,subp=NULL,mulp=NULL; int n,m; int sign=y; printf(1、創(chuàng)建兩個(gè)一元多項(xiàng)式 n); printf(2、兩多項(xiàng)式相加得一新多項(xiàng)式 n); printf(3、兩多項(xiàng)式相減得一新多項(xiàng)式 n); printf(4、兩多項(xiàng)式相乘得一新多項(xiàng)式 n); printf(5、銷毀已建立的兩個(gè)多項(xiàng)式 n); printf(6、退出 n); printf(n); while(sign!=n) printf(請(qǐng)選擇： ); scanf(%d,&n); switch(n) case 1: if(pa!=NULL) printf(已建立兩 個(gè)一元多項(xiàng)式，請(qǐng)選擇其他操作！ ); break; printf(請(qǐng)輸入第一個(gè)多項(xiàng)式： n); printf(要輸入幾項(xiàng)： ); 11 scanf(%d,&m); while(m=0) printf(m 不能為 0，請(qǐng)重新輸入 m:); scanf(%d,&m); pa=creatpolyn(pa,m); printpolyn(pa); printf(請(qǐng)輸入第二個(gè)多項(xiàng)式： n); printf(要輸入 幾項(xiàng)： ); scanf(%d,&m); pb=creatpolyn(pb,m); printpolyn(pb); break; case 2: if(pa=NULL) printf(請(qǐng)先創(chuàng)建兩個(gè)一元多項(xiàng)式！ n); break; addp=addpolyn(pa,pb); printpolyn(addp); break; case 3: if(pa=NULL) printf(請(qǐng)先創(chuàng)建兩個(gè) 一元多項(xiàng)式！ n); break; subp=subpolyn(pa,pb); printpolyn(subp); break; case 4: if(pa=NULL) printf(請(qǐng)先創(chuàng)建兩