数据结构实验报告交通指南.doc

数据结构实验报告主要探讨了如何构建一个交通指南系统，该系统使用数据结构来解决实际问题，即找到城市公交线路图中两点之间的最短路径。在这个实验中，有以下几个关键的知识点： 1. **数据结构**：实验采用了图数据结构来表示公交线路。图是由顶点（vertices）和边（edges）组成的数据结构，其中顶点代表区域中的重要站点，边则表示公交线路。这里使用了带权有向图，权值可以是票价或搭乘所需时间。 2. **结点和图的存储结构**：实验中定义了两个结构体，`edgenode` 和 `vexnode`。`edgenode` 用于表示边，包含边的序号、权值和指向下一个边的指针；`vexnode` 用于表示顶点，包含顶点的字符标识和连接到其他顶点的链表头。整个图是一个二维数组 `Graph[n]`，每个元素是 `vexnode` 类型。 3. **Floyd 算法**：Floyd-Warshall 算法是一种解决所有顶点对之间最短路径的算法。在实验中，`Floyd` 函数用于计算图中任意两点间的最短路径。该算法通过迭代更新所有可能的路径，每次选择中间节点来尝试缩短路径，直到无法再缩短为止。`Floyd` 函数接受一个图 `G`，一个距离矩阵 `A` 和一个路径矩阵 `P` 作为参数，最终将最短路径信息存储在 `A` 和 `P` 中。 4. **算法实现**：实验提供了部分 C++ 代码，包括 `ArcCell` 结构体表示边的信息，`_MGraph` 结构体表示整个图，以及 `MGraph` 类来操作图。`MGraph` 类中包含了构造有向网的 `CreateDN` 函数，用于读取用户输入的站点信息和线路数据，以及使用 Floyd 算法计算最短路径的 `ShortestPath_FLOYD` 函数。 5. **输入与输出**：实验要求输入图的相关信息，如顶点数、边数、每条边的起点、终点和权值，以及用户查询的任意两个站点。输出是最短路径的详细信息，包括一条从起点到终点的最短简单路径。 6. **编程实践**：实验报告中的源代码展示了如何在实际编程中实现这些数据结构和算法，包括创建图对象、读取输入、计算最短路径，并将结果输出。 通过这个实验，学生不仅可以掌握图数据结构的基本概念，还能理解并应用 Floyed 算法求解实际问题，同时锻炼了 C++ 编程能力，特别是在处理复杂数据结构和算法时的编程技巧。