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

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

課程設(shè)計(jì)報(bào)告

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

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

軟件工程

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

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

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

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

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

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

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

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

校。

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

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

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

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

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

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

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

測試。

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

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

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

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

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

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

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

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

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

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

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

2、基本操作：

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

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

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

四、全部源程序清單

#include\

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

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

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

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

該頂點(diǎn)的前一頂點(diǎn)的頂點(diǎn)號

inttS[Num];//S為已求得的在最短路徑上的頂點(diǎn)號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()