1地铁建设问题1x问题的定义与描述1.K 问题定义：地铁建设问题1.2、问题描述：某城市要在其各个辖区之间修建地铁来加快经济发展，但由于建设地铁的费用昂贵，因此需要合理安排地铁的建设路线，使程客可以沿地铁到达各个辖区,并使总的建设费用最小。图 1-1 各区距离图32、关键技术2.1 从包含各辖区的地图文件中读入辖区名称和各辖区间的距离。2.2 根据读入的各辖区的距离信息，计算出应该建设哪些辖区间的地铁路线。2.3 输出应该建设的地铁路线及所需建设的总里程信息。3、数据的组织3.1 数据结构定义：本课程设计使用的数据结构是无向图，无向图采用邻接矩阵作为存储结构。3.2 数据定义：3.2.1、站点（顶点）结构定义：站点号站点名3.3、数据类型定义：（1）在计算的过程中除要读取数（用字符数组表示，设其最大长度不超过 50）外，还要读入各顶点的边的权值（权值设一默认最大值为 60000 计算需要，当两地没有可建路线时）。同时还要输出汉字表示的路段，有用字符串。故定义头文件、常量、顶点数及权值数据类型如下：#include"stdio.h"#include"string.h"#defineMAXVEX50/*顶点数最大值*/#defineMAXWEIGHT60000/*若顶点间无路径，则以此最大值表示不通*/typedefintweight;（2）每一个顶点由顶点号（初始从 0 开始）和站点名称组成。顶点号为整型，顶点名称则为字符数组。顶点总体定义为结构体类型。/*顶点（站点）的数据类型*/typedefstruct{intno;charname[100];}DataType;（3）定义邻接矩阵，邻接边由 weight 型的二维数组，顶点为 DataType 类型，记录总顶点数的 vexs。typedefstruct{weightarcs[MAXVEX][MAXVEX];DataTypedata[MAXVEX];intvexs;}MGraph,*AdjMatrix;（4）在定义一 DataType 类型的数组，用来存放顶点的信息（顶点号和顶点名称）然后定义一 long 类型的用来存放各铁路的权值，这两个数组用来创建邻接距阵时为邻接矩阵赋值。DataTyped[];/*存放路段信息的数组*/intm[][MAXVEX];4、分析与实现4.1 总体设计：创建邻接矩阵(以各站点及其路段间的距离为参数创建邻接矩阵)\输出相通站点及路段(深度优先遍历，输出所有相通站点名称及其对应路段长度)kJ求最短路线并输出(用普里姆算法求出最短路线，并输出相应路线)\丿4rA程序模块图图 4-1 总流程图4.2 函数原型定义：4.2.1 voidCreateGraph(AdjMatrixg,DataTypevex[],inta[][MAXVEX],intn);/*初始化并创建邻接矩阵的函数*/参数：①“AdjMatrixg”此参数用来传...
