应用程序课程设计--校园导游图C语言实现

【问题描述】 设计一个校园导游程序，为来访的客人提供各种信息查询服务。 一．需求分析 1.程序为用户提供路径咨询方案。构造一个无向图M并用邻接矩阵来存储。 2.利用佛洛依德算法来计算出起点到各个顶点之间的最短路径用二维数组path[i][j]来记录，最短路径长度就用一维数组shortext[i][j]存放。 3.根据起点和终点输出最短路径和路径长度。 4.程序要求输入编号来查询景点信息和路径。 5.为了增加程序的通用性，地图信息不是提前在程序里初始化过的，而是通过文件来读入程序，这样既可以增加程序的通用性，也可以使程序文件更加小，也节省了空间。 【课程设计概述】 本次课程设计的目标是开发一个校园导游程序，使用C语言实现，旨在为访问校园的客人提供路径查询和其他信息查询服务。程序的核心功能包括构建无向图、运用佛洛依德算法求解最短路径以及读取地图信息等。 **1. 图的构建与数据结构** 在需求分析阶段，程序需要构建一个无向图来表示校园的地理布局。无向图是指图中的边没有方向，任意两个顶点之间可以双向通行。邻接矩阵是一种常用的存储无向图的方法，它使用一个二维数组来表示图中顶点之间的关系，数组的元素表示相应顶点之间是否存在边及其权重。 **2. 佛洛依德算法** 佛洛依德算法用于求解所有顶点对间的最短路径，适用于有权重的图。在本程序中，它被用来计算起点到其他所有顶点的最短路径。算法会更新一个二维数组`path[i][j]`，记录从顶点i到顶点j的最短路径，以及一个一维数组`shortest[i]`，保存从起点到各顶点的最短路径长度。 **3. 景点信息查询** 用户可以通过输入编号查询特定景点的相关信息，如名称、编号和详细描述。这些信息需以某种形式存储，如结构体数组，以便快速查找和输出。 **4. 文件读入地图信息** 为提高程序的通用性和减小程序文件大小，地图信息不预先写入代码，而是从外部文件读取。这样使得程序能适应不同校园的地图，只需更改输入文件即可。 **5. 模块设计** - **主程序模块**：负责初始化，接收并处理用户命令，直至用户选择退出。 - **初始化模块**：加载地图信息文件，构建图的数据结构。 - **景点简介模块**：根据用户输入的编号输出景点信息。 - **佛洛依德算法模块**：计算最短路径。 - **求最小路径模块**：调用佛洛依德算法并处理结果。 - **输出模块**：显示最短路径和路径长度。 **6. 图的抽象数据类型（ADT）** 在概要设计中，定义了图的ADT，包括顶点集、边集和一系列基本操作，如创建图、销毁图、查找顶点、获取和设置顶点值、遍历邻接顶点、添加或删除顶点和边等。这些操作为图的高效处理提供了基础。 **7. 图的类型定义** 具体到程序实现，使用结构体`Elemtype`存储景点信息，包括名称、编号和描述。`Vertex`结构体包含了景点编号和`Elemtype`信息。整个图则使用一个结构体数组`vexs`来表示，其中数组的每个元素代表一个顶点。 **8. 各模块调用关系** 主程序模块调用初始化模块加载地图，然后循环接受用户命令，根据命令调用相应的处理模块。例如，当用户请求路径查询时，主程序会调用求最小路径模块，该模块内部调用佛洛依德算法模块。如果用户请求景点信息，主程序则调用景点简介模块。 综上，这个校园导游程序结合了数据结构、算法和文件操作等多个核心计算机科学概念，是学习C语言和图论的实践项目。通过这个项目，学生能够深入理解如何在实际应用中运用所学知识，并提升问题解决能力。