校园导航问题课程设计论文

1、。摘要校园导航要求两个地方之间可以有不同的道路，而且道路的长度可能不同，所以要找出从一个地方到另一个地方的最佳路径(最短路径)。用“邻接矩阵”存储每个点之间的距离，然后用Dijkstra算法寻找最短路径。因此，利用工程思想，系统分为以下五个模块：节点数据结构类型、导航图创建功能、最短路径导航功能、查询功能声明和主菜单。关键词校园导航查询的Dijkstra算法目录摘要1校园导航问题61问题分析和任务定义：62数据结构的描述和定义73 Dijkstra算法流程图84程序运行和调试95结论11参考文献12附录：12校园导航问题1问题分析和任务定义：本课程设计的内容是设计学校的平面图，包括至少10个位

2、置。每两个地方之间可能有不同的道路，道路的长度也可能不同，从而找出从一个地方到另一个地方的最佳路径(最短路径)。如图1所示，主要路线已经标记，每条路线的长度如表1所示。显然，要解决这个问题，应该使用“邻接矩阵”来存储每个点之间的距离，然后使用Dijkstra来寻找最短路径。7图书馆1个大厅8主楼0分析测试中心3二号教学楼6个足球场410一号楼2一个教学习地面9学生食堂5个篮球场图1:校园规划01:200 0:20 07:100 08:10017:50 18336050 24:350 25:20026:100 29:150 34:290 36:20039:300 45:200 49:50 59:

3、10067:200 78:100表1:距各景点的距离单位：米(米)2数据结构的描述和定义1.节点数据结构类型#定义最大值20000#定义NUM 10typedef结构ArcCellint adj/*相邻景点之间的距离*/ ArcCell/*定义边的类型*/typedef结构VertexType整数；/*景点编号*/char*瞄准器；/*景点名称*/char*信息；/*景点描述*/ VertexType/*定义顶点的类型*/typedef结构顶点类型vexNUM；/*图片中的顶点是景点*/弧单元弧数值数值；/*图中的边缘是景点之间的距离*/int vexnum，arcnum/*顶点数，边数*/

4、MGraph/*定义图形的类型*/2.创建导航图表功能void CreateUDN(int v，int a)每个节点都被命名，从每个顶点到所有其他固定点的路径值由邻接矩阵存储。示例：G.vex0。sight=分析和测试中心；功能：将0号定点命名为“分析测试中心”；G.vex0。info=教师工作，学生做实验；角色：0号被描述为“老师的办公室，学生做实验”；G.arcs01。可调=圆弧10。可调=200；函数：从节点0到节点1的路径被指定为200，它应该是一个无向图，所以从节点1到节点0的路径长度也应该被指定为200。3.最短路径导航功能void肖特路径(int num)功能描述：利用Dijks

5、tra算法找到从无向网络G的不动点V0到其他不动点V的最短路径Pv及其加权长度Dv。如果Pvw为真，那么w是从V0到v的最短路径上的顶点。当且仅当VS，即从V0到V的最短路径已经获得时，最终v为真。4.查询函数声明char搜索菜单()void HaMiTonian(int)功能描述：哈密尔顿图的遍历。5.炙单char菜单()描述；显示导航地图中的所有导航节点，可以快速方便地导航到每个地方。3 Dijkstra算法流程图4程序运行和调试用microsoft visual c 6.0运行此程序的结果如下：主界面：景点路径查询景点信息查询推荐的旅游路线6结论该系统可以在大量的校园景点中任意指定两个景

6、点，给出最短路径。Save()保存功能和load()下载功能分别用于保存创建的导航数据和下载其他导航数据，使系统更加实用。void createadj()函数的原始原型是arcnode *createdj()，它使用链表结构保存adjmatrix的数据，以便保存数据。但是，Dijkstra中的adjmatrix应该转换为arcnode指针的形式，因为只有这样才能使用下载的数据。参考1 数据结构 (c语言版)，严为民，清华大学出版社，2005。2 算法设计与分析，王晓东主编，清华大学出版社，20053王世林译，数据结构、算法与应用，萨达尼译，机械工业出版社，19994 数据结构与算法分析，CLI

7、FFORD A. SHAFFER，张明刘小丹译，电子工业出版社，19985谭浩强。c编程Z。北京：清华大学出版社，2001。6薛。c语言编程教程。北京：机械工业出版社，2000。颜路。实用C语言及其编程Z。大连：大连理工大学出版社，1993。8郑源。编程技能汇编Z。北京：电子工业出版社，1993。附加记录源程序：#包含“string.h”#包括“stdio.h”#包括“stdio.h”#包括 malloc.h #包括“stdlib.h”#定义最大值20000#定义NUM 10typedef结构ArcCellint adj/*相邻景点之间的距离*/ ArcCell/*定义边的类型*/typede

8、f结构VertexType整数；/*景点编号*/char*瞄准器；/*景点名称*/char*信息；/*景点描述*/ VertexType/*定义顶点的类型*/typedef结构顶点类型vexNUM；/*图片中的顶点是景点*/弧单元弧数值数值；/*图中的边缘是景点之间的距离*/int vexnum，arcnum/*顶点数，边数*/ MGraph/*定义图形的类型*/图G；/*将图形定义为全局变量*/整数数值数值；/* */长整型数；/*辅助变量存储最短路径长度*/int x9= 0 ；void CreateUDN(int v，int a)；/*映射函数*/无效叙述()；/*描述功能*/void肖

9、特路径(int num)；/*最短路径函数*/无效输出(int view 1，int view 2)；/*输出函数*/char菜单()；/*主菜单*/无效搜索()；/*查询景点信息*/char搜索菜单()；/*查询子菜单*/无效哈密顿量(整数)；/*哈密尔顿图的遍历*/void NeXt VaLue(int)；无效显示()；/*显示遍历结果*/无效主()/*主功能*/int v0，v1；char ckCreateUDN(NUM，11)；做ck=菜单()；开关(ck)案例1:系统(“cls”)；讲述()；/*输出景点列表*/printf( n n t t t请选择起点(0 9):)；scanf(

10、“% d”，v0)；printf( t t t请选择目标(0 9):)；scanf(“% d”，v1)；短路径(v0)；/*计算两个景点之间的最短路径*/输出(v0，v1)；/*输出结果*/printf( n n t t t t按任意键继续. n)；getchar()；getchar()；打破；案例2: search()；打破；案例3:系统(“cls”)；讲述()；x0=1；哈米托尼亚；printf( n n t t t t按任意键继续. n)；getchar()；getchar()；打破；同时(ck！=e)；字符菜单()/*主菜单*/char c；int标志；do标志=1；系统(“cls”)

11、；讲述()；/*输出景点列表*/printf(ntttn)；printf(tttn)；Printf(ttt 1、查询景点路径(n)；2、查询Printf(ttt景区信息(n)；Printf ( t t t 3，推荐的游览路线 n )；Printf ( t t t e，exit n )；printf(tttn)；printf(tttn)；printf( t t t t请输入您的选择：)；scanf(% c ，c)；if(c=1|c=2|c=3|c=e)标志=0；当(旗帜)；返回c .茶搜索菜单()/*查询子菜单*/char c；int标志；do标志=1；系统(“cls”)；讲述()；printf(ntttn)；printf(tttn)；printf(ttt 1、按照景点编号查询n)；printf(ttt 2、按照景点名称查询n)；printf(ttte，返回n)；printf(tttn)；printf(tttn)；printf(tttt请输入您的