数据结构课程设计桂林电子科技大学海洋信息工程学院导航系统.doc

桂林电子科技大学课程设计说明书 编号：201 数据结构与算法课程设计数据结构与算法课程设计 说明书说明书 桂电海院校园导游咨询与最短路径（桂电海院校园导游咨询与最短路径（+5） 学 院： 海洋信息工程学院 专 业： 计算机科学与技术 学生姓名： 黄兰丽 学 号： 1316040201 指导教师： 王晓莹 2015 年 6 月 29 日 桂林电子科技大学课程设计说明书 桂电海院校园导航系统桂电海院校园导航系统 学生姓名： 指导老师：王晓莹 摘 要 本文主要介绍了利用 windows7 系统和 c+开发语言编写校园导航系统的应用程序。 在现代条件下实现平台广。 校园导航问题是基于校园中的不同的景点，建立结构体数据结构模型，设计能够 让普通用户更便捷更具体详细地了解景点信息，最短路径，常用设施以及管理用户的 修改信息。为来往的客人提供校园景点和校园设施相关信息的查询，提供校园中任意 景点间的最短路径查询。管理员通过密码登录以后可以根据校园发展变化来修改景点 信息，既保证了安全也便于更新景点信息。 在本校园导航系统中，可以实现三大功能：一、景点的介绍；二、设施查询，人 行和开车人性化分开的精准度高的路线查询；三、管理员修改信息。同时，本系统的 功能选择、景点输入、设施输入等都拥有友好而强大的异常处理功能，具有实用性， 便利性和发展性。 关键字关键字：数据结构 校园导航 异常处理 安全权限 桂林电子科技大学课程设计说明书 campus navigation system of guet hai yuan student: teacher:wang xiaoying astacrt this article mainly 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 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 shortest 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, 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 powerful exception handling, practical, convenience and expansibility. key words: data structure the campus navigation exception handling security permissions 桂林电子科技大学课程设计说明书 目 录 引引 言言.1 设计背景.1 研究方法.1 实现目标.2 问题重述问题重述.2 1.1 桂电海院校园导游咨询与最短路径（+5） .2 2 需求分析需求分析.3 2.1 系统需求概述.3 2.2.功能需求.3 2.3 设计要求.3 2.3 界面需求.4 2.4 开发环境.4 2.5.实验构思 .5 3 概要设计概要设计.7 3.1 设计原理（c/c+语言简介).7 3.2 方案设计与论证 .7 3.3 系统模块设计.7 4 整体设计整体设计.9 4.1 整体设计概述.9 4.2 函数详细设计.9 4.3 各功能模块详细设计：.15 5 系统特色及关键技术系统特色及关键技术.20 5.1 关键技术.20 5.2 系统特色：.20 6 测试结果测试结果.21 6.1 运行程序测试.21 6.2 测试结果分析 .24 7 所遇到的问题和分析解决所遇到的问题和分析解决.25 8 使用说明使用说明.26 总结总结.26 致致 谢谢.28 附录附录.29 桂林电子科技大学课程设计说明书 1 引引 言言 设计背景设计背景 现在科技越来越发达，电脑上、手机上的软件越来越多，所以开发一些小程序也 越来越可变为实用了，越来越有必要。 无论什么导航仪最主要的部分都是电子地图，开发电子地图成为了导航的关键。 然而，根据调查得知电子地图制作困难且相当昂贵，给导航仪开发带来了许多不便。 自主绘制地图，编写与地图功能相关的程序，不管是从经济上还是研究上都具有非常 大的意义。同时与传统的地图相比，地理信息系统有着不可比拟的优势，它信息量大， 简洁直观，切换方便，可扩展性强。 面对广阔的校园环境,刚入学的新生或是初次到学校参观的人往往不清楚怎样才能 到达自己的目的地,需要一个校园自主导航器引导他们出行可是，到目前为止，桂林电 子科技大学海洋信息工程学院是没有这种校内导航系统的。桂电海院是桂林电子科技 大学一所新的二本院校，也是北海市唯一的一所二本院校，相信一定会引来许多老师， 学生，家长或者普通游客来参观。针对校园现代化的实现，也是对于来访我校的访客 和新生能够更方便的了解学校的景点，便于参观，减少访客的迷茫感，因此,在校园中 设置一些旅游景区中的自主导航器十分必要。我也觉得研究开发一个校园导航系统是 很有意义的，于是我们编写了这个校园导航系统，为刚入学的新生或是初次到学校参 观的人员提供一个校园自主导航器引导他们出行。 研究方法研究方法 对本系统的研究，我们是通过实地考察与测量，建立把实际问题转为数据结构中 图类的问题，这样就有了算法的模型，再采用了分模块解决实际问题的方法。 首先将校园景点的基本信息用结构体数组来存储起来，即能把景点相关信息，如 基本介绍，设有的设施和评分等连接起来，也便于输出；其次就是把各个景点作为图 的结点，将景点间的路径作为图的边，路径距离作为边的权值。这样一来，求两景点 间最短路径的问题就抽象成了求图中一结点到另一结点的问题。 桂林电子科技大学课程设计说明书 2 数据结构与算法，也是计算机代替人工的实现方法，是软件工程必不可少的基础。 对于本次校园导航系统，我有如下陈述：本系统是一个涉及桂电海院相关景点和场所 查询系统,是为了方便人们能够更快更准地获得学校各个景点和场所的详细信息。其设 计主要根据学校的各个景点和场所所设计的导航系统。我们是通过结构体的顺序存储 的方式设置基本的景点信息的，然后以图的邻接矩阵存储景点间的距离，并用弗洛里 德算法求的最短路径，同样是用邻接矩阵存储的。在需要的时候，只要按要求输出就 好。在修改模块部分，我们设定需要密码，增加了权限，保证系统内信息不被破坏。 实现目标实现目标 本课题命名为桂电海院校园导游咨询与最短路径，以实际问题为基础，参照其他 学校导航系统的建立起来的一个新的模型，旨在建立一个本校的导航系统。可以根据 不同用户的需求，不用实地参观，就可以得到各种信息。 基于上述背景与目标，开发一个校园导航项目，使用 windows7 搭配 codeblocks 来实现这个项目的功能，开发一个可以运行的小客户端，手机电脑都可以使用，给用 户提供友好的服务。 问题重述问题重述 1.1 桂电海院校园导游咨询与最短路径（桂电海院校园导游咨询与最短路径（+5） 1.1.问题描述问题描述 1) 从桂电海洋学院的平面图中选取有代表性景点（10-15 个），抽象成一个无向 带权图。以图中顶点表示景点，边上的权值表示两地之间距离。 2) 本程序的目的是为用户提供路径咨询。根据用户指定的始点和终点输出相应路 径，或者根据用户指定的景点输出景点的信息。 2.2.任务要求任务要求 1) 从桂电海洋学院的平面图中选取有代表性景点（10-15 个），抽象成一个无向 带权图。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以 边表示路径，存放路径长度等信息。 2) 为来访客人提供图中任意景点相关信息的查询。 桂林电子科技大学课程设计说明书 3 3) 为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最 短的简单路径。 4) 区分汽车线路与步行线路。 3.3.测试数据测试数据 桂电海院校园导游图（距离可估计）。 个人总结： 问题重述，明确研究对象，清晰任务要求，有助于需求分析，模型建立。 2 需求分析需求分析 2.1 系统需求概述系统需求概述 界面简洁、清楚、功能齐全，使用方便，交互界面良好，容易操作，让没用过这 个系统的人一看就知道如何操作。系统稳定，有一定的异常处理功能。 2.2.功能需求功能需求 1.在菜单中显示校园景点编号。 2.用户能够查询任意景点的景点信息。 3.能根据用户输入的起始以及终点景点编号查询最短路程以及指引路线。 4.能根据用户的特殊需求，如厕所，银行，商店来进行特殊查询； 5.能对内部数据进行修改，验证内部人员密码后即可； 2.3 设计要求设计要求 数据结构与算法课程设计基本要求： 1.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3.独立完成，提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的 桂林电子科技大学课程设计说明书 4 科学的工作方法和作风。 校园导航系统具体要求： 1. 设计学校的平面图，每两个场所间可以有不同的路，且路长也可能不同，找出从任 意场所到达另一场所的最短路径（路线及最短路程）。 2. 设置及显示，要能完成各景点信息记录以及查阅功能。 3. 景点问路查询，即求任意两个景点间的一条最短的简单路径以及任意 景点到其他 所有景点的最短路径查询。在邻接矩阵中 int_max 表示最大距离即两个景点之间是不 可到达的。用实际权值来表示两个景点之间是可达的，权值即是距离。 4. 特殊设施查询，景点结构体数组中包括特殊设施，便于用户查询。 5. 主界面，列出所有校内无重复排列的景点，提供使用者选择功能界面，按照提示进 行操作。 6.输入输出，根据菜单提示键入相应的键已完成相应操作。程序对用户键入信息都会 在后台进行判断与异常处理，并根据用户键入的正确信息，调用相应函数，完成查找 或其他操作，不只是查找结果的屏幕显示，其实每一次输入都是有相应的内容输出到， 界面友好，详细又明白，可读性强。 2.3 界面需求界面需求 系统界面要具有广泛的实用性，又要便于移植。界面友好，操作简便。根据软件 的使用环境、用户的要求，系统界面应该简单、友好、易于使用、方便查看、简洁明 快。而且系统是在 windows 环境下的应用软件，软件产品的界面应该与操作系统的界 面相切合，产品的主界面可供选择功能齐全，分类明确，编号清楚，让用户一眼看去 就能明白大致的功能。 2.4 开发环境开发环境 随着科学技术的不断发展，计算机科学日渐成熟，其强大的功能已为人们所深刻 认识，它己进入人类社会的各个领域并发挥着越来越重要的作用。采用计算机进行校 园导航已成为衡量校园数字化的重要标志。校园导航效率的好坏对于来校参观的客人 和学校管理者来说都至关重要，在很大程度上影响着校园的数字化建设和学校的影响 力。因此，本文所研究的校园导航系统具有一定的使用价值和现实意义。 开发语言：c+ 开发环境：win7 64 位操作系统 桂林电子科技大学课程设计说明书 5 开发软件：codeblocks 校园导航查询系统的开发方法总结如下： (1)数据收集，首先了解学校各个场所与场所或者是各个景点与景点之间的信息，路径 和距离，然后给景点编号，估计测量和记录景点间距离（我们用两个 txt 文件： walk.txt 和 car.txt）。 (2)数据分析，对调查得到的数据进行分析，从外来人员或者参观者和走访者的角度出 发，该如何设计才能满足用户需求。根据其要求实现的功能分析系统结构和界面将实 现的基本功能。 (3)设计与开发，设计系统界面并编辑实现其各个功能的代码。 (4)调试阶段，在设计完成后调试系统运行的状况，修改完善系统,然后继续进行全方 面测试。 2.5.实验构思实验构思 本次实验的主要目的在于熟悉图这种数据结构的表示和应用，学会运用图对实际 问题进行建模和设计，以便在实际问题背景下灵活运用图和抽象数据类型的基本操作。 （本部包括：描述实验实现的基本思路，包括所用到的离散数学、工程数学、程序设 计、算法等相关知识） 具体要求如下： 根据海院校区主要道路建筑景点示意图，测量出主要建筑之间的距离。以图为工具， 建立模型，用户通过终端可询问从某一景点到另一景点的最短路径。 1.基本思路： 用无向网表示校区内的各建筑的平面图，图中顶点表示主要景点，存放建筑的编 号、名称、简介、设施等信息，图中的边表示景点间的道路，存放路径长度等信息。 将导游图看作一张带权无向图，顶点表示校园的各个建筑，边表示各景点之间的道路， 边上的权值表示距离，为此图选择适当的数据结构。把各种路径都显示给用户，由用 户自己选择浏览路线。首先用结构体数组存储景点信息，即图中顶点和边的信息。景 点数据信息由程序指定存储，然后采用弗洛伊德算法求出最短路径，即从某景点出发， 顺着某一条边开始循环，求得到某个顶点的最短路径，将路径结果存储到路径矩阵中， 求得一条通路。最后调用 show 函数将路径结果和景点信息打印出来。 2.算法思想： 对于用户查询景点信息，通过结构体数组（也是指针）直接访问该图中的顶点， 并将该顶点中存储的信息用 one_show(jingdian jd,int no)显示出来。 floyd 算法又称为插点法，是一种用于寻找给定的加权图中多源点之间最短路径的算法。其状态 桂林电子科技大学课程设计说明书 6 转移方程： mapi,j:=minmapi,k+mapk,j,mapi,j。mapi,j表示 i 到 j 的 最短距离，k 是穷举 i,j 的断点，mapn,n初值应该为 0，或者按照题目意思来做。如 果这条路没有通的话，须特殊处理，比如没有 mapi,k这条路。 floyd 算法适用于 apsp(all pairs shortest paths，多源最短路径)，是一种动 态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构 紧凑，对于稠密图，效率要高于执行|v|次 dijkstra 算法，也要高于执行 v 次 spfa 算 法。 优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。 缺点：穷举法，时间复杂度比较高，不适合计算大量数据。 这里，所研究校区景点间道路的数据比较小，用 floyd 算法既可以算出任意两个节点 之间的最短距离，代码编写又简单，容易理解。 对于景点导航，首先用邻接矩阵来存储，建立一个结构体数组将图的信息存储起 来。再分别用 setwalk(walk)和 setcar(car)来设置两景点之间人行和开车的两种方式 的距离矩阵 walkmaxsizemaxsize和 carmaxsizemaxsize。然后，两种方式的 最短路径用利用 floyd 算法的两个函数 floyd(walk,gowalk)和 floyd(car,gocar)分别 算出，最短路径长度即二维数组 gowalk 和 gocar 对应的值。即根据起点和终点输出最 短路径长度。最后调用 path(walkmaxsize,carmaxsize, gowalkmaxsize,gocarmaxsize)函数将路径结果打印出来。 桂林电子科技大学课程设计说明书 7 3 概要设计概要设计 3.1 设计原理（设计原理（c/c+语言简介语言简介) c 语言是一种计算机程序设计语言。它既具有高级语言的特点，又具有汇编语言的 特点。它由美国贝尔研究所的 d.m.ritchie 于 1972 年推出。1978 后，c 语言已先后被 移植到大、中、小及微型机上。它可以作为工作系统设计语言，编写系统应用程序， 也可以作为应用程序设计语言，编写不依赖计算机硬件的应用程序。它的应用范围广 泛，具备很强的数据处理能力，不仅仅是在软件开发上，而且各类科研都需要用到 c 语言，适于编写系统软件，三维，二维图形和动画。具体应用比如单片机以及嵌入式 系统开发。 c+是在 c 语言得基础上的一种静态数据类型检查的、支持多重编程范式的通用程 序设计语言。它支持过程化程序设计、数据抽象、面向对象程序设计、制作图标等等 泛型程序设计等多种程序设计风格。 3.2 方案设计与论证方案设计与论证 校园旅游模型是由各个景点和景点以及场所和场所之间的路径组成的，所以这完 全可以用数据结构中的图来模拟。用图的结点代表景点或场所，用图的边代表景点或 场所之间的路径。所以首先应创建图的存储结构。结点值代表景点信息，边的权值代 表景点间的距离。结点值及边的权值采用图存储。本系统需要查询景点信息和求一个 景点到另一个景点的最短路径长度及路线，为方便操作，所以给每个景点一个代码， 用结构体类型实现。计算路径长度，最短路线弗洛伊德（floyd）算法实现。最后用 switch 选择语句选择执行浏览景点信息或查询最短路径和距离等操作。 设置 void check(int dmaxsize,long long howmaxsize)检查两景点最短 路径矩阵。 3.3 系统模块设计系统模块设计 （本部分包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说 明，主程序模块与各子程序模块间的调用关系） 桂林电子科技大学课程设计说明书 8 采用工程思想，可以将系统共分一下六个模块:数据结构定义模块、景点信息设置 模块、距离矩阵建立模块、求最短路径模块、特殊寻找设施模块、修改信息模块和主 菜单模块； 下面是具体各功能简单的实际应用： 1.数据结构定义模块：模块定义了导航图中各个节点的基本结构类型，主要采用邻 接矩阵（数组）的存储结构来真实反映各节点到其他所有节点的路径长度（权值大小） 。 struct jingdian int no; /存放景点编号 char name18;/存放景点名称 char introduction180;/存放景点介绍 int bank; /标记银行 int shop; /标记商店 int wc; /标记厕所 int score; /存放景点评分 ; 2.景点信息设置模块：采用上述结构体类型对导航图中每个节点进行赋值。包括： 景点编号，名称，简介,设施，评分。各个点到其可直达景点的间的真实路径长度 （txt 文件打开读入数组，建立距离矩阵）。 walkmaxsizemaxsize、carmaxsizemaxsize 3.求最短路径模块：本模块的基本思想是采用 floyd 算法求最短路径。这模块是 也本校区导航系统的核心模块，求任意两点间的最短路径的功能就是在最短路径算法 模块的基础上进行调用，进而实现导航功能。 4.特殊寻找设施模块：是建立在景点介绍功能的基础上的，它的优点就是根据用 户的特殊时刻需求来更快地来获取需要的信息。 5.修改信息模块：本模块是有限制的，需要密码进入操作，便于管理员修改和完 善信息。 以上程序的几个模块，构成了校园导航系统的基本组成部分，程序运行良好，达到 了课程设计的基本要求。 桂林电子科技大学课程设计说明书 9 4 整体设计整体设计 4.1 整体设计概述整体设计概述 1、程序使用 c+语言。 2、建立桂电北海校区各景点信息，包括名称，简介,设施，评分。 3、能够提供各景点信息查询功能。 4、能够提供各景点之间导航功能。 5、数据采用简单结构体数组存储。 6、程序包括结构体定义、主函数、初始化录入数据、数据修改函数、导航函数、 检查数据函数等部分。 主界函数联系各个函数，利用 char 型变量来检验异常数据，利用简单的结构体数 组的调用完成信息的录入与输出，利用弗洛伊德算法完成最短距离的计算，利用输入 输出流完成邻接矩阵的创建，后面还增设了留言板。 4.2 函数详细设计函数详细设计 1) 主函数 main：调用和连接起各个函数来实现功能的分组或连接，用 switch 语句分 别选择各项功能。while(1)保持循环继续 int main() jingdian jdmaxsize;/景点结构体数组存放 14 个景点的信息 setdata(jd); /初始化景点信息 int walkmaxsizemaxsize=0;setwalk(walk);/建立人行邻接矩阵 int carmaxsizemaxsize=0;setcar(car); /建立开车邻接矩阵 long long gowalkmaxsizemaxsize=0; /二维数组 gowalkmaxsize maxsize用来存储两景点间人行最短路径 long long gocarmaxsizemaxsize=0; /二维数组 gocarmaxsize maxsize用来存储两景点间开车最短路径 int password;/修改权限密码变量 桂林电子科技大学课程设计说明书 10 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();one_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;/密码正确才能对景点信息进行修改，错误则重新选择查询 case e:return 0;/exit(0)安全退出系统 default :break; return 0; 2) 主界面函数 showface()：打印主界面，显示景点编号，显示功能选择项。 void showface() 桂林电子科技大学课程设计说明书 11 coutn-欢迎使用桂电北海校区东区校园景点导游系 统-nn; cout 学校景点编号如下：nn ; cout 0.学院大门t1.综合实验楼t2.外宾招待所t3.第二教学楼t4.网 球排球场endl; cout 5.老青工楼t6.一号篮球场t7.图书馆t8.田径场t9.学院食堂 endl; cout 10.女生宿舍楼t11.男生宿舍楼t12.二号篮球场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);：将景点数据录入结构体中。 struct jingdian int no; /存放景点编号 char name18;/存放景点名称 char introduction180;/存放景点介绍 int bank; /标记银行 int shop; /标记商店 int wc; /标记厕所 桂林电子科技大学课程设计说明书 12 int score; /存放景点评分 ; void setdata(jingdian jd) int i=0; jd0.no=0; char name018=学院大门; for(i=0;name0i!=0;i+)/name0i!=0作循环控制条件，节省时间，提高效率 i=name0i;/ i=name0i; char introduction0180=n 学院正门，外人开车出入登记处nn; for(i=0;introduction0i!=0;i+)/name2i!=0作循环条件，避免不必要循环，增加效率 roductioni=introduction0i; roductioni=introduction0i; jd0.bank=0; jd0.shop=0; jd0.wc=0; jd0.score=4; jd1.no=1; char name118=综合实验楼; for(i=0;name1i!=0;i+) i=name1i; i=name1i; char introduction1180=n 综合实验楼，计算机、电路等教学实验教室；n 楼顶阁楼是大 学生社团活动中心，设有乒乓球、台球室。nn; for(i=0;introduction1i!=0;i+) roductioni=introduction1i; roductioni=introduction1i; jd1.bank=0; jd1.shop=0; jd1.wc=1; jd1.score=4; . 桂林电子科技大学课程设计说明书 13 /重复太多了，这里略，可见附录完整版 4) 查询景点信息 one_show(jd,n)：输入景点编号，输出景点介绍。 void one_show(jingdian jd,int no)/显示景点数据函数 system(cls); : roductionn 景点评分为: 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,gowalk,gocar)：通过输入起始和结束景点编号或 名字来进行导航，输出的最短路