數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告5

1、成都工業(yè)學(xué)院課程設(shè)計報告課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題 目一元多項式相加姓名涂顯超班級1405012學(xué)號22指導(dǎo)教師楊勇設(shè)計時間 2015-12-21 至 2013-12-25成都工業(yè)學(xué)院計算機工程系成都工業(yè)學(xué)院課程設(shè)計（論文）任務(wù)書一、 課程設(shè)計（論文）題目一元多項式相加二、課程設(shè)計（論文）工作自2015 年12月21日至2015 年12月2_日。三、課程設(shè)計（論文）地點：2307四、課程設(shè)計（論文）內(nèi)容要求：1 本課程設(shè)計的目的1）使學(xué)生增進對數(shù)據(jù)結(jié)構(gòu)各理論知識的熟練程度，2）加強算法設(shè)計的能力，為以后的數(shù)據(jù)庫原理等課程的學(xué)習(xí)打下良好基 礎(chǔ)。，2 課程設(shè)計的任務(wù)及要求題目一：大整數(shù)的代數(shù)運算（

2、難度0.5）題目二：一元多項式相加（難度0.5）題目三：表達式求值（難度0.7）題目四：迷宮問題（難度 0.6） 題目五：近似串匹配（難度0.7）題目六：數(shù)字旋轉(zhuǎn)方陣（難度0.5）題目七：信號放大器（難度0.5）題目八：哈夫曼算法的應(yīng)用（難度0.8）題目九：農(nóng)夫過河（難度 0.7）題目十：醫(yī)院選址問題（難度0.7）題目一：個人電話號碼查詢系統(tǒng)（難度0.5）題目十二：斐波那契查找（難度 0.6）在以上分屬各章的題目從不同章選至少三個題目完成，分別填寫三份報告。3）課程設(shè)計論文編寫要求1）詳細清晰地描述個人的課程設(shè)計工作；2）要按照本模板的規(guī)格打印謄寫課程報告；3）課設(shè)報告包括目錄、內(nèi)容提要、正文

3、、課程設(shè)計體會、參考文獻、附錄等;4）課程報告裝訂按學(xué)校的統(tǒng)-要求完成4）評分標準：1）完成原理分析：20分；2）完成設(shè)計過程：40分；3）完成代碼分析：20分。4）個人創(chuàng)新工作：20分。學(xué)生簽名：涂顯超2015年12月23日課程設(shè)計（論文）評審意見（1）原理分析（20分優(yōu)（）、良（）、中（般（）、差（）；（2）設(shè)計分析（20分優(yōu)（）、良（）、中（般（）、差（）；（3）程序流程（20分優(yōu)（）、良（）、中（般（）、差（）；（4）代碼分析（20分優(yōu)（）、良（）、中（般（）、差（）；（5）個人創(chuàng)新（20 分）:優(yōu)（）、良（）、中（般（）、差（）；（6）格式規(guī)范性及考勤是否降等級：是（）、否（)評閱人

4、：職稱：年 月 日目錄-1 -正文-1 -一、需求分析-1 -二、個人工作-1 -三、概要設(shè)計-3 -五、程序結(jié)果-9 -課程設(shè)計體會 -12 -一、需求分析本人選擇課程設(shè)計題目：一元多項式相加 對于一個一元多項式，在計算機中的存儲以及運算，沒有一種固定 的數(shù)據(jù)結(jié)構(gòu)來存儲它以及運算它，因此，在本課程設(shè)計中，我們要 設(shè)計一中存儲結(jié)構(gòu)來表示一元多項式，并且設(shè)計算法來實現(xiàn)一元多 項式相加。二、個人工作根據(jù)問題的需求分析：我提出以下設(shè)計過程要存儲一元多項式，那么我們就要設(shè)計一種結(jié)構(gòu)來存儲一元多項式，一個一元多項式A(x)=a0+a1x+a2xA2+a3xA3+a4xA4 .+anxn。由n+1個系數(shù)唯

5、一確定，因此，可以用一個線性表(a0.a1.a2.a3.a4 .an)來表示，每一項的指數(shù)i隱含在其系數(shù)ai的序號里，但是，單多想多項式的指數(shù)很高且變化較大時，在多項式的線性表中就會存在很多0元素，一個較好的存儲方法是只存儲非 0元素,但是需要在存儲非0元素的同時存儲存儲相 應(yīng)的指數(shù)，這樣，一個一元多項式的每一非0 元素可由指數(shù)和系數(shù)唯一表示。但是，考慮 到兩個一元多項式相加后，會改變多項式的 系數(shù)和指數(shù)，因此采用順序表這種存儲結(jié)構(gòu) 并不適合進行一元多項式的運算，如果，采 用單鏈表來存儲，則每一個非0項對應(yīng)著單鏈表的一個節(jié)點，且單鏈表按指數(shù)遞增有序 排列，其結(jié)構(gòu)如下XishuZhishuNex

6、t其中：Xishu是系數(shù)域，存放非0項的系數(shù)； Zhishu是指數(shù)域，存放非0項的指數(shù)；Next是指針域，存放指向下一節(jié)點的指針三、概要設(shè)計接收用戶輸入第二個一元多項 式的信息生成鏈表B，存儲第二個一元 多多項式輸出第一個一元多項式輸出第二個表達式一元 多項式輸出兩個一元表達式相 加的和四、源程序（關(guān)鍵代碼分析）首先設(shè)計一個結(jié)構(gòu)體來存儲每一個節(jié)點struct Node double xishu;int zhishu;Node *next; 對于存儲一元表達式，可用單鏈表來 ; void Creat(Node *&head, int n) / 生成帶表頭結(jié)點的單鏈表， 除 頭結(jié)點外另生成

7、 n 個結(jié)點head = (Node *)malloc(STRUCTSIZE);head->xishu = 0;head->zhishu = 0;head->next = NULL; / 初始化頭結(jié) 點八、cout << " 請輸入各項系數(shù)及指數(shù)(用空格隔開，如： a b 表示系數(shù)為 a,指數(shù)為 b) ： " << endl;Node *p = head;for(int i = 0; i < n; i+) p->next = (Node *)malloc(STRUCTSIZE); / 生成新結(jié)點,尾 插入生成鏈表p =

8、p->next;cin >> p->xishu >> p->zhishu; p->next = NULL; 打印輸出節(jié)點：void Print(Node *&head)/ 結(jié)果是 0if(head->next = NULL)時直接輸出 0putchar('0');else for(Node *p = head->next; p != NULL; p = p->next) if(p != head->next && p->xishu >0)/當 p 非首項且指向的系數(shù)為正時

9、才輸出 '+'putchar('+');/之前只判定了 p->xishu >0if(p->xishu = 1) 或 -1 時特殊處理/ 系數(shù)為 1if(p->zhishu= 0)putchar('1'); / 能寫在一起：判斷條件不/if(p->xishu = 1 && p->zhishu =0) putchar('1');else if(p->xishu =-1)putchar('-');elsecout << p->xishu;swit

10、ch(p->zhishu)/ 指數(shù)為0或 1 時特殊處理case 0:break;case 1:putchar('x');break;default:p->zhishu<0 ? prin tf("xA(%d)",p->zhishu) :prin tf("xA%d", p->zhishu);/指數(shù)小于 0 時打括號break; cout << endl;兩個表達式相加并輸出：/ 傳進兩個鏈表的頭指/ ha, hb 分別跟在 qa,/ qa, qb 分別指向 Pa,oid PrintAdd(Node

11、*&pA, Node *&pB) 針Node *ha = pA;Node *hb = pB;Node *qa = ha->next;qb 的后一位置Node *qb = hb->next;Pb 中當前比較元素 while(qa && qb) double sum = 0; int a = qa->zhishu; int b = qb->zhishu; switch( Compare(a, b) ) case '<': / 第一種情況 非 ha = ha->next; ha = qa;qa = qa->ne

12、xt;break;case '=': /第二種情況sum = qa->xishu + qb->xishu; if(sum != 0.0) qa->xishu = sum; ha = qa;else if(ha->next != qa)cout << "Error: ha->next != qa" << endl;ha->next = ha->next->next; / 刪除和為 0 的結(jié) 點， ha 不變，還在 qa 后一位置Delete(qa); if(hb->next != q

13、b)cout << "Error: hb->next != qb" << endl; hb->next = hb->next->next;/ 刪除 qb 指向的結(jié)/ 將 qb 插入 ha 后 qa<<Delete(qb); qb = hb->next; qa = ha->next; break;case '>':/第三種情況hb->next = hb->next->next; 點八、qb->next = ha->next;、八前ha->next

14、= qb;qb = hb->next;ha = ha->next; break;default:cout << "Error!" << endl; break;if(qb)ha->next = qb;Delete(hb);主函數(shù)代碼如下： int main(void) Node *A = NULL; Node *B = NULL; int lenA;int lenB;int flag = 0; while (true) cout" << endl;II,II,cout << "ttt co

15、ut元多項式相加計算 " << endl;<<=" << endl;cout << endl;cout << " 輸入任意數(shù)字繼續(xù)，輸入 0 退出 :" << endl;cin >> flag; if (flag = 0) cout << endl; cout << endl; cout << endl; cout << endl; cout << endl;cout << "tttt 謝謝

16、使用 !" << endl;cout << endl; cout << endl; cout << endl; cout << endl; cout <<endl;system("pause"); exit(0);cout << "請輸入第一個多項式 cin >> lenA;Creat(A, lenA); / 生成 A 鏈表 cout << "請輸入第二個多項式 cin >> lenB; / 生成 B 鏈表 Creat(B,

17、lenB);cout << "ttA = "Print(A);cout << "ttB = "Print(B);A 的項數(shù)： " << endl,B 的項數(shù)： " << endl;/ 輸出 A 鏈表/ 輸出 B 鏈表/ A = A + B/ 輸出 A+B務(wù)必釋放結(jié)點PrintAdd(A, B);cout << "ttA + B = "Print(A);cout << endl;Delete(A); Delete(B);/ system(&quo

18、t;pause"); system("cls");return 0;四、程序結(jié)果程序開始:輸入測試數(shù)據(jù)運行結(jié)果:按任意鍵繼續(xù):六、參考文獻1數(shù)據(jù)結(jié)構(gòu)C+版（第2版）作者：王紅梅，出版社：清華 大學(xué)出版社2012年2.數(shù)據(jù)結(jié)構(gòu) 作者：嚴蔚敏，出版社：清華大學(xué)出版社 2000 年3. 數(shù)據(jù)結(jié)構(gòu)實驗題集作者：嚴蔚敏，出版社：清華大學(xué)出版 社 2000 年課程設(shè)計體會在課程設(shè)計過程中的個人感想，字數(shù)不多于200。(包括：課程設(shè)計 過程的收獲、遇到問題、遇到問題解決問題過程的思考、 程序調(diào)試能力的思考、對數(shù)據(jù)結(jié)構(gòu)這門課程的思考、 在課程設(shè)計過程中對數(shù)據(jù) 結(jié)構(gòu)課程的認識等內(nèi)容)通過此數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題目為：一元多項式相加在此課程設(shè)計過程中遇到好多問題呀，可能還沒有學(xué)好吧.如創(chuàng)建 單鏈表，對兩個表達式相加，有好多代碼呀我實在沒有什么好的方法 能決此冋題呀.總算還是把我搞出來了 .可能遇到最大