校園導(dǎo)航問題課程設(shè)計(jì)論文(已修改)
2025-08-07 11:26 本頁面
【正文】 摘 要校園導(dǎo)航要求每兩個(gè)場所間可以有不同的路，且路長也可能不同，找出從任意場所到達(dá)另一場所的最佳路徑(最短路徑)。要用“鄰接矩陣”來存儲(chǔ)各點(diǎn)間的距離，然后用Dijkstra算法求出最短路徑。所以采用工程思想，將系統(tǒng)共分以下五個(gè)模塊：節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)類型、創(chuàng)建導(dǎo)航圖函數(shù)、最短路徑導(dǎo)航函數(shù)、查詢函數(shù)聲明、主菜單。關(guān)鍵字 校園導(dǎo)航 查詢 Dijkstra算法目 錄摘 要 1校園導(dǎo)航問題 61 問題分析與任務(wù)定義： 62 數(shù)據(jù)結(jié)構(gòu)描述與定義 73 Dijkstra算法流程圖 84 程序運(yùn)行調(diào)試 95 結(jié)論 11參考文獻(xiàn) 12附錄： 12校園導(dǎo)航問題1 問題分析與任務(wù)定義：本課程設(shè)計(jì)的內(nèi)容為設(shè)計(jì)學(xué)校的平面圖,至少包括10個(gè)以上的場所,每兩個(gè)場所間可以有不同的路,且路長也可能不同,找出從任意場所到達(dá)另一場所的最佳路徑(最短路徑)。如圖1,圖中已標(biāo)出主要路線，各路線的長度如表1中所示。顯然要解決這一問題要用“鄰接矩陣”來存儲(chǔ)各點(diǎn)間的距離，然后用Dijkstra求出最短路徑。 7 圖書館1 會(huì)堂8 主樓 0 分析測試中心 3 二教學(xué)樓6 足球場410號(hào) 樓2一教學(xué)樓9 學(xué)生食堂 5 籃球場圖1：校園平面圖0←→1:200 0←→3:20 0←→7:100 0←→8:1001←→7:50 1←→8:50 2←→4:350 2←→5:2002←→6:100 2←→9:150 3←→4:290 3←→6:2003←→9:300 4←→5:200 4←→9:50 5←→9:1006←→7:200 7←→8:100 表1：各景點(diǎn)距離單位：米（m）2 數(shù)據(jù)結(jié)構(gòu)描述與定義define Max 20000define NUM 10typedef struct ArcCell{int adj。 /* 相鄰接的景點(diǎn)之間的路程 */}ArcCell。 /* 定義邊的類型 */typedef struct VertexType{int number。 /* 景點(diǎn)編號(hào) */char* sight。 /* 景點(diǎn)名稱 */char* info。 /* 景點(diǎn)描述 */}VertexType。 /* 定義頂點(diǎn)的類型 */typedef struct{VertexType vex[NUM]。 /* 圖中的頂點(diǎn)，即為景點(diǎn) */ArcCell arcs[NUM][NUM]。 /* 圖中的邊，即為景點(diǎn)間的距離 */int vexnum,arum。 /* 頂點(diǎn)數(shù)，邊數(shù) */}MGraph。 /* 定義圖的類型 */void CreateUDN(int v,int a) 函數(shù)描述：主要將每個(gè)節(jié)點(diǎn)進(jìn)行命名、每個(gè)頂點(diǎn)到其他所有定點(diǎn)的路徑值用鄰接矩陣進(jìn)行存儲(chǔ)。例：[0].sight=“分析測試中心”； 作用：使0號(hào)定點(diǎn)命名為“分析測試中心”；[0].info=“老師辦公和學(xué)生做實(shí)驗(yàn)”；作用：0號(hào)描述為“老師辦公和學(xué)生做實(shí)驗(yàn)”；[0][1].adj=[1][0].adj=200；作用：使0號(hào)節(jié)點(diǎn)到1號(hào)節(jié)點(diǎn)的路徑賦值為200，應(yīng)為是無向圖，所以1號(hào)節(jié)點(diǎn)到0號(hào)節(jié)點(diǎn)的路徑長度也應(yīng)賦值為200。void ShortestPath(int num)函數(shù)描述：用Dijkstra算法求無向網(wǎng)G的V0定點(diǎn)到其余定點(diǎn)V的最短路徑P[v]及其帶權(quán)長度D[v]。若P[v][w]為True，則w是從V0到V當(dāng)前求得最短路徑上的頂點(diǎn)。Final[v]為True當(dāng)且僅當(dāng)V∈S，即已經(jīng)求得從V0到V的最短路徑。char SearchMenu()void HaMiTonian(int)函數(shù)描述：哈密爾頓圖的遍歷。char Menu()描述。顯示導(dǎo)航圖中的所有導(dǎo)航節(jié)點(diǎn)，能夠快速方便的對(duì)各個(gè)地點(diǎn)進(jìn)行導(dǎo)航。3 Dijkstra算法流程圖4 程序運(yùn)行調(diào)試 本程序用microsoft visual c++ ：主界面：景點(diǎn)路徑查詢景點(diǎn)信息查詢推薦參觀路線6 結(jié)論 本系統(tǒng)實(shí)現(xiàn)了在大量的校園景點(diǎn)中任意指定兩個(gè)景點(diǎn)就能給出最短路徑。并且設(shè)計(jì)save()保存函數(shù)，和load()下載函數(shù)，分別用來保存創(chuàng)建的導(dǎo)航數(shù)據(jù)，和下載其它導(dǎo)航數(shù)據(jù)，這樣這個(gè)系統(tǒng)才能更加實(shí)用，void createadj()原來的函數(shù)原型為ar
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1