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

1、課程論文（設(shè)計(jì)）2011-2012學(xué)年第 2 學(xué)期課程名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 課程性質(zhì)：實(shí)踐課 專業(yè)班級(jí)： 考核方式：考查 學(xué)生姓名：學(xué) 號(hào)：學(xué)時(shí)： 1 周教師姓名：評(píng)分：95分評(píng)語及評(píng)分1. 作業(yè)內(nèi)容12. 基本思路12.1 本校10個(gè)景點(diǎn)12.2 圖的初始化22.3 圖的遍歷22.4 求最短路徑33. 系統(tǒng)流程43.1 系統(tǒng)的簡(jiǎn)單說明43.2 系統(tǒng)流程圖54. 系統(tǒng)運(yùn)行效果圖54.1 校園導(dǎo)游界面54.2 華農(nóng)校園地圖64.3 景點(diǎn)的相關(guān)信息查詢64.4 任意兩個(gè)景點(diǎn)間的最短路徑74.5 退出校園導(dǎo)游系統(tǒng)85. 總結(jié)96. 參考文獻(xiàn)101. 作業(yè)內(nèi)容設(shè)計(jì)一個(gè)校園導(dǎo)游程序，為來訪客人提供各種

2、信息查詢?nèi)蝿?wù)?；疽螅海? ）設(shè)計(jì)你所在學(xué)校的校園平面圖，所含景點(diǎn)不少于 10個(gè)。以圖中頂點(diǎn)表示校 內(nèi)各景點(diǎn)，存放景點(diǎn)名稱、代號(hào)、簡(jiǎn)介信息，以邊表示路權(quán)，存放路徑長度等相關(guān)信 息。（2 ）為來訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢（3）為來訪客人提供圖中任意景點(diǎn)的問路查詢，即查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的一條 最短的簡(jiǎn)單路徑。2. 基本思路要完成對(duì)整個(gè)導(dǎo)游圖系統(tǒng)的功能實(shí)現(xiàn)，需要對(duì)的每一項(xiàng)功能都有清楚的設(shè)想和認(rèn) 識(shí)，了解并明確每一項(xiàng)功能的實(shí)現(xiàn)需要解決的問題，選擇正確并且高效的算法把問題 逐個(gè)解決，最終實(shí)現(xiàn)程序的正確調(diào)試運(yùn)行。有以下設(shè)計(jì)思路：（1）.結(jié)合本校的實(shí)際情況，選出10個(gè)景點(diǎn)；（2）.人為手工為選

3、出的10個(gè)景點(diǎn)賦上相關(guān)信息（名稱、代號(hào)、簡(jiǎn)介信息、以 及路權(quán)等等）；（3）.根據(jù)選出來的10個(gè)景點(diǎn)用鄰接矩陣存儲(chǔ)校園圖。（4）.依照景點(diǎn)的相關(guān)信息創(chuàng)建校園圖。（5）.把紙質(zhì)上的內(nèi)容，利用C+編程語言編寫查找景點(diǎn)相關(guān)信息的程序。（6）.根據(jù)人為賦值的路權(quán)，迪杰斯特拉算法計(jì)算任意兩點(diǎn)之間的最短路徑。（7）.綜上所訴，用一個(gè)主函數(shù)把這些板塊合成，生產(chǎn)一個(gè)菜單界面呈現(xiàn)在用戶 面前。為此，可把系統(tǒng)分為以下幾個(gè)核心：圖的初始化、圖的遍歷、求最佳路線。2.1 選出本校10個(gè)景點(diǎn)結(jié)合華南農(nóng)業(yè)大學(xué)實(shí)際情況，我選出以下 10個(gè)景點(diǎn)，從1到10編號(hào)：編號(hào)名稱編號(hào)名稱編號(hào)名稱編號(hào)名稱1校史館2紅滿堂3行政4西園樓5東

4、區(qū)運(yùn)動(dòng)場(chǎng)6樹木園7竹園8新校門9老校門10黑山運(yùn)動(dòng)場(chǎng)2.2 圖的初始化由于鄰接矩陣特殊的存儲(chǔ)方式，它非常便于快速的查找兩個(gè)頂點(diǎn)之間的邊上的權(quán) 值。所以，圖采用帶權(quán)的鄰接矩陣存儲(chǔ)。決定了圖的存儲(chǔ)方式后，以華南農(nóng)業(yè)大學(xué)10個(gè)景點(diǎn)的游覽地圖作為藍(lán)本，把校園地圖抽象化成頂點(diǎn)與邊構(gòu)成的圖形式，如圖2.2所示，途中數(shù)字代表線的權(quán)值。2.3 圖的遍歷 圖2. 2抽象化的校園導(dǎo)游圖圖的遍歷是圖中最基本的操作。圖的遍歷是指從圖中某一頂點(diǎn)出發(fā)，對(duì)圖中所有 頂點(diǎn)訪問一次且僅訪問一次。導(dǎo)游圖需要把每條路徑的信息都向游客展示，就需要讀 取每兩個(gè)頂點(diǎn)間的路徑信息。由于采用了帶權(quán)的鄰接矩陣存儲(chǔ)結(jié)構(gòu)進(jìn)行存儲(chǔ)，所以需 要針對(duì)這

5、一存儲(chǔ)結(jié)構(gòu)對(duì)路線進(jìn)行遍歷操作。其遍歷算法如圖 2.3所示。圖2.3遍歷算法示意圖2.4 求最短路徑基于本程序中圖的存儲(chǔ)是鄰接矩陣結(jié)構(gòu)存儲(chǔ)的圖結(jié)構(gòu)，因而采用適合該存儲(chǔ)結(jié)構(gòu)的 迪杰斯特拉算法用于解決求最短路徑的問題。迪杰斯特拉提出了一個(gè)按路徑長度遞增的持續(xù)產(chǎn)生最短路徑的算法，其基本思想是：設(shè)置一個(gè)集合S存放已經(jīng)找到最短路徑的頂點(diǎn)，S的初始狀態(tài)只包含源點(diǎn)v，對(duì)于Vi V-S，假設(shè)從源點(diǎn)v到Vi的有向邊為最短路徑。以后每求得一條最短路徑 v,， Vk，就將Vk加入集合S中，并將路徑V，vk，Vi，與原來的假設(shè)相比較，取路 徑長度較小者為最短路徑。重復(fù)上述過程，直到集合V中全部頂點(diǎn)加入到集合S中。如圖2

6、.4所示。輔助數(shù)組distn:元素disti表示當(dāng)前找到的從源點(diǎn)到終點(diǎn)Vi的最短路徑的長度。初態(tài)為：若從v到Vi有弧，則disti為弧上的權(quán)值；否則置disti 為。若當(dāng)前求得的終點(diǎn)為 vk ,則根據(jù)下式進(jìn)行迭代：disti=mi ndisti,distk+arcki 1= i = n輔助數(shù)組 pathn:元素 pathi 是一個(gè)串，表示當(dāng)前所找到的從源點(diǎn)到終點(diǎn) v i的最短路徑。初態(tài)為：若從 v到Vi有弧，則pathi 為“vv k”，否則置pathi 為空串。數(shù)組sn:存放源點(diǎn)和已經(jīng)生成的終點(diǎn)（即集合 S），初態(tài)為只有一個(gè)源點(diǎn)v。 算法的偽代碼描述是：1. 初始化數(shù)組 dist 、path

7、和 s ；2. while（ s 中的元素個(gè)數(shù) <n ）2.1 在 distn 中求最小值，其下標(biāo)為 k （則 vk 為正在生成的終點(diǎn)） ；2.2 輸出 distj 和 pathj ；2.3 修改數(shù)組 dist 和 path;2.4 將頂點(diǎn) vk 添加到數(shù)組 s 中；3. 系統(tǒng)流程3.1 系統(tǒng)的簡(jiǎn)單說明1. 創(chuàng)建校園圖：（1 ）先手工畫好華農(nóng)的 10 個(gè)景點(diǎn)的草圖，再用 C+ 語言輸出抽象化的校園地 圖。（ 2 ）再用 C+ 語言定義節(jié)點(diǎn)個(gè)數(shù) N ，編寫函數(shù) name（ ） 為景點(diǎn)賦值各類信 息項(xiàng)，函數(shù) information（ ），輸入各個(gè)景點(diǎn)的簡(jiǎn)介。（ 3 ）讀入道路的起始點(diǎn)，為鄰接

8、矩陣的邊賦相應(yīng)的值。2 利用函數(shù) travgraph來查找景點(diǎn)信息。3 創(chuàng)建一個(gè)校園圖 creat（Matrix_Graph*G） ，然后為相應(yīng)的邊賦上現(xiàn)實(shí)意義上的權(quán)值。4用 path（ ） 函數(shù)來求任意兩景點(diǎn)之間的最短路徑。5. 如果不查詢則調(diào)用 exit（ ） 函數(shù)退出。5 用 main 函數(shù)來輸出導(dǎo)游界面。11開始、'Main函數(shù)'Y:NO；調(diào)用查詢最短距離函E 數(shù)path是否再二返二回丄界農(nóng)面菜十單4. 系統(tǒng)運(yùn)行效果圖 4.1校園導(dǎo)游界面程序運(yùn)行，后臺(tái)對(duì)圖結(jié)構(gòu)進(jìn)行初始化，運(yùn)行結(jié)果如圖4.1園-異-游*1- 華農(nóng)校園地圖：2- 華農(nóng)景點(diǎn)信息：旅查找兩點(diǎn)間最短路徑=0.退出

9、華南農(nóng)業(yè)大學(xué)校訕：修德博學(xué)求實(shí)創(chuàng)新請(qǐng)輸人你的趕擇0-3:圖4.1校園導(dǎo)游節(jié)目圖4.2 華農(nóng)校園地圖函數(shù)輸出地圖，在輸入校園地圖的查看是通過抽象化10個(gè)景點(diǎn)來用printf() 選擇1之后彈出的界面，運(yùn)行結(jié)果如圖 4.2 。圖"-西園A- - - 5皿-黑山運(yùn)動(dòng)場(chǎng)“ 校史館編癥滿堂 >行政樓4B-» saa.<6 . 木園 <7-1+園'-td東區(qū)運(yùn)動(dòng)場(chǎng)<9層校門- * e新就門輸入任意鍵返回菜單圖4.2抽象化的華南農(nóng)業(yè)大學(xué)校園導(dǎo)游地圖4.3 景點(diǎn)的相關(guān)信息查詢景點(diǎn)的相關(guān)信息查詢是通過in formati on()函數(shù)來調(diào)用輸出的，在主菜單那輸

10、入2之后，拿第2個(gè)景點(diǎn)紅滿堂和第7個(gè)景點(diǎn)竹園來當(dāng)例子，第運(yùn)行結(jié)果如圖4.3.1 和圖4.3.2請(qǐng)輸人您娶査詢的景點(diǎn)序號(hào):、匸懈園X老稜門側(cè)-黒匝動(dòng)場(chǎng) 漏嘰鐘堂此景點(diǎn)的介紹是澄滿堂為日色圓頂建筑，外觀華美。日常重要報(bào)告召開地。歸的選擇是：圖4.3.1 景點(diǎn)2紅滿堂信息查詢請(qǐng)?jiān)僬磔斎肽樵兊木包c(diǎn)序號(hào):丄-孩史蛍皐緡膛茲酉園 5 G樹木園億竹園 圧亦枝門丸老校門10-圖4.3.2 景點(diǎn)7竹園信息查詢4.4 任意兩個(gè)景點(diǎn)間的最短路徑根據(jù)用戶的需求，在用戶輸入了起點(diǎn)和終點(diǎn)后計(jì)算出最短路徑是哪一條路徑。以下舉兩個(gè)例子。第一個(gè)例子的起點(diǎn)是 5東區(qū)運(yùn)動(dòng)場(chǎng)，終點(diǎn)是1校史館。第二個(gè)例子的起點(diǎn)是2紅滿堂，終點(diǎn)是1

11、0黑山運(yùn)動(dòng)場(chǎng)。運(yùn)行結(jié)果如圖441和圖442 所示。傳胚輸入足Fk樹木園<新檢門>>(?> X1KIJ矍山運(yùn)功場(chǎng)最矩路徑是此T這親<2 >><3)9 東M運(yùn)動(dòng)t 佃黑山運(yùn)動(dòng)u目”里山:云動(dòng)場(chǎng)強(qiáng).東匸勺場(chǎng)、"-新校門5.東區(qū)運(yùn)訪場(chǎng)你的輸入是，1B<1 校史館紅満室人.<3.行嘶-華農(nóng)一一也一一咽館-V-紅佛藝行政樓你陣輸人島a 禰想爭(zhēng)去的軸方倉請(qǐng)輸入1-1航：技史館"軻滿堂"行i玖樓*曹園 駙木園化竹同務(wù)新枸9.標(biāo)咖現(xiàn)価吐H 舊沁丫卡豊 備緒堂'遽改管仏護(hù)丘甬叱離站詛慰燔眸詐園淞玆弩禽木園¥

12、出匱«>Sl化老松門汕一黒山運(yùn)就細(xì)頑臉昨是伽七徐仙趙6.m詞隊(duì)竹園氛新務(wù)|一圖441從東區(qū)運(yùn)動(dòng)場(chǎng)到校史館的最短路徑圖442從紅滿堂到黑山運(yùn)動(dòng)場(chǎng)的最短路徑根據(jù)截圖可知，在現(xiàn)實(shí)生活中的最短路徑也是如此。證明了程序的正確性。4.5 退出校園導(dǎo)游系統(tǒng)用戶滿足了需求之后，只要在界面菜單處輸入4便可退出此次校園導(dǎo)游系統(tǒng)。運(yùn)行結(jié)果如圖4.5 。按吒意鍵退出?:謝謝您的使用辛*ress 虱n日to continue圖4.5 退出校園導(dǎo)游系統(tǒng)5. 總結(jié)由于設(shè)計(jì)者水平有限，本導(dǎo)游圖系統(tǒng)的功能還比較簡(jiǎn)單，還有一些好的設(shè)想沒有 實(shí)現(xiàn)：比如添加管理模式，使得公園管理人員能夠同樣方便的更改導(dǎo)游圖，因此更改

13、 這一導(dǎo)游圖還必須在程序員的幫助下進(jìn)行。另外，本導(dǎo)游圖系統(tǒng)還有一定的局限性， 如果存在只有一條通路的景點(diǎn)，導(dǎo)游圖將無法求得最佳旅游路徑。公園的導(dǎo)游圖系統(tǒng) 的這些不足請(qǐng)老師多多諒解。通過這次的課程設(shè)計(jì)左右，讓我對(duì)數(shù)據(jù)結(jié)構(gòu)中定義無向 圖和創(chuàng)建無向圖的理解更加深刻，不斷提升認(rèn)識(shí)，提高編程技巧，借以不斷地提高程 序設(shè)計(jì)水平，了解數(shù)據(jù)結(jié)構(gòu)在編寫比較復(fù)雜的程序的重要作用；理解了迪杰斯特拉算 法的原理，但對(duì)于其算法的程序編寫還是不太明白；學(xué)會(huì)了在編寫幾百行程序時(shí)如何 查找錯(cuò)誤，如何改錯(cuò)誤等等?？偠灾?，這次的課程設(shè)計(jì)很好地鍛煉自己實(shí)際操作能力！參考文獻(xiàn)1 嚴(yán)蔚敏，吳偉民 .數(shù)據(jù)結(jié)構(gòu)（ C 語言版） .清華大

14、學(xué)出版社 .1997.2 李春葆，尹為民，李蓉蓉 . 數(shù)據(jù)結(jié)構(gòu)教程（第 3 版）上機(jī)實(shí)驗(yàn)指導(dǎo) . 清華大學(xué)出版 社.2009.3 滕國文 .數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) .清華大學(xué)出版社 .2010.218-223.4 蔣盛益 .數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)指導(dǎo)與訓(xùn)練 .中國水利水電出版社 .2003./ 程序名稱：校園導(dǎo)游系統(tǒng)/ 程序員：/ 編寫時(shí)間： 2012 年 6 月#define N 10#define MAX 25#define MAXedg 30#include <stdio.h>#include <string.h>#include <stdlib.h>#include

15、 <conio.h> void clrscr()system("cls");typedef int AdjMatrixMAXMAX;typedef structint vexsMAX;AdjMatrix arcs;Matrix_Graph;typedef structchar name10;char information100;struct edgenode *link; vexnode;typedef struct edgenode int adjvex;int length;char info10;char info2100; struct edgenod

16、e *next;edgenode, *Node ;typedef struct Edgeint lengh; int ivex, jvex; struct Edge *next; EdgeType;typedef structint num;char name10; vertex;typedef structvertex vexsMAX;int edgesMAXMAX;adjmax;void Name(int i) switch(i)case 1:printf（"1: 校史館 nn"）;break;case 2: printf（"2: 紅滿堂 nn"）;

17、break;case 3: printf（"3:行政樓 nn"）;break;case 4: printf（"4:西園 nn"）;break;case 5: printf（"5: 東區(qū)運(yùn)動(dòng)場(chǎng) nn"）;break;case 6: printf（"6:樹木園 nn"）;break;case 7: printf（"7:竹園 nn"）;break;case 8: printf（"8:新校門 nn"）;break;case 9: printf（"9:老校門 nn"

18、）;break;case 10:printf（"10: 黑山運(yùn)動(dòng)場(chǎng) nn"）;break;default:printf（" 景點(diǎn)編號(hào)輸入錯(cuò)誤！請(qǐng)輸入 1-10 的數(shù)字編號(hào)！ nn"）; break; void Information（int i）/* 景點(diǎn)介紹 */switch（i）case 1:printf（" 校史館 : 華農(nóng)校史檔案保存的地方。為原來華南農(nóng)學(xué)院地址，建筑中西 結(jié)合，每屆畢業(yè)班照相處。 nn"）;break;case 2:printf（" 紅滿堂為白色圓頂建筑，外觀華美。日常重要報(bào)告召開地。 nn&quo

19、t;）;break;case 3:printf（" 行政樓：為學(xué)校日常事務(wù)辦公點(diǎn)，外觀壯麗，是華農(nóng)的標(biāo)志性建筑。 nn"）;break;case 4:printf（" 西園：坐落華山學(xué)生區(qū)。分為三層，第一層和第二層為學(xué)生餐廳，第三層為自助餐。 nn"）;break;case 5:printf（" 東區(qū)運(yùn)動(dòng)場(chǎng)：是華農(nóng)全校最大設(shè)施最先進(jìn)齊全的運(yùn)動(dòng)場(chǎng)，平時(shí)各類體 育比賽都在這里進(jìn)行。 nn"）;break;case 6:printf（" 樹木園：面積寬廣，里面有眾多珍貴樹種。 nn"）;break;case 7:prin

20、tf（"竹園：校內(nèi)高檔賓館，為外校嘉賓專設(shè)住宿。 nn"）;break;case 8:printf（"新校門：華農(nóng)百年校慶時(shí)建立，牌坊建筑。 。 nn"）;break;case 9:printf（"老校門：在地鐵口附件， 是華農(nóng)重要標(biāo)志之一。 nnn"）;break;case 10:printf（"黑山運(yùn)動(dòng)場(chǎng)：面積不大，為研究生和老師而設(shè)立的運(yùn)動(dòng)場(chǎng)。nn"）;break;default:printf（"景點(diǎn)編號(hào)輸入錯(cuò)誤！請(qǐng)輸入1->10的數(shù)字編號(hào)！ nn"）; break;void tra

21、vgraph（vexnode g,int n,adjmax adj） /查找指定景點(diǎn)信息int i = 1,flag = 1,len;char ch;printf（"ttt請(qǐng)輸入您要查詢的景點(diǎn)序號(hào) : 、nn"）;printf（"ttt1.校史館 2. 紅滿堂 3. 行政樓 4. 西園 5. 東區(qū)運(yùn)動(dòng)場(chǎng)n"）;printf（"ttt6.樹木園 7. 竹園 8. 新校門 9. 老校門 10. 黑山運(yùn)動(dòng)場(chǎng)n"）;printf（" 你的選擇是 "）;scanf（"%d",&len）;getch

22、ar（）;printf（"此景點(diǎn)的名稱是 :"）;Name（len）;printf（"此景點(diǎn)的介紹是 :"）;Information（len）;doprintf（"tt是否繼續(xù) ? Y/N n"）;printf（"tt你的選擇是： "）;scanf("%c",&ch); getchar(); if(ch = 'Y' | ch = 'y')clrscr();flag = 1;i = 1;printf("ttt 請(qǐng)?jiān)俅屋斎肽樵兊木包c(diǎn)序號(hào) :nn&

23、quot;);printf("ttt1. 校史館 2. 紅滿堂 3. 行政樓 4. 西園 5. 東區(qū)運(yùn)動(dòng) 場(chǎng)n");printf("ttt6. 樹木園 7. 竹園 8. 新校門 9. 老校門 10. 黑 山運(yùn)動(dòng)場(chǎng) n");printf(" 你的選擇是 "); scanf("%d",&len); getchar();printf("此景點(diǎn)的名稱是 :");Name(len);printf("此景點(diǎn)的介紹是 :");Information(len);continue ;e

24、lse flag = 0;printf("tt請(qǐng)?jiān)俅伟椿剀囨I或者任意鍵加回車鍵返回至主菜單 "); break;while(1);void creat(Matrix_Graph *G)int i,j;for(i=1;i<=N;i+) G->vexsi=i;for(i=1;i<=N;i+)for(j=1;j<=N;j+) G->arcsij=0;G->arcs12=1; G->arcs19=7;G->arcs21=1;G->arcs23=2;G->arcs24=9;G->arcs29=6;G->arcs3

25、2=2; G->arcs34=7;G->arcs37=3;G->arcs39=4;G->arcs310=15;G->arcs43=7;G->arcs46=25;G->arcs56=6;G->arcs58=10;G->arcs64=25;G->arcs67=2;G->arcs76=2;G->arcs75=18;G->arcs710=10;G->arcs85=10;G->arcs89=9;G->arcs91=7;G->arcs93=4;G->arcs103=15;G->arcs42=9

26、G->arcs410=22;G->arcs57=18;G->arcs65=6;G->arcs610=9;G->arcs73=3;G->arcs78=5;G->arcs87=5;G->arcs92=6;G->arcs98=9;G->arcs104=22;G->arcs106=9; G->arcs107=10;for(i=1;i<=N;i+)for(j=1;j<=N;j+)if(G->arcsij=0) G->arcsij=MAX;void path(Matrix_Graph *G,int s,int

27、e)int i,j,u,c=1,t,v;int rN+1N+1;int TN,flagN,dN;for(i=0;i<=N;i+) for(j=0;j<=N;j+) rij=0; for(i=1;i<=N;i+)Ti=-1;flagi=1;di=MAX;flags=0;while(c<=N)t=MAX;for(i=1;i<=N;i+)if(flagi&&G->arcssi<t)t=G->arcssi;v=i;rv1=v;for(i=1;i<=c;i+)for(j=1;j<=N;j+)if(flagj&&d

28、i+G->arcsTij<t)t=di+G->arcsTij;v=j;if(rv0!=-1)u=1;while(rTiu!=0)rvu=rTiu;u+;rvu=v;rv0=-1;Tc=v;flagv=0;dc=t;c+;printf("n 最短路徑是以下這條 :n(%d)",s); j=1;while(rej!=0)printf("->(%d)",rej);j+; printf("nn");int main()int i,j;Matrix_Graph G;creat(&G);int n = 0;vexn

29、ode gMAX;EdgeType eMAXedg;adjmax adj;char choice = 'x'while(1)clrscr();printf("nnttt *校- 園- 導(dǎo) - 游*");printf("nttnn");printf("ttt1.華農(nóng)校園地圖 :nn");printf("ttt2.華農(nóng)景點(diǎn)信息 :nn");printf("ttt3.查找兩點(diǎn)間最短路徑 :nn");printf("ttt0.退出 nn");printf("nttnn"