數(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 月 25 日。三、課程設(shè)計(論文) 地點: 2307 四、課程設(shè)計(論文)內(nèi)容要求：1本課程設(shè)計的目的1) 使學(xué)生增進對數(shù)據(jù)結(jié)構(gòu)各理論知識的熟練程度， 2) 加強算法設(shè)計的能力，為以后的數(shù)據(jù)庫原理等課程的學(xué)習(xí)打下良好基礎(chǔ)。， 2課程設(shè)計的任務(wù)及

2、要求 題目一：大整數(shù)的代數(shù)運算（難度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、印謄寫課程報告；3）課設(shè)報告包括目錄、內(nèi)容提要、正文、課程設(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

4、）個人創(chuàng)新（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（6）格式規(guī)范性及考勤是否降等級：是（）、否（）評閱人： 職稱： 年 月 日目 錄目 錄- 1 -正 文- 1 -一、 需求分析- 1 -二、 個人工作- 1 -三、概要設(shè)計- 3 -五、程序結(jié)果- 11 -課程設(shè)計體會- 16 -正 文一、 需求分析 本人選擇課程設(shè)計題目:一元多項式相加對于一個一元多項式，在計算機中的存儲以及運算，沒有一種固定的數(shù)據(jù)結(jié)構(gòu)來存儲它以及運算它，因此，在本課程設(shè)計中，我們要設(shè)計一中存儲結(jié)構(gòu)來表示一元多項式，并且設(shè)計算法來實現(xiàn)一元多項式相加。二、 個人工作 根據(jù)問題的需求分析 :我提出以下設(shè)計過程要存儲

5、一元多項式，那么我們就要設(shè)計一種結(jié)構(gòu)來存儲一元多項式，一個一元多項式A(x)=a0+a1x+a2x2+a3x3+a4x4.+anxn。由n+1個系數(shù)唯一確定，因此，可以用一個線性表（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)并不適合進行一元多項式的運

6、算，如果，采用單鏈表來存儲，則每一個非0項對應(yīng)著單鏈表的一個節(jié)點，且單鏈表按指數(shù)遞增有序Xishu排列，其結(jié)構(gòu)如下NextZhishu其中：Xishu是系數(shù)域，存放非0項的系數(shù)；Zhishu是指數(shù)域，存放非0項的指數(shù)；Next是指針域，存放指向下一節(jié)點的指針接收用戶輸入第一個一元多項式的信息三、 概要設(shè)計生成鏈表A，存儲第一個一元多項式接收用戶輸入第二個一元多項式的信息生成鏈表B，存儲第二個一元多多項式輸出第一個一元多項式 輸出第二個表達式一元多項式輸出兩個一元表達式相加的和 四、源程序（關(guān)鍵代碼分析）首先設(shè)計一個結(jié)構(gòu)體來存儲每一個節(jié)點struct Node double xishu; int

7、 zhishu; Node *next; ;對于存儲一元表達式，可用單鏈表來;void Creat(Node *&head, int n) / 生成帶表頭結(jié)點的單鏈表，除頭結(jié)點外另生成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;

8、 for(int i = 0; i < n; i+) p->next = (Node *)malloc(STRUCTSIZE); / 生成新結(jié)點，尾插入生成鏈表 p = p->next; cin >> p->xishu >> p->zhishu; p->next = NULL; 打印輸出節(jié)點：void Print(Node *&head) if(head->next = NULL) / 結(jié)果是0時直接輸出0 putchar('0'); else for(Node *p = head->next; p

9、 != NULL; p = p->next) if(p != head->next && p->xishu >0) / 當p非首項且指向的系數(shù)為正時才輸出'+' putchar('+'); / 之前只判定了p->xishu >0 if(p->xishu = 1) / 系數(shù)為1或-1時特殊處理 if(p->zhishu = 0) putchar('1'); / 判斷條件不能寫在一起： / if(p->xishu = 1 && p->zhishu = 0) p

10、utchar('1'); else if(p->xishu = -1) putchar('-'); else cout << p->xishu; switch(p->zhishu) / 指數(shù)為0或1時特殊處理 case 0: break; case 1: putchar('x'); break; default: p->zhishu < 0 ? printf("x(%d)", p->zhishu) : printf("x%d", p->zhishu);

11、/ 指數(shù)小于0時打括號 break; cout << endl; 兩個表達式相加并輸出：oid PrintAdd(Node *&pA, Node *&pB) / 傳進兩個鏈表的頭指針 Node *ha = pA; Node *hb = pB; Node *qa = ha->next; / ha, hb分別跟在qa, qb的后一位置 Node *qb = hb->next; / qa, qb分別指向Pa, Pb中當前比較元素 while(qa && qb) double sum = 0; int a = qa->zhishu; int

12、 b = qb->zhishu; switch( Compare(a, b) ) case '<': /第一種情況 非ha = ha->next; ha = qa; qa = qa->next; 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

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

14、 hb->next = hb->next->next; / 刪除qb指向的結(jié)點 qb->next = ha->next; / 將qb插入ha后qa前 ha->next = 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 = N

15、ULL;int lenA;int lenB;int flag = 0;while (true) cout << "=" << endl;cout << "ttt 一元多項式相加計算" << endl;cout << "=" << endl;cout << endl;cout << "輸入任意數(shù)字繼續(xù)，輸入0退出:" << endl;cin >> flag;if (flag = 0)cout <

16、;< endl; cout << endl; cout << endl; cout << endl; cout << endl;cout << "tttt謝謝使用!" << endl;cout << endl; cout << endl; cout << endl; cout << endl; cout << endl;system("pause");exit(0);cout << "請輸入第一個

17、多項式A的項數(shù)：" << endl,cin >> lenA;Creat(A, lenA); /生成A鏈表 cout << "請輸入第二個多項式B的項數(shù)：" << endl; cin >> lenB; /生成B鏈表Creat(B, lenB);cout << "ttA = " / 輸出A鏈表 Print(A);cout << "ttB = " / 輸出B鏈表 Print(B);PrintAdd(A, B); / A = A + B cout &

18、lt;< "ttA + B = "Print(A); / 輸出A+B cout << endl;Delete(A); Delete(B);/ 務(wù)必釋放結(jié)點 system("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)建單鏈表，對兩個表達式相加,有好多代碼呀.我實在沒有什么好的方法能決此問題呀.總