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.总结

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

8.参考文献

[1] 张磊编著《C语言程序设计教程第2版》 中国铁道出版社
[2] 薛小龙编著《开发日记:深入体验C语言项目开发》清华大学出版社
[3] 刘字君张月琴叶瑶王庆生编著《C+理序设计案例分析》 清华大学出版社