校園導(dǎo)游系統(tǒng)

1、南昌師范學(xué)院 課程設(shè)計(jì)報(bào)告 課程名稱： 數(shù)據(jù)結(jié)構(gòu)與算法 題目名稱： 校園導(dǎo)游系統(tǒng) 學(xué)生學(xué)院： 數(shù)學(xué)與計(jì)算機(jī)科學(xué)系 專業(yè)班級(jí)： 2016級(jí)計(jì)算機(jī)科學(xué)與技術(shù)本科班 小組組長(zhǎng)： 王明 小組成員： 王明鄭雙鳳呂運(yùn)發(fā) 指導(dǎo)老師： 熊小穎老師 精選范本 2017年 10月 15日 目錄 一、設(shè)計(jì)目的 3 二、問(wèn)題描述 3 三、基本要求 3 四、概要設(shè)計(jì) 3 五、主程序 4 六、測(cè)試數(shù)據(jù) 13 6.1調(diào)試程序所用數(shù)據(jù) 13 6.2程序的調(diào)試結(jié)果 七、總結(jié) 一、設(shè)計(jì)目的 隨著現(xiàn)代社會(huì)生活節(jié)奏的加快， 人們外出旅行以尋求放松的時(shí)間 越來(lái)越多。 考慮到游客不可能對(duì)所有景點(diǎn)都有所了解， 因此可能無(wú)法 找到游玩景點(diǎn)最

2、省時(shí)，最高效的路徑，而人工導(dǎo)游成本又過(guò)高，故使 用 C 語(yǔ)言，基于數(shù)據(jù)結(jié)構(gòu) 中圖的相關(guān)算法開發(fā)了“南昌師范學(xué)院 導(dǎo)游系統(tǒng)”。 開發(fā)本系統(tǒng)目的在于為來(lái)訪我校的游客提供一條最短 游覽路徑，本系統(tǒng)從實(shí)際出發(fā)，通過(guò)對(duì)校園平面圖的分析，將其轉(zhuǎn)化 為數(shù)據(jù)并保存在系統(tǒng)中，因此系統(tǒng)提供的路徑具有較大的可信性。 二、問(wèn)題描述 設(shè)計(jì)校園導(dǎo)游程序， 為來(lái)訪的客人提供服務(wù)， 為來(lái)訪我校的游客 提供一條在游客當(dāng)前位置到目的地的最短游覽路徑， 找到游玩景點(diǎn)最 省時(shí)，最高效的路徑。 三、基本要求 1. 假設(shè)有一所校園的平面圖，所含景點(diǎn)不小于 10 個(gè)，請(qǐng)選擇適當(dāng) 的坐標(biāo)來(lái)表示出該圖上的各個(gè)景點(diǎn)。 2. 為來(lái)訪的客人提供從當(dāng)

3、前位置到其他景點(diǎn)的最短路徑的咨詢； 3. 必須具有校園平面圖的修改和擴(kuò)充功能(即某些景點(diǎn)坐標(biāo)的修改 和景點(diǎn)個(gè)數(shù)的增加) 。 四、概要設(shè)計(jì) 算法思路 本設(shè)計(jì)的重難點(diǎn)在于問(wèn)題二的解決。 利用了弗洛伊德算法函數(shù)設(shè) 計(jì) Floyd() 本算法在設(shè)計(jì)時(shí)參考了 數(shù)據(jù)結(jié)構(gòu) C 語(yǔ)言版一書中 有關(guān) Floyd 算法的介紹，同時(shí)借鑒了如今網(wǎng)上流行的設(shè)計(jì)方式。 之所以選擇本算法來(lái)實(shí)現(xiàn)計(jì)算最短路徑， 原因在于本算法容易理 解，可以算出任意兩個(gè)節(jié)點(diǎn)之間的最短距離， 代碼編寫簡(jiǎn)單。 但 是，本算法缺點(diǎn)在于時(shí)間復(fù)雜度過(guò)高， 不適合用于計(jì)算大量數(shù)據(jù)。 Floyd算法首先將兩景點(diǎn)間路徑長(zhǎng)度數(shù)據(jù)存儲(chǔ)于數(shù)組Dvw中， 而后使用一

4、個(gè)三維數(shù)組用于存放最短路徑所經(jīng)過(guò)的頂點(diǎn)， 接下來(lái) 使用三重循環(huán)判斷兩景點(diǎn)之間直接路徑是否大于間接路徑， 若大 于，則將三維數(shù)組中存放的頂點(diǎn)信息更改為簡(jiǎn)介路徑所經(jīng)過(guò)的頂 點(diǎn)信息。以上部分完成后，當(dāng)用于標(biāo)記輸入數(shù)據(jù)是否合法的 flag=1 時(shí)，輸出錯(cuò)誤信息，提示用戶重新輸入，當(dāng)輸入數(shù)據(jù)合法 時(shí)，輸出以上程序得到結(jié)果。 五、主程序 #include #include #define MAX_VERTEX_NUM 100 / 最大頂點(diǎn)數(shù) #define MAX_INT 10000 / 無(wú)窮大 typedef int AdjType; typedef struct int piMAX_VERTEX_NU

5、M; 存放 v 到 vi 的一條最短 路徑 int end; PathType; typedef char VType; /設(shè)頂點(diǎn)為字符類型 typedef struct VType VMAX_VERTEX_NUM; / 頂點(diǎn)存儲(chǔ)空間 AdjType AMAX_VERTEX_NUMMAX_VERTEX_NUM; / 鄰接矩陣 MGraph;/ 鄰接矩陣表示的圖 /Floyd 算法 /求網(wǎng)G (用鄰接矩陣表示)中任意兩點(diǎn)間最短路徑 D是最短路徑長(zhǎng)度矩陣，path最短路徑標(biāo)志矩陣 void shortdistance(MGraph*G,int pathMAX_VERTEX_NUM,int DMAX

6、_VERTEX_NUM,int n) int i,j,k; for(i=0;in;i+)/ 初始化 for(j=0;jAijAij; for(k=0;kn;k+)/ 進(jìn)行 n 次試探 for(i=0;in;i+) for(j=0;jDik+Dkj) Dij=Dik+Dkj;/ 取小者 pathij=pathik;/ 改 Vi 的后繼 短路徑 for(i=0;in;i+)/ 輸出每對(duì)頂點(diǎn)間最短路徑長(zhǎng)度及最 for(j=0;jn;j+) printf(V%d 到 V%d 的最短長(zhǎng)度 :,i,j); printf(%dt,Dij);/ 輸出 Vi 到 Vj 的最短路 徑長(zhǎng)度 精選范本 k=pathi

7、j;/ 取路徑上 Vi 的后續(xù) Vk if(k=-1) printf(There is no path between V%d and V%dn,i,j);/ 路徑不存在 else printf( 最短路徑為 :); printf(V%d,i);/ 輸出 Vi 的序號(hào) i while(k!=j)/k 不等于路徑終點(diǎn) j 時(shí) printf(,V%d,k);/ 輸出 k k=pathkj;/ 求路徑上下一頂點(diǎn)序 號(hào) printf(,V%d)n,j);/ 輸出路徑終點(diǎn)序號(hào) printf(n); int introduce(char scenery) getchar(); printf( 請(qǐng)輸入景點(diǎn)對(duì)

8、應(yīng)的大寫字母 n); scanf(%c, switch(scenery) default:printf(沒有該景點(diǎn) n); case A:pri ntf(圖書館，距離南大門100米n); break; case B:pri ntf(實(shí)驗(yàn)樓，距離南大門200米n); break; case C:printf(理科樓，理科類學(xué)生上課地點(diǎn)n); break; n); case D:pri ntf(女宿舍樓，南昌師范學(xué)院的女孩子的家 精選范本 break; n); n); case E:pr intf（男宿舍樓，南昌師范學(xué)院的男孩子的家 break; case F:pr intf（大學(xué)生活動(dòng)中心，大學(xué)

9、生活動(dòng)休閑場(chǎng)所 break; case G:printf（田徑場(chǎng)，運(yùn)動(dòng)會(huì)舉辦場(chǎng)地n）; break; case H:printf（逸夫大禮堂，各種活動(dòng)舉辦場(chǎng)所n）; break; case T:printf體育館，正在建設(shè)中n）; break; case J:printf（綜合樓，領(lǐng)導(dǎo)辦公處n）; break; case K:printf（北大門，學(xué)校出口 n）; break; return 0; int main() char kk; char scenery; int i,j,k,v=A,m=11;/v 為起點(diǎn)， n 為頂點(diǎn)個(gè)數(shù) MGraph G; int pathMAX_VERTEX_N

10、UMMAX_VERTEX_NUM;/v 到各頂點(diǎn) 的最短路徑向量 int DMAX_VERTEX_NUMMAX_VERTEX_NUM;/v 到各頂 點(diǎn) 最短路徑長(zhǎng)度向量 char VMAX_VERTEX_NUM=A,B,C,D,E,F,G,H,I,J,K; int aMAX_VERTEX_NUMMAX_VERTEX_NUM= / 初始化 0,50,200,100,MAX_INT,MAX_INT,MAX_INT,MAX_INT,MAX_I NT,MAX_INT,MAX_INT, 50,0,100,MAX_INT,MAX_INT,MAX_INT,MAX_INT,MAX_INT, MAX_INT,M

11、AX_INT,MAX_INT, 200,100,0,MAX_INT,MAX_INT,100,50,MAX_INT,MAX_INT,MA X_INT,MAX_INT, 100,MAX_INT,MAX_INT,0,500,200,MAX_INT,MAX_INT,MAX_ INT,MAX_INT,MAX_INT, MAX_INT,MAX_INT,MAX_INT,500,0,300,MAX_INT,300,MAX_ INT,300,500, MAX_INT,MAX_INT,100,200,300,0,400,200,100,MAX_INT,MAX _INT, MAX_INT,MAX_INT,MAX_I

12、NT,MAX_INT,MAX_INT,400,0,1 00,300,MAX_INT,MAX_INT, MAX_INT,MAX_INT,MAX_INT,MAX_INT,200,200,100,0,MA X_INT,400,MAX_INT, MAX_INT,MAX_INT,50,MAX_INT,MAX_INT,100,300,MAX_I NT,0,MAX_INT,MAX_INT, MAX_INT,MAX_INT,MAX_INT,MAX_INT,300,MAX_INT,M AX_INT,400,MAX_INT,0,300, MAX_INT,MAX_INT,MAX_INT,MAX_INT,500,MA

13、X_INT,M AX_INT,MAX_INT,MAX_INT,300,0 ; for(i=0;im;i+) for(j=0;jm;j+) G.Aij=aij; 精選范本 printf( H* n); printf(* *n); printf(* *n); printf（* 歡迎使用南昌師范學(xué)院校園咨詢系統(tǒng)！ *n）; printf(* *n ); printf(* *n ); printf( H* n); printf(n); while(1) printf（1.景點(diǎn)信息查詢請(qǐng)按“ T鍵:n）; prin tf（2.景點(diǎn)最短路徑查詢（弗洛伊德算法）請(qǐng)按“2” 鍵:n); prin tf（3.景

14、點(diǎn)最短路徑查詢 迪杰斯特拉算法） 請(qǐng)按“ 3” 精選范本 鍵:n); printf（4.校內(nèi)景點(diǎn)地圖查詢請(qǐng)按“ 4”鍵:n）; printf（5.退出系統(tǒng)請(qǐng)按“ 5”鍵:n）; printf（請(qǐng)選擇：n）; scanf（%c, switch（k） case1:printf（景點(diǎn)介紹查詢 n）; introduce（scenery）;break; n）; case2:pri ntfC景點(diǎn)最短路徑查詢（弗洛伊德算法） shortdistance（break; case5:printf（謝謝使用！ n”）;exit（O）; return 0; 六、 測(cè)試數(shù)據(jù) 精選范本 6.1調(diào)試程序所用數(shù)據(jù) 精選范

15、本 6.2程序的調(diào)試結(jié)果 精選范本 E. “-jp Canto w P白 （幗川門 加郵U2的亀丄邑屢：1強(qiáng) 欝-扭豁 jaff ua的:ft短展匿“時(shí) 耳施路計(jì)弓；（uy”） JB賈IH兇尬吃長(zhǎng)曜：5E 邊嗨路螢為：【帕.IP U2.UB.UT.UJJ WeUS的息短展廈：25 最爼路空勺江血U1 g,U訂 uefri fif sea 親矩路 :(W,U1 ,UZtU6) JB- Lb：-A?空 E Iff ：3S9 七和掙咗為：UO山，U2,UEM） 啊扛韓的更區(qū)氏庫(kù)慮料 舄如豁庇 J：(UOH1 .U2.U5 U8) 榷駆路螢勺艸U4U1 ,U1.U&.U7.U41 帆乳U1O的最邁士度：10泗 量短翹為；(M8.U1 ,UahU&fU7.lRfWlB) 航粗路輕溝：（QI g 七、總結(jié) 雖然 經(jīng)過(guò)小組同學(xué)的努力，我們終于結(jié)束了這次的課程設(shè)計(jì), 我們盡了很大的努力，但是其中仍顯現(xiàn)出許多的不足。 其中在處理查詢兩景點(diǎn)最短路徑這一問(wèn)題時(shí)： 一開始對(duì)于題目的 閱讀不夠仔細(xì)， 將隨機(jī)的當(dāng)前位置當(dāng)成了， 一進(jìn)校門的位置作為與其 他建筑物的路徑距離。浪費(fèi)了一些時(shí)間，之后與重新思考思路。所以 由此發(fā)現(xiàn)對(duì)于需求的正確分析確實(shí)很重要。 另外經(jīng)過(guò)這次課程設(shè)計(jì)，我對(duì)程序中算法的概念理解的更加透 徹。算 法是程序中