校园导航系统-数据结构

校园导航系统-数据结

构

-CAL-FENGHAI.-(YICAI)-CompanyOne1

《数据结构预与算法分析》

^^呈设计报告

题目：校园导航系统

班级：网络工程

XXX

学号：XXXXXXX

指导教师：XXX

日期：2022/7/11

目录

1.任务说明（要求、知识点、实现的功能）............................................1

1.1题目：........................................................................1

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

1.3知识点....................................................................1

2.概要设计（结构体类型及函数声明，功能模块图，流程图）.........................2

2.1结构体类型及函数声明........................................................2

22功能Wi图...................................................................3

2.3流程图......................................................................3

3.1节点数据结构类型：..........................................................5

3.2创建导航图函数：............................................................5

3.3最短路径导航函数：..........................................................5

3.4导航菜单函数声明............................................................6

4调试分析（浮现哪些问题，如何解决）................................................6

5.测试结果.........................................................................6

6.总结............................................................................9

7.附录.............................................................................9

7.1源代码......................................................................9

72参考文献....................................................................22

2

1.任务说明(要求、知识点、实现的功能)

1.1题目：

校园导航系统

1.2要求：

用无向网表示你所在学校的校园景点品面图，图中顶点表示主要景点，存放景点的编号,

名称，简绍等信息，图中的边表示景点间的道路，存放路径长度等信息。

系统功能：

(1)景点信息简绍

(2)任意两景点间最短距离

(3)任意一点到所有点最短距离

1.3知识点：

图的创建，图的搜素，领接矩阵，迪杰斯特拉算法，结构体，函数的声明与调用等知识

1

2.概要设计（结构体类型及函数声明，功能模块

图，流程图）

2.1结构体类型及函数声明

在近一个星期的努力下，我编写的校园导航系统软件终于能够成功完成。采用工程思

想，将系统共分一下几个模块:导航图建立模块、求最短路径模块、主菜单；

下面是具体各功能简单的实际应用：

»导航图建立模块：采用上述结构体类型对导航图中每一个节点进行赋值。包括：

各定点的名称（地点名），各个节点到其他所有节点的真实路径长度（赋权

值）。

»求厨豆路径模块：本模块的基本思想是采用迪杰斯特拉算法求最短路径。次模

块是本校园导航系统的核心模块，求两点间的最短路径与求一点到其他所有点

最短路径两个子功能均是在最短路径算法模块的基础上进行调用，进而实现导

航功能。

»主菜单：主菜单中主要是显示导航图中的所有导航节点，能够快速方便的对各

个地点进行导航。

以上程序的几个模块，构成为了校园导航系统的基本组成部份，程序运行良好,达到了

课程设计的基本要求。由于所学知识有限，功能各个方面还有欠妥之处，希冀得到指出与

改正。

函数声明：

intCreateUDN（MGraph&G）创建导航图函数

2

voidShortPath(MGraph&G,intvO,intp[MAX_V][MAX_V],intd[])最短路径导航函数

voidmenu()导航菜单声明

2.2功能模块图

总功能模块图

2.3流程图

迪杰其耐立算法流程图

3

开始

d[vO-1)=0

final[v0-1]=1

toe[Q}=Y0U.

4

3.详细设计(数据类型实现、编码)

3.1节点数据结构类型：

^defineMAX_V40〃最大顶点个数

typedefstruct

(

char*vexs[MAX_V];〃顶点向量

intarcs[MAX_V][MAX_V];〃邻接矩阵

intvexnum,arcnum;〃图的当前顶点数和弧数

}MGraph;

3.2创建导航图函数：

intCreatellDN(MGraph&G)

函数描述：主要将每一个节点进行命名、每一个顶点到其他所有定点的路径值用邻

接矩阵进行存储。

例：

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

作用：使0簸点够为"校门"；

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

作用：使0号节点到2号节点的路径赋值为900,因为是无向图，所以2号节点到0

号节点的路径长度也应赋值为900；

3.3最短路径导航函数：

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

5

函数描述：用Dijkstra算法求无向网G的V0定点到其余定点V的最短路径P[v]及

其带权长度D[v].

若P[v][w]为True,则w是从VO至W当前求得最短路径上的顶点。

Final[v]为True当且仅当VeS,即已经求得从V0至[|V的最短路径。

3.4导航菜单函财明

voidmenu()

函数描述：输出各个节点的编号，放便导航。

4调试分析(浮现哪些问题，如何解决)

问题：

在程序的一开始是准备，将系统共分为:数据结构定义模块、导航图建立模块、求最短

路径模块、主菜单这四个模块的来构成为了校园导航系统的基本组成部份，但调试的过程数

据结构定义这一模块总是浮现调试错误，程序的调试一度进入难题。

改进方法：

由于数据结构定义模块总出错，便再也不把数据结构定义设为单独的模块，而是在每一

个其他模块中都进行一次编写，这样就避免了数据结构定义模块的调用错误，虽然这样使

得程序变得冗余，但好在能调试成功,能使校园导航系统按照预先的设想正常运行。

5.测试结果

系统登陆界面：

6

•1•»，・

*・、•

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

15支a帔国导萧第统为行用知

於

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一☆

•一

区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

学校大门

番啤：王修手训练中心

造板感颁：激悟语

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

15M教学拓审理,褚拿宰〉：警哇学院和档室管理交

揭娥他朋群院

实效隹；虾验的载孚楼

13喜愈笑发建工,：建工学院

:嘘嘉畴髅：解舞雌鬻辗

图书曾：知识的海与

；■:曦君杭学院

父霸露疆.所

昌母津.I豫雅调夏天有火炉之称

国节翻情郑霎慕

女生宿舍甫米解卷

6

:品以及零食的场所

0E

&不解释

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

第二学R生食堂：食堂饭不好吃啊

做事：洗地方海的

雅悭；超球转蹩寓一在西科之重

池s游冰半树叶啊什么都有

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

e号学生公寓：学生有舍

7

A导航功能2——两点最短是瞒导航测试结果如下

A导航功能3——某点到其他所有点的是巨离

速附步入龄H2玲蹴，is颦稀片』

7杓分^格一堆）7伤】

|»必显E_—______.

外）一）163行字幡（计翼机.通宫〉一”谓依I电控.5tf?»-》工程蝴势中心

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

N2力工修

用唱号5”…

界小华“WgF“日壮学耀【人W）—若字恃（甘耳寸.通喧〉一内抻

»呜郴:大怀）”.目依学梅（UB1L通三）

岸馆二川E

“薪饵七合亭”.必学中*f）

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

持在用e

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

内，;十工遥"”一'.一

_）ffl4RK—

墙配田xg

我里修（堆环.雌〉-T12-费率榜《化工・>1内*学桂0工）

市冲空a号怙抽，地讦.朝娃）,2♦独学悌（化工.U>4>

曲乐也3

卡;：厅一”，*依¥⑷,；雉讦.，■隹）

即廿导M

学生黄堂>7T,七♦学££齐>田土*川耳蒙中E什，•杆*至।”•旦赞用多

8

6.总结

经过一个学期对数据结构课程的学习，我能够掌握数据结构所教会我的对待问题的方

法，以及遇到问题时如何抽象出一个合理的数据结构类型。数据结构教会我的非但是每一个

算法，更多的是如何解决问题的方法。例如，在本次课程设计中我做的是校园导航系统，对

于校园导航问题的关键是最短路径的问题，在教材中有算法一迪杰斯特拉求最短路径问

题，在花了几天时间后，终于能够将算法的整个流程弄清晰，在对各个定点的存储上采用邻

接矩阵的方法，在寻觅各个点到其他所有点的关系的时候更为方便直观。在课程设计中遇到

的一系列问题都能够在老师和同学的指导下及时解决。

最后，感谢一年来为我们付出努力的老师们，感谢给过我指导意见的同学们，在这一年

对数据结构的学习中，真的收获颇多，为我以后继续学习计算机的基础课程打下了坚实的基

础。

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号教学楼（艺术）〃；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号教学楼（地环，测绘）“；G.vexs[14]="图书馆"；

G.vexs[15]=〃10号教学楼（机械）〃；G.vexs[16]="9号教学楼（阶梯教室）

G.vexs[17]="体育馆"；G.vexs[18]="第二俱乐部”；

G.vexs[19]=〃综合楼,校医院"；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号教学楼(艺术)(8)15号教学楼(管理，档案室)(9)14

号教学楼(能源)☆\n");

printf(〃☆(10)3号教学楼(11)实验楼(12)13

号教学楼(建工)☆\n");

printf(〃☆(13)12号教学楼(化工，材料)(14)11号教学楼(地环，测绘)(15)图

书馆☆\n");

printf(〃☆(16)10号教学楼(机械)(17)9号教学楼(阶梯教室)(⑻体

育馆☆\n");

printf(〃☆(19)第二俱乐部(20)综合楼，校医院(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西安科技大学校园导游系统为你服务！\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号教学楼（电控，继教）：电气控制与自动化学院和继续教

育学院合楼\n〃）；

printf。16号教学楼（计算机，通信）：计算机科学与技术学院和

通信学院合楼\n"）;

printf（"2号教学楼（人外）：人文外国语\n"）;

printfCl号教学楼（艺术）:艺术学院\n〃）；

printf（〃15号教学楼（管理，档案室）：管理学院和档案管理室

\n〃）;

printf（“14号教学楼（能源）：能源学院\n〃）；

printf（"3号教学楼：教学楼不解释\n"）;

printf（"实验楼：做实验的教学楼\n"）;

printf（“13号教学楼（建工）：建工学院\n"）;

printf（〃12号教学楼（化工，材料）：化工学院与材料学院的合

楼\n〃）；

printfC11号教学楼（地环，测绘）：地环学院与测绘学院的合

楼\n〃）；

printf（"图书馆：知识的海洋\n"）;

18

printf（“10号教学楼（机械）：机械学院\n"）;

printfC9号教学楼:阶梯教室\n〃）；

printf（"体育馆：体育锻炼的场所\n"）;

printf（〃第二俱乐部：简称二俱\n〃）；

printf（〃综合楼，校医院：生病就医的场所\n"）;

printf（〃1,2号学生公寓:学生宿舍没有空调夏天有火炉之

称\n〃）；

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

printf（〃教师公寓：老师宿舍有空调慢慢的羡慕\n"）;

printf（〃3,4,5号学生公寓：女生宿舍楼不解释\n〃）；

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

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

printf（〃田径场：体育锻炼\n"）;

printf（"6,7号学生公寓：男生宿舍楼不解释\n"）;

printf（〃体育场：篮球场网球场集中地\n"）;

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