校園導航系統(tǒng)-數(shù)據(jù)結(jié)構(gòu)

校園導航系統(tǒng)-數(shù)據(jù)結(jié)

構(gòu)

-CAL-FENGHAI.-(YICAI)-CompanyOne1

《數(shù)據(jù)結(jié)構(gòu)預與算法分析》

^^呈設計報告

題目：校園導航系統(tǒng)

班級：網(wǎng)絡工程

XXX

學號：XXXXXXX

指導教師：XXX

日期：2022/7/11

目錄

1.任務說明（要求、知識點、實現(xiàn)的功能）............................................1

1.1題目：........................................................................1

1.2要求：........................................................................1

1.3知識點....................................................................1

2.概要設計（結(jié)構(gòu)體類型及函數(shù)聲明，功能模塊圖，流程圖）.........................2

2.1結(jié)構(gòu)體類型及函數(shù)聲明........................................................2

22功能Wi圖...................................................................3

2.3流程圖......................................................................3

3.1節(jié)點數(shù)據(jù)結(jié)構(gòu)類型：..........................................................5

3.2創(chuàng)建導航圖函數(shù)：............................................................5

3.3最短路徑導航函數(shù)：..........................................................5

3.4導航菜單函數(shù)聲明............................................................6

4調(diào)試分析（浮現(xiàn)哪些問題，如何解決）................................................6

5.測試結(jié)果.........................................................................6

6.總結(jié)............................................................................9

7.附錄.............................................................................9

7.1源代碼......................................................................9

72參考文獻....................................................................22

2

1.任務說明(要求、知識點、實現(xiàn)的功能)

1.1題目：

校園導航系統(tǒng)

1.2要求：

用無向網(wǎng)表示你所在學校的校園景點品面圖，圖中頂點表示主要景點，存放景點的編號,

名稱，簡紹等信息，圖中的邊表示景點間的道路，存放路徑長度等信息。

系統(tǒng)功能：

(1)景點信息簡紹

(2)任意兩景點間最短距離

(3)任意一點到所有點最短距離

1.3知識點：

圖的創(chuàng)建，圖的搜素，領接矩陣，迪杰斯特拉算法，結(jié)構(gòu)體，函數(shù)的聲明與調(diào)用等知識

1

2.概要設計（結(jié)構(gòu)體類型及函數(shù)聲明，功能模塊

圖，流程圖）

2.1結(jié)構(gòu)體類型及函數(shù)聲明

在近一個星期的努力下，我編寫的校園導航系統(tǒng)軟件終于能夠成功完成。采用工程思

想，將系統(tǒng)共分一下幾個模塊:導航圖建立模塊、求最短路徑模塊、主菜單；

下面是具體各功能簡單的實際應用：

?導航圖建立模塊：采用上述結(jié)構(gòu)體類型對導航圖中每一個節(jié)點進行賦值。包括：

各定點的名稱（地點名），各個節(jié)點到其他所有節(jié)點的真實路徑長度（賦權(quán)

值）。

?求廚豆路徑模塊：本模塊的基本思想是采用迪杰斯特拉算法求最短路徑。次模

塊是本校園導航系統(tǒng)的核心模塊，求兩點間的最短路徑與求一點到其他所有點

最短路徑兩個子功能均是在最短路徑算法模塊的基礎上進行調(diào)用，進而實現(xiàn)導

航功能。

?主菜單：主菜單中主要是顯示導航圖中的所有導航節(jié)點，能夠快速方便的對各

個地點進行導航。

以上程序的幾個模塊，構(gòu)成為了校園導航系統(tǒng)的基本組成部份，程序運行良好,達到了

課程設計的基本要求。由于所學知識有限，功能各個方面還有欠妥之處，希冀得到指出與

改正。

函數(shù)聲明：

intCreateUDN（MGraph&G）創(chuàng)建導航圖函數(shù)

2

voidShortPath(MGraph&G,intvO,intp[MAX_V][MAX_V],intd[])最短路徑導航函數(shù)

voidmenu()導航菜單聲明

2.2功能模塊圖

總功能模塊圖

2.3流程圖

迪杰其耐立算法流程圖

3

開始

d[vO-1)=0

final[v0-1]=1

toe[Q}=Y0U.

4

3.詳細設計(數(shù)據(jù)類型實現(xiàn)、編碼)

3.1節(jié)點數(shù)據(jù)結(jié)構(gòu)類型：

^defineMAX_V40〃最大頂點個數(shù)

typedefstruct

(

char*vexs[MAX_V];〃頂點向量

intarcs[MAX_V][MAX_V];〃鄰接矩陣

intvexnum,arcnum;〃圖的當前頂點數(shù)和弧數(shù)

}MGraph;

3.2創(chuàng)建導航圖函數(shù)：

intCreatellDN(MGraph&G)

函數(shù)描述：主要將每一個節(jié)點進行命名、每一個頂點到其他所有定點的路徑值用鄰

接矩陣進行存儲。

例：

G.vexs[0]="校門"；G.vexs⑵=”校辦公室〃;

作用：使0簸點夠為"校門"；

G.arcs[0][2]=G.arcs[2][0]=900;

作用：使0號節(jié)點到2號節(jié)點的路徑賦值為900,因為是無向圖，所以2號節(jié)點到0

號節(jié)點的路徑長度也應賦值為900；

3.3最短路徑導航函數(shù)：

voidShortPath(MGraph&G,intvO,intp[MAX_V][MAX_V],intd[])

5

函數(shù)描述：用Dijkstra算法求無向網(wǎng)G的V0定點到其余定點V的最短路徑P[v]及

其帶權(quán)長度D[v].

若P[v][w]為True,則w是從VO至W當前求得最短路徑上的頂點。

Final[v]為True當且僅當VeS,即已經(jīng)求得從V0至[|V的最短路徑。

3.4導航菜單函財明

voidmenu()

函數(shù)描述：輸出各個節(jié)點的編號，放便導航。

4調(diào)試分析(浮現(xiàn)哪些問題，如何解決)

問題：

在程序的一開始是準備，將系統(tǒng)共分為:數(shù)據(jù)結(jié)構(gòu)定義模塊、導航圖建立模塊、求最短

路徑模塊、主菜單這四個模塊的來構(gòu)成為了校園導航系統(tǒng)的基本組成部份，但調(diào)試的過程數(shù)

據(jù)結(jié)構(gòu)定義這一模塊總是浮現(xiàn)調(diào)試錯誤，程序的調(diào)試一度進入難題。

改進方法：

由于數(shù)據(jù)結(jié)構(gòu)定義模塊總出錯，便再也不把數(shù)據(jù)結(jié)構(gòu)定義設為單獨的模塊，而是在每一

個其他模塊中都進行一次編寫，這樣就避免了數(shù)據(jù)結(jié)構(gòu)定義模塊的調(diào)用錯誤，雖然這樣使

得程序變得冗余，但好在能調(diào)試成功,能使校園導航系統(tǒng)按照預先的設想正常運行。

5.測試結(jié)果

系統(tǒng)登陸界面：

6

?1??，?

*?、?

商■上希西珊我g.R杯錢管假

15支a帔國導蕭第統(tǒng)為行用知

於

4☆會

I■

二

忖六公會代會會總會我會力

)t>C*S|jL￡X9itafto

段

“

由8）工穆V曝麗i13，檢抬浙

4>髭我,4>1，￡的都（止胃粗.@律>“>2號狀R副及2c

仲

7>三<t>15*tFTO<t}i匕曼Q<，>145T嗤他再》*

l?常*2*59嗎"遞工，4

L9u“卅0_4_>1W1精和地霸力3“圖a比臺

得mIL

T。

工《17”號豺用啊歐寶》<i*>#wtt

i9二

M儲at身白格.玉鐮二號學生公事*

里Cl”

K一☆

?一

區(qū)anmLX（M?，.，5白工主工,

7廣

M☆

鈕6?杷工<m用役場

n——☆

造5噸有出《A?警二學主自學

J1x$

\Ql>—妨帚屬■>-?>tI1.--

Y☆〈XX，目學豐二富☆

a*合占々會aa$

?*,-丁.*

m<3m>?巨~學且7他語H育占0?斛）預P墨人

導航功能1——景點信息介紹

■E:\MicrosoftVisualStudo\school\D<bug\Crcat.<xc*

<n量電停息醛

4<2>兩［罐蠢蠢的最短距寓

a<3>某:

“RRRPP-RRRRPP2RRRPPP

學校大門

番?。和跣奘钟柧氈行?/p>

造板感頒：激悟語

1r亭子科-'（二才》?乙^^千」兀

15M教學拓審理,褚拿宰〉：警哇學院和檔室管理交

揭娥他朋群院

實效隹；蝦驗的載孚樓

13喜愈笑發(fā)建工,：建工學院

:噓嘉疇髏：解舞雌鬻輾

圖書曾：知識的海與

；■:曦君杭學院

父霸露疆.所

昌母津.I豫雅調(diào)夏天有火爐之稱

國節(jié)翻情鄭霎慕

女生宿舍甫米解卷

6

:品以及零食的場所

0E

&不解釋

IFT..-?r，，r-/上口

第二學R生食堂：食堂飯不好吃啊

做事：洗地方海的

雅慳；超球轉(zhuǎn)蹩寓一在西科之重

池s游冰半樹葉啊什么都有

,，，5/6學生翳公寓嚏撬％瀛整

e號學生公寓：學生有舍

7

A導航功能2——兩點最短是瞞導航測試結(jié)果如下

A導航功能3——某點到其他所有點的是巨離

速附步入齡H2玲蹴，is顰稀片』

7杓分^格一堆）7傷】

|?必顯E_—______.

外）一）163行字幡（計翼機.通宮〉一”謂依I電控.5tf??-》工程蝴勢中心

塌靠”;丈胎塔“W我學梅丫十

N2力工修

用唱號5”…

界小華“WgF“日壯學耀【人W）—若字恃（甘耳寸.通喧〉一內(nèi)抻

?嗚郴:大懷）”.目依學梅（UB1L通三）

岸館二川E

“薪餌七合亭”.必學中*f）

-渦施堆計,■蛇）》g和t惶(4LXt“I?n衣c<T)一>"T?事楂叱算一”sH/r?百姓?的案篁

持在用e

->ffi^->u^f^，.地計.M雌）《化工.W)<?X>->i4^f?r>F

內(nèi)，;十工遙"”一'.一

_）ffl4RK—

墻配田xg

我里修（堆環(huán).雌〉-T12-費率榜《化工?>1內(nèi)*學桂0工）

市沖空a號怙抽，地訐.朝娃）,2?獨學悌（化工.U>4>

曲樂也3

卡;：廳一”，*依￥⑷,；雉訐.，■隹）

即廿導M

學生黃堂>7T,七?學￡￡齊>田土*川耳蒙中E什，?桿*至?”?旦贊用多

8

6.總結(jié)

經(jīng)過一個學期對數(shù)據(jù)結(jié)構(gòu)課程的學習，我能夠掌握數(shù)據(jù)結(jié)構(gòu)所教會我的對待問題的方

法，以及遇到問題時如何抽象出一個合理的數(shù)據(jù)結(jié)構(gòu)類型。數(shù)據(jù)結(jié)構(gòu)教會我的非但是每一個

算法，更多的是如何解決問題的方法。例如，在本次課程設計中我做的是校園導航系統(tǒng)，對

于校園導航問題的關鍵是最短路徑的問題，在教材中有算法一迪杰斯特拉求最短路徑問

題，在花了幾天時間后，終于能夠?qū)⑺惴ǖ恼麄€流程弄清晰，在對各個定點的存儲上采用鄰

接矩陣的方法，在尋覓各個點到其他所有點的關系的時候更為方便直觀。在課程設計中遇到

的一系列問題都能夠在老師和同學的指導下及時解決。

最后，感謝一年來為我們付出努力的老師們，感謝給過我指導意見的同學們，在這一年

對數(shù)據(jù)結(jié)構(gòu)的學習中，真的收獲頗多，為我以后繼續(xù)學習計算機的基礎課程打下了堅實的基

礎。

7.附錄

7.1源代碼

Creat.cpp

#include<stdio.h>

ttdefineMAX_V36

^defineINFINITY32767

typedefstruct{

char*vexs[MAX_V];

intarcs[MAX_V][MAX_V];

intvexnum,arcnum;

}MGraph;

9

intCreateUDN(MGraph&G)

inti=0,j=0;

G.vexnum=36;

G.arcnum=49;

G.vexs[0]=〃校門〃；G.vexs[l]=〃工程訓練中心〃;

G.vexs[2]=〃校辦公樓〃；G.vexs[3]=〃17號教學樓（電控，繼教）〃；

G.vexs[4]=〃16號教學樓（計算機，通信）〃；G.vexs[5]=〃2號教學樓（人外）〃；

G.vexs[6]=〃1號教學樓（藝術(shù)）〃；G.vexs[7]="15號教學樓（管理，檔案室）〃;

G.vexs[8]="14號教學樓（能源）"；G.vexs[9]="3號教學樓”；

G.vexstlO]="實驗樓"；G.vexs[ll]=〃13號教學樓（建工）”；

G.vexs[12]="12號教學樓（化工,材料）〃；

G.vexs[13]="11號教學樓（地環(huán)，測繪）“；G.vexs[14]="圖書館"；

G.vexs[15]=〃10號教學樓（機械）〃；G.vexs[16]="9號教學樓（階梯教室）

G.vexs[17]="體育館"；G.vexs[18]="第二俱樂部”；

G.vexs[19]=〃綜合樓,校醫(yī)院"；G.vexs[20]="—，二號學生公寓"；

G-vexs[21]=〃第一學生食堂"；G.vexs[22]="教師公寓"；

G.vexs[23]="三，四，五號學生公寓”；G.vexs[24]="水房

G.vexs[25]="超市";G.vexs[26]="田徑場；

G.vexs[27]="六，七號學生公寓"；G.vexs[28]="體育場";

G.vexs[29]="第二學生食堂”；G.vexs[30]=〃浴室”；

G.vexs[31]="后勤用房”；G.vexs[32]="十，十一，十二，十三號學生公寓”;

10

G.vexs[33]="游泳池G.vexs[34]="十四，十五，十六號學生公寓

G.vexs[35]="八,九號學生公寓”;

for(i=0;KG.vexnum;i++)〃初始化路徑長度

for(j=0;j<G.vexnum;j++)

(

if(i==j)

G.arcs[i][j]=0;

else

G.arcs[i][j]=INFINITY;

G.arcs[0][2]=G.arcs[2][0]=900;

G.arcs[1][2]=G.arcs[2][1]=340;

G.arcs[l][3]=G.arcs[3][1]=80;

G.arcs[2][5]=G.arcs[5][2]=240;

G.arcs[2][6]=G.arcs[6][2]=300;

G.arcs[3][4]=G.arcs[4][3]=80;

G.arcs[4][5]=G.arcs[5][4]=340;

G.arcs[4][7]=G.arcs[7][4]=80;

G.arcs[5][6]=G.arcs[6][5]=180;

G.arcs[5][9]=G.arcs[9][5]=180;

G.arcs[6][9]=G.arcs[9][6]=250;

G.arcs[6][10]=G.arcs[10][6]=50;

G.arcs[7][8]=G.arcs[8][7]=80;

G.arcs[8][11]=G.arcs[11][8]=110;

G.arcs[9][10]=G.arcs[10][9]=180;

G.arcs[9][14]=G.arcs[14][9]=220;

G.arcs[10][14]=G.arcs[14][10]=240;

11

G.arcs[ll][12]=G.arcs[12][11]=80;

G.arcs[12][13]=G.arcs[13][12]=80;

G.arcs[13][14]G.arcs[14][13]=350;

G.arcs[13][15]G.arcs[15][13]=80;

G.arcs[14][19]G.arcs[19][14]=70;

G.arcs[14][18]=G.arcs[18][14]=90;

G.arcs[14][20]=G.arcs[20][14]=50;

G.arcs[14][22]=G.arcs[22][14]=45;

G.arcs[15][16]=G.arcs[16][15]=80;

G.arcs[16][18]=G.arcs[18][16]=300;

G.arcs[17][18]=G.arcs[18][17]=20;

G.arcs[18][19]=G.arcs[19][18]=10;

G.arcs[19][20]=G.arcs[20][19]=15;

G.arcs[20][21]=G.arcs[21][20]=10;

G.arcs[21][23]=G.arcs[23][21]=20;

G.arcs[21][22]=G.arcs[22][21]=43;

G.arcs[21][25]=G.arcs[25][21]=26;

G.arcs[23][25]=G.arcs[25][23]=30;

G.arcs[25][30]=G.arcs[30][25]=18;

G.arcs[30][31]=G.arcs[31][30]=20;

G.arcs[26][16]=G.arcs[16][26]=10;

G.arcs[26][27]=G.arcs[27][26]=50;

G.arcs[27][29]=G.arcs[29][27]=30;

G.arcs[27][28]=G.arcs[28][27]=40;

G.arcs[29][30]=G.arcs[30][29]=15;

G.arcs[29][32]=G.arcs[32][29]=70;

G.arcs[28][32]=G.arcs[32][28]=100;

G.arcs[28][35]=G.arcs[35][28]=100;

G.arcs[28][34]=G.arcs[34][28]=160;

12

G.arcs[33][34]=G.arcs[34][33]=35;

G.arcs[34][35]=G.arcs[35][34]=60;

G.arcs[34][26]=G.arcs[26][34]=100;

return1;

Short_path.cpp

#include<stdio.h>

#defineMAX_V36

SdefineINFINITY32767

typedefstruct

(

char*vexs[MAX_V];

intarcs[MAX_V][MAX_V];

intvexnum,arcnum;

}MGraph;

externhave[36];

voidShortPath(MGraph&G,intvO,intp[MAX_V][MAX_V],intd[])

(

intv,w,i,j,min;

intfinal[MAX_V];

intk=l;

for(v=0;v<G.vexnum;++v)

{〃初始化

final[v]=0;

d[v]=G.arcs[vO-1][v];

for(w=0;w<G.vexnum;++w)

p[v][w]=0;

if(d[v]<INFINITY)

13

p[v][vO-l]=l;

p[v][v]=l;

)

}

d[vO-l]=O;

final[vO-l]=l;

have[O]=vO-l;

for(i=l;i<G.vexnum;++i)

{〃其余的vexnum-1個頂點

min=INFINITY;

for(w=0;w<G.vexnum;++w)

if(!finalW)

if(d[w]<min)

{

v=w;

min=d[w];

)

final[v]=l;

have[k]=v;

k++;

for(w=0;w<G.vexnum;++w)

if(!final[w]&&(min+G.arcs[v][w]<d[w]))

{

d[w]=min+G.arcs[v][w];

for(j=0;j<G.vexnum;j++)

p[w][j]=p[v][j];

p[w][w]=l;

14

Menu,cpp

#include<stdio.h>

voidmenu()

printf('?☆☆☆☆☆☆☆☆☆☆☆☆☆導航主菜單☆☆☆☆☆

☆☆☆☆☆☆☆\n,，);

printf(〃☆⑴校門⑵工程訓練中心⑶校辦

公樓☆\n");

printf(〃☆(4)17號教學樓(電控，繼教)(5)16號教學樓(計算機，通信)(6)2號

教學樓(人外)☆\n");

printf(〃☆(7)1號教學樓(藝術(shù))(8)15號教學樓(管理，檔案室)(9)14

號教學樓(能源)☆\n");

printf(〃☆(10)3號教學樓(11)實驗樓(12)13

號教學樓(建工)☆\n");

printf(〃☆(13)12號教學樓(化工，材料)(14)11號教學樓(地環(huán)，測繪)(15)圖

書館☆\n");

printf(〃☆(16)10號教學樓(機械)(17)9號教學樓(階梯教室)(⑻體

育館☆\n");

printf(〃☆(19)第二俱樂部(20)綜合樓，校醫(yī)院(21)1,2

號學生公寓☆\n");

printf(〃☆(22)第一學生食堂(23)教師公寓

(24)3,4,5號學生公寓☆\n〃)；

15

printf(〃☆(25)水房(26)超市(27)田徑

場☆\n");

printf(〃☆(28)6,7號學生公寓(29)體育場(30)第

二學生食堂☆\n");

printf("☆(31)浴室(32)后勤用房

(33)10,11,12,13號學生公寓☆\n/，);

printf(〃☆(34)游泳池(35)14,15,16學生公寓(36)8,9

號學生公寓☆'<);

printf(z，☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆

☆☆☆☆☆☆☆\n\n〃)；

printf(〃請選擇導航W能：\n〃)；

1h+\yx\

\?>*/>//*</?/>zz??//*/?/>zz?z??/>zz?z?/>/\1]),

printfCu(1)景點信息簡紹u\n〃);

printf(，?~(2)兩點最短距離導航儀\n");

printfC。(3)某點到其他所有點的最短距離a\n");

1-1+*f*(\n、

MxX11LX\************z*</*>?/z*</*>?/zxzz*<//??/zxzr>j\JJ),

}

Main,cpp

#include<stdio.h>

^include<stdlib.h>

Sinclude<string.h>

ttdefineMAX_V36

SdefineINFINITY32767

16

typedefstruct

char*vexs[MAX_V];

intarcs[MAX_V][MAX_V];

intvexnum,arcnum;

}MGraph;

inthave[36];

intGreateUDN(MGraph&G);

voidShortPath(MGraph&G,intvO,intp[MAX_V][MAX_V],intd口)；

voidmenu();

voidmain()

(

system(，zmodecon:cols=140lines=130z，);

MGraphG;

intvO,i,end,j;

intP[MAX_V][MAX_V];

intD[MAX_V];

intchoice,choicel;

v*T\c、

I/X￡￡1LJ.\***/>/~/wz*//>//w/>/z*/~/wz*//>/\Jj),

printf("\n歡迎光臨西安科技大學，祝旅程愉快！??\n");

printf(〃\n西安科技大學校園導游系統(tǒng)為你服務！\n〃)；

\nzxzf-jr-^jz??zr^jr^jr-^r-jr>jrsyr>j\n\n〃、?

J.UI/JL\\U***o**,>/r>j/>/zs?/>zzszz*zo/rszrxzrxz^szzszr>jr>j/>/zs?/>/zsz/>/o//?\\,

CreateUDN(G);

while(1)

(

menu();

scanf(〃%d〃,&choice);

switch(choice)

17

case1:

printf（〃校門:學校大門\n〃）；

printf（“工程訓練中心：工程實驗訓練中心\n"）;

printf（"校辦公樓：行政辦公樓\n"）;

printf（〃17號教學樓（電控，繼教）：電氣控制與自動化學院和繼續(xù)教

育學院合樓\n〃）；

printf。16號教學樓（計算機，通信）：計算機科學與技術(shù)學院和

通信學院合樓\n"）;

printf（"2號教學樓（人外）：人文外國語\n"）;

printfCl號教學樓（藝術(shù)）:藝術(shù)學院\n〃）；

printf（〃15號教學樓（管理，檔案室）：管理學院和檔案管理室

\n〃）;

printf（“14號教學樓（能源）：能源學院\n〃）；

printf（"3號教學樓：教學樓不解釋\n"）;

printf（"實驗樓：做實驗的教學樓\n"）;

printf（“13號教學樓（建工）：建工學院\n"）;

printf（〃12號教學樓（化工，材料）：化工學院與材料學院的合

樓\n〃）；

printfC11號教學樓（地環(huán)，測繪）：地環(huán)學院與測繪學院的合

樓\n〃）；

printf（"圖書館：知識的海洋\n"）;

18

printf（“10號教學樓（機械）：機械學院\n"）;

printfC9號教學樓:階梯教室\n〃）；

printf（"體育館：體育鍛煉的場所\n"）;

printf（〃第二俱樂部：簡稱二俱\n〃）；

printf（〃綜合樓，校醫(yī)院：生病就醫(yī)的場所\n"）;

printf（〃1,2號學生公寓:學生宿舍沒有空調(diào)夏天有火爐之

稱\n〃）；

printf（〃第一學生食堂：小食堂飯不好吃\n〃）；

printf（〃教師公寓：老師宿舍有空調(diào)慢慢的羨慕\n"）;

printf（〃3,4,5號學生公寓：女生宿舍樓不解釋\n〃）；

printf（"水房：打水的地方\n"）;

printfC超市：買生活用品以及零食的場所\n〃）；

printf（〃田徑場：體育鍛煉\n"）;

printf（"6,7號學生公寓：男生宿舍樓不解釋\n"）;

printf（〃體育場：籃球場網(wǎng)球場集中地\n"）;

printf（〃第二學生食堂：食堂飯不好吃啊\n〃）；