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

一、設(shè)計(jì)題目 一元多項(xiàng)式的加法、減法、乘法的實(shí)現(xiàn)。 二、主要內(nèi)容 設(shè)有一元多項(xiàng)式 Am(x)和 Bn(x). Am(x)=A0+A1x1+A2x2+A3x3+ +Amxm Bn(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) 首先判定多項(xiàng)式是否稀疏 2) 采用動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)； 3) 結(jié)果 M(x)中無重復(fù)階項(xiàng)和無零系數(shù)項(xiàng)； 4) 要求輸出結(jié)果的 升冪和降冪兩種排列情況 三、具體要求及應(yīng)提交的材料 1 每個(gè)同學(xué)以自己的學(xué)號(hào)和姓名建一個(gè)文件夾，如：“ 312009080611101 張三”。里面應(yīng)包括： 學(xué)生按照課程設(shè)計(jì)的具體要求所開發(fā)的所有源程序（應(yīng)該放到一個(gè)文件夾中） 、任務(wù)書和課程設(shè)計(jì)說明書的電子文檔。 2 打印的 課程設(shè)計(jì)說明書（注意：在封面后夾入打印的“任務(wù)書”以后再裝訂）。 四、主要技術(shù)路線提示 為把多個(gè)小功能結(jié)合成一個(gè)完整的小軟件，需 使用 “菜單設(shè)計(jì) ”技術(shù) （可以是控制臺(tái)方式下的命令行形式，若能做成圖形方式則更好）。 五、進(jìn)度安排 共計(jì)兩周時(shí)間，建議進(jìn) 度安排如下： 選題，應(yīng)該在上機(jī)實(shí)驗(yàn)之前完成 需求分析、概要設(shè)計(jì)可分配 4學(xué)時(shí)完成 詳細(xì)設(shè)計(jì)可分配 4 學(xué)時(shí) 調(diào)試和分析可分配 10 學(xué)時(shí)。 2學(xué)時(shí)的機(jī)動(dòng)，可用于答辯及按教師要求修改課程設(shè)計(jì)說明書。 注：只用課內(nèi)上機(jī)時(shí)間一般不能完成設(shè)計(jì)任務(wù)，所以需要學(xué)生自行安排時(shí)間做補(bǔ)充。 六、推薦參考資料 (不少于 3 篇 ) 1 蘇仕華等編著 ， 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) ，機(jī)械工業(yè) 出版社 ， 2007 2 嚴(yán)蔚敏 等編著 ， 數(shù)據(jù)結(jié)構(gòu) （ C語言版） ， 清華大學(xué) 出版社， 2003 3 嚴(yán)蔚敏 等編著 ， 數(shù)據(jù)結(jié)構(gòu) 題集 （ C語言版） ， 清華大學(xué) 出版社， 2003 指導(dǎo)教師 簽名日期 年 月 日 系 主 任 審核日期 年 月 日 摘 要 分析了 matlab， mathmatic， maple 等數(shù)學(xué)軟件對一元多項(xiàng)式的計(jì)算過程，步驟后。由于這些軟件比較大功能齊全，但是實(shí)用性不強(qiáng)。因此，利用microsoft visual studio 6.0 開發(fā)工具，編程實(shí)現(xiàn)了一元多項(xiàng)式的加法、減法、乘法的計(jì)算器系統(tǒng)，該系統(tǒng)具有一元多項(xiàng)式的加法、減法、乘法等功能。 關(guān)鍵詞： 一元多項(xiàng)式 ; 軟件 ; 計(jì)算 目 錄 1 需求分析 . 1 2 開發(fā)及運(yùn)行平臺(tái) . 2 3 概要設(shè)計(jì) . 3 4 詳細(xì)設(shè)計(jì) . 4 5 調(diào)試分析 . 8 6 測試結(jié)果 . 9 7 結(jié)論 . 11 致 謝 . 12 參考文獻(xiàn) . 13 附 錄 . 16 1 1 需求分析 動(dòng)態(tài)鏈表結(jié)構(gòu)下的一元多項(xiàng)式的加法、減法、乘法的實(shí)現(xiàn)。 設(shè)有一元多項(xiàng)式 Am(x)和 Bn(x). Am(x)=A0+A1x1+A2x2+A3x3+ +Amxm Bn(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） 輸入形式 和輸入值范圍 ： 輸入的系數(shù)為 float類型，輸入的冪為 int類型 請選擇 :1 請輸入你要運(yùn)算的第一個(gè)一元多項(xiàng)式的項(xiàng)數(shù) : 2 請輸入第 1項(xiàng)的系數(shù)和指數(shù) : 系數(shù) :1 指數(shù) :1 請輸入第 2項(xiàng)的系數(shù)和指數(shù) : 系數(shù) :1 指數(shù) :2 （ 2）輸出形式 請選擇 :5 一元多項(xiàng)式 A為： x+x2 一元多項(xiàng)式 B為： 4x4+5x5+6x6 （ 3） 程序所能達(dá)到的功能 1) 首先判定多項(xiàng)式是否稀疏 ; 2) 采用 動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn) ; 2 3) 結(jié)果 M(x)中無重復(fù)階項(xiàng)和無零系數(shù)項(xiàng) ； 4) 要求輸出結(jié)果的升冪和降冪兩種排列情況 （ 4）測試數(shù)據(jù)：包括正確地輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入及其輸出結(jié)果。 正確的輸入： 請選擇 :5 一元多項(xiàng)式 A為： x+x2 一元多項(xiàng)式 B為： 4x4+5x5+6x6 錯(cuò)誤的 輸入： 請輸入第 1項(xiàng)的系數(shù)和指數(shù) : 系數(shù) :1 指數(shù) :1 請輸入第 2項(xiàng)的系數(shù)和指數(shù) : 系數(shù) :2 指數(shù) :1 輸入的該項(xiàng)指數(shù)與多項(xiàng)式中已存在的某項(xiàng)相同 ,請重新創(chuàng)建一個(gè)正確的多項(xiàng)式 請輸入第 1項(xiàng)的系數(shù)和指數(shù) : 2 開發(fā)及 運(yùn)行平臺(tái) Windows 7 alienware 平臺(tái)上， Microsoft Visual studio 6.0 環(huán)境下開發(fā)。所以建議用戶在使用時(shí)，在 windows 7 平臺(tái)上使用。 3 3 概要設(shè)計(jì) 數(shù)據(jù)類型的定義 ： struct Node float coef;/結(jié)點(diǎn)類型，系數(shù) int exp;/指數(shù) ; typedef Node polynomial; struct LNode polynomial data;/鏈表類型 LNode *next; ; typedef LNode* Link; 模塊調(diào)用關(guān)系如圖 1 所示： 退出 一元多項(xiàng)式創(chuàng)建 一元多項(xiàng)式相加 一元多項(xiàng)式相減 4 圖 1 一元多項(xiàng)式計(jì)算器模塊調(diào)用圖 4 詳細(xì)設(shè)計(jì) 加法模塊： 5 void PolyAdd(Link &pc,Link pa,Link pb) Link p1,p2,p,pd; CopyLink(p1,pa); CopyLink(p2,pb); pc=new LNode; pc-nextnext; p2next; while(p1不為空且 p2不為空 ) if(p1-data.expdata.exp) then： p-next=p1;p=p-next; p1=p1-next; else if(p1-data.expp2-data.exp) then： p-nextnext;p2next; else p1-data.coefdata.coef+p2-data.coef;/指數(shù)相同，系數(shù)想加 if(p1-data.coef 不等于 0) p-nextnext; p1next; p2next; else pdnext; p2next; 6 delete pd;/如果系數(shù)為 0，則刪除該項(xiàng) if(p1!=NULL) then： p-next=p1;endif if(p2!=NULL) then ： p-next=p2;endif 減法模塊 ，如圖 2所示 ： 圖 2 減法模塊結(jié)構(gòu)圖 void PolySubstract(Link &pc,Link pa,Link pb) Link p,pt; CopyLink(pt,pb); pdata).coefdata).coef);/被減的多項(xiàng)式前加 -號(hào) pnext） ; PolyAdd(pc,pa,pt);/調(diào)用多項(xiàng)式加法運(yùn)算函數(shù) 開始 調(diào)用多 項(xiàng)式加法函數(shù)進(jìn)行運(yùn)算 將多項(xiàng)式 B 進(jìn)行復(fù)制 取多項(xiàng)式 B 的相反數(shù) 7 DestroyLink(pt); 乘法模塊： 如圖 3所示 圖 3 乘法模塊結(jié)構(gòu)圖 void PolyMultiply(Link &pc,Link pa,Link pb) Link p1,p2,p,pd,newp,t; pc=new LNode; pc-next=NULL; p1=pa-next; p2=pb-next; while(p1不為空 ) pd=new LNode; pd-next=NULL; p=new LNode; p-next=NULL; t=p; while(p2) newp=new LNode; newp-next=NULL; newp-data.coef=p1-data.coef*p2-data.coef;/系數(shù)相乘 開始 給出運(yùn)算的兩個(gè)多項(xiàng)式 按系數(shù)相乘指數(shù)相加進(jìn)行運(yùn)算 將運(yùn)算的結(jié)果相加并輸出 8 newp-data.exp=p1-data.exp+p2-data.exp;/指數(shù)相加 t-next=newp; t=t-next; p2=p2-next; PolyAdd(pd,pc,p);/調(diào)用加法函數(shù) CopyLink(pc,pd); p1=p1-next; p2=pb-next; DestroyLink(p); DestroyLink(pd); 5 調(diào)試分析 （ 1） 調(diào)試過程中遇 到的問題 ： 獨(dú)立測試各個(gè)模塊的功能時(shí)發(fā)現(xiàn)在創(chuàng)建鏈表后和另一個(gè)進(jìn)行運(yùn)算后多余的存儲(chǔ)單元沒有釋放而造成內(nèi)存的泄漏，還有對于鏈表的運(yùn)算時(shí)結(jié)束條件掌握不透徹導(dǎo)致沒有按計(jì)劃地去結(jié)束，比如在用 For 循環(huán)及 While 循環(huán)時(shí)沒有正確地判斷指針的移動(dòng)與結(jié)束條件而得不到自己想要的結(jié)果 。 進(jìn)入函數(shù)內(nèi)部調(diào)試時(shí)發(fā)現(xiàn)有誤用沒有初始化的變量，還有贅余的語句擾亂了代碼的健壯性。 在主函數(shù)中對各個(gè)函數(shù)的調(diào)用時(shí)沒有一個(gè)清晰的思路，使程序顯得很混亂，給調(diào)試造成了很大困難。 對非法操作控制的不夠完善，例如缺少對越界訪問及其非法數(shù)據(jù)的控制機(jī)制，使程 序的安全性下降。 9 （ 2）算法的時(shí)空分析 該程序的實(shí)現(xiàn)是用鏈表實(shí)現(xiàn)的，所以時(shí)間復(fù)雜度和空間復(fù)雜度主要來自于鏈表的操作，都是 O(n)。 （ 3）經(jīng)驗(yàn)和體會(huì) 編寫的程序不但要拿來使用，還要給別人查看，以便代碼的維護(hù)。所以代碼編寫的風(fēng)格盡量規(guī)范，清晰。變量要盡量少定義，結(jié)構(gòu)夜采用簡單的。另外，對指針的使用要小心，盡量在定義的時(shí)候就進(jìn)行初始化，避免野指針，指針的使用涉及到內(nèi)存的分配。 6 測試結(jié)果 判斷稀疏，如圖 4所示： 圖 4 判斷多項(xiàng)式是否稀疏 加法運(yùn)算 ，如圖 5所示 : 10 圖 5 加法測試結(jié)果 減法運(yùn)算 ，如圖 6所示 : 圖 6 減法測試結(jié)果 乘法運(yùn)算 ，如圖 7所示 : 圖 7 乘法測試結(jié)果 降冪升冪排序 ，如圖 8 所示 圖 8 降冪升冪排序 測試結(jié)果 11 7 結(jié)論 該程序基本實(shí)現(xiàn)了要求的 順序結(jié)構(gòu)、動(dòng)態(tài)鏈表結(jié)構(gòu)下的一元多項(xiàng)式的加法、減法、乘法 等功 能。代碼較為冗余，可讀性較差，可以多添加一些提示語句以及注釋。 在這次課程設(shè)計(jì)中我又進(jìn)一步地了解了數(shù)據(jù)結(jié)構(gòu)中算法的核心思想的重要性，懂得了一個(gè)程序地好壞關(guān)鍵在于算法是否優(yōu)秀，一個(gè)好的優(yōu)秀的算法可以使我們的程序更加完善，安全性更高以及有更高的效率。這次設(shè)計(jì)中我發(fā)現(xiàn)了自己的許多不足，如對指針的機(jī)制掌握的還不是很透徹，有的時(shí)候會(huì)出現(xiàn)指針指向錯(cuò)誤以及空指針的錯(cuò)誤 ,還有不能很好地分析自己算法地復(fù)雜度以及不能很好地使用控制機(jī)制使自己的程序流暢地運(yùn)行。 12 致 謝 感謝指導(dǎo)老師 給我的一些重要指導(dǎo)以及提供的資料，感謝 嚴(yán)蔚敏 編著的數(shù)據(jù)結(jié)構(gòu)等資料，讓我在編寫代碼的過程中少走了很多彎路。 13 參考文獻(xiàn) 1 蘇仕華等編著 .數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) .機(jī)械工業(yè) 出版社 .2007 2 嚴(yán)蔚敏 等編著 .數(shù)據(jù)結(jié)構(gòu) （ C語言版） .清華大學(xué)出版社 .2003 3 嚴(yán)蔚敏 等編著 .數(shù)據(jù)結(jié)構(gòu)題集 （ C語言版） .清華大學(xué)出版社， 2003 4鄭莉等 編著 . C+程序設(shè)計(jì)語言（第三版） .清華大學(xué)出版社， 2005.06北京 5.陳清華 朱紅主編 . Visual C+課程 設(shè)計(jì)案例精選與編程指導(dǎo) .東南大學(xué)出版社，2003.06，南京 6.劉振安等編著 . C+程序設(shè)計(jì)課程設(shè)計(jì) .機(jī)械工業(yè)出版社， 2004.08，北京 14 附 錄 附錄 1 源程序清單 #include/標(biāo)準(zhǔn)輸入輸出流 #include/使程序中可用鍵盤輸入函數(shù) #include/使程序中可用系統(tǒng)標(biāo)準(zhǔn)輸出函數(shù) #include/調(diào)用數(shù)學(xué)庫函數(shù) using namespace std;/命名空間 std內(nèi)定義的所有標(biāo)識(shí)符均有效 struct Node float coef;/結(jié)點(diǎn)類型，系數(shù) int exp;/指數(shù) ; typedef Node polynomial; struct LNode polynomial data;/鏈表類型 LNode *next; ; typedef LNode* Link; void CreateLink(Link &L,int n); void PrintList(Link L); void PolyAdd(Link &pc,Link pa,Link pb); void PolySubstract(Link &pc,Link pa,Link pb); 15 void CopyLink(Link &pc,Link pa); void PolyMultiply(Link &pc,Link pa,Link pb); int JudgeIfExpSame(Link pa,Link e); void DestroyLink(Link &L); int CompareIfNum(int i); void DestroyLink(Link &L) Link p; p=L-next; while(p) L-next=p-next; delete p; p=L-next; delete L; L=NULL; void CreateLink(Link &L,int n) if(L!=NULL) DestroyLink(L); Link p,newp; L=new LNode; L-next=NULL; (L-data).exp=-1;/創(chuàng)建頭結(jié)點(diǎn) p=L; for(int i=1;i(newp-data).coef; cout(newp-data).exp; if(newp-data.expnext=NULL; p=L; if(newp-data.coef=0) coutnext!=NULL)&(p-next-data).expdata).exp) p=p-next; /p指向指數(shù)最小的那一個(gè) if(!JudgeIfExpSame( L, newp) newp-next=p-next; p-next=newp; else coutnext; while(p-next!=NULL) if(abs(p-next-data.exp-p-data.exp)1) 17 flag=1; else flag=0; p=p-next; if(flag) coutnext; while(p!=NULL&(e-data.exp!=p-data.exp) p=p-next; if(p=NULL) return 0; else return 1; void PrintList(Link L) Link p; if(L=NULL|L-next=NULL) coutnext; if(p-data).coef0) if(p-data).exp=0) coutdata).coef;/如果指數(shù)為 0則直接輸出系數(shù) else if(p-data).coef=1&(p-data).exp=1) coutdata).coef=1&(p-data).exp!=1) coutdata).exp; else if(p-data).exp=1&(p-data).coef!=1) coutdata).coefdata).coefdata).exp; if(p-data).coefdata).exp=0) coutdata).coef;/如果指數(shù)為 0，則直接輸出系數(shù) else if(p-data.coef=-1&p-data.exp=1) coutdata.coef=-1&p-data.exp!=1) coutdata.exp; else if(p-data.exp=1) coutdata.coefdata).coefdata).exp; p=p-next; while(p!=NULL) if(p-data).coef0)/系數(shù)大于 0時(shí)輸出情況 if(p-data).exp=0) coutdata).coef; else if(p-data).exp=1&(p-data).coef!=1) coutdata).coefdata).exp=1&(p-data).coef=1) coutdata).coef=1&(p-data).exp!=1) coutdata).exp; else coutdata).coefdata).exp; if(p-data).coefdata).exp=0) coutdata).coef; else if(p-data.coef=-1&p-data.exp=1) coutdata.coef=-1&p-data.exp!=1) coutdata.exp; else if(p-data.exp=1) 19 coutdata.coefdata).coefdata).exp; p=p-next; coutnext=NULL; r=pc; p=pa; while(p-next!=NULL) q=new LNode; q-data.coef=p-next-data.coef; q-data.exp=p-next-data.exp; r-next=q; q-next=NULL; r=q; p=p-next; void PolyAdd(Link &pc,Link pa,Link pb) Link p1,p2,p,pd; CopyLink(p1,pa); CopyLink(p2,pb); pc=new LNode; pc-next=NULL; p=pc; p1=p1-next; p2=p2-next; while(p1!=NULL&p2!=NULL) if(p1-data.expdata.exp) 20 p-next=p1; p=p-next; p1=p1-next; else if(p1-data.expp2-data.exp) p-next=p2; p=p-next; p2=p2-next; else p1-data.coef=p1-data.coef+p2-data.coef; if(p1-data.coef!=0) p-next=p1; p=p-next; p1=p1-next; p2=p2-next; else pd=p1; p1=p1-next; p2=p2-next; delete pd;/如果系數(shù)為 0，則刪除該項(xiàng) if(p1!=NULL) p-next=p1; if(p2!=NULL) p-next=p2; void PolySubstract(Link &pc,Link pa,Link pb) 21 Link p,pt; CopyLink(pt,pb); p=pt; while(p!=NULL) (p-data).coef=(-(p-data).coef);/被減的多項(xiàng)式前加 -號(hào) p=p-next; PolyAdd(pc,pa,pt);/調(diào)用多項(xiàng)式加法運(yùn)算函數(shù) DestroyLink(pt); void Clear() system(pause); system(cls); /讓用戶重新選擇 void PolyMultiply(Link &pc,Link pa,Link pb) Link p1,p2,p,pd,newp,t; pc=new LNode; pc-next=NULL; p1=pa-next; p2=pb-next; while(p1!=NULL) pd=new LNode; pd-next=NULL; p=new LNode; p-next=NULL; t=p; while(p2) newp=new LNode; newp-next=NULL; newp-data.coef=p1-data.coef*p2-data.coef;/系數(shù)相乘 newp-data.exp=p1-data.exp+p2-data.exp;/指數(shù)相加 t-next=newp; t=t-next; p2=p2-next; 22 PolyAdd(pd,pc,p); CopyLink(pc,pd); p1=p1-next; p2=pb-next; DestroyLink(p); DestroyLink(pd); void Menu() cout0&ichoose; switch(choose) case 1: coutn; if(CompareIfNum(n)=1) coutn; if(CompareIfNum(n)=1) cout您的輸入有誤，請重新輸入 endl; Clear(); break; CreateLink(Lb,n); Clear(); break; case 2: if(La=NULL|Lb=NULL) cout您的多項(xiàng)式創(chuàng)建有誤，請重新選擇 endl; Clear(); break; PolyAdd(L,La,Lb); coutendl; cout設(shè)相加的兩個(gè)一元多項(xiàng)式 為和則： endl; coutendl; 24 coutA 的多項(xiàng)式為： ; PrintList(La); coutendl; coutB 的多項(xiàng)式為： ; PrintList(Lb); coutendl; cout相加后的結(jié)果為： ; PrintList(L); coutendl; Clear(); DestroyLink(L); break; case 3: if(La=NULL|Lb=NULL) cout您的多項(xiàng)式創(chuàng)建