搜索
校园导航课程设计报告书专业：计算机科学与技术课程设计名称：《数据结构课程设计》题目：校园导航问题班级：学号：姓名：同组人员:指导老师：完成时间：2012年2月17日摘要校园导航问题是基于校园中的不同的景点，从陌生人的角度，为来往的客人提供校园景点相关信息的查询以及为来往的客人提供校园中任意景点的问路查询，以便客人能用最短的时间从某一地点到达想要去的地方。大大节约了旅客参观校园的时间。本文是采用C++作为开发语言，又最大程度上用了C语言的有关的语法。以visualc++6.0为开发工具。旨在实现校园导航系统中，学校的简介，景点的介绍，路线查询等基本的问题。为来往客人参观校园提供方便。关键词：C++；C；visualc++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参考文献..........................................................291第一章开发环境和开发工具1.1C/C++语言简介C语言是一种计算机程序设计语言。它既具有高级语言的特点，又具有汇编语言的特点。它由美国贝尔研究所的D.M.Ritchie于1972年推出。1978后，C语言已先后被移植到大、中、小及微型机上。它可以作为工作系统设计语言，编写系统应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。它的应用范围广泛，具备很强的数据处理能力，不仅仅是在软件开发上，而且各类科研都需要用到C语言，适于编写系统软件，三维，二维图形和动画。具体应用比如单片机以及嵌入式系统开发。C++是一种静态数据类型检查的、支持多重编程范式的通用程序设计语言。它支持过程化程序设计、数据抽象、面向对象程序设计、制作图标等等泛型程序设计等多种程序设计风格。1.2开发背景随着科学技术的不断发展，计算机科学日渐成熟，其强大的功能已为人们所深刻认识，它己进入人类社会的各个领域并发挥着越来越重要的作用。采用计算机进行校园导航已成为衡量校园数字化的重要标志。校园导航效率的好坏对于来校参观的客人和学校管理者来说都至关重要，在很大程度上影响着校园的数字化建设和学校的影响力。因此，本文所研究的校园导航系统具有一定的使用价值和现实意义。1.3开发环境本文所采用的开发环境主要是基于c++的visualstadioc++。它是一个系统的集成开发环境。很适合C\C++程序的开发。我们日常的学习和生活中大多就用这个开发环境进行学习和编程。2第二章算法思想2.1系统需求分析1、设计你的学校的校园平面图，所选的景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。2、为来往客人提供图中任意景点相关信息的查询。3、为来往的客人提供图中任意景点的问路查询，即查询任意两个景点间的一条最短的简单路径。根据以上分析和抽象可得到本系统的抽象数据类型如下：ADTgraph{数据对象R：V是校园中景点的集合，称为顶点集。R={VR}VR={v,w,|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出发到图中任意顶点的最短的路径。}ADTgraph；32.2系统总体设计2.2.1系统设计目标本文研究开发的校园导航系统用于支持来往校园参观的客人提供最省时的导航服务，有如下三个方面的目标:1、为来往的客人提供校园的简介。2、为来往的客人提供校园中各景点的简介，以及各景点的距离等情况。3、为来往的客人提供到达目的地的最短的路线。2.2.2开发设计思想基于以上系统设计目标，本文在开发校园导航系统时遵循了以下开发设计思想:1、采用现有的软硬件环境及先进的管理系统开发方案，从而达到充分利用现有资源，提高系统开发水平和应用效果的目的。2、尽量达到操作过程中的直观、方便、实用、安全等要求。3、系统采用模块化程序设计方法，既便于系统功能的各种组合和修改，又便于未参与开发的技术维护人员补充、维护。2.2.3系统功能模块设计本系统分为四个模块：菜单模块、景点介绍模块、路径查询模块、最短路径模块。得到如图3-1所示的系统功能模块图。4图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、邻接矩阵建立有无向权图的算法思想：校园导航系统菜单景点介绍路径查询最短路径查询子菜单退出学校简介景点简介各景点间距离最短路径长度最短路线主菜单5用两个数组分别存储数据元素的信息和数据之间的关系的信息其形式描述如下：#defineMax32767//最大值∞#defineNUM11//最大顶点个数typedefstructArcCell{intadj;//相邻接的景点之间的路程char*info;}ArcCell;//定义边的类型typedefstructVertexType{intnumber;//景点编号char*sight;//景点名称char*description;//景点描述}VertexType;//定义顶点的类型typedefstruct{VertexTypevex[NUM];//图中的顶点，即为景点ArcCellarcs[NUM][NUM];//图中的边，即为景点间的距离intvexnum,arcnum;//顶点数，边数}MGraph;//定义图的类型其中用二维数组表示途中个边之间的关系。6第三章算法实现3.1数据结构1、顶点、边和图类型：typedefstructArcCell{intadj;//相邻接的景点之间的路程char*info;}ArcCell;//定义边的类型typedefstructVertexType{intnumber;//景点编号char*sight;//景点名称char*description;//景点描述}VertexType;//定义顶点的类型typedefstruct{VertexTypevex[NUM];//图中的顶点，即为景点ArcCellarcs[NUM][NUM];//图中的边，即为景点间的距离intvexnum,arcnum;//顶点数，边数}MGraph;//定义图的类型3.2程序模块1.main函数voidmain()//主函数{intv0,v1;charck;system(colorcb);CreateUDN(NUM,11);do{ck=Menu();switch(ck){case'1':introduce();printf(\n\n\t\t\t%-25s\n\n,G.vex[0].description);getchar();getchar();break;case'2':7system(cls);pingmu();printf(\n\n\t\t\t请选择起点景点（1～10）：);scanf(%d,&v0);printf(\t\t\t请选择终点景点（1～10）：);scanf(%d,&v1);ShortestPath(v0);//计算两个景点之间的最短路径output(v0,v1);//输出结果printf(\n\n\t\t\t\t请按回车键继续...\n);getchar();getchar();break;case'3':search();break;case'5':PrintMGraph();printf(\n\n\t\t\t\t请按回车键继续...\n);getchar();getchar();break;};}while(ck!='e');}2.主菜单charMenu()//主菜单//{charc;intflag;do{flag=1;system(cls);pingmu();printf(\n\t\t┏━━━━━━━━━━━━━━━━━━━┑\n);printf(\t\t┃┃\n);printf(\t\t┃1.学校简介┃\n);printf(\t\t┃2.查询景点路径┃\n);print