题目8：全国铁路运输网最佳经由问题

《题目8：全国铁路运输网最佳经由问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、课程设计报告（本科）课程：数据结构学号：1210441019、12104410041210441020姓名：葛程、徐双双杜明辉班级：2012级物联网工程班教师：程敏时间：2014.01.02计算机科学与技术系设计名称：全国铁路运输网最佳经由问题设计内容、目的与要求：实验内容：铁路运输网络中由铁路线和火车站的两个主要概念，譬如：1号铁路线表示京广线，2号铁路线表示京沪线等。铁路线对象包括铁路线编号,铁路线名称，起始站编号,终点站编号,该铁路线长度，通行标志(00B客货运禁行,01B货运通行专线，10B客运通行专线，11B客货运通行)。火车站对象包括所属铁路线编号，车站代码，车站名，车

2、站简称，离该铁路线起点站路程及终点站路程。实验要求：（1）查询某站所属的铁路线（2）要求具备新增铁路线的管理功能（3）要求具备新增车站的管理功能（4）针对客运，货运情况能计算任何一个起始车站到任何一个终点站之间的最短路径。并且要求能够显示出该最短路径的各个火车站的经由顺序计划与进度安排：11.1——11.10大体规划几部分函数，设计基本的铁路图，今后在基本图上实验铁路的基本管理功能。11.11——11.30各组员完成自己的功能函数，并尽量达到要求。12.1——12.15组员一起完成函数的组建及基本辅助函数功能的实现。12.16——12.25组员各自拿到所有的程序，开始个人调试与完善

3、。12.26——12.30组员一起讨论最后的方案，并做最后的优化。设计过程、步骤（可加页）：一：设计过程：将铁路网抽象成图，然后查询中国现有的铁路网结构图，选取合适的站点数目，构造一个简单的铁路图，在构造的铁路图上实现设计的要求。用结构体创建图，然后再图的基础上实现算法要求。通过对题目的分析我们觉得会用到会用到数据结构的邻接矩阵的存储图的定义，图的遍历算法（深度优先遍历），两点间最短路径查询（迪杰斯特拉算法）。使用文件的存储方式，对数据进行存储。32现行的铁路图：最后简单化的铁路网如下：typedefstruct{intid;charname[20];chardes[100];}v

4、info;//站点typedefstruct{intdistance;32intkind;}ArcCell,AdjMatrix[MAX_V_NUM][MAX_V_NUM];//邻接矩阵typedefstruct{vinfovexs[MAX_V_NUM];//站点数组AdjMatrixarcs;intvexnum,arcnum;}MGraph;//图主函数客货运及两个站点的最短路径查询函数站点查询介绍函数站点、铁路线的管理函数客运查询站点管理路线管理货运查询两站间查询二：函数的声明和调用:voidwelcome();//欢迎界面voidsearch_vex_info();//站点信息

5、介绍voidsearch_rantwo_short();//查询任意两个站点之间的一条最短简单路径voidmap_manage();//站点线路修改扩充voidsearch_two_allpath();//查询两站点间所有路径voidsearch_kh_path();//客货运类别路径查询voidabout();//关于voidcreate_map();//初始化地图voidsave_map();//将程序中的图结构体写入数据文件intinput_num_check(intmin,intmax);//数字输入检验voidshortest_path_ota(intbegin);//生

6、成某一站点到所有其它站点的最短路径数据voidprint_fgx();//输出独占一行的分割线32voidmap_add_vex();//新增站点voidmap_add_road();//新增道路voidmap_revise_vex();//修改站点voidmap_revise_road();//修改道路(引导界面)voidmap_reroad_in(intvid);//修改道路(公用嵌入函数)voidmap_delete_vex();//删除站点voidmap_delete_road();//删除道路(引导界面)voidmap_re_arc(intbid,intfid,intki

7、nd,intxid);//修改道路(模块函数)若修改终点:调用前需确保xid(新终点)与原终点不相同voidmap_de_arc(intbid,intfid);//删除道路(模块函数)voidDFS_allpath(intbid,intfid,intk);//寻找两点间所有路径并输出voidsearch_kh_kh(intkind);//查找所有符合类别的路径voidDFS_allpath_kh(intbid,intfid,intk,intkind);//寻找两点间所