地铁建设问题数据结构课程设计

地铁建设问题数据结构课程设计 一、设计时间 数据结构课程设计的设计时间为2015年1月19日至2012年1月23日，总计5天。 二、设计目的 通过课程设计，加深对《数据结构》这一课程所学内容的进一步理解与巩固，加深对结构化设计思想的理解，能对系统功能进行分析，并设计合理的模块化结构。提高程序开发功能，能运用合理的控制流程编写清晰高效的程序。训练C程序调试能力，能将一个中小型各级组织系统联调通过。开发一个中小型系统，掌握系统研发全过程。培养分析问题、解决实际问题的能力。 三、设计任务 某城市要在各个辖区之间修建地铁，由于地铁建设费用昂贵，因此需要合理安排地铁建设线路，使市民可以沿地铁到达各个辖区，并使总费用最小。 四、设计容 设计思路： 1. 输入各个辖区名称和各辖区间直接距离（地铁铺设费用与距离成正比）。 2. 根据辖区距离信息，计算出应该在哪些辖区建立地铁线路。 3. 输出应该建设的地铁线路及所需建设总里程。 五、抽象数据类型的定义 在本程序中，用到了以下抽象数据类型的定义： 1. `typedef char InfoType;`：定义一个字符类型的 InfoType，用来存储辖区名称信息。 2. `typedef char VertexType[MAX_NAME];`：定义一个字符数组类型的 VertexType，用来存储辖区名称信息。 3. `typedef struct{ VRType adj; InfoType *info; }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];`：定义一个结构体类型的 ArcCell，用来存储辖区之间的关系信息。 4. `typedef struct{ VertexType vexs[MAX_VE`：定义一个结构体类型，用来存储辖区信息。 六、数据结构设计 在本程序中，我们使用了以下数据结构： 1. 图（Graph）：用来存储辖区之间的关系信息。 2. 矩阵（Matrix）：用来存储辖区之间的距离信息。 七、算法设计 在本程序中，我们使用了以下算法： 1. Prim 算法：用来计算最小生成树，确定地铁线路。 2. Dijkstra 算法：用来计算最短路径，确定地铁线路的总里程。 八、测试与分析 在本程序中，我们使用了以下测试方法： 1. 单元测试：测试每个模块的功能是否正确。 2. 集成测试：测试整个系统的功能是否正确。 九、结论 通过本课程设计，我们加深了对《数据结构》这一课程所学内容的理解，掌握了系统研发的全过程，培养了分析问题、解决实际问题的能力。