一、目的
1.掌握图结构的逻辑特点及存储实现；
二、设计要求
1.问题描述（5分）
假设要在某地各辖区之间修建地铁来加快经济发展，但由于建设地铁的费用昂贵，因此需要设计一个程序，合理安排地铁的建设路线，使乘客可以沿地铁到达各个辖区，并使总的建设费用最小。
2.需求分析。（10分）
（1）功能需求：
需要从包含各辖区的地图文件中读入辖区名称和各辖区间的直接距离；
根据读入的各辖区的距离信息，计算出应该建设哪些辖区间的地铁路线；
输出应该建设的地铁路线及所需建设的总里程信息。
（2）数据需求：
各辖区名称和各辖区间直接距离。
三、概要设计（20分）
四、模块设计
五、详细设计
六、测试分析
七、设计总结
附完整代码
### 数据结构C语言地铁站建设问题实验报告知识点解析
#### 一、实验目的
本次实验的主要目的是通过实际项目加深学生对图结构的理解及其在实际应用中的实现方式。具体目标如下：
1. **掌握图结构的基本概念**：了解图的基本组成（顶点与边）、图的类型（有向图与无向图）以及图的应用场景。
2. **理解图的存储结构**：熟悉常用的图存储方法，如邻接矩阵和邻接表等，并能够根据实际情况选择合适的存储方式。
3. **学习图的相关算法**：掌握解决图问题的常用算法，例如最短路径算法、深度优先搜索和广度优先搜索等。
#### 二、问题背景及设计要求
本实验基于一个具体的场景进行设计：在一个区域内规划地铁线路，旨在通过优化线路布局达到最小化建设成本的目标。具体要求如下：
1. **问题描述**：
- **背景**：为了促进地方经济的发展，计划在某区域内的不同行政区内建设地铁线路。
- **挑战**：由于建设成本高昂，需要设计一种方案，既能覆盖所有行政区，又能使总体建设费用最低。
2. **需求分析**：
- **功能需求**：
- 从地图文件中读取行政区名称和相互间的距离信息。
- 计算并确定哪些行政区之间需要建设地铁线路。
- 输出建议的线路布局及其总长度。
- **数据需求**：需要提供各个行政区的名称及其相互间的直接距离。
#### 三、概要设计
在这一阶段，主要涉及的是整个程序的架构设计。关键点包括：
1. **主界面设计**：设计一个友好的用户界面，便于用户输入信息。
2. **存储结构设计**：
- 使用邻接矩阵来表示图结构，其中顶点代表行政区，边的权重代表两个行政区之间的距离。
- 定义了`Graph`结构体来存储图的信息，包括顶点数组`V`和邻接矩阵`R`。
3. **系统功能设计**：
- 输入行政区信息。
- 输入各个行政区之间的距离。
- 指定起始地点。
- 输出最终的线路布局和总长度。
#### 四、模块设计
在模块设计阶段，将整个程序分解成若干个小模块，每个模块负责特定的功能：
1. **主程序模块**：负责程序的启动和整体流程控制。
2. **辖区无向图算法模块**：用于创建行政区之间的无向图，并建立邻接矩阵。
3. **最小生成树结点算法模块**：使用最小生成树算法（如Prim算法）来确定最优线路布局。
4. **普利姆算法输出模块**：输出最小生成树的结果，包括线路布局和总长度。
5. **位置函数模块**：提供一个函数来查找指定行政区在图中的位置。
#### 五、详细设计
在详细设计阶段，进一步细化每个模块的实现细节：
1. **数据类型定义**：
- 定义了`Graph`结构体来存储行政区的信息。
- 定义了`struct tree`结构体来辅助最小生成树算法的实现。
2. **主要子程序详细设计**：
- 创建辖区无向图：通过用户输入创建行政区之间的无向图，并初始化邻接矩阵。
- 位置函数：用于查找指定行政区在整个行政区图中的位置。
- 最小生成树结点算法：使用Prim算法计算最小生成树。
通过以上几个阶段的设计与实现，最终能够完成一个能够有效规划地铁线路布局的程序。这不仅有助于理解和掌握图结构的基本理论，还能够在实践中提高解决问题的能力。
