《数据结构课程设计桂林电子科技大学海洋信息工程学院导航系统.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计桂林电子科技大学海洋信息工程学院导航系统.doc（47页珍藏版）》请在三一办公上搜索。
1、 编号：201 数据结构与算法课程设计说明书 桂电海院校园导游咨询与最短路径（+5）学院： 海洋信息工程学院 专 业： 计算机科学与技术 学生姓名： 黄兰丽 学 号： 1316040201 指导教师： 王晓莹 2015年 6 月 29 日桂电海院校园导航系统 学生姓名： 指导老师：王晓莹摘 要本文主要介绍了利用Windows7系统和C+开发语言编写校园导航系统的应用程序。在现代条件下实现平台广。 校园导航问题是基于校园中的不同的景点，建立结构体数据结构模型，设计能够让普通用户更便捷更具体详细地了解景点信息，最短路径，常用设施以及管理用户的修改信息。为来往的客人提供校园景点和校园设施相关信息的查
2、询，提供校园中任意景点间的最短路径查询。管理员通过密码登录以后可以根据校园发展变化来修改景点信息，既保证了安全也便于更新景点信息。在本校园导航系统中，可以实现三大功能：一、景点的介绍；二、设施查询，人行和开车人性化分开的精准度高的路线查询；三、管理员修改信息。同时，本系统的功能选择、景点输入、设施输入等都拥有友好而强大的异常处理功能，具有实用性，便利性和发展性。关键字：数据结构校园导航异常处理安全权限CAMPUS NAVIGATION SYSTEM of GUET HAI YUAN Student:Teacher:Wang XiaoyingAstacrtThis article mainly
3、introduce the use of Windows system and c + + development language to write the campus navigation system applications. In the condition of modern, there are implementation platform Campus navigation is based on the campus in different spots, structure data structure model is established, the design
4、can make ordinary users more convenient and more detailed understanding of the attractions, the shortest path, common facilities and management user modify information. For the guest to provide the campus scenic spots and campus facilities information query, provide any attractions between the short
5、est path query in the campus. Administrator through the password after login information can be modified according to the development and change of campus scenic spots, not only ensure the safe and easy to update attractions.In this campus navigation system, it can realize the three functions: one,
6、the introduction, the introduction of attractions, Second, the query facilities, separate pedestrian and human driving route query of high precision; Third, the administrator to modify information. The function of this system choose input, attractions, facilities such as input with a friendly and po
7、werful exception handling, practical, convenience and expansibility.Key words: data structureThe campus navigationException handlingSecurity permissions目 录引 言1设计背景1研究方法1实现目标2问题重述21.1桂电海院校园导游咨询与最短路径（+5）22需求分析32.1系统需求概述32.2.功能需求32.3设计要求32.3界面需求42.4开发环境42.5.实验构思53概要设计73.1设计原理（C/C+语言简介)73.2方案设计与论证73.3系统
8、模块设计74整体设计94.1整体设计概述94.2函数详细设计94.3各功能模块详细设计：155系统特色及关键技术205.1关键技术205.2系统特色：206测试结果216.1运行程序测试216.2测试结果分析247所遇到的问题和分析解决258使用说明26总结26致谢28附录29引 言设计背景现在科技越来越发达，电脑上、手机上的软件越来越多，所以开发一些小程序也越来越可变为实用了，越来越有必要。无论什么导航仪最主要的部分都是电子地图，开发电子地图成为了导航的关键。然而，根据调查得知电子地图制作困难且相当昂贵，给导航仪开发带来了许多不便。自主绘制地图，编写与地图功能相关的程序，不管是从经济上还是研
9、究上都具有非常大的意义。同时与传统的地图相比，地理信息系统有着不可比拟的优势，它信息量大，简洁直观，切换方便，可扩展性强。面对广阔的校园环境,刚入学的新生或是初次到学校参观的人往往不清楚怎样才能到达自己的目的地,需要一个校园自主导航器引导他们出行可是，到目前为止，桂林电子科技大学海洋信息工程学院是没有这种校内导航系统的。桂电海院是桂林电子科技大学一所新的二本院校，也是北海市唯一的一所二本院校，相信一定会引来许多老师，学生，家长或者普通游客来参观。针对校园现代化的实现，也是对于来访我校的访客和新生能够更方便的了解学校的景点，便于参观，减少访客的迷茫感，因此,在校园中设置一些旅游景区中的自主导航器
10、十分必要。我也觉得研究开发一个校园导航系统是很有意义的，于是我们编写了这个校园导航系统，为刚入学的新生或是初次到学校参观的人员提供一个校园自主导航器引导他们出行。研究方法对本系统的研究，我们是通过实地考察与测量，建立把实际问题转为数据结构中图类的问题，这样就有了算法的模型，再采用了分模块解决实际问题的方法。首先将校园景点的基本信息用结构体数组来存储起来，即能把景点相关信息，如基本介绍，设有的设施和评分等连接起来，也便于输出；其次就是把各个景点作为图的结点，将景点间的路径作为图的边，路径距离作为边的权值。这样一来，求两景点间最短路径的问题就抽象成了求图中一结点到另一结点的问题。数据结构与算法，也
11、是计算机代替人工的实现方法，是软件工程必不可少的基础。对于本次校园导航系统，我有如下陈述：本系统是一个涉及桂电海院相关景点和场所查询系统,是为了方便人们能够更快更准地获得学校各个景点和场所的详细信息。其设计主要根据学校的各个景点和场所所设计的导航系统。我们是通过结构体的顺序存储的方式设置基本的景点信息的，然后以图的邻接矩阵存储景点间的距离，并用弗洛里德算法求的最短路径，同样是用邻接矩阵存储的。在需要的时候，只要按要求输出就好。在修改模块部分，我们设定需要密码，增加了权限，保证系统内信息不被破坏。实现目标 本课题命名为桂电海院校园导游咨询与最短路径，以实际问题为基础，参照其他学校导航系统的建立起
12、来的一个新的模型，旨在建立一个本校的导航系统。可以根据不同用户的需求，不用实地参观，就可以得到各种信息。基于上述背景与目标，开发一个校园导航项目，使用Windows7搭配Codeblocks来实现这个项目的功能，开发一个可以运行的小客户端，手机电脑都可以使用，给用户提供友好的服务。问题重述1.1桂电海院校园导游咨询与最短路径（+5）1.问题描述1) 从桂电海洋学院的平面图中选取有代表性景点（10-15个），抽象成一个无向带权图。以图中顶点表示景点，边上的权值表示两地之间距离。2) 本程序的目的是为用户提供路径咨询。根据用户指定的始点和终点输出相应路径，或者根据用户指定的景点输出景点的信息。2.
13、任务要求1) 从桂电海洋学院的平面图中选取有代表性景点（10-15个），抽象成一个无向带权图。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等信息。2) 为来访客人提供图中任意景点相关信息的查询。3) 为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。4) 区分汽车线路与步行线路。3.测试数据桂电海院校园导游图（距离可估计）。个人总结：问题重述，明确研究对象，清晰任务要求，有助于需求分析，模型建立。2需求分析2.1系统需求概述界面简洁、清楚、功能齐全，使用方便，交互界面良好，容易操作，让没用过这个系统的人一看就知道如何操作。
14、系统稳定，有一定的异常处理功能。2.2.功能需求1. 在菜单中显示校园景点编号。2. 用户能够查询任意景点的景点信息。3. 能根据用户输入的起始以及终点景点编号查询最短路程以及指引路线。4. 能根据用户的特殊需求，如厕所，银行，商店来进行特殊查询；5. 能对内部数据进行修改，验证内部人员密码后即可；2.3设计要求数据结构与算法课程设计基本要求：1. 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3. 独立完成，提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4. 训练用系统的观点和软件
15、开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。校园导航系统具体要求： 1. 设计学校的平面图，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最短路径（路线及最短路程）。 2. 设置及显示，要能完成各景点信息记录以及查阅功能。3. 景点问路查询，即求任意两个景点间的一条最短的简单路径以及任意 景点到其他所有景点的最短路径查询。在邻接矩阵中INT_MAX表示最大距离即两个景点之间是不可到达的。用实际权值来表示两个景点之间是可达的，权值即是距离。4. 特殊设施查询，景点结构体数组中包括特殊设施，便于用户查询。5. 主界面，列出所有校内无重复排列的
16、景点，提供使用者选择功能界面，按照提示进行操作。 6.输入输出，根据菜单提示键入相应的键已完成相应操作。程序对用户键入信息都会在后台进行判断与异常处理，并根据用户键入的正确信息，调用相应函数，完成查找或其他操作，不只是查找结果的屏幕显示，其实每一次输入都是有相应的内容输出到，界面友好，详细又明白，可读性强。2.3界面需求系统界面要具有广泛的实用性，又要便于移植。界面友好，操作简便。根据软件的使用环境、用户的要求，系统界面应该简单、友好、易于使用、方便查看、简洁明快。而且系统是在Windows环境下的应用软件，软件产品的界面应该与操作系统的界面相切合，产品的主界面可供选择功能齐全，分类明确，编号
17、清楚，让用户一眼看去就能明白大致的功能。2.4开发环境随着科学技术的不断发展，计算机科学日渐成熟，其强大的功能已为人们所深刻认识，它己进入人类社会的各个领域并发挥着越来越重要的作用。采用计算机进行校园导航已成为衡量校园数字化的重要标志。校园导航效率的好坏对于来校参观的客人和学校管理者来说都至关重要，在很大程度上影响着校园的数字化建设和学校的影响力。因此，本文所研究的校园导航系统具有一定的使用价值和现实意义。开发语言：C+开发环境：win7 64位操作系统开发软件：Codeblocks校园导航查询系统的开发方法总结如下：(1) 数据收集，首先了解学校各个场所与场所或者是各个景点与景点之间的信息，
18、路径和距离，然后给景点编号，估计测量和记录景点间距离（我们用两个txt文件：walk.txt和car.txt）。(2)数据分析，对调查得到的数据进行分析，从外来人员或者参观者和走访者的角度出发，该如何设计才能满足用户需求。根据其要求实现的功能分析系统结构和界面将实现的基本功能。(3)设计与开发，设计系统界面并编辑实现其各个功能的代码。(4)调试阶段，在设计完成后调试系统运行的状况，修改完善系统,然后继续进行全方面测试。2.5.实验构思本次实验的主要目的在于熟悉图这种数据结构的表示和应用，学会运用图对实际问题进行建模和设计，以便在实际问题背景下灵活运用图和抽象数据类型的基本操作。（本部包括：描述
19、实验实现的基本思路，包括所用到的离散数学、工程数学、程序设计、算法等相关知识）具体要求如下：根据海院校区主要道路建筑景点示意图，测量出主要建筑之间的距离。以图为工具，建立模型，用户通过终端可询问从某一景点到另一景点的最短路径。1.基本思路：用无向网表示校区内的各建筑的平面图，图中顶点表示主要景点，存放建筑的编号、名称、简介、设施等信息，图中的边表示景点间的道路，存放路径长度等信息。将导游图看作一张带权无向图，顶点表示校园的各个建筑，边表示各景点之间的道路，边上的权值表示距离，为此图选择适当的数据结构。把各种路径都显示给用户，由用户自己选择浏览路线。首先用结构体数组存储景点信息，即图中顶点和边的
20、信息。景点数据信息由程序指定存储，然后采用弗洛伊德算法求出最短路径，即从某景点出发，顺着某一条边开始循环，求得到某个顶点的最短路径，将路径结果存储到路径矩阵中，求得一条通路。最后调用show函数将路径结果和景点信息打印出来。2. 算法思想：对于用户查询景点信息，通过结构体数组（也是指针）直接访问该图中的顶点，并将该顶点中存储的信息用one_show(jingdian jd,int no)显示出来。Floyd算法又称为插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法。其状态转移方程： mapi,j:=minmapi,k+mapk,j,mapi,j。mapi,j表示i到j的最短距离，K
21、是穷举i,j的断点，mapn,n初值应该为0，或者按照题目意思来做。如果这条路没有通的话，须特殊处理，比如没有mapi,k这条路。Floyd算法适用于APSP(All Pairs Shortest Paths，多源最短路径)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法，也要高于执行V次SPFA算法。优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。缺点：穷举法，时间复杂度比较高，不适合计算大量数据。这里，所研究校区景点间道路的数据比较小，用Floyd算法既可以算出任意两个节点之间
22、的最短距离，代码编写又简单，容易理解。对于景点导航，首先用邻接矩阵来存储，建立一个结构体数组将图的信息存储起来。再分别用setwalk(walk)和setcar(car)来设置两景点之间人行和开车的两种方式的距离矩阵walkmaxsizemaxsize和carmaxsizemaxsize。然后，两种方式的最短路径用利用Floyd算法的两个函数floyd(walk,gowalk)和floyd(car,gocar)分别算出，最短路径长度即二维数组gowalk和gocar对应的值。即根据起点和终点输出最短路径长度。最后调用path(walkmaxsize,carmaxsize,gowalkmaxsi
23、ze,gocarmaxsize)函数将路径结果打印出来。3概要设计3.1设计原理（C/C+语言简介)C语言是一种计算机程序设计语言。它既具有高级语言的特点，又具有汇编语言的特点。它由美国贝尔研究所的D.M.Ritchie于1972年推出。1978后，C语言已先后被移植到大、中、小及微型机上。它可以作为工作系统设计语言，编写系统应用程序，也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。它的应用范围广泛，具备很强的数据处理能力，不仅仅是在软件开发上，而且各类科研都需要用到C语言，适于编写系统软件，三维，二维图形和动画。具体应用比如单片机以及嵌入式系统开发。C+是在C语言得基础上的一种静
24、态数据类型检查的、支持多重编程范式的通用程序设计语言。它支持过程化程序设计、数据抽象、面向对象程序设计、制作图标等等泛型程序设计等多种程序设计风格。3.2方案设计与论证校园旅游模型是由各个景点和景点以及场所和场所之间的路径组成的，所以这完全可以用数据结构中的图来模拟。用图的结点代表景点或场所，用图的边代表景点或场所之间的路径。所以首先应创建图的存储结构。结点值代表景点信息，边的权值代表景点间的距离。结点值及边的权值采用图存储。本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所以给每个景点一个代码，用结构体类型实现。计算路径长度，最短路线弗洛伊德（Floyd）算法
25、实现。最后用switch选择语句选择执行浏览景点信息或查询最短路径和距离等操作。设置void check(int dmaxsize,long long howmaxsize)检查两景点最短路径矩阵。3.3系统模块设计（本部分包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系） 采用工程思想，可以将系统共分一下六个模块:数据结构定义模块、景点信息设置模块、距离矩阵建立模块、求最短路径模块、特殊寻找设施模块、修改信息模块和主菜单模块；下面是具体各功能简单的实际应用：1.数据结构定义模块：模块定义了导航图中各个节点的基本结构类型，主要采用邻接矩
26、阵（数组）的存储结构来真实反映各节点到其他所有节点的路径长度（权值大小）。struct jingdian int no; /存放景点编号 char name18;/存放景点名称 char introduction180;/存放景点介绍 int bank; /标记银行 int shop; /标记商店 int wc; /标记厕所 int score; /存放景点评分;2.景点信息设置模块：采用上述结构体类型对导航图中每个节点进行赋值。包括：景点编号，名称，简介,设施，评分。各个点到其可直达景点的间的真实路径长度（txt文件打开读入数组，建立距离矩阵）。walkmaxsizemaxsize、carm
27、axsizemaxsize3.求最短路径模块：本模块的基本思想是采用Floyd算法求最短路径。这模块是也本校区导航系统的核心模块，求任意两点间的最短路径的功能就是在最短路径算法模块的基础上进行调用，进而实现导航功能。4.特殊寻找设施模块：是建立在景点介绍功能的基础上的，它的优点就是根据用户的特殊时刻需求来更快地来获取需要的信息。5.修改信息模块：本模块是有限制的，需要密码进入操作，便于管理员修改和完善信息。以上程序的几个模块，构成了校园导航系统的基本组成部分，程序运行良好，达到了课程设计的基本要求。4整体设计4.1整体设计概述1、程序使用C+语言。2、建立桂电北海校区各景点信息，包括名称，简介
28、,设施，评分。 3、能够提供各景点信息查询功能。4、能够提供各景点之间导航功能。5、数据采用简单结构体数组存储。6、程序包括结构体定义、主函数、初始化录入数据、数据修改函数、导航函数、检查数据函数等部分。主界函数联系各个函数，利用char型变量来检验异常数据，利用简单的结构体数组的调用完成信息的录入与输出，利用弗洛伊德算法完成最短距离的计算，利用输入输出流完成邻接矩阵的创建，后面还增设了留言板。4.2函数详细设计1) 主函数main：调用和连接起各个函数来实现功能的分组或连接，用switch语句分别选择各项功能。While(1)保持循环继续int main() jingdian jdmaxsi
29、ze;/景点结构体数组存放14个景点的信息 setdata(jd); /初始化景点信息 int walkmaxsizemaxsize=0;setwalk(walk);/建立人行邻接矩阵 int carmaxsizemaxsize=0;setcar(car); /建立开车邻接矩阵 long long gowalkmaxsizemaxsize=0; /二维数组gowalkmaxsizemaxsize用来存储两景点间人行最短路径 long long gocarmaxsizemaxsize=0; /二维数组gocarmaxsizemaxsize用来存储两景点间开车最短路径 int password;/
30、修改权限密码变量 char ch; /字符ch，用于控制继续循环查询/弗洛伊德算法求任意两景点最短路程的矩阵 floyd(walk,gowalk); /人行最短路程的矩阵 floyd(car,gocar);/开车最短路程的矩阵 /check(walk,gowalk);/两景点最短路径矩阵输出，用于检查 int a,n;/景点编号变量 char choice; /服务项目选择变量 while(1) system(cls);/清屏 showface(); /屏幕显示函数(菜单) choice=check_c();/输入服务项目 switch(choice) case i:n=check_n();o
31、ne_show(jd,n);break;/调用one_show函数，输出景点信息 case d:path(walk,car,gowalk,gocar);break;/调用path函数来导航 case o:cout;n=check_n();one_show(jd,n); findfac(jd);break;/调用按设施查找景点函数,输出配备所查找设施的所有景点 case c:coutpassword; if(password=password0)n=check_n();change(n,jd);else cout密码错误！endl;system(pause);break;/密码正确才能对景点信息
32、进行修改，错误则重新选择查询 case e:return 0;/exit(0)安全退出系统 default :break; return 0;2) 主界面函数showface()：打印主界面，显示景点编号，显示功能选择项。 void showface() coutn-欢迎使用桂电北海校区东区校园景点导游系统-nn; cout 学校景点编号如下：nn ; cout 0.学院大门t1.综合实验楼t2.外宾招待所t3.第二教学楼t4.网球排球场endl; cout 5.老青工楼t6.一号篮球场t7.图书馆t8.田径场t9.学院食堂 endl; cout 10.女生宿舍楼t11.男生宿舍楼t12.二号
33、篮球场t13.游泳池nendl; cout 景点内可供特殊寻找设施的编号如下：nn ; cout 1.寻找厕所t2.寻找银行t3.寻找商店t4.寻找医务室nendl; cout-nn; cout i.景点信息查询请按i (introduction)n; cout d.景点导航(最短路径)请按d (distance)n; cout o.其他设施查询请按o (other)n; cout c.修改数据请按c (change)n; cout e.退出系统请按e,或直接右击右上角X关闭n; coutn-n; cout请选择服务项目：;3) 初始化录入数据setdata(jd);：将景点数据录入结构体中。
34、struct jingdian int no; /存放景点编号 char name18;/存放景点名称 char introduction180;/存放景点介绍 int bank; /标记银行 int shop; /标记商店 int wc; /标记厕所 int score; /存放景点评分;void setdata(jingdian jd) int i=0; jd0.no=0; char name018=学院大门; for(i=0;name0i!=0;i+)/name0i!=0作循环控制条件，节省时间，提高效率 jd0.namei=name0i;/ jd0.namei=name0i; char
35、 introduction0180=n学院正门，外人开车出入登记处nn; for(i=0;introduction0i!=0;i+)/name2i!=0作循环条件，避免不必要循环，增加效率 jd0.introductioni=introduction0i; jd0.introductioni=introduction0i; jd0.bank=0; jd0.shop=0; jd0.wc=0; jd0.score=4; jd1.no=1; char name118=综合实验楼; for(i=0;name1i!=0;i+) jd1.namei=name1i; jd1.namei=name1i; ch
36、ar introduction1180=n综合实验楼，计算机、电路等教学实验教室；n楼顶阁楼是大学生社团活动中心，设有乒乓球、台球室。nn; for(i=0;introduction1i!=0;i+) jd1.introductioni=introduction1i; jd1.introductioni=introduction1i; jd1.bank=0; jd1.shop=0; jd1.wc=1; jd1.score=4;./重复太多了，这里略，可见附录完整版4) 查询景点信息one_show(jd,n)：输入景点编号，输出景点介绍。void one_show(jingdian jd,in
37、t no)/显示景点数据函数 system(cls); coutjdno.name: njdno.introductionn景点评分为: jdno.scoreendl; cout温馨提示：n; if(jdno.wc) cout 此处有厕所n; if(jdno.bank) cout 此处有银行n; if(jdno.shop) cout 此处有商店n; char ch; coutendl; system(pause);5) 通过读入txt文件建立图的邻接矩阵函数setwalk(walk)，setcar(car),分别建立人行和开车距离的邻接矩阵。6) 求最短路径函数path(walk,car,go
38、walk,gocar)：通过输入起始和结束景点编号或名字来进行导航，输出的最短路径，两种方式的最短距离矩阵分别用floyed算法的函数floyd(walk,gowalk)和floyd(car,gocar)求出。 void floyd(int dmaxsize,long long howmaxsize)/弗洛伊德算法求任意两景点最短路径 /int d记录两景点间路径长度，寻找最小；int how记录两景点间最短路径矩阵 for(int n=0;nmaxsize;n+)/计数器n，让弗洛里德算法多次遍历，这个有一个缺点，大型数据不能使用 for(int i=0;imaxsize;i+)/i表示所求
39、j,k编号两景点间是否经过的景点编号 for(int j=0;jmaxsize;j+) for(int k=0;kdij+djk) dik=dij+djk; howik=j;/howiki到k的最短路径矩阵， /路径表示：所有经过的景点编号；0表示直达 7) 按设施查询景点函数findfac(jd);：输入要查询设施如则所，银行或商店等查询景点。其中功能选择和景点输入都有相对应的检查函数check:1.char check_c() char ch; cinch; while ( ch!=i&ch!=d&ch!=o&ch!=c&ch!=e) coutch; return ch;2.int check_n() char n; char n2; int sum=0; coutn; sum=n-0; cin.get(n2); if(n2=0) sum=sum*10+n2-0; while ( sum13 ) coutn; sum=n-0; cin.get(n2); if(n2=0) sum=sum*10+n2-0; return sum;3.char check_f() char n; cout
