13級(jí)數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)指導(dǎo)書

1、長(zhǎng)沙學(xué) 院課程設(shè)計(jì)指導(dǎo)書系（部） 計(jì)算機(jī)科學(xué)技術(shù)專 業(yè)軟件工程（服務(wù)外包）2013年13月1日課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)課程編號(hào)：JX020232主 筆 人：劉鋼欽主 審 人：潘怡一、課程設(shè)計(jì)的目的1 鞏固與加深對(duì)課程內(nèi)容的理解。通過應(yīng)用程序的設(shè)計(jì)過程，使學(xué)生加深對(duì)課程內(nèi)容的理解，鞏固 所學(xué)的專業(yè)基礎(chǔ)知識(shí)。2 熟悉開發(fā)工具的使用。通過編制與上機(jī)調(diào)試程序，使學(xué)生逐步積累編制與調(diào)試程序的經(jīng)驗(yàn)，促進(jìn) 實(shí)踐能力提高。3 培養(yǎng)與增強(qiáng)學(xué)生的綜合運(yùn)用能力。 通過有一定實(shí)用價(jià)值的應(yīng)用程序的開發(fā)， 激發(fā)學(xué)生的學(xué)習(xí)興趣， 促進(jìn)學(xué)生綜合運(yùn)用能力的提高。4 培養(yǎng)與增強(qiáng)學(xué)生的自學(xué)能力和利用文獻(xiàn)的能力。二、課程設(shè)計(jì)

2、的題目為了充分調(diào)動(dòng)學(xué)生的學(xué)習(xí)積極性與主動(dòng)性， 適應(yīng)不同興趣、 不同程度的學(xué)生對(duì)課程設(shè)計(jì)的要求， 本 課程設(shè)計(jì)提供四個(gè)任選題。 每個(gè)學(xué)生可以根據(jù)本人的興趣及能力選擇教師指定的選題， 也可以自定其他 的選題。1、一元多項(xiàng)式計(jì)算問題2、迷宮問題3、利用二叉排序樹對(duì)順序表進(jìn)行排序4、交通咨詢系統(tǒng)5、內(nèi)部排序算法的比較三、設(shè)計(jì)內(nèi)容1、一元多項(xiàng)式計(jì)算問題問題描述：設(shè)計(jì)一個(gè)稀疏多項(xiàng)式簡(jiǎn)單計(jì)算器基本要求：(1) 輸入并分別建立多項(xiàng)式A 和 B(2) 輸入輸出多項(xiàng)式，輸出形式為整數(shù)序列：n,c1,e1,c2,e2，其中n是多項(xiàng)式的項(xiàng)數(shù)，ci和ei 是第 i 項(xiàng)的系數(shù)和指數(shù)，序列按指數(shù)降序排列（3）完成兩個(gè)多項(xiàng)式

3、的相加、相減，并將結(jié)果輸出;測(cè)試數(shù)據(jù)：(1)A+B1482A= 3x -8x +6x +210 8 2B=2x +4x +-6x(2)A-B141086A=11x +3x +2x +10x +51486B=2x +3x +5x +7(3)A+B八 3 1f 3 1A=x +xB=-x -x(4)A+B7531A=0B=x +x +x +x10050201005020(5)A-BA=100x+50x +20x +xB=10x+10x +10x +x選作內(nèi)容：(1)多項(xiàng)式在x=1時(shí)的運(yùn)算結(jié)果(2)求多項(xiàng)式A和B的乘積2、迷宮問題問題描述：以一個(gè)m*n的長(zhǎng)方陣表示迷宮，0和1分別表示迷宮中的通路和障

4、礙。迷宮問題要求求出從入口（1,1）到出口（ m,n）的一條通路，或得出沒有通路的結(jié)論。 基本要求：首先實(shí)現(xiàn)一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的棧類型，然后編寫一個(gè)求迷宮問題的非遞歸程序，求得的通路以三元組（i，j，d）的形式輸出，其中：（i，j）指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一坐標(biāo)的方向。測(cè)試數(shù)據(jù)：左上角（1， 1）為入口，右下角（m, n）為出口。 選作內(nèi)容：（1）編寫遞歸形式的算法，求得迷宮中的所有可能的通路（2 ）以方陣的形式輸出迷宮及其通路迷宮中的所有可能的通路3、利用二叉排序樹對(duì)順序表進(jìn)行排序 問題描述：利用二叉排序樹對(duì)順序表進(jìn)行排序。基本要求：（1 ）生成一個(gè)順序表 L;（2）對(duì)所生成的順

5、序表 L構(gòu)造二叉排序樹；（3 ）利用棧結(jié)構(gòu)實(shí)現(xiàn)中序遍歷二叉排序樹；（4）中序遍歷所構(gòu)造的二叉排序樹將記錄由小到大輸出。 測(cè)試數(shù)據(jù)：用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生，表長(zhǎng)不小于20。選作內(nèi)容：用實(shí)現(xiàn)二叉排序樹的插入和刪除操作。4、交通咨詢系統(tǒng)問題描述： 設(shè)計(jì)一個(gè)交通咨詢系統(tǒng)，為自駕游旅行者客咨詢從任一個(gè)城市到另一個(gè)城市之間的最短路徑問題。設(shè)計(jì)分三個(gè)部分， 一是建立交通網(wǎng)絡(luò)圖的存儲(chǔ)結(jié)構(gòu)； 二是解決單源最短路徑問題； 最后再實(shí)現(xiàn)兩個(gè)城市 頂點(diǎn)之間的最短路徑問題?；疽螅? 對(duì)城市信息 （城市名、城市間的里程 ） 進(jìn)行編輯：具備添加、修改、刪除功能；2 咨詢以用戶和計(jì)算機(jī)對(duì)話方式進(jìn)行，要注意人機(jī)交互的屏幕界面

6、。由用戶選擇輸入起點(diǎn)、終點(diǎn)， 輸出信息：旅行者從起點(diǎn)、終點(diǎn)經(jīng)過的每一座城市。3. 主程序可以有系統(tǒng)界面、菜單；也可用命令提示方式；選擇功能模塊執(zhí)行，要求在程序運(yùn)行過程中可以反復(fù)操作。測(cè)試數(shù)據(jù)：參考數(shù)據(jù)結(jié)構(gòu)（ C 語言版）（嚴(yán)蔚敏 吳偉民編著） 7.6 節(jié)圖 7.33 的交通圖。 測(cè)試數(shù)據(jù)：北京到烏魯木齊；北京到昆明；廣州到哈爾濱；烏魯木齊到南昌；沈陽到昆明。5、內(nèi)部排序算法的比較問題描述： 通過隨機(jī)數(shù)據(jù)比較各內(nèi)部排序算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動(dòng)的次數(shù)，以取得直觀感受?；疽螅海?1）待排序表的表長(zhǎng)不小于 100；（ 2）至少要用 5 組不同的輸入數(shù)據(jù)作比較；（3）排序算法不少于 5 種；

7、（4）最后要對(duì)結(jié)果作簡(jiǎn)單的分析。測(cè)試數(shù)據(jù)：用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生。選作內(nèi)容：對(duì)不同的表長(zhǎng)做試驗(yàn)分析兩個(gè)指標(biāo)相對(duì)于表長(zhǎng)變化關(guān)系。四、設(shè)計(jì)步驟1. 問題分析和任務(wù)定義根據(jù)設(shè)計(jì)題目的要求，充分地分析和理解問題，明確問題要求做什么？ （而不是怎么做？） 限制條件是什么？2. 邏輯設(shè)計(jì)對(duì)問題描述中涉及的操作對(duì)象定義相應(yīng)的數(shù)據(jù)類型， 并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊， 定 義主程序模塊和各抽象數(shù)據(jù)類型。邏輯設(shè)計(jì)的結(jié)果應(yīng)寫出每個(gè)抽象數(shù)據(jù)類型的定義（ 包括數(shù)據(jù)結(jié)構(gòu)的描述和每個(gè)基本操作的功能說明 ），各個(gè)主要模塊的算法，并畫出模塊之間的調(diào)用關(guān)系圖；3. 詳細(xì)設(shè)計(jì)定義相應(yīng)的存儲(chǔ)結(jié)構(gòu)并寫出各函數(shù)的偽碼算法。 在

8、這個(gè)過程中， 要綜合考慮系統(tǒng)功能， 使得系統(tǒng)結(jié) 構(gòu)清晰、合理、 簡(jiǎn)單和易于調(diào)試，抽象數(shù)據(jù)類型的實(shí)現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可 能明確具體。 詳細(xì)設(shè)計(jì)的結(jié)果是對(duì)數(shù)據(jù)結(jié)構(gòu)和基本操作作出進(jìn)一步的求精， 寫出數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的類型定 義，寫出函數(shù)形式的算法框架；4. 程序編碼 把詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精為程序設(shè)計(jì)語言程序。同時(shí)加入一些注解和斷言，使程序中邏輯概 念清楚；5. .程序調(diào)試與測(cè)試采用自底向上， 分模塊進(jìn)行，即先調(diào)試低層函數(shù)。 能夠熟練掌握調(diào)試工具的各種功能， 設(shè)計(jì)測(cè)試數(shù) 據(jù)確定疑點(diǎn)，通過修改程序來證實(shí)它或繞過它。調(diào)試正確后， 認(rèn)真整理源程序及其注釋，形成格式和風(fēng) 格良好的源程序

9、清單和結(jié)果；6. 結(jié)果分析程序運(yùn)行結(jié)果包括正確的輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入及其輸出結(jié)果。 算法的時(shí)間、 空間復(fù) 雜性分析；7. 撰寫課程設(shè)計(jì)報(bào)告五、設(shè)計(jì)要點(diǎn)1 問題分析和功能定義準(zhǔn)確2 數(shù)據(jù)結(jié)構(gòu)定義合理3 關(guān)鍵算法描述清楚4 代碼編寫力求規(guī)范5 測(cè)試時(shí)注意邊緣條件的測(cè)試6 課程設(shè)計(jì)報(bào)告書按規(guī)范編寫六、設(shè)計(jì)進(jìn)度安排見課程設(shè)計(jì)工作計(jì)劃表。七、考核標(biāo)準(zhǔn)1考核方式課程設(shè)計(jì)結(jié)束時(shí)，在機(jī)房當(dāng)場(chǎng)驗(yàn)收。1) 教師檢查運(yùn)行結(jié)果是否正確。2) 學(xué)生回答教師提出的問題。3) 學(xué)生提交課程設(shè)計(jì)文檔( A4 紙打印)2評(píng)分方法1 課程設(shè)計(jì)的成績(jī)分為：優(yōu)、良、中、及格、不及格五個(gè)等級(jí)。2 評(píng)分標(biāo)準(zhǔn)：獨(dú)立完成課程設(shè)計(jì)、并有所創(chuàng)新，作品有實(shí)用價(jià)值，評(píng)為優(yōu)；獨(dú)立完成課程設(shè)計(jì)、個(gè)性化特色明顯， 課程設(shè)計(jì)報(bào)告完成較好， 評(píng)為良； 按規(guī)定完成課程設(shè)計(jì)并