校园导航问题.doc

内置模块：目的与要求、需求分析、概要设计、详细设计、源代码 使用txt文件读入Map地图，退出程序时保存修改后的地图到school.txt文件。 用C++STL标准库中的vector容器做的动态数组。 免费下载，看个人简介 【校园导航问题】是一个课程设计项目，旨在帮助学生掌握数据结构中的树和图型结构，以及如何使用C++STL中的vector容器进行动态数组操作。在这个项目中，开发者需要实现一个程序，该程序能处理一个表示校园景点的无向网，并提供一系列功能，如查询景点信息、查找最短路径、显示所有路径以及修改地图。 **需求分析**： 1. 程序应能够存储主要景点的信息，包括编号、名称和简介。 2. 地图由景点间的道路组成，记录路径长度。 3. 支持查询特定景点的详细信息。 4. 提供任意两个景点之间的最短路径查询。 5. 显示任意两个景点之间的所有可能路径。 6. 允许用户增加、删除和更新景点及道路信息。 **概要设计**： - 抽象数据类型描述：定义了Vertex类表示景点，包含编号、名称和简介；Route类表示道路，包含两个端点和长度；Map类作为整个地图的容器，包含顶点集、边集和已删除景点编号集。 - 程序结构：使用主页面设计，包含四个功能选项，用户可以选择查询、最短路径、所有路径、修改信息等功能。用户可以通过输入回车返回主页面，输入0退出程序。 - 数据存储：使用txt文件读取和保存地图数据，使用vector容器实现动态数组，简化了数据管理。 **详细设计**： 1. **存储结构**： - `Vertex`类包含景点编号`num`、名称`name`和简介`intro`。 - `Route`类包含边的权重`m`以及两个端点`point1`和`point2`。 - `Map`类存储`Vertex`和`Route`的集合，还有已删除景点的编号集`dropNum`和景点总数`verNum`。 2. **算法设计**： - **寻找最短路径**：采用Dijkstra算法，这是一种经典的单源最短路径算法，通过不断更新节点的最短距离来找到起点到其他所有点的最短路径。 - **显示所有路径**：使用广度优先搜索（BFS）策略，每次扩展时计算当前路径的最短距离，直到找到目标节点，从而找出所有可能的路径。 **实现细节**： 1. 初始化地图：程序从名为"school.txt"的文本文件中读取地图数据，文件格式为"路 : "格式。 2. 删除景点：首先删除与该景点相关的所有道路，然后将景点编号加入到删除的点集。 3. 添加和修改信息：在添加新景点时，需要确保编号未被使用。修改信息时，需再次确认新信息。 这个课程设计项目涵盖了数据结构、算法和文件操作等多个重要概念，对于理解和应用C++STL以及图理论提供了实践平台。通过这个项目，学生可以提高编程技巧，增强问题解决能力，同时加深对数据结构的理解。