校园导航系统课程设计.doc

校园导航课程设计报告书专 业：计算机科学与技术 课程设计名称：数据结构课程设计题 目：校园导航问题班 级：学号：姓名：同 组 人 员: 指 导 老 师：完 成 时 间：2012年2月17日摘要校园导航问题是基于校园中的不同的景点，从陌生人的角度，为来往的客人提供校园景点相关信息的查询以及为来往的客人提供校园中任意景点的问路查询，以便客人能用最短的时间从某一地点到达想要去的地方。大大节约了旅客参观校园的时间。本文是采用C+作为开发语言，又最大程度上用了C语言的有关的语法。以visual c+6.0为开发工具。旨在实现校园导航系统中，学校的简介，景点的介绍，路线查询等基本的问题。为来往客人参观校园提供方便。关键词：C+；C；visual c+6.0；校园导航目录目录1第一章开发环境和开发工具11.1C/ C +语言简介11.2 开发背景11.3 开发环境1第二章 算法思想22.1 系统需求分析22.2 系统总体设计32.2.1 系统设计目标32.2.2 开发设计思想32.2.3 系统功能模块设计32.3 算法思想描述4第三章算法实现63.1 数据结构63.2 程序模块63.3 各模块之间的调用关系上123.4 源程序代码12第四章测试与分析224.1 测试数据选择224.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+。它是一个系统的集成开发环境。很适合CC+程序的开发。我们日常的学习和生活中大多就用这个开发环境进行学习和编程。第二章 算法思想2.1 系统需求分析1、设计你的学校的校园平面图，所选的景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。2、为来往客人提供图中任意景点相关信息的查询。3、为来往的客人提供图中任意景点的问路查询，即查询任意两个景点间的一条最短的简单路径。根据以上分析和抽象可得到本系统的抽象数据类型如下：ADT graph 数据对象 R：V是校园中景点的集合，称为顶点集。 R=VR VR=|v,wV且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.1 系统设计目标 本文研究开发的校园导航系统用于支持来往校园参观的客人提供最省时的导航服务，有如下三个方面的目标: 1、为来往的客人提供校园的简介。2、为来往的客人提供校园中各景点的简介，以及各景点的距离等情况。3、为来往的客人提供到达目的地的最短的路线。2.2.2 开发设计思想 基于以上系统设计目标，本文在开发校园导航系统时遵循了以下开发设计思想: 1、采用现有的软硬件环境及先进的管理系统开发方案，从而达到充分利用现有资源，提高系统开发水平和应用效果的目的。2、尽量达到操作过程中的直观、方便、实用、安全等要求。3、系统采用模块化程序设计方法，既便于系统功能的各种组合和修改，又便于未参与开发的技术维护人员补充、维护。2.2.3 系统功能模块设计 本系统分为四个模块：菜单模块、景点介绍模块、路径查询模块、最短路径模块。得到如图3-1所示的系统功能模块图。主菜单校园导航系统菜单景点介绍路径查询最短路径查询子菜单退出学校简介景点简介各景点间距离最短路径长度最短路线图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、邻接矩阵建立有无向权图的算法思想：用两个数组分别存储数据元素的信息和数据之间的关系的信息其形式描述如下：#define Max 32767/最大值#define NUM 11/最大顶点个数typedef struct ArcCellint adj; / 相邻接的景点之间的路程 char *info;ArcCell; / 定义边的类型 typedef struct VertexTypeint number; / 景点编号 char *sight; / 景点名称 char *description; / 景点描述 VertexType; / 定义顶点的类型 typedef structVertexType vexNUM; / 图中的顶点，即为景点 ArcCell arcsNUMNUM; / 图中的边，即为景点间的距离 int vexnum,arcnum; / 顶点数，边数 MGraph; / 定义图的类型 其中用二维数组表示途中个边之间的关系。第三章 算法实现3.1 数据结构1、顶点、边和图类型：typedef struct ArcCellint adj; / 相邻接的景点之间的路程 char *info;ArcCell; / 定义边的类型 typedef struct VertexTypeint number; / 景点编号 char *sight; / 景点名称 char *description; / 景点描述 VertexType; / 定义顶点的类型 typedef structVertexType vexNUM; / 图中的顶点，即为景点 ArcCell arcsNUMNUM; / 图中的边，即为景点间的距离 int vexnum,arcnum; / 顶点数，边数 MGraph; / 定义图的类型3.2 程序模块 1.main函数 void main() / 主函数 int v0,v1;char ck;system(color cb);CreateUDN(NUM,11);do ck=Menu();switch(ck)case1:introduce();printf(nnttt%-25snn,G.vex0.description);getchar();getchar();break;case 2:system(cls);pingmu();printf(nnttt请选择起点景点（110）：);scanf(%d,&v0);printf(ttt请选择终点景点（110）：);scanf(%d,&v1);ShortestPath(v0); / 计算两个景点之间的最短路径 output(v0,v1); / 输出结果 printf(nntttt请按回车键继续.n);getchar();getchar();break;case 3:search();break;case5:PrintMGraph();printf(nntttt请按回车键继续.n);getchar();getchar();break;while(ck!=e);2.主菜单 char Menu() / 主菜单 /char c;int flag;doflag=1;system(cls);pingmu();printf(nttn);printf(tt n);printf(tt 1.学校简介 n);printf(tt 2.查询景点路径 n);printf(tt 3.查询景点信息 n);printf(tt 5.查询各景点之间的距离 n);printf(tt e.退出 n);printf(tt n);printf(ttn);printf(tttt请输入您的选择：);scanf(%c,&c);if(c=1|c=2|c=3|c=5|c=e)flag=0;while(flag);return c;3.查询子菜单char SearchMenu() / 查询子菜单 char c;int flag;doflag=1;system(cls);pingmu();printf(nttn);printf(tt n);printf(tt 1、按照景点编号查询 n);printf(tt 2、按照景点名称查询 n);printf(tt e、返回 n);printf(tt n);printf(ttn);printf(ttt请输入您的选择：);scanf(%c,&c);if(c=1|c=2|c=e)flag=0;while(flag);return c;4.查询景点信息void search() / 查询景点信息 int num;int i;char c;char name20;dosystem(cls);c=SearchMenu();switch (c)case 1: system(cls);/introduce();pingmu();printf(nntt请输入您要查找的景点编号：);scanf(%d,&num);for(i=0;iNUM;i+)if(num=G.vexi.number)printf(nnttt您要查找景点信息如下:);printf(nnttt%-25snn,G.vexi.description);printf(nttt按任回车返回.);getchar();getchar();break;if(i=NUM)printf(nnttt没有找到！);printf(nnttt按回车键返回.);getchar();getchar();break;case 2:system(cls);pingmu();introduce();printf(nntt请输入您要查找的景点名称：);scanf(%s,name);for(i=1;iNUM;i+)if(!strcmp(name,G.vexi.sight)printf(nnttt您要查找景点信息如下:);printf(nnttt%-25snn,G.vexi.description);printf(nttt按回车键返回.);getchar();getchar();break;if(i=NUM)printf(nnttt没有找到！);printf(nnttt按回车键返回.);getchar();getchar();break;while(c!=e);5.创建图的函数void CreateUDN(int v,int a) / 创建图的函数 6. 打印出邻接矩阵void PrintMGraph()int i,j;coutn =nn ;for(i=1;iG.vexnum;+i)coutG.vexi.sight ;coutendl;for(i=1;iG.vexnum;+i)coutnnG.vexi.sight ;for(j=1;jG.vexnum;+j)if(G.arcsij.adj=Max)cout no ;elsecout G.arcsij.adj;coutnnnn=nnn;7.迪杰斯特拉算法void ShortestPath(int num) / 迪杰斯特拉算法最短路径函数 num为入口点的编号 int v,w,i,t; / i、w和v为计数变量 int finalNUM; int min;for(v=1;vNUM;v+)finalv=0; / 假设从顶点num到顶点v没有最短路径 Dv=G.arcsnumv.adj;/ 将与之相关的权值放入D中存放 for(w=1;wNUM;w+) / 设置为空路径 Pvw=0;if(Dv32767) / 存在路径 Pvnum=1; / 存在标志置为一 Pvv=1; / 自身到自身 Dnum=0;finalnum=1; / 初始化num顶点属于S集合 / 开始主循环，每一次求得num到某个顶点的最短路径，并将其加入到S集合 for(i=1;iNUM;+i) / 其余G.vexnum-1个顶点 min=Max; / 当前所知离顶点num的最近距离 for(w=1;wNUM;+w)if(!finalw) / w顶点在v-s中 if(Dwmin) / w顶点离num顶点更近 v=w;min=Dw; finalv=1; / 离num顶点更近的v加入到s集合 for(w=1;wNUM;+w) / 更新当前最短路径极其距离 if(!finalw&(min+G.arcsvw.adj)Dw)/ 不在s集合，并且比以前所找到的路径都短就更新当前路径 /Dw=min+G.arcsvw.adj;for(t=0;tNUM;t+)Pwt=Pvt;Pww=1;8、输出：屏幕输出函数：void pingmu()；最短路线输出函数void output；3.3 各模块之间的调用关系上 模块调用关系如图32所示：mainCreateUDNmenusearchShortestPathoutputPrintMGraphpingmusearchmenu图32模块调用关系图3.4 源程序代码#include #include string.h #include stdio.h #include stdlib.h#define Max 32767#define NUM 11typedef struct ArcCellint adj; / 相邻接的景点之间的路程 char *info;ArcCell; / 定义边的类型 typedef struct VertexTypeint number; / 景点编号 char *sight; / 景点名称 char *description; / 景点描述 VertexType; / 定义顶点的类型 typedef structVertexType vexNUM; / 图中的顶点，即为景点 ArcCell arcsNUMNUM; / 图中的边，即为景点间的距离 int vexnum,arcnum; / 顶点数，边数 MGraph; / 定义图的类型 MGraph G; / 把图定义为全局变量 int PNUMNUM; / /long int DNUM; / 辅助变量存储最短路径长度 int x13=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(color 4b);CreateUDN(NUM,11);do ck=Menu();switch(ck)case1:introduce();printf(nnttt%-25snn,G.vex0.description);getchar();getchar();break;case 2:system(cls);pingmu();printf(nnttt请选择起点景点（110）：);scanf(%d,&v0);printf(ttt请选择终点景点（110）：);scanf(%d,&v1);ShortestPath(v0); / 计算两个景点之间的最短路径 output(v0,v1); / 输出结果 printf(nntttt请按回车键继续.n);getchar();getchar();break;case 3:search();break;case5:PrintMGraph();printf(nntttt请按回车键继续.n);getchar();getchar();break;while(ck!=e);char Menu() / 主菜单 /char c;int flag;doflag=1;system(cls);pingmu();introduce();printf(nttn);printf(tt n);printf(tt 1.学校简介 n);printf(tt 2.查询景点路径 n);printf(tt 3.查询景点信息 n);printf(tt 5.查询各景点之间的距离 n);printf(tt e.退出 n);printf(tt n);printf(tt n);printf(tttt请输入您的选择：);scanf(%c,&c);if(c=1|c=2|c=3|c=5|c=e)flag=0;while(flag);return c;char SearchMenu() / 查询子菜单 char c;int flag;doflag=1;system(cls);pingmu();introduce();printf(ntt n);printf(tt n);printf(tt 1、按照景点编号查询 n);printf(tt 2、按照景点名称查询 n);printf(tt e、返回 n);printf(tt n);printf(tt n);printf(ttt请输入您的选择：);scanf(%c,&c);if(c=1|c=2|c=e)flag=0;while(flag);return c;void search() / 查询景点信息 int num;int i;char c;char name20;dosystem(cls);c=SearchMenu();switch (c)case 1: system(cls);introduce();pingmu();printf(nntt请输入您要查找的景点编号：);scanf(%d,&num);for(i=0;iNUM;i+)if(num=G.vexi.number)printf(nnttt您要查找景点信息如下:);printf(nnttt%-25snn,G.vexi.description);printf(nttt按任回车返回.);getchar();getchar();break;if(i=NUM)printf(nnttt没有找到！);printf(nnttt按回车键返回.);getchar();getchar();break;case 2:system(cls);pingmu();introduce();printf(nntt请输入您要查找的景点名称：);scanf(%s,name);for(i=1;iNUM;i+)if(!strcmp(name,G.vexi.sight)printf(nnttt您要查找景点信息如下:);printf(nnttt%-25snn,G.vexi.description);printf(nttt按回车键返回.);getchar();getchar();break;if(i=NUM)printf(nnttt没有找到！);printf(nnttt按回车键返回.);getchar();getchar();break;while(c!=e);void CreateUDN(int v,int a) / 创建图的函数 int i,j;G.vexnum=v; / 初始化结构中的景点数和边数 G.arcnum=a;for(i=1;iG.vexnum;+i) G.vexi.number=i; / 初始化每一个景点的编号 / 初始化没一个景点名及其景点描述 G.vex0.sight=学校简介;G.vex1.sight=校大门;G.vex2.sight=教学楼;G.vex3.sight=中心广场;G.vex4.sight=山顶操场;G.vex5.sight=学生宿舍;G.vex6.sight=图书馆;G.vex7.sight=体育馆;G.vex8.sight=二食堂;G.vex9.sight=服务楼;G.vex10.sight=北门;/ 这里把所有的边假定为32767，含义是这两个景点之间是不可到达 for(i=1;iG.vexnum;+i)for(j=1;jG.vexnum;+j) G.arcsij.adj=Max;G.arcsij.info=NULL;/下边是可直接到达的景点间的距离，由于两个景点间距离是互相的，/ 所以要对图中对称的边同时赋值。G.arcs14.adj=G.arcs41.adj=200;G.arcs13.adj=G.arcs31.adj=500;G.arcs35.adj=G.arcs53.adj=100;G.arcs310.adj=G.arcs103.adj=400;G.arcs46.adj=G.arcs64.adj=200;G.arcs25.adj=G.arcs52.adj=200;G.arcs24.adj=G.arcs42.adj=300;G.arcs57.adj=G.arcs75.adj=500;G.arcs46.adj=G.arcs64.adj=400;G.arcs47.adj=G.arcs74.adj=600;G.arcs68.adj=G.arcs86.adj=500;G.arcs78.adj=G.arcs87.adj=300;G.arcs69.adj=G.arcs96.adj=500;/ 打印出邻接矩阵void PrintMGraph()int i,j;coutn =nn ;for(i=1;iG.vexnum;+i)coutG.vexi.sight ;coutendl;for(i=1;iG.vexnum;+i)coutnnG.vexi.sight ;for(j=1;jG.vexnum;+j)if(G.arcsij.adj=Max)cout no ;elsecout G.arcsij.adj;coutnnnn=nnn;void introduce() / 介绍函数 int i;for(i=1;i=NUM;i+) G.vex0.description=河南城建学院坐落在国家旅游城市nntt国家历史文化名城-平顶山，校园椰风流韵、芳林叠翠、风景秀丽。nntt经过二十多年的发展,学校现已形成以城建为主要办学特色nntt文、管、理、经等多学科协调发展的格局,是河南省培养城建类nntt高级应用型人才的重要基地.目前，学校确立了立足河南nntt逐渐面向全国服务面向定位，充分发挥学校特色nntt积极扩大对外交流与合作，学术交流日趋nntt频繁，国际影响不断增强nntt下面几点是河南城建学院的办学特色：nntt办学历史较为悠久nntt学科专业较为齐全nntt师资队伍素质优良nntt教学成果较为丰硕nntt科研水平不断提高nntt校园文化丰富活跃nntt人才培养成效显著nntt合作交流日趋频繁nntt;G.vex1.description=学校大门，对面是祥云公园ntt是我们学生休闲娱乐的好地方;G.vex2.description=计教系办公大楼，计算机科学技术的科研中心;G.vex3.description=这里是学校的主要的风景区，是学校的标志之一;