數(shù)據(jù)結構課程設計-校園導航報告

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結構課程設計—校園導航報告

課程設計報告

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

吉林大學計算機科學與技術系

軟件工程

數(shù)據(jù)結構

校園導航系統(tǒng)設計報告

一、設計任務與目標

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

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

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

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

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

校。

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

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

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

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

結構和界面將實現(xiàn)的基本功能。

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

(4)調試，在設計完成后，調試系統(tǒng)運行的狀況，修改完善系統(tǒng),然后進行

測試。

二、方案設計與論證

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

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

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

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

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

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

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

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

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

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

2、基本操作：

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

初始條件：V是圖的頂點集，VR是圖中邊的集合。操作結果：按V和VR的定義構造圖G。（二）主要算法設計及相關算法補充

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

四、全部源程序清單

#include\

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

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

inttEdge[Num][Num];//Edge為帶權鄰接矩陣

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()