校园导游系统
1. 要求
大二下学期修了数据结构这门课，课设的要求是做一个校园导航系统。详细的要求如下
问题描述：
当我们参观校园时，会遇到如下问题：从当前所处位置去校园另外一个位置，要走什么样的路线距离最短？本课程设计任务要求，在给出校园各主要建筑的名称信息及有路线连通的建筑之间的距离的基础上，利用校园导游系统计算出给定起点到终点之间距离最近的行进路线。
任务要求：
（1）从地图文件中读取校园主要建筑信息及建筑之间的距离信息。
（2）计算出给定的起点到终点之间距离最近的行进路线。
（3）输出该路线及其总距离。
2. 分析
2.1 数据提取
第一个问题，如何看地图把信息提取出来，根据目前所掌握的知识来看并没有很智能、自动化的方法，只有人手工地把地图重要信息进行提取并录入。这些信息包括各个地点与各地点之间的距离。接下来就以我的学校地图为例。
为了演示的方便，便于后期算法正确与否的验证，提取中其中15个重要的点
同样为了演示、检验的方便，目测（编造）点与点之间的距离以及关系，来抽象成一张图：
而数据结构与算法这门课可以帮助解决的问题是怎么来存储这些数据。这个问题比较好回答，地图抽象出来就是图结构，而图的信息的常常用邻接矩阵来存储。
2.2 路径搜索
第二个问题，如何得到最优路径，以我的水平，或者说我接触过、学过的方法来说，可以选择的有两种算法，Dijkstra算法和Floyd算法。
3 设计
3.1 功能设计
首先，要先确定这个系统能实现什么样的功能。
3.1.1 菜单
第一肯定是要有一个菜单，当然，这是一个课设就不搞什么UI了，就是最基础的输入选项选择式菜单就可以了。
3.1.2 点位选择
第二，要找出两点最短路径，那肯定需要能够进行起点，终点的选择
3.1.3 地图数据来源选择
第三，我希望我做出来的东西不只是一个只是用来演示的东西，所以地图的数据肯定不能写死，希望能够实现只要能把地图数据抽取出来抽象成图，无论多大多小，都可以用我这个工具来找最短路径。因此，这就需要这个系统可以进行地图数据来源的选择。可以是默认的，也可以是自己手动输入的图数据。并且地图起点、中断选择界面的内容可以根据我们的数据来源进行对应的改变。
如果想要自定义输入地图数据，那么肯定需要有一个固定的输入格式，这样才能通过程序来把输入的数据提取出来，所以我们要规定一个格式。我的规定是，需要把每个点之间的关系都告诉程序，因此就需要很多组的两个端点与端点距离。因此我规定
每组三个数据,组内数据以空格分开，组间以分号分开。例如节点1序号 节点2序号 权值;节点3序号 节点4序号 权值;...
这个自定义的问题解决的，但是随后又想到，如果这个图是一个很大的图，我们自己手动输入会很麻烦，但是这是必须的。可是最要救命的是，如果下一次还想接着用，那么就要再输入一大堆，非常的麻烦，这是可以避免的。因此可以设计一个配置文件的方法方式，通过直接读取配置文件的内容来直接配置好地图数据。这样的话我们也需要再对配置文件的内容格式进行一个规范，我很简单地使用了这样的标准
地图数据在前 地图节点名称在后，写在同一行，之间用星号(*)隔开,最终以感叹号(!)结尾 地图数据：每组三个数据,组内数据以空格分开，组间以分号分开 例如：节点1序号 节点2序号 权值;节点3序号 节点4序号 权值;... 节点名称：顺序填写逗号分割. 例如：北门，东门，南门 例如：1 2 30; 2 3 50;*北门,东门,西门! 注意：为了避免中文乱码的问题，配置文件的编码格式需要是ANSI
3.1.4 算法选择
第四，能够使用不同的算法来处理。现在我还是个小菜鸡，只会两种算法Dijkstra算法和Floyd算法，而且这两个算法最后的结果看不出来差别。
3.2 代码结构设计
我对于程序的代码结构没什么研究，并且没有写出过结构优美的代码，那是我很渴望的。我希望自己写出来的程序是很清晰明了的，代码之间的关系、结构都很清晰，我也在慢慢地摸索。而我所知道或者所秉承的观念是很朴素的：1.不同功能的代码块要尽量解耦 2. 变量尽可能地用面向对象的思维来进行管理，在C语言里具体的体现就是尽可能用结构体将变量进行整合。
因为在RM战队写过屎山代码，所以我脑子里有一个很浅显或者说是粗俗的观点：各个部分要有一个Controller结构体来进行管理。因此怀着这样的想法，我把代码在结构上整体分成了三部分：
- 算法模块
- 系统管理模块
- 界面展示模块
然后整个系统围绕着三个控制器(结构体)展开：
- 系统控制器 SystemController
- 算法控制器 DijkstraController、FloydController
- 图信息控制器 MGraph
在控制器中SystemController掌控着整个系统的所有信息，如：地图数据、配置文件数据、算法控制器、选项结果等等。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-GWOBNuq8-1671969502895)(https://www.houenup.com/wp-content/uploads/2022/12/数据结构课设程序控制器.png)]
4 具体实现
4.1 程序流程
整个程序的入口是main函数，在main函数中调用System_Start()进入系统，System_Start的作用就是将系统中核心的控制器(控制结构体)之间建立联系并初始化相关数据，然后进入界面的控制。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UARpp9Z8-1671969502895)(https://www.houenup.com/wp-content/uploads/2022/12/数据结构课设程序流程图1.png)]
4.2 算法实现
4.2.1 Dijkstra算法：
Dijkstra算法的核心是对于三个列表的更新迭代，三个列表分别为，前驱节点列表、顶点最短路径列表、顶点是否确认列表。
具体的算法实现步骤为：
- 初始化：从出发点开始，将出发点确定为第一个已经确定最短路径的顶点，最短路径为0，然后更新与出发点有路径的顶点的最短路径和对应顶点的前驱顶点。
- 进行循环更新：从未确定最短路径的顶点中选取最短路径最小的顶点为新确定的顶点，然后更新与新确认顶点有路径的顶点的最短路径和前驱顶点，如果新路径更长就不更新，更短就更新。
算法控制器
/** Dijkstra算法控制器 **/
typedef struct
{
int forerunner_list[MAX_VERTICES]; /** 前驱顶点列表 **/
int confirmed_flag_list[MAX_VERTICES]; /** 该顶点是否确定了最短路径 **/
int distance_list[MAX_VERTICES]; /** 最短路径距离 **/
int start_point; /** 起点 **/
int end_point; /** 终点 **/
int latest_confirmed_node; /** 最新被确认的节点 **/
int route[MAX_VERTICES]; /** 最终算出来的最优路径 **/
int sum_distance; /** 路径总距离 **/
MGraph * mgraph; /** 存储了图数据的指针 **/
}DijkstraControler;
初始化函数
/**
* @brief 算法初始化
* @param controler:算法控制器
* @param system_data: 系统控制器
* */
void Dijkstra_Init(DijkstraControler* controler,SystemControler* system_data)
{
/**
* 初始化：1.出发点是第一的已经确定最短路径的顶点
* 2.更新与出发点有路径的顶点的最短路径和前驱顶点
* */
int distance_temp = 0;
/* 获取需要使用的信息 */
controler->mgraph = system_data->graph_data;
controler->start_point = system_data->start_point;
controler->end_point = system_data->end_point;
for (int i = 0; i < MAX_VERTICES; ++i) {
controler->distance_list[i] = 0;
controler->confirmed_flag_list[i] = 0;
controler->forerunner_list[i] = 0;
}
int node_num = controler->mgraph->numNodes;
/*顶点最短路径初始化为无穷*/
for (int i = 0; i < node_num; ++i) {
controler->distance_list[i+1] = GIGANTIC; //0弃除不用 从1开始
}
/* 出发点是第一的已经确定最短路径的顶点,自己到自己的距离是0 */
controler->latest_confirmed_node = controler->start_point;
controler->distance_list[controler->start_point] = 0;
controler->confirmed_flag_list[controler->start_point] = 1; //起始点已经确定
controler->forerunner_list[controler->start_point] = controler->start_point;
/* 更新与出发点有路径的顶点的最短路径和前驱顶点 */
Update_Distance_Predecessor(controler,controler->start_point);
}
更新确认节点函数
/**
* @brief 更新确认节点节点
* */
void Update_Confirmed_Node(DijkstraControler* controler)
{
int min_distance_index;
for (int i = 0; i < controler->mgraph->numNodes; ++i) //找最短路径最小的顶点
{
if (controler->confirmed_flag_list[i+1] != 1)
{
min_distance_index = Find_Min(controler->distance_list[i+1],i+1);
controler->latest_confirmed_node = min_distance_index; //更新最新被确认的顶点
}
}
min_distance = GIGANTIC;
controler->confirmed_flag_list[controler->latest_confirmed_node] = 1;
}
更新最短路径与前驱节点函数
/**
* @brief 更新与确认顶点有路径的顶点的最短路径
* @param controler：控制器
* @param comfirmed_point: 需要更新的与其之间有路径的点
* */
void Update_Distance_Predecessor(DijkstraControler* controler,int comfirmed_point)
{
int node_num = controler->mgraph->numNodes;
int distance_temp = 0;
for (int i = 0; i < node_num; ++i)
{
distance_temp = controler->mgraph->arc[comfirmed_point][i+1];
if ( distance_temp != 0) //找到有路径的顶点的路径长度
{
//如果与confirmed_point有关的路径的最短距离比它原来的最短距离更小 就更新它
if (distance_temp + controler->distance_list[comfirmed_point] < controler->distance_list[i+1] || controler->distance_list[i+1]==GIGANTIC)
{
controler->distance_list[i+1] = distance_temp + controler->distance_list[comfirmed_point]; //更新最短距离
Update_predecessor_node(controler,comfirmed_point,i+1);//更新前驱顶点
}
}
}
}
算法循环函数
/**
* @brief 算法循环
* @param controler:算法控制器
* */
void Dijkstra_Loop(DijkstraControler* controler)
{
/**
* 循环：1.从未确定最短路径的顶点中选取最短路径最小的顶点为新确定最短路径的顶点；
* 2.更新与新确认顶点有路径的顶点的最短路径和前驱顶点。(如果新路径更短就更新，更长则不更新)
*
* 结束条件：所有的点都被确定过最短路径了即寻找完毕
* */
int min_distance = 0;
int new_point = 0;
while (!controler->confirmed_flag_list[controler->end_point])
{
/*从未确定最短路径的顶点中选取最短路径最小的顶点为新确定最短路径的顶点*/
Update_Confirmed_Node(controler);
/* 更新与新确认顶点有路径的顶点的最短路径和前驱顶点 */
Update_Distance_Predecessor(controler,controler->latest_confirmed_node);
}
}
4.2.2 Floyd算法
Floyd算法的核心在于对两张表的更新迭代，分别为两点距离表和两点间中继节点表。
具体的算法实现步骤为：
- 初始化两张表，将中继节点表初始化为全-1，将两点距离表中有直接路径的点值初始化为其距离，无直接路径的初始化为-1
- 进行更新循环，不断地加入中继节点，遍历整张距离表，如果直接距离大于中继之后的间接距离，则更新两点之间距离，并将对应的中继节点表中的位置更新为当下的中继节点。
Floyd算法控制器
/** Floyd算法控制器 **/
typedef struct
{
int shortest_distance_table[MAX_VERTICES][MAX_VERTICES]; /** 两点之间最短距离表 (0,0)弃用 **/
int relay_node_table[MAX_VERTICES][MAX_VERTICES]; /** 两点之间中继节点表 (0,0)弃用 **/
int start_point; /** 起点 **/
int end_point; /** 终点 **/
int route[MAX_VERTICES]; /** 最终算出来的最优路径 **/
int route_num; /** 路线途径点个数 **/
int sum_distance; /** 路径总距离 **/
MGraph * mgraph; /** 存储了图数据的指针 **/
}FloydControler;
初始化函数
/**
* @brief 算法初始化函数
* */
void Floyd_Init(FloydControler* controler, SystemControler* system_data)
{
controler->mgraph = system_data->graph_data;
controler->start_point = system_data->start_point;
controler->end_point = system_data->end_point;
controler->route[0] = controler->start_point;
controler->route_num = 1;
/* 初始化两张表 */
for (int i = 0; i < MAX_VERTICES-1; ++i) {
for (int j = 0; j < MAX_VERTICES-1; ++j) {
controler->relay_node_table[i+1][j+1] = GIGANTIC;
if (controler->mgraph->arc[i+1][j+1] == 0)
{
if (i == j)
{
controler->shortest_distance_table[i+1][j+1] = 0;
} else
{
controler->shortest_distance_table[i+1][j+1] = GIGANTIC;
}
}
else
{
controler->shortest_distance_table[i+1][j+1] = controler->mgraph->arc[i+1][j+1];
}
}
}
}
更新循环函数
/**
* @brief 更新循环
* */
void Floyd_Upgrade_Loop(FloydControler* controler)
{
int node_num = controler->mgraph->numNodes;
//最短距离表更新
for (int v = 1; v < node_num; ++v) {
for (int i = 1; i < node_num+1; ++i) {
for (int j = 1; j < node_num+1; ++j) {
//中继节点到某一点不通就不更新
if (controler->shortest_distance_table[i][v]==GIGANTIC || controler->shortest_distance_table[v][j] == GIGANTIC)
{
;
}
else
{ //中继到两边都通，总长更小就更新
if ((controler->shortest_distance_table[i][j] == GIGANTIC) || (controler->shortest_distance_table[i][j]>controler->shortest_distance_table[i][v]+controler->shortest_distance_table[v][j]))
{
controler->shortest_distance_table[i][j] = controler->shortest_distance_table[i][v]+controler->shortest_distance_table[v][j];
controler->relay_node_table[i][j] = v; //更新中继节点表
}
}
}
}
}
}
路径寻找函数
/**
* @brief 寻找最短路径
* */
void Floyd_Find_Path(FloydControler* controler,int start,int end)
{
if (controler->relay_node_table[start][end] == GIGANTIC)
{
controler->route[controler->route_num++] = end;
controler->sum_distance+=controler->shortest_distance_table[start][end];
} else
{
int mid = controler->relay_node_table[start][end];
Floyd_Find_Path(controler,start,mid);
Floyd_Find_Path(controler,mid,end);
}
}
4.3 管理实现
总体来说整个系统管理起来的逻辑是比较简单的，就是通过用户在对应界面选择的选项来调用不同的函数实现界面的跳转、数据的选择与输出等。
其中相对花了一些时间的地方在输入数据的提取、配置文件的数据提取上。
主菜单管理
/**
* @brief 主菜单管理
* */
void MainMenu_Control(SystemControler* system_controler)
{
uint8_t temp = 0;
static int time_flag = 0; //用来表示是首次进入该界面还是成功设置完成后再次进入的 0 首次 1 成功设置 2 设置错误
system("cls"); //刷新界面
MainMenu_Show();
switch (time_flag) {
case 0:
printf("请输入选项：");
scanf("%s",&temp);
break;
case 2:
printf("请选择正确选项!\r\n");
printf("请输入选项：");
scanf("%s",&temp);
break;
}
if ((temp-48 <1 || temp-48>6) && temp != '*')
{
time_flag = 2;
MainMenu_Control(system_controler);
}
switch (temp-48) {
case 1:
MapDataSelectionMenu_Control(system_controler);
break;
case 2:
Origin_LocationSelectionMenu_Control(system_controler);
break;
case 3:
Destination_LocationSelectionMenu_Control(system_controler);
break;
case 4:
AlgorithmSelectionMenu_Control(system_controler);
break;
case 5:
RouteOutputMenu_Control(system_controler);
break;
case 6:
Configuration_Import_Control(system_controler);
break;
case -6:
Thanks_Show();
break;
}
}
可以看到这个switch就是选项的逻辑，选择不同的选项会调用不同的菜单管理控制函数，每一个菜单管理控制函数都包括菜单的展示、逻辑的实现… 基本上方法是一样的。
导游系统执行函数
系统，或者说是算法，的执行是在最后用户选择输出地址的时候才开始执行的。如果使用的是默认的地图数据，那么地图数据的提取也是在这个时候开始的。
/**
* @brief 导游系统执行函数
* */
void Work_Start(SystemControler* system_controler)
{
Information_Entry(system_controler);
/*使用Dijkstra算法*/
if (system_controler->algorithm_options == 0)
{
Dijkstra_Init(system_controler->pdijkstra_controler,system_controler);
Dijkstra_Loop(system_controler->pdijkstra_controler);
Dijkstra_Find_Path(system_controler->pdijkstra_controler);
}
/*使用Floyd算法*/
else
{
Floyd_Init(system_controler->pfloyd_controler,system_controler);
Floyd_Upgrade_Loop(system_controler->pfloyd_controler);
Floyd_Find_Path(system_controler->pfloyd_controler,system_controler->pfloyd_controler->start_point,system_controler->pfloyd_controler->end_point);
}
}
地图数据录入函数
该函数的所有精髓都在数据数据提取函数中。
/**
* @brief 系统景点信息录入函数
* @param data:存放景点数据的邻接矩阵指针
* */
void Information_Entry(SystemControler* system_controler)
{
if (system_controler->map_data_options) //使用自定义地图数据
{
Data_Extracte(data_buffer,system_controler->data); //将原始数据提取出来并转换成整数类型存储在extracted_data中
/*邻接矩阵初始化*/
Adjacency_Matrix_Init(system_controler->graph_data,system_controler->data);
}
else
{
Adjacency_Matrix_Init(system_controler->graph_data,system_controler->data);
}
}
数据数据提取函数
对于有固定格式的数据的提取，我一般都是用状态机编程的思想来实现。而这个实现的方式是从一个开源的RM裁判系统解析程序中学习到的。当然这样的方法可能不是最好的，但是易懂、易实现。这个方法的总体思路是，把解析的过程分成若干步，然后用枚举来定义这个连续的步骤，通过枚举变量的数值来得知到了哪一步，下一步该到哪个状态。
/**
* @brief 输入数据提取操作
* @param data_input:需要提取数据的存储地址
* @param data_output:提取数据输出地址
* */
void Data_Extracte(char* data_input,int* data_output)
{
int run_flag = 1;
int index_buffer = 0; //提取暂存buffer索引
int index_raw_data = 0; //原始数据扫描索引
int index_data = 0; //提取完成数据索引
char buffer[20]; //用来暂存提取的时候读到的数据
while (run_flag)
{
switch (step)
{
case NODE_1:
{
if(data_input[index_raw_data] == ' ')
{
step++;
}
else
{
buffer[index_buffer] = data_input[index_raw_data];
index_raw_data++;
index_buffer++;
}
}break;
case BLANK_1: /*遇见空格就把上一次的字符数据给转换成数字数据存在存放提取数据的数组中*/
{
buffer[index_buffer] = '\0'; /*将数组构造成字符串形式*/
data_output[index_data] = atoi(buffer); //将提取出来的数据转换成int型存放在处理好的数组中
memset(buffer,0,sizeof(buffer)/sizeof(char));
step++;
index_raw_data++;
index_buffer++;
index_buffer = 0; //重置buffer索引
index_data++;
}break;
case NODE_2:
{
if(data_input[index_raw_data] == ' ')
{
step++;
}
else
{
buffer[index_buffer] = data_input[index_raw_data];
index_raw_data++;
index_buffer++;
}
}break;
case BLANK_2:
{
buffer[index_buffer] = '\0'; /*将数组构造成字符串形式*/
data_output[index_data] = atoi(buffer); //将提取出来的数据转换成int型存放在处理好的数组中
memset(buffer,0,sizeof(buffer)/sizeof(char));
step++;
index_raw_data++;
index_buffer++;
index_buffer = 0; //重置buffer索引
index_data++;
}break;
case EDGE:
{
if(data_input[index_raw_data] == ';')
{
step++;
}
else
{
buffer[index_buffer] = data_input[index_raw_data];
index_raw_data++;
index_buffer++;
}
}break;
case BRANCH:
{
buffer[index_buffer] = '\0'; /*将数组构造成字符串形式*/
data_output[index_data] = atoi(buffer); //将提取出来的数据转换成int型存放在处理好的数组中
memset(buffer,0,sizeof(buffer)/sizeof(char));
step++;
index_raw_data++;
index_buffer++;
index_buffer = 0; //重置buffer索引
index_data++;
}break;
case END:
{
if(data_input[index_raw_data] == 0)
{
run_flag = 0;
}
else
{
step = 0;
}
}
}
}
}
5 链接
5.1 演示视频
https://www.bilibili.com/video/BV1e14y1P7Aa/?spm_id_from=333.999.0.0&vd_source=e240c7dafa7cf5d1b5ebfa7d64e9b941
5.2 源码链接
https://gitee.com/HouEna/campus-tour-guide-system
文章出处登录后可见！
