地铁建设问题.doc

_地铁建设问题.doc软件技术学院游戏算法实践报告姓名 专业 数字媒体艺术班级指导教师 2012年1月6日通州区地铁建设问题1、问题的定义与描述1・1、问题定义:、问题描述:某城市要在其各个辖区之间修建地铁來加快经济发展,但由于建设地铁的费用昂贵,因此需耍合理安排地铁的建设路线,使程客可以沿地铁到达各个辖区,并使总的建设费用最小。怀衆区\・-1各区距离图2、 关键技术1从包含各辖区的地图文件中读入辖区名称和各辖区间的距离。,计算出应该建设哪些辖区间的地铁路线。。3、 数据的组织1数据结构定义:木课程设计使用的数据结构是无向图,无向图采用邻接矩阵作为存储结构。2数据定义:、站点(顶点)结构定义:站点号站点名3・3、数据类型定义:(1) 在计算的过程中除要读取数(用字符数组表示,设其最大长度不超过50)夕卜,还耍读入各顶点的边的权值(权值设一默认最大值为60000计算需耍,当两地没有可建路线时)。同时还要输出汉字表示的路段,有用字符串。故定义头文件、常量、顶点数及权值数据类型如下:#includez,〃#includez,"^defineMAXVEX50 /*顶点数最大值*/ttdefincMAXWEIG1IT60000/*若顶点间无路径,则以此最大值表示不通*/typedefintweight;(2) 每一个顶点由顶点号(初始从0开始)和站点名称组成。顶点号为整型,顶点名称则为字符数组。顶点总体定义为结构体类型。/*顶点(站点)的数据类型*/typedefstruct{intno;charname[100];}DataTypc;(3) 定义邻接矩阵,邻接边由weight型的二维数组,顶点为DataType类型,记录总顶点数的vexsotypedefstruct{weightarcs[MAXVEX][MAXVEX];DataTypedata[MAXVEX];intvexs;}MGraph,*AdjMatrix;(4) 在定义一DataType类型的数组,用來存放顶点的信息(顶点号和顶点名称),然后定义一long类型的用來存放各铁路的权值,这两个数组用來创建邻接距阵时为邻接矩阵赋值。DataTyped[];/*存放路段信息的数组*/int[MAXVEX];4、:程序模块图J 丿创建邻接矩阵(以各站点及其路段间的距离为参数创建邻接矩阵)\ JA输出相通站点及路段(深度优先遍历,输出所冇相通站点名称及其对应路段长度) 求最短路线并输出(用普里姆算法求出最短路线,并输出相应路线)\ )图4-1总流程图2函数原型定义:(AdjMatrixg,DataTypevex[],inta[][MAXVEX],intn);/*初始化并创建邻接矩阵的函数*/参数:"AdjMatrixg"此参数用來传递在主函数已定义的邻接矩阵的地址。“DataTypevex[]”传递给函数顶点信息。“inta[][MAXVEX]”用来传递给函数邻接边(连接路段长度)信息的数组参数。“intn”用來传递顶点个数的参数。