數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-校園導(dǎo)航報告

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)課程設(shè)計—校園導(dǎo)航報告

課程設(shè)計報告

學(xué)院、系：專業(yè)：班級：課程設(shè)計科目學(xué)生姓名：指導(dǎo)教師：完成時間：

吉林大學(xué)計算機(jī)科學(xué)與技術(shù)系

軟件工程

數(shù)據(jù)結(jié)構(gòu)

校園導(dǎo)航系統(tǒng)設(shè)計報告

一、設(shè)計任務(wù)與目標(biāo)

設(shè)計要求：設(shè)計你的學(xué)校的平面圖，至少包括10個以上的場所，每兩個場所間可以有不同的路，且路長也可能不同，找出從任意場所到達(dá)另一場所的最正確路徑（最短路徑）。

本系統(tǒng)是一個涉及吉林大學(xué)珠海學(xué)院相關(guān)景點和場所查詢系統(tǒng),是為了便利人們能夠更快更準(zhǔn)地獲得學(xué)校各個景點和場所的詳細(xì)信息。

本系統(tǒng)為用戶提供以下功能:

(一)、查詢了解學(xué)校概況，為導(dǎo)游參觀者提供關(guān)于學(xué)校的相關(guān)信息。(二)、查詢校園各個場所和景點信息;

(三)、為導(dǎo)游者或外來人員參觀人員提供校園交通信息，便利用戶走訪學(xué)

校。

校園導(dǎo)航查詢系統(tǒng)的開發(fā)方法總結(jié)如下：

(1)調(diào)查，了解學(xué)校各個場所與場所或者是各個景點與景點之間的信息，

路徑和距離，從外來人員或者參觀者和走訪者的角度出發(fā)，該如何設(shè)計才能滿足用戶需求。

(2)分析，對調(diào)查得到的數(shù)據(jù)進(jìn)行分析，根據(jù)其要求實現(xiàn)的功能分析系統(tǒng)

結(jié)構(gòu)和界面將實現(xiàn)的基本功能。

(3)設(shè)計與開發(fā)，設(shè)計系統(tǒng)界面并編輯實現(xiàn)其各個功能的代碼。

(4)調(diào)試，在設(shè)計完成后，調(diào)試系統(tǒng)運(yùn)行的狀況，修改完善系統(tǒng),然后進(jìn)行

測試。

二、方案設(shè)計與論證

校園旅游模型是由各個景點和景點以及場所和場所之間的路徑組成的，所以這完全可以用數(shù)據(jù)結(jié)構(gòu)中的圖來模擬。用圖的結(jié)點代表景點或場所，用圖的

邊代表景點或場所之間的路徑。所以首先應(yīng)創(chuàng)立圖的存儲結(jié)構(gòu)。結(jié)點值代表景點信息，邊的權(quán)值代表景點間的距離。結(jié)點值及邊的權(quán)值采用圖存儲。本系統(tǒng)需要查詢景點信息和求一個景點到另一個景點的最短路徑長度及路線，為便利操作，所以給每個景點一個代碼，用結(jié)構(gòu)體類型實現(xiàn)。計算路徑長度，最短路線和最正確路徑時可分別用迪杰斯特拉（Dijkastra）算法和哈密而頓回路算法實現(xiàn)。最終用switch選擇語句選擇執(zhí)行瀏覽景點信息或查詢最短路徑和距離。

搭建程序框架圖，其圖如下所示：選擇相應(yīng)數(shù)字2、主菜單查詢學(xué)校簡介，導(dǎo)航參觀路線和各個景點與場所之間的距離1、開啟導(dǎo)航在屏幕顯示輸出學(xué)校各個景點場所回車返回主菜選擇屏幕所設(shè)菜單單進(jìn)入子菜單選擇相應(yīng)數(shù)字3、子菜單退出系統(tǒng)

4、退出導(dǎo)航選擇景點與場所，查詢了解景點與場所信息，及景點與場所之間的最短路徑三、算法說明

（一）設(shè)計功能的實現(xiàn)

接下來根據(jù)以上搭建的程序框架完成各個模塊的算法1、

首先是抽象數(shù)據(jù)類型的定義：

圖的抽象數(shù)據(jù)類型的定義：ADTMgragh{

數(shù)據(jù)對象V:V是具有一致特征的數(shù)據(jù)元素的集合，稱為定點集數(shù)據(jù)關(guān)系R={VR}

VR={|V,W∈V,表示從V到W的邊}

2、基本操作：

CreateUDN(//創(chuàng)立圖

初始條件：V是圖的頂點集，VR是圖中邊的集合。操作結(jié)果：按V和VR的定義構(gòu)造圖G。（二）主要算法設(shè)計及相關(guān)算法補(bǔ)充

先創(chuàng)立圖存儲學(xué)校各個景點或場所，以圖的頂點表示景點或場所，以邊表示路徑，再利用迪杰斯特拉（DijkStra）算法求出校園各個地方的最短路徑，然后根據(jù)需要進(jìn)行補(bǔ)充相關(guān)算法。

四、全部源程序清單

#include\

#include\#include\#include\#include\

#defineNum11//最多頂點個數(shù)#defineuplimit100000//定義一個無窮大的值structintt{intvalue;};

inttEdge[Num][Num];//Edge為帶權(quán)鄰接矩陣

inttdist[Num];//dist為最短路程inttpath[Num];//path為最短路徑上

該頂點的前一頂點的頂點號

inttS[Num];//S為已求得的在最短路徑上的頂點號inttD[Num];

/**

*生成地圖，輸入地圖的基本信息*

**/

voidBuildMap(){

inti,j;

/*初始化平面圖矩陣*/for(i=0;iEdge[3][6].value=uplimit,Edge[3][7].value=uplimit,

Edge[3][8].value=26;

Edge[3][9].value=uplimit,Edge[3][10].value=uplimit;Edge[4][0].value=uplimit,Edge[4][2].value=uplimit;Edge[4][3].value=uplimit,Edge[4][5].value=9;Edge[4][6].value=uplimit,

Edge[4][7].value=uplimit

,

Edge[4][1].value=uplimit

,

Edge[4][4].value=0,

Edge[4][8].value=uplimit;

Edge[4][9].value=uplimit,Edge[4][10].value=60;

Edge[5][0].value=uplimitEdge[5][2].value=uplimit;Edge[5][3].value=uplimit,Edge[5][5].value=0;Edge[5][6].value=uplimit

Edge[5][8].value=50;

Edge[5][9].value=14,Edge[5][10].value=uplimit;

Edge[6][0].value=10,Edge[6][2].value=uplimit;Edge[6][3].value=uplimit,Edge[6][5].value=uplimit;

Edge[6][6].value=0,Edge[6][8].value=uplimit;

Edge[6][9].value=30,Edge[6][10].value=uplimit;

Edge[7][0].value=uplimitEdge[7][2].value=uplimit;Edge[7][3].value=uplimit,Edge[7][5].value=15;

Edge[7][6].value=35,Edge[7][8].value=uplimit;

Edge[7][9].value=13,Edge[7][10].value=uplimit;Edge[8][0].value=uplimit

Edge[8][2].value=uplimit;

Edge[8][3].value=26,Edge[8][5].value=50;Edge[8][6].value=uplimitEdge[8][8].value=0;

Edge[8][9].value=22,Edge[8][10].value=10;

,Edge[5][1].value=uplimit,

Edge[5][4].value=9,

,

Edge[5][7].value=15

,

Edge[6][1].value=10,

Edge[6][4].value=uplimit,

Edge[6][7].value=35,,Edge[7][1].value=uplimit,

Edge[7][4].value=uplimit,

Edge[7][7].value=0,,

Edge[8][1].value=21

,

Edge[8][4].value=uplimit;,

Edge[8][7].value=uplimit

,

Edge[9][0].value=uplimitEdge[9][2].value=uplimit;Edge[9][3].value=uplimit,Edge[9][5].value=14;

,

Edge[9][1].value=16,

Edge[9][4].value=uplimit,

Edge[9][6].value=30,Edge[9][7].value=13,Edge[9][8].value=22;

Edge[9][9].value=0,Edge[9][10].value=uplimit;Edge[10][0].value=uplimitEdge[10][2].value=uplimit;Edge[10][3].value=uplimit,Edge[10][5].value=uplimit;Edge[10][6].value=uplimit

,,

Edge[10][1].value=uplimit

,

Edge[10][4].value=60;

,

Edge[10][7].value=uplimit

Edge[10][8].value=10;

Edge[10][9].value=uplimit,Edge[10][10].value=0;}}}

/*找出場所間的最短距離--迪杰斯特拉算法*/

voidShortestDist(ints){

for(inti=0;i>s>>e;

cout\

break;case9:

cout>option;

while(option!='0'){switch(option)

{

case'1':num();

cout>option;

system(\清屏

break;

case'2'://具體信息

cout>c;info(c);if(c==11){cout>option;

}

break;

case'3'://查詢

BuildMap()