校园导航系统课程设计

校园导航

课

程设

计报

专 业：计算机科学与技术 课程设计名称：《数据结构课程设计》 题 目：校园导航问题 班 级： 学 号： 姓 名： 同 组 人 员: 指 导 老 师：

完 成 时 间：2012年2月17日

告书

摘要

校园导航问题是基于校园中的不同的景点，从陌生人的角度，为来往的客人提供校园景点相关信息的查询以及为来往的客人提供校园中任意景点的问路查询，以便客人能用最短的时间从某一地点到达想要去的地方。大大节约了旅客参观校园的时间。

本文是采用C++作为开发语言，又最大程度上用了C语言的有关的语法。以visual c++6.0为开发工具。旨在实现校园导航系统中，学校的简介，景点的介绍，路线查询等基本的问题。为来往客人参观校园提供方便。

关键词：C++；C；visual c++6.0；校园导航

目录

目录 ................................................................. 1 第一章 开发环境和开发工具 ............................................. 1

1.1 C/ C ++语言简介 ................................................ 1

1.2 开发背景 ........................................................ 1 1.3 开发环境 ........................................................ 1 第二章 算法思想 ....................................................... 2

2.1 系统需求分析 .................................................... 2 2.2 系统总体设计 .................................................... 3

2.2.1 系统设计目标 .............................................. 3 2.2.2 开发设计思想 .............................................. 3 2.2.3 系统功能模块设计 .......................................... 3 2.3 算法思想描述 .................................................... 4 第三章 算法实现 ....................................................... 6

3.1 数据结构 ........................................................ 6 3.2 程序模块 ........................................................ 6 3.3 各模块之间的调用关系上 ......................................... 12 3.4 源程序代码 ..................................................... 12 第四章 测试与分析 .................................................... 22

4.1 测试数据选择 ................................................... 22 4.2 测试结果分析 ................................................... 26 总 结 .............................................................. 27 心得体会 .............................................................. 28 参考文献 .......................................................... 29

第一章 开发环境和开发工具

1.1 C/ C ++语言简介

C语言是一种计算机程序设计语言。它既具有高级语言的特点，又具有汇编语言的特点。它由美国贝尔研究所的D.M.Ritchie于1972年推出。1978后，C语言已先后被移植到大、中、小及微型机上。它可以作为工作系统设计语言，编写系统应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。它的应用范围广泛，具备很强的数据处理能力，不仅仅是在软件开发上，而且各类科研都需要用到C语言，适于编写系统软件，三维，二维图形和动画。具体应用比如单片机以及嵌入式系统开发。

C++是一种静态数据类型检查的、支持多重编程范式的通用程序设计语言。它支持过程化程序设计、数据抽象、面向对象程序设计、制作图标等等泛型程序设计等多种程序设计风格。

1.2 开发背景

随着科学技术的不断发展，计算机科学日渐成熟，其强大的功能已为人们所深

刻认识，它己进入人类社会的各个领域并发挥着越来越重要的作用。采用计算机进行校园导航已成为衡量校园数字化的重要标志。校园导航效率的好坏对于来校参观的客人和学校管理者来说都至关重要，在很大程度上影响着校园的数字化建设和学校的影响力。因此，本文所研究的校园导航系统具有一定的使用价值和现实意义。

1.3 开发环境

本文所采用的开发环境主要是基于c++的visual stadio c++。它是一个系统的集成开发环境。很适合C\\C++程序的开发。我们日常的学习和生活中大多就用这个开发环境进行学习和编程。

1

第二章 算法思想

2.1 系统需求分析

1、设计你的学校的校园平面图，所选的景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。

2、为来往客人提供图中任意景点相关信息的查询。

3、为来往的客人提供图中任意景点的问路查询，即查询任意两个景点间的一条最短的简单路径。

根据以上分析和抽象可得到本系统的抽象数据类型如下： ADT graph{

数据对象 R：V是校园中景点的集合，称为顶点集。 R={VR}

VR={|v,w∈V且P（v,w）,（v,w）表示从景点v到景点w的路径长度

基本操作 P： Creatgraph(&G,V,VR)

初始条件：V是图的顶点集,VR是图中边的集合。 操作结果：按V和VR的定义构造图G。 Output（G）

初始条件：图G已经存在。 操作结果：打印出图的信息 ShortestPath（G，v）

初始条件：图G已存在，v是图中的一个顶点。

操作结果：返回从v出发到图中任意顶点的最短的路径。 }ADT graph；

2

2.2 系统总体设计

2.2.1 系统设计目标

本文研究开发的校园导航系统用于支持来往校园参观的客人提供最省时的导航

服务，有如下三个方面的目标:

1、为来往的客人提供校园的简介。

2、为来往的客人提供校园中各景点的简介，以及各景点的距离等情况。 3、为来往的客人提供到达目的地的最短的路线。 2.2.2 开发设计思想

基于以上系统设计目标，本文在开发校园导航系统时遵循了以下开发设计思

想:

1、采用现有的软硬件环境及先进的管理系统开发方案，从而达到充分利用现有

资源，提高系统开发水平和应用效果的目的。

2、尽量达到操作过程中的直观、方便、实用、安全等要求。

3、系统采用模块化程序设计方法，既便于系统功能的各种组合和修改，又便于未参与开发的技术维护人员补充、维护。 2.2.3 系统功能模块设计

本系统分为四个模块：菜单模块、景点介绍模块、路径查询模块、最短路径模块。

得到如图3-1所示的系统功能模块图。

3

校园导航系统 菜单 景点介绍 路径查询 最短路径 主菜单 查询子菜单 退 出 学校简介 景点简介 各景点间距离 最短路径长度 最短路线

图3-1系统功能模块图

2.3 算法思想描述

1、迪杰斯特拉算法思想：

按路径长度递增次序产生最短路径算法： 把V分成两组：

（1）S：已求出最短路径的顶点的集合

（2）V-S=T：尚未确定最短路径的顶点集合 将T中顶点按最短路径递增的次序加入到S中， 保证：（1）从源点V0到S中各顶点的最短路径长度都不大于 从V0到T中任何顶点的最短路径长度 （2）每个顶点对应一个距离值

S中顶点：从V0到此顶点的最短路径长度

T中顶点：从V0到此顶点的只包括S中顶点作中间 顶点的最短路径长度

依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的 直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和 2、邻接矩阵建立有无向权图的算法思想：

4

用两个数组分别存储数据元素的信息和数据之间的关系的信息其形式描述如下： #define Max 32767//最大值∞ #define NUM 11//最大顶点个数 typedef struct ArcCell{

int adj; // 相邻接的景点之间的路程 char *info;

}ArcCell; // 定义边的类型 typedef struct VertexType{ int number; // 景点编号 char *sight; // 景点名称

char *description; // 景点描述 }VertexType; // 定义顶点的类型 typedef struct{

VertexType vex[NUM]; // 图中的顶点，即为景点

ArcCell arcs[NUM][NUM]; // 图中的边，即为景点间的距离 int vexnum,arcnum; // 顶点数，边数 }MGraph; // 定义图的类型

其中用二维数组表示途中个边之间的关系。

5

第三章 算法实现

3.1 数据结构

1、顶点、边和图类型： typedef struct ArcCell{

int adj; // 相邻接的景点之间的路程 char *info;

}ArcCell; // 定义边的类型 typedef struct VertexType{ int number; // 景点编号 char *sight; // 景点名称

char *description; // 景点描述 }VertexType; // 定义顶点的类型 typedef struct{

VertexType vex[NUM]; // 图中的顶点，即为景点

ArcCell arcs[NUM][NUM]; // 图中的边，即为景点间的距离 int vexnum,arcnum; // 顶点数，边数 }MGraph; // 定义图的类型

3.2 程序模块

1.main函数

void main() // 主函数 { int v0,v1; char ck;

system(\CreateUDN(NUM,11); do {

ck=Menu(); switch(ck) {

case'1': introduce(); printf(\.vex[0].description); getchar(); getchar(); break; case '2':

6

system(\ pingmu(); printf(\请选择起点景点（1～10）：\ scanf(\ printf(\请选择终点景点（1～10）：\ scanf(\ ShortestPath(v0); // 计算两个景点之间的最短路径 output(v0,v1); // 输出结果 printf(\请按回车键继续...\\n\ getchar(); getchar(); break;

case '3':search(); break; case'5': PrintMGraph(); printf(\请按回车键继续...\\n\ getchar(); getchar(); break; };

}while(ck!='e'); }

2.主菜单

char Menu() // 主菜单 // {

char c; int flag; do{ flag=1; system(\ pingmu(); printf(\┏━━━━━━━━━━━━━━━━━━━┑\\n\ printf(\┃ ┃\\n\ printf(\┃ 1.学校简介 ┃\\n\ printf(\┃ 2.查询景点路径 ┃\\n\ printf(\┃ 3.查询景点信息 ┃\\n\ printf(\┃ 5.查询各景点之间的距离 ┃\\n\ printf(\┃ e.退出 ┃\\n\ printf(\┃ ┃\\n\ printf(\┗━━━━━━━━━━━━━━━━━━━┛\\n\ printf(\请输入您的选择：\ scanf(\

7

}

if(c=='1'||c=='2'||c=='3'||c=='5'||c=='e') flag=0; }while(flag); return c;

3.查询子菜单

char SearchMenu() // 查询子菜单 {

char c; int flag; do{ flag=1; system(\ pingmu(); printf(\┏━━━━━━━━━━━━━━━━━━┑\\n\ printf(\┃ ┃\\n\ printf(\┃ 1、按照景点编号查询 ┃\\n\ printf(\┃ 2、按照景点名称查询 ┃\\n\ printf(\┃ e、返回 ┃\\n\ printf(\┃ ┃\\n\ printf(\┗━━━━━━━━━━━━━━━━━━┛\\n\ printf(\请输入您的选择：\ scanf(\ if(c=='1'||c=='2'||c=='e') flag=0; }while(flag); return c; }

4.查询景点信息

void search() // 查询景点信息 {

int num; int i; char c;

char name[20]; do { system(\ c=SearchMenu(); switch (c) {

8

case '1': system(\ //introduce(); pingmu(); printf(\请输入您要查找的景点编号：\ scanf(\ for(i=0;i

9

} if(i==NUM) { printf(\没有找到！\ printf(\按回车键返回...\ getchar(); getchar(); } break; }

}while(c!='e'); }

5.创建图的函数

void CreateUDN(int v,int a) // 创建图的函数 6. 打印出邻接矩阵 void PrintMGraph() {

int i,j; cout<<\

====================================================================\\n\\n \

for(i=1;i

cout<

for(i=1;i

cout<<\========================================\\n\\n\\n\7.迪杰斯特拉算法

void ShortestPath(int num) // 迪杰斯特拉算法最短路径函数 num为入口点的编号 {

10

int v,w,i,t; // i、w和v为计数变量 int final[NUM]; int min;

for(v=1;v

D[num]=0;

final[num]=1; // 初始化num顶点属于S集合

// 开始主循环，每一次求得num到某个顶点的最短路径，并将其加入到S集合 for(i=1;i

8、输出：

屏幕输出函数：void pingmu()； 最短路线输出函数void output；

11

3.3 各模块之间的调用关系上

模块调用关系如图3—2所示：

main output CreateUDN menu search ShortestPaPrintMGraph pingmu searchmenu

图3—2模块调用关系图

3.4 源程序代码

#include #include \#include \#include \#define Max 32767 #define NUM 11

typedef struct ArcCell{

int adj; // 相邻接的景点之间的路程 char *info;

}ArcCell; // 定义边的类型 typedef struct VertexType{ int number; // 景点编号 char *sight; // 景点名称

char *description; // 景点描述

12

}VertexType; // 定义顶点的类型 typedef struct{

VertexType vex[NUM]; // 图中的顶点，即为景点

ArcCell arcs[NUM][NUM]; // 图中的边，即为景点间的距离 int vexnum,arcnum; // 顶点数，边数 }MGraph; // 定义图的类型

MGraph G; // 把图定义为全局变量 int P[NUM][NUM]; // //

long int D[NUM]; // 辅助变量存储最短路径长度 int x[13]={0};

void CreateUDN(int v,int a); // 创建图的函数 void pingmu(); //屏幕输出函数 void introduce();

void ShortestPath(int num); //最短路径函数 void output(int sight1,int sight2); //输出函数 void PrintMGraph(); char Menu(); // 主菜单 void search(); ;// 查询景点信息

char SearchMenu(); // 查询子菜单 void NextValue(int);

void display(); // 显示遍历结果 void main() // 主函数 {

int v0,v1; char ck;

system(\ CreateUDN(NUM,11); do { ck=Menu(); switch(ck) { case'1': introduce(); printf(\ getchar(); getchar(); break; case '2': system(\ pingmu(); printf(\请选择起点景点（1～10）：\

13

scanf(\ printf(\请选择终点景点（1～10）：\ scanf(\ ShortestPath(v0); // 计算两个景点之间的最短路径 output(v0,v1); // 输出结果 printf(\请按回车键继续...\\n\ getchar(); getchar(); break; case '3':search(); break; case'5': PrintMGraph(); printf(\请按回车键继续...\\n\ getchar(); getchar(); break; };

}while(ck!='e'); }

char Menu() // 主菜单 // {

char c; int flag; do{ flag=1; system(\ pingmu(); introduce(); printf(\┏━━━━━━━━━━━━━━━━━━━┑\\n\ printf(\┃ ┃\\n\ printf(\┃ 1.学校简介 ┃\\n\ printf(\┃ 2.查询景点路径 ┃\\n\ printf(\┃ 3.查询景点信息 ┃\\n\ printf(\┃ 5.查询各景点之间的距离 ┃\\n\ printf(\┃ e.退出 ┃\\n\ printf(\┃ ┃\\n\ printf(\┗━━━━━━━━━━━━━━━━━━━┛\\n\ printf(\请输入您的选择：\ scanf(\ if(c=='1'||c=='2'||c=='3'||c=='5'||c=='e') flag=0; }while(flag);

14

return c; }

char SearchMenu() // 查询子菜单 {

char c; int flag; do{ flag=1; system(\ pingmu(); introduce(); printf(\┏━━━━━━━━━━━━━━━━━━┑\\n\ printf(\┃ ┃\\n\ printf(\┃ 1、按照景点编号查询 ┃\\n\ printf(\┃ 2、按照景点名称查询 ┃\\n\ printf(\┃ e、返回 ┃\\n\ printf(\┃ ┃\\n\ printf(\┗━━━━━━━━━━━━━━━━━━┛\\n\ printf(\请输入您的选择：\ scanf(\ if(c=='1'||c=='2'||c=='e') flag=0; }while(flag); return c; }

void search() // 查询景点信息 {

int num; int i; char c;

char name[20]; do { system(\ c=SearchMenu(); switch (c) { case '1': system(\ introduce(); pingmu(); printf(\请输入您要查找的景点编号：\ scanf(\

15

for(i=0;i

16

getchar(); getchar(); } break; }

}while(c!='e'); }

void CreateUDN(int v,int a) // 创建图的函数 {

int i,j;

G.vexnum=v; // 初始化结构中的景点数和边数 G.arcnum=a;

for(i=1;i

// 这里把所有的边假定为32767，含义是这两个景点之间是不可到达 for(i=1;i

//下边是可直接到达的景点间的距离，由于两个景点间距离是互相的， // 所以要对图中对称的边同时赋值。

G.arcs[1][4].adj=G.arcs[4][1].adj=200; G.arcs[1][3].adj=G.arcs[3][1].adj=500; G.arcs[3][5].adj=G.arcs[5][3].adj=100; G.arcs[3][10].adj=G.arcs[10][3].adj=400; G.arcs[4][6].adj=G.arcs[6][4].adj=200; G.arcs[2][5].adj=G.arcs[5][2].adj=200; G.arcs[2][4].adj=G.arcs[4][2].adj=300;

17

G.arcs[5][7].adj=G.arcs[7][5].adj=500; G.arcs[4][6].adj=G.arcs[6][4].adj=400; G.arcs[4][7].adj=G.arcs[7][4].adj=600; G.arcs[6][8].adj=G.arcs[8][6].adj=500; G.arcs[7][8].adj=G.arcs[8][7].adj=300; G.arcs[6][9].adj=G.arcs[9][6].adj=500; }

// 打印出邻接矩阵 void PrintMGraph() {

int i,j; cout<<\

====================================================================\\n\\n \

for(i=1;i

cout<

for(i=1;i

cout<<\===================================\\n\\n\\n\}

void introduce() // 介绍函数 {

int i;

for(i=1;i<=NUM;i++) { G.vex[0].description=\河南城建学院坐落在国家旅游城市\\n\\n\\t\\t国家历史文化名城--平顶山，校园椰风流韵、芳林叠翠、风景秀丽。\\n\\n\\t\\t经过二十多年的发展,学校现已形成以城建为主要办学特色\\n\\n\\t\\t文、管、理、经等多学科协调发展的格局,是河南省培养城建类\\n\\n\\t\\t高级应用型人才的重要基地.目前，学校确立了立足河南\\n\\n\\t\\t逐渐面向全国服务面向定位，充分发挥学校

18

}

void pingmu() // 屏幕输出函数 {

int i;

printf(\欢迎来到河南城建学院%c%c%c%c%c%c%c%c%c%c\\n\\n\;

printf(\c %c\\n\ printf(\学校简介\\t\\t%c\\n\

printf(\c %c\\n\ printf(\学校概况\\t\\t%c\\n\

printf(\c %c\\n\ for(i=1;i

printf(\

19

特色\\n\\n\\t\\t积极扩大对外交流与合作，学术交流日趋\\n\\n\\t\\t频繁，国际影响不断增强\\n\\n\\t\\t下面几点是河南城建学院的办学特色：\\n\\n\\t\\t办学历史较为悠久\\n\\n\\t\\t学科专业较为齐全\\n\\n\\t\\t师资队伍素质优良\\n\\n\\t\\t教学成果较为丰硕\\n\\n\\t\\t科研水平不断提高\\n\\n\\t\\t校园文化丰富活跃\\n\\n\\t\\t人才培养成效显著\\n\\n\\t\\t合作交流日趋频繁\\n\\n\\t\\t\ G.vex[1].description=\学校大门，对面是祥云公园\\n\\t\\t是我们学生休闲娱乐的好地方\ G.vex[2].description=\计教系办公大楼，计算机科学技术的科研中心\ G.vex[3].description=\这里是学校的主要的风景区，是学校的标志之一\ G.vex[4].description=\在这破地方什么鸟人都 有，拿书呐喊的，失恋的，打KISS的，暗送秋波的，\\n\\t\\t可千万别来这鸳鸯之地，你来了，一个电灯泡亮那儿\\n\\t\\t你说人家两口子咋亲热啊，还是闪为上策\ G.vex[5].description=\学生生活的天堂\ G.vex[6].description=\河南城建学院信息中心，各种书籍应有尽有\ G.vex[7].description=\排球篮球比赛，晚会，各种报告，开学典礼举行都在这破地方举行\ G.vex[8].description=\老师和同学们吃饭的地方，这里的饭比一食堂好吃，菜不错\\n\\t\\t看你肚皮有没有猪八戒大,你要是吃不饱可以考虑来这吃，准让你撑死\ G.vex[9].description=\学生可以在这里买到日常必须品。\ G.vex[10].description=\北门雄伟壮观，十分气派！\}

%c%c%c%c%c%c%c%c%c%c%c%c\\n\\n\6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,1);

}

void ShortestPath(int num) // 迪杰斯特拉算法最短路径函数 num为入口点的编号 {

int v,w,i,t; // i、w和v为计数变量 int final[NUM]; int min;

for(v=1;v

D[num]=0;

final[num]=1; // 初始化num顶点属于S集合

// 开始主循环，每一次求得num到某个顶点的最短路径，并将其加入到S集合 for(i=1;i

20

} } }

void output(int sight1,int sight2) // 输出函数 {

int a,b,c,d,q=0;

a=sight2; // 将景点二赋值给a

if(a!=sight1) // 如果景点二不和景点一输入重合，则进行... { printf(\从%s到%s的最短路径是\输出提示信息 printf(\最短距离为 %dm.)\\n\\n\\t\输出sight1到sight2的最短路径长度，存放在D[]数组中 printf(\输出景点一的名称 d=sight1; // 将景点一的编号赋值给d for(c=0;c

gate:; // 标号，可以作为goto语句跳转的位置 P[a][sight1]=0; for(b=0;b

21

第四章 测试与分析

4.1 测试数据选择

22

23

24

25

4.2 测试结果分析

1、在系统的设计中考虑到道路网的复杂性，故采用邻接矩阵作为存储结构，其空间复杂度为O（e）此时的空间复杂度也为O(e)。构建邻接矩阵的时间复杂度为O（n2+e*n），故本系统在构件图的时候的时间复杂度为O（n2+e*n）。

2、由于本系统在执行的时候，需要用户临时输入求最短的路径。迪杰斯特拉算法的时间复杂度比弗洛伊德算法的时间复杂度低。从这一角度考虑用地杰斯特拉算法更为合适。且其算法的时间复杂度为O（n3）.

26

总 结

1、特色：我们组在完成设计球最短路径的函数后，又实现了交互界面的设计，方便用户个不够好的使用本程序进行在校导航。另外我们还实现了查询校园中各景点间的距离以及信息查询等功能。

2、改进之处：在我们设计的导航系统中不能实现增加景点、删除道路以及修改景点信息等功能。另外在见图的时候算法的时间复杂度太大。如果能用邻接多重表的存储方式建立图的其时间复杂度会更好，算法也更加先进。

3、总结：本次数据结构课程设计针对具体的项目来进行需求分析、测试计划、概要设计、详细设计、测试分析等具体的步骤走下来，我从中收获巨大。首先在编写函数之前要充分利用各种资源、其次。应该更详细的考虑实际情况。才能使程序更具有实用性。当然更多的是组员之间要有合作的精神。

编程是一件和枯燥的事情，但是只要我们认真的专研，我们会从中学到很多在课本上无法学到的东西，同时也能从中感受到编程的乐趣。在今后的工作、学习中我将认真总结经验教训，努力使自己成为一名技术过硬、工作严谨、思维活跃的工程人员，为提高人们的生活质量做出更大的贡献。

27

心得体会

通过本次课程设计，我更熟练的应用了C语言中函数调用、函数声明、函数自定义类型、全局变量、局部变量······，以及数据结构中图和迪杰斯特拉算法。

图能够在计算机中存在，首先要知道他有哪些具体化、数字化的信息，比如说权值、顶点的个数等。这也就是说明了要想把生活中的信息转化到计算机中必须用数字来完整的构成一个信息库，而图的存储。又涉及到定点之间的联系。图分为有向图和无向图，而无向图又是有向图在权值双向想等下的一种特例。而在系统中我所选用的数据结构就是无向有权图。

迪杰斯特拉算法始终都是核心内容，从顶点一步一步找最近的路线并与其直线距离相比较，但是，在计算机中实现这么一个简单的想法就需要涉及到很多的专业知识。为了完成设计在前期的工作中基本都是以学习C语言为主，所以浪费了很多的时间。比如在程序中打印出最短路径经过的景点。在起初的时候只能以数字代替景点的名称。却无法直接打出要经过的景点的名称。最后通过查资料最终完成了程序的设计任务。

通过课程设计 再次夯实了C语言基础以及数据结构的应用能力，让我看清了自己的能力以及不足之处，看到了以后编程该走的路找到了通向成功的航标。其实这次更大的收获是编程必须有耐心，程序运行有很多漏洞不足是不可避免的，但是只要你有耐心，一步一步脚踏实地的做下去，一个一个语法的改总会成功。

28

参考文献

[1]严蔚敏、吴为民.数据结构（C语言版）.北京:清华大学出版社.2007 [2]钱能.C++程序设计教程.北京.清华大学出版社.1999

[3]邓文华.数据结构实验和实训教程.北京.清华大学出版社.2011

[4] 高寒弢. 最短路径算法在交通咨询系统中的应用.成都.计算机与信息技术.2011

29

本文来源：https://www.bwwdw.com/article/bh3a.html