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

目录一、需求分析1.问题描述2.基本要求二、概要设计1.程序流程图2.数据结构设计三、详细设计1.程序设计思想2.软件模块结构图3.源程序四、调试分析1.测试数据2.时间复杂度分析3.上机遇到的问题及解决方案4.算法的改进设想五、用户使用手册六、心得体会一、需求分析1.问题描述该题目采用我国铁路运输网的数据进行编程和运行验证。详细可在网上搜索《全国铁路局管辖线路示意图》，只要全国的主干线就可以了。铁路运输网络中由铁路线和火车站的两个主要概念，譬如：1号铁路线表示京广线，2号铁路线表示京沪线等。铁路线对象包括铁路线编号,铁路线名称，起始站编号,终点站编号,该铁路线长度，通行标志(00B客货运禁行,01B货运通行专线，10B客运通行专线，11B客货运通行)。火车站对象包括所属铁路线编号，车站代码，车站名，车站简称，离该铁路线起点站路程及终点站路程。2.基本要求（1）查询某站所属的铁路线（2）要求具备新增铁路线的管理功能(3)要求具备新增车站的管理功能(4)针对客运，货运情况能计算任何一个起始车站到任何一个终点站之间的最短路径。并且要求能够显示出该最短路径的各个火车站的经由顺序二、概要设计1.程序流程图（我负责的为除弗洛伊德算法外的设计）在这里简单介绍弗洛伊德算法的核心思想：从图的带权邻接矩阵开始，假设从Vi到Vj有弧，则从Vi到Vj存在一条长度为arcs[i][j]的路径，该路径不一定是最小路径，尚需进行n次试探。首先考虑路径（Vi,V0，Vj）是否存在。如果存在，则比较（Vi，Vj）和（Vi,V0，Vj）的路径长度取长度较短者为从Vi到Vj的中间顶点的序号不大于0的最短路径。假如在路径上再增加一个顶点V1，如果（Vi，….，V1）和（V1，….，Vj）分别是当前找到的中间顶点的序号不大于0的最短路径，那么（Vi，…V1，…,Vj）就有可能是从Vi到Vj的中间顶点的序号不大于1的最短路径。将它和已经得到的Vi到Vj的中间顶点的序号不大于0的最短路径相比较，从中选出中间顶点的序号不大于1的最短路径之后，再增加一个V2继续试探，以此类推，经过n次比较后，即可求出从Vi到Vj的最短路径。结束switch(menu)main开始readviews();readways();readlines();menu=1menu=2menu=5menu=3menu=4addview();addline();addway();输出谢谢使用.再见.谢梦芳李婷婷search（）;short_path();floyed();2.数据结构设计存储结构：本程序部分函数采用的是文件进行数据的存储，所以采用的是顺序存储结构，如要添加数据，直接在文件里面进行操作就行了。弗洛伊德算法中采用的存储结构是图的邻接矩阵。A.如下为抽象数据类型定义的模板以及抽象数据类型线性表的定义：ADTList{数据对象：D={ai|ai∈ElemSet,i=1,2,3……,n,n≥0}数据关系：R1={ai-1,ai|ai-1,ai∈D,i=1,2,3,……,n}基本操作：voidreadviews()初始条件:views.txt已经存在。操作结果:将views.txt里面的数据一次存入数组views[SIZE_view]里，并将数组里面的存储数据的个数赋值给全局变量view_count；voidreadways()初始条件:ways.txt已经存在。操作结果:将ways.txt里面的数据一次存入数组ways[SIZE_way]里，并将数组里面的存储数据的个数赋值给全局变量way_count；voidreadlines()初始条件：lines.txt已经存在。操作结果:将lines.txt里面的数据一次存入数组lines[SIZE_line]里，并将数组里面的存储数据的个数赋值给全局变量line_count；voidsearch();初始条件：views[SIZE_view]存在，且里面放有相关信息。操作结果：根据用户输入的车站名查找该车站的相关信息并输出；voidaddview()初始条件:views.txt已经存在。操作结果:将views.txt里面的数据一次存入数组views[SIZE_view]里，并将数组里面的存储数据的个数赋值给全局变量view_count；voidaddway()初始条件:ways.txt已经存在。操作结果:将ways.txt里面的数据一次存入数组ways[SIZE_way]里，并将数组里面的存储数据的个数赋值给全局变量way_count；voidaddline()初始条件：lines.txt已经存在。操作结果:将lines.txt里面的数据一次存入数组lines[SIZE_line]里，并将数组里面的存储数据的个数赋值给全局变量line_count；voidfloyed()初始条件:views[SIZE_view]、ways[SIZE_way]、lines[SIZE_line]已经存在并且存有相关信息。操作结果：把每个车站到各个车站的最短经由路径及此路径的距离存储在path_info、path_list[SIZE_view][SIZE_view]数组里；voidshortest_path()初始条件：path_info、path_list[SIZE_view][SIZE_view]存储相关的数据；操作结果：输出输入的两个站的最短距离及经过的所有站；voidaddadta(intmenu)初始条件：views.txt、ways.txt、lines.txt已经存在。操作结果：如果menu=1，则添加车站数据，如果menu=2，则添加路线数据；B.弗洛伊德算法中，数据结构所用到的思想为图的思想，所以数据结构的设计主要的目的为便于图的操作的设计。因此我们用了下面这些数据定义。structview_info/*城市信息结构*/{intid;charname[20];intcode;charshortname[20];charLName[100];//经过此站的铁路线名称}views[SIZE_view];structline_info//铁路线信息结构{intLid;charLName[20];intstart_id;//始发站intend_id;//终点站intdist;//铁路线长charsign[5];//通行标志}lines[SIZE_line];structway_info//铁路度的信息结构{intstation1;intstation2;intdist;}ways[SIZE_way];structpath_info//用于最短路径的查询{intcount;intpath[SIZE_view];};三、详细设计1.程序设计思想设计思路:核心问题：求最短路径(弗洛伊德算法)数据模型(逻辑结构)：带权有向图输入输出：初始数据是从views.txt、lines.txt、way.txt三个文件中读入，在读入数据后，用户可以根据选项选择相应的功能，不同的功能有不同的数据输入/输出，比如：查询的功能是要求输入要查询的站的名称，然后输出是该站的相关信息；查询最短路径的功能则是输入起点站、终点站的名称，输出则是该段路线距离和经由站等。程序的输入：(1)铁路线信息的输入：依次输入“铁路线代码,铁路线名称，起始站代码,终点站代码，该铁路线长度、通行标志”，并且中间以空格隔开。（2）火车站信息的输入：依次输入“车站代码，车站名，车站编号、车站简称，所属铁路线编号”，并且中间以空格隔开。程序的输出格式：（1）当显示铁路线或者火车站的信息时，与输入时的格式完全一致；（2）输出最短路径的长度，以及最短路径的经由顺序；按照程序功能要求，设计了一下各个功能模块：（1）、文件读取模块文件读取模块包括读取车站信息模块readviews、路段权值信息读取模块readlines、铁路线信息读取模块readlines。这些模块的主要功能为从文件中读取所需的信息。（2）、添加信息模块adddata添加信息模块又包括以下子功能模块：A、添加站点信息模块addview。B、添加路段权值模块addway。C、添加铁路线信息模块addline。（3）查询模块根据用户需求，查询站点信息（4）最短路径查询模块该模块为本软件设计的核心部分。根据该模块可以很方便的找出两个城市的最短路径。该最短路径的算法为常用的弗洛伊德算法。（5）操作菜单模块该模块主要用于与用户的交互，一个界面友好的菜单可以提高软件的人机交互体验。2.软件模块结构图(1)主程序模块，其中主函数为：voidmain(){新增火车站；新增铁路线；查询火车站的信息；针对客运、货运情况，求两站之间的最短路径及其经由顺寻；退出界面}(2)文件模块为:voidreadways()；voidreadviews()；voidreadlines()(3)图模块为：Voidshort_path()；voidfloyed()(4)查询函数和添加函数voidsearch()；voidadddata(inmenu)；voidaddway()；voidaddline()；voidaddview()函数的调用：进入主函数，调用文件模块各函数以读取数据；选择1或2，则调用voidadddata(inmenu),其中若选择1，则调用voidaddview()函数，若选择2，则调用voidaddline()和voidaddway()函数；选择3，调用voidsearch()函数进行查询；选择4，调用voidshort_path()和voidfloyed()函数以得到最短路径。3.源程序(见附录)四、调试分析voidaddline()voidaddway()voidaddview()voidfloyed()voidmain（）voidsearch()voidshort_path()voidadddata(intmune)voidreadlines()voidreadways()voidreadviews()1.测试数据数据读取如下：操作界面如下：功能测试截图：输入1，增加车站信息如下：输入2，增加铁路线信息如下：输入3，查询车站信息如下：输入4，查询最短路径如下：输入5，退出界面如下;2.时间复杂度分析程序中图的存储结构为带权邻接矩阵，其中对邻接矩阵的初始化的时间复杂度为O(n*n);在求最短路径的时候，用的是弗洛伊德算法，时间复杂度主要在于求每一站到任意站的最短路径由是的for循环，那有三个for循环，所以时间复杂度为O(n3)。3.上机过程中出现的问题及其解决方案（1）刚刚看到题目要求的时候就想到了弗洛伊德算法，但是不知道如何去做，在网站搜索到类似代码，经过修改后，最终得出了源程序。（2）源程序可以运行的时候，忘记添加相关文本文件，所以运行文件的时候会提示文件打开失败，无法进行接下来的功能使用，这时候才想起来要自行添加相关的文本文档，接着问题就解决了。（3）在way.text文本文档中添加各站权值的时候，一开始不知道如何添加，经过思考和查询课本后，明白了添加权值时是以各站编码代表各站，由于是有向图，所以需要添加两站往返权值。（4）在输入信息时，由于是输入汉字，系统不稳定，容易出现刷屏，这个问题，我是向学长寻求帮助并得以解决的。4.算法的改进设想1.程序界面不够美观，需要改进，作为人机交互的界面，应尽量美观舒适，提高人机交互体验。2.铁路交通网的管理还有很多方面，例如删除某些铁路线或火车站五、用户使用手册首先运行可执行文件，执行文件为：test.exe。根据需要选择相应的数字代码：【1】选择1，增加车站信息。首先输入新车站的id，输入为数字（必须大于所给提示信息），其次输入新车站名称，输入为文字，接着输入新车站的编号，输入为数字（必须大于所给信息），然后输入新车站的简称，输入为英文字母（一般为新车站拼音首字母），接着输入新车站经过的路线，输入为文字。最后选择是否继续，输入为n（不）或y（是）。【2】选择2，增加铁路线信息。首先输入新铁路线信息的Lid，输入为数字