1.问题概述

综合运用所学的数据结构知识解决一个关于学校导航系统的问题，侧重对图的相关内容特别是求最短路径的应用，使得能进一步熟悉掌握数据结构的基础知识，进一步提升自己的解决问题和编程调试能力，为后续专业课程的学习打下基础。

2.系统需求分析

设计学校的平面图，至少包括30个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从某个场所到达另一场所的最佳路径。
求最短路径用Floryd算法实现。

3.系统概要设计

3.1系统主要功能

系统的主要功能是实现两个建筑之间的导航以及信息查询
主要包括:

(1)查询起点与终点

(2)计算两点之间的距离

(3)求两点之间的最短路径

(4)添加一个景点

3.2系统的总体结构

(1)将校园平面图绘制为无向图并标各点和权值

(2)结构图设计

图3.2.1校园导航系统计结构图

(3)图的制作

图3.2.2图的制作

(4)最短路径计算

图3.2.3最短路径计算

(5)图的制作

①载入顶点数、边数、权值
②建立顶点表和边表，构建邻接表

(6)最短路径计算

①利用Floryd算法计算各个顶点之间最短路径
②输出最短路径

(7)添加景点

对类中对象进行修改即可

3.3数据结构的设计

校园导航数据结构类型如下:

4.系统详细设计

①根据系统总体结构对问题进行的模块划分，对总的问题可划分为:校园地图的制作、校园地图的展示、计算两地点最短路径
②在主函数中创建了Map类型guide变量，为map变量申请一个邻接表空间
③调用InMap(map)函数初始化地图，调用CreateMap(map)函数创建地图
④调用ShortWay(map)函数计算两点之间的最短路径，调用ShowShortWay(begin, end)函数输出两点之间的最短路径
⑤调用Add(map)函数进行添加景点

4.1校园地图的制作

(InMap(MapBox map)、CreateMap(MapBox map))

(1)InMap(MapBox *map)

①用来初始化地图，该函数实现过程中首先将32个顶点数赋给map->topnum，59条边赋给map->edgenum。将每个点之间的权值赋给distance数据储存

②代码实现

(2)CreateMap(MapBox *map)

①用来创建地图，该函数实现过程中首先定义一个边结点指针e。然后先用for来读取顶点信息，利用了strvpy函数，将mapname[i]中储存顶点名称传给map->Box[i].data，以此来读取顶点信息，并且将每个顶点对应的边头指针初始化，以达到将边表制空的目的。
再利用for循环，采用头插法创建边表。判断条件，当无向图两个点之间存在路径的时候，将两点之间的距离赋给temp变量。
为变量e申请新的空间来存放对应的下标、后继的地址、权值。将j赋给e->script作为入度下标，将两点的权值temp赋给e->weight。再利用e->next = map->Box[i].edgefirst和map->Box[i].edgefirst = e将边结点的头指针与后继相连接
为变量e申请新的空间来存放对应的下标、后继的地址、权值。将i赋给e->script作为出度下标，将两点的权值temp赋给e->weight。再利用e->next = map->Box[j].edgefirst和map->Box[j].edgefirst = e将边结点的头指针与后继相连接

②代码实现

4.2校园地图的展示

(1)用来显示校园平面图

该函数实现过程中首先将制作好的校园平面图命名为SchoolMap并存放在Project1中等待调用。在主函数中使用system函数，执行system(“mspaint SchoolMap.png”)来使用Win10自带画板打开SchoolMap，使校园平面图得到调出，让用户直观了解学校景点信息，以及便于选择需要查询的景点信息和最短路径

(2)操作实现

4.3计算两地点最短路径

(ShortWay(MapBox *map)、ShowShortWay(int begin, int end))

(1)ShortWay(MapBox *map)

①利用Floryd算法计算各个顶点之间最短路径，该函数实现过程中首先用两层for循环初始化，用if判断，若两点之间不存在路径并且不是相同的点，则将权值赋为10000,然后将每个结点对应的最短路径和下标信息分别初始化为distance[i][j]和下标j，以此来引入一个矩阵法S
利用三层循环判断最短路径，对引入的矩阵S进行k次更新，第一个顶点为中介，若shortdistance[i][j] > shortdistance[i][0] + shortdistance[0][j]，将shortdistance[i][j]更新为shortdistance[i][0] + shortdistance[0][j]，同理，第k次更新时，如果shortdistance[i][j] > shortdistance[i][k] + shortdistance[k][j]，则将shortdistance[i][j]更新为shortdistance[i][k] + shortdistance[k][j]。更新k次之后，操作即可完成。此时shortdistance[i][j]之中储存的即为每个顶点到其他顶点之间的最短路径距离，而shortpath中储存最短路径对应的信息。
图解如下:

②代码实现

(2)ShowShortWay(int begin, int end)

①用来输出路径长度和具体路径，该函数实现过程中首先定义一个temp变量。
输出地点名字、两点之间的最短距离，然后将两点间最短路径的下标信息temp = shortpath[begin][end]赋给temp变量。
之后利用while输出两点之间的最短路径，判断条件为temp不等于终点数值，若不相等，输出mapname[temp]，令temp赋为shortpath[temp][end]，如此循环，输出两点之间最短路径的具体路径。

②代码实现

4.4景点的添加

mapname数组添加元素进行点的添加，distance数组添加元素进行边的添加

5.系统的测试及调试

系统的测试及调试是为了发现程序中错误而执行程序的过程。

5.1运行过程

(1)进入主界面，进入选择界面

(2)显示地图

(3)添加一个景点

(4)查询两点之间最短路径

5.2系统调试过程中遇到的问题

(1)每次只能进行一次查询，并不能进行多次查询
错误原因:没有对代码进行完善
解决方案:添加一个while循环，使得用户可以进行多次查询

(2)校园平面图输出复杂，容易出现地图混乱的情况
错误原因:输出一幅图的处理不当
解决方案:采用system函数直接将已经绘制完成的校园平面图进行调用

6.用户手册

(1)本系统执行文件为Project1.sln
(2)进入系统界面后，根据提示，在校园平面图中查找对应的地点，输入两点信息
(3)两点输入为整型

7.总结

通过对校园导航系统的设计，我对数据结构又有了进一步的了解与掌握，尤其是对其中的一些地方又有了深刻的理解，使得对知识有了进一步的加深。使求最短路径的算法有了更深一个层次的掌握，更进一步的把握，希望将来可以用来解决更加切合实际的问题，从而达到学以致用的目的。还明白了在做一个系统之前还应该做好全面的安排，对一个系统的整个流程及功能实现有一个很好的统筹。另在遇到困难不能解决时，应查资料或问其它懂的同学，参考一下意见，再结合自己的想法，最后实现自己想实现的功能。在本次设计中我发现细节有时候很重要，又是一个很小的问题都可能导致失败，所以细心非常重要。