数据结构——校园导游程序

要求

大一新生刚刚入学时，对自己的新校园比较陌生，需要一个导游程序为其提供校园主要场所介绍、最短路径推荐等服务。
编写一个校园导游程序，要求如下：
（1） 程序具有合理、友好的操作界面；
（2） 程序启动时，从School.txt 文件中加载校园信息（如，主要场所及其间的道路等）；
（3） 程序运行中，可查询校园任一主要场所的相关信息、任两个主要场所间的最短路径，
并将每次查询请求及相应的查询结果保存到Query.txt 文件中。
（4） 程序退出时，将程序此次运行期间查询的主要场所按其热门程度排序显示在屏幕上；
（5） 可按需输出School.txt文件、Query.txt 文件内容。

解决思路

（一）整体设计

    新生导游系统可以为用户提供场所信息、最优路线查询功能，并且对查询结果进行统计。

    将整个程序分为三个文件：main.c、strcture.h、operation.h，分别为主函数文件、整体框架及数据结构定义文件、各种操作函数的文件，这样规划方便程序的构建与阅读，思路清晰。

（二）数据结构设计

       根据地图的特性，构建无向带权图的数据结构，并采用邻接矩阵的方式进行储存，数据结构的设计如下：

//图的顶点的数据类型
typedef struct Vextype
{
    char name[MAX_NAME]; //顶点的名字（即地点/建筑名）
    char info[MAX_INFO]; //对顶点的介绍
    int heat; //记录热度
    int visited; //标记值
}Vextype;
//图的边的数据类型
typedef struct Arcstype
{
    int weight; //边的权重
    char name[MAX_NAME]; //边的名字（即道路名）
}Arcstype;
//图的邻接矩阵表示
typedef struct AdjMatrix
{
    int vexnum; //顶点数目
    int arcnum; //边的数目
    Vextype vex[MAX_VER]; //顶点的数据类型
    Arcstype arcs[MAX_VER][MAX_VER]; //边的数据类型
    int visited[MAX_VER]; //标记数组
}AdjMatrix;

（三）算法设计

       根据程序的设计目标，主要为弗洛伊德算法(Floyd算法)的实现。通过逐渐加入顶点进行试探，构建矩阵 arcs_flo。矩阵初始值类似于图的邻接矩阵表示，只需当 $i==j$ 时，元素值置为 $0$ 即可。然后通过三层 $for$ 循环，不断插入顶点，对矩阵进行更新。当进行 $n-1$ 次最外层循环后，得到的矩阵即为最优路径值的矩阵。其中需要利用递归思想来输出其路径。算法复杂度为 $O(n^3)$

源代码与程序展示

源代码请移步至 code.techxw.com

选择1，则进行场所信息查询操作。
选择2，则进行任意两场所之间的最短路径查询。
选择3，则进行School.txt文件内容的按需输出。
选择4，则进行Query.txt文件内容的按需输出。
选择5，则进行各场所的热门度查询并排名。
选择6，则显示程序此次运行期间查询的主要场所按其热门程度排序。