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

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

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

3、印謄寫課程報(bào)告；3）課設(shè)報(bào)告包括目錄、內(nèi)容提要、正文、課程設(shè)計(jì)體會(huì)、參考文獻(xiàn)、附錄等；4）課程報(bào)告裝訂按學(xué)校的統(tǒng)一要求完成4）評(píng)分標(biāo)準(zhǔn)： 1）完成原理分析：20分； 2）完成設(shè)計(jì)過程：40分； 3）完成代碼分析：20分。4）個(gè)人創(chuàng)新工作：20分。學(xué)生簽名： 涂顯超 2015年 12 月 23日課程設(shè)計(jì)(論文)評(píng)審意見（1）原理分析 （20分）：優(yōu)（）、良（）、中（）、一般（）、差（）； （2）設(shè)計(jì)分析（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）； （3）程序流程（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（4）代碼分析（20分）：優(yōu)（）、良（）、中（）、一般（）、差（）；（5

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

5、一元多項(xiàng)式，那么我們就要設(shè)計(jì)一種結(jié)構(gòu)來存儲(chǔ)一元多項(xiàng)式，一個(gè)一元多項(xiàng)式A(x)=a0+a1x+a2x2+a3x3+a4x4.+anxn。由n+1個(gè)系數(shù)唯一確定，因此，可以用一個(gè)線性表（a0.a1.a2.a3.a4.an）來表示，每一項(xiàng)的指數(shù)i隱含在其系數(shù)ai的序號(hào)里，但是，單多想多項(xiàng)式的指數(shù)很高且變化較大時(shí)，在多項(xiàng)式的線性表中就會(huì)存在很多0元素，一個(gè)較好的存儲(chǔ)方法是只存儲(chǔ)非0元素，但是需要在存儲(chǔ)非0元素的同時(shí)存儲(chǔ)存儲(chǔ)相應(yīng)的指數(shù)，這樣，一個(gè)一元多項(xiàng)式的每一非0元素可由指數(shù)和系數(shù)唯一表示。但是，考慮到兩個(gè)一元多項(xiàng)式相加后，會(huì)改變多項(xiàng)式的系數(shù)和指數(shù)，因此采用順序表這種存儲(chǔ)結(jié)構(gòu)并不適合進(jìn)行一元多項(xiàng)式的運(yùn)

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

7、 zhishu; Node *next; ;對(duì)于存儲(chǔ)一元表達(dá)式，可用單鏈表來;void Creat(Node *&head, int n) / 生成帶表頭結(jié)點(diǎn)的單鏈表，除頭結(jié)點(diǎn)外另生成n個(gè)結(jié)點(diǎn) head = (Node *)malloc(STRUCTSIZE); head->xishu = 0; head->zhishu = 0; head->next = NULL; / 初始化頭結(jié)點(diǎn) cout << "請(qǐng)輸入各項(xiàng)系數(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é)點(diǎn)，尾插入生成鏈表 p = p->next; cin >> p->xishu >> p->zhishu; p->next = NULL; 打印輸出節(jié)點(diǎn)：void Print(Node *&head) if(head->next = NULL) / 結(jié)果是0時(shí)直接輸出0 putchar('0'); else for(Node *p = head->next; p

9、 != NULL; p = p->next) if(p != head->next && p->xishu >0) / 當(dāng)p非首項(xiàng)且指向的系數(shù)為正時(shí)才輸出'+' putchar('+'); / 之前只判定了p->xishu >0 if(p->xishu = 1) / 系數(shù)為1或-1時(shí)特殊處理 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時(shí)特殊處理 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時(shí)打括號(hào) break; cout << endl; 兩個(gè)表達(dá)式相加并輸出：oid PrintAdd(Node *&pA, Node *&pB) / 傳進(jìn)兩個(gè)鏈表的頭指針 Node *ha = pA; Node *hb = pB; Node *qa = ha->next; / ha, hb分別跟在qa, qb的后一位置 Node *qb = hb->next; / qa, qb分別指向Pa, Pb中當(dāng)前比較元素 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é)點(diǎn)，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é)點(diǎn) 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 一元多項(xiàng)式相加計(jì)算" << 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 << "請(qǐng)輸入第一個(gè)

17、多項(xiàng)式A的項(xiàng)數(shù)：" << endl,cin >> lenA;Creat(A, lenA); /生成A鏈表 cout << "請(qǐng)輸入第二個(gè)多項(xiàng)式B的項(xiàng)數(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é)點(diǎn) system("pause");system("cls");return 0; 四、 程序結(jié)果程序開始：輸入測(cè)試數(shù)據(jù)運(yùn)行結(jié)果：按任意鍵繼續(xù)：六、參考文獻(xiàn)1. 數(shù)據(jù)結(jié)構(gòu)C+版（第2版） 作者：王紅梅，出版社：清華大學(xué)出版社 2012年2. 數(shù)據(jù)結(jié)構(gòu) 作者：嚴(yán)蔚敏，出版社：清華大學(xué)出版社 2000 年3. 數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)題集作者：嚴(yán)蔚敏，出版社：清華大學(xué)出版社 2000 年課程設(shè)計(jì)體會(huì)在課程設(shè)計(jì)過程中的個(gè)人感想，字?jǐn)?shù)不多于200。（包括 : 課程設(shè)計(jì) 過程的收獲、遇到問題、遇到問題解決問題過程的思考、程序調(diào)試能力的思考、對(duì)數(shù)據(jù)結(jié)構(gòu)這門課程的思考、在課程設(shè)計(jì)過程中對(duì)數(shù)據(jù)結(jié)構(gòu)課程的認(rèn)識(shí)等內(nèi)容） 通過此數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目為: 一元多項(xiàng)式相加 在此課程設(shè)計(jì)過程中遇到好多問題呀,可能還沒有學(xué)好吧.如創(chuàng)建單鏈表，對(duì)兩個(gè)表達(dá)式相加,有好多代碼呀.我實(shí)在沒有什么好的方法能決此問題呀.總