课程设计报告
课程：学号：姓名：班级：教师：时间：（本科）
数据结构
1210441019、1210441004
1210441020
葛程、徐双双 杜明辉
2012级物联网工程班
程敏
2014.01.02
计算机科学与技术系
设计名称： 全国铁路运输网最佳经由问题 设计内容、目的与要求： 实验内容： 铁路运输网络中由铁路线和火车站的两个主要概念，譬如：1号铁路线表示京广线，2号铁路线表示京沪线等。 铁路线对象包括铁路线编号,铁路线名称，起始站编号,终点站编号,该铁路线长度，通行标志(00B客货运禁行,01B货运通行专线，10B客运通行专线，11B客货运通行)。 火车站对象包括所属铁路线编号，车站代码，车站名，车站简称，离该铁路线起点站路程及终点站路程。 实验要求： （1）查询某站所属的铁路线 （2）要求具备新增铁路线的管理功能 （3）要求具备新增车站的管理功能 （4）针对客运，货运情况能计算任何一个起始车站到任何一个终点站之间的最短路径。并且要求能够显示出该最短路径的各个火车站的经由顺序 计划与进度安排： 11.1 ——11.10大体规划几部分函数，设计基本的铁路图，今后在基本图上实验铁路的基本管理功能。 11.11——11.30各组员完成自己的功能函数，并尽量达到要求。 12.1——12.15 组员一起完成函数的组建及基本辅助函数功能的实现。 12.16——12.25 组员各自拿到所有的程序，开始个人调试与完善。 12.26——12.30 组员一起讨论最后的方案，并做最后的优化。 设计过程、步骤（可加页）： 一：设计过程： 将铁路网抽象成图，然后查询中国现有的铁路网结构图，选取合适的站点数目，构造一个简单的铁路图，在构造的铁路图上实现设计的要求。用结构体创建图，然后再图的基础上实现算法要求。通过对题目的分析我们觉得会用到会用到数据结构的邻接矩阵的存储图的定义，图的遍历算法（深度优先遍历），两点间最短路径查询（迪杰斯特拉算法）。使用文件的存储方式，对数据进行存储。
1
现行的铁路图： 最后简单化的铁路网如下： typedef struct { int id; char name[20]; char des[100]; }vinfo;//站点 typedef struct { int distance;
2
int kind; }ArcCell, AdjMatrix[MAX_V_NUM][MAX_V_NUM];//邻接矩阵 typedef struct { vinfo vexs[MAX_V_NUM];//站点数组 AdjMatrix arcs; int vexnum,arcnum; }MGraph;//图 主函数 客货运及两站点查询站点、铁 个站点的最介绍函数 路线的管 短路径查询理函数 函数 客货两路站 运运站线点 查查间管管 询 询 查理 理 询 二：函数的声明和调用: void welcome();//欢迎界面 void search_vex_info();//站点信息介绍 void search_rantwo_short();//查询任意两个站点之间的一条最短简单路径 void map_manage();//站点线路修改扩充 void search_two_allpath();//查询两站点间所有路径 void search_kh_path();//客货运类别路径查询 void about();//关于 void create_map();//初始化地图 void save_map();//将程序中的图结构体写入数据文件 int input_num_check(int min,int max);//数字输入检验 void shortest_path_ota(int begin);//生成某一站点到所有其它站点的最短路径数据 void print_fgx();//输出独占一行的分割线
3
void map_add_vex();//新增站点 void map_add_road();//新增道路 void map_revise_vex();//修改站点 void map_revise_road();//修改道路(引导界面) void map_reroad_in(int vid);//修改道路(公用嵌入函数) void map_delete_vex();//删除站点 void map_delete_road();//删除道路(引导界面) void map_re_arc(int bid,int fid,int kind,int xid);//修改道路(模块函数) 若修改终点:调用前需确保xid(新终点)与原终点不相同 void map_de_arc(int bid,int fid);//删除道路(模块函数) void DFS_allpath(int bid,int fid,int k);//寻找两点间所有路径并输出 void search_kh_kh(int kind);//查找所有符合类别的路径 void DFS_allpath_kh(int bid,int fid,int k,int kind);//寻找两点间所有路径并判断该路径上到道路是否全为客/货运线路 int DFS_allpath_kh_isinclude(int bz_i,int pa_k,int kind);//人客/货运线路 判断较长路径是否完全包含较短路径 int DFS_allpath_kh_test(int a_i,int b_i) 结果与分析（可以加页）： 4