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

列表一、需求分析1.问题说明2.基本要求二、摘要设计1.流程图2.设计数据结构三、详细设计1.编程思想2.软件模块结构图3.源程序四、调试分析1.测试数据2.时间复杂性分析3.机械问题和解决方案算法的改进假设五、用户用户手册六、经验一、需求分析1.问题说明本主题利用我国铁路运输网络的数据进行编程和运行验证。详细内容只需在网上搜索全国铁路局管辖线路示意图，全国主线即可。铁路网有两个主要概念：铁路线和火车站。例如，1号铁路线表示京射线，2号铁路线表示轻伤线。铁路路线对象包括铁路路线编号、铁路路线名称、起点桩号编号、端子编号、相应的铁路路线长度、通行标记(00B客运禁运线、01B货运专线、10B客运专线和11B旅客运输路线)。火车站对象包括所属铁路线号、站码、站名、站名、站名、这条铁路线始发站和终点站距离等。2.基本要求(1)调查车站所属的铁路线(2)需要新铁路线的管理功能(3)需要新车站的管理功能(4)对于客运，货物运输情况可以计算从任何起点站到任何终点站的最短路径。并要求能显示这条最短路径的各个火车站的通过顺序二、摘要设计1.程序流程图(负责弗洛伊德算法以外的设计)结束交换机(菜单)缅因启动readviews()；read ways()；readlines()；Menu=1Menu=2Menu=5Menu=3Menu=4add view()；addline()；add way()；谢谢打印。你好。谢梦芳李婷婷search()；short _ path()；floyed()；这里简单介绍弗洛伊德算法的核心思想，假设从图的加权相邻矩阵开始，从Vi到Vj有一个弧，从Vi到Vj有一个长度为arcsi 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与中间顶点的序号不大于0的最短路径进行比较，选择中间顶点的序号不大于1的最短路径，然后添加V2继续试验，这样在n次比较后，就可以找到从Vi到Vj的最短路径。2.设计数据结构存储结构：此程序中的某些函数使用文件存储数据，因此要添加数据，请使用顺序存储结构，在文件中直接工作即可。弗洛伊德算法中使用的存储结构是图的邻接矩阵。A.为抽象数据类型定义的模板和抽象数据类型线性表的定义如下：Adt列表数据对象：d=ai | ai/elem set，I=1，2，3.n，n 0数据关系：R1=| ai-1，ai-d，I=1，2，3，n基本任务：Void readviews()初始条件：views.txt已存在。操作结果：一次将views.txt中的数据存储在数组viewsSIZE_view中，并将数组中存储的数据数存储在全局变量view _ count中。Void readways()初始条件：ways.txt已存在。操作结果：一次将ways.txt中的数据存储在数组waysSIZE_way中，并将数组中存储的数据数存储在全局变量way _ count中。Void readlines()初始条件：lines.txt已存在。操作结果：一次将lines.txt中的数据存储在数组linesSIZE_line中，并将数组中存储的数据数存储在全局变量line _ count中。void search()；初始条件：viewsSIZE_view存在，其中包含相关信息。任务结果：根据用户输入的工作站名称查找并输出有关该工作站的信息。Void addview()初始条件：views.txt已存在。操作结果：一次将views.txt中的数据存储在数组viewsSIZE_view中，并将数组中存储的数据数存储在全局变量view _ count中。Void addway()初始条件：ways.txt已存在。操作结果：一次将ways.txt中的数据存储在数组waysSIZE_way中，并将数组中存储的数据数存储在全局变量way _ count中。Void addline()初始条件：lines.txt已存在。操作结果：一次将lines.txt中的数据存储在数组linesSIZE_line中，并将数组中存储的数据数存储在全局变量line _ count中。Void floyed()初始条件： viewsSIZE_view，waysSIZE_way，linesSIZE_line已存在，且具有相关信息。作业结果：将每个车站到每个车站的最短路径以及此路径的距离储存在path_info，path _ listsize _ viewsize _ view阵列中。Void shortest_path()初始条件：path_info，path _ listsize _ viewsize _ view存储相关数据。任务结果：输出输入的两个工作站的最短距离和通过的所有工作站；Void add adata (intmenu)初始条件：views.txt、ways.txt和lines.txt已存在。作业结果：如果menu=1，则加入工作站资料；如果menu=2，则加入定线资料；B.在弗洛伊德算法中，用于数据结构的想法是图形的想法，因此数据结构的设计主要是为了便于图形的操纵。因此，我们使用了以下数据定义：Struct view_info /*城市信息结构*/Int idchar name20；Int代码；char short name20；char LName100；/经过该站的铁路路线的名称 viewsSIZE _ view；Struct line_info/铁路线信息结构Int Lidchar LName20；Int start _ id/始发站Int end _ id/端子Int dist/铁路路线长度char sign5；/交通标志 linesSIZE _ line；Struct way_info /铁路图的资讯结构Int station1Int station2Int dist waysSIZE _ way；Struct path_info /最短路径的查询Int countint pathSIZE _ view；三、详细设计1.编程思想设计理念：核心问题：最短路径查找(弗洛伊德算法)数据模型(逻辑结构):权重图形输入I/o:初始数据来自三个文件：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.软件模块结构图VoidAddline()VoidAddway()VoidAddview()VoidFloyed()Void main()VoidSearch()VoidShort_path()VoidAdddata(intMune)Void readlines()Void readways()Void readviews()(1)主程序模块，其中主函数为：Void main() 新火车站；添加铁路线。查询火车站的信息。关于客运、货物运输情况，求两站之间的最短路径及其通过和巡航；退出界面(2)文件模块为：void read ways()；void read views()；Void readlines()(3)图模块包括：void short _ path()；Void floyed()(4)查询函数并添加函数void search()；void add data(in menu)；void add way()；void addline()；Void addview()函数调用：进入主函数并调用文件模块中的函数以读取数据。选择1或2将调用void adddata(in menu)。其中，选择1将调用void addview()函数，选择2将调用void addline()和void addway()函数。要为查询调用void search()函数，请选择3。选择4，然后调用void short_path()和void floyed()函数以获取最短路径。源程序(请参阅附录)四、调试分析1.测试数据数据读取如下：操作界面如下：功能测试屏幕抓图：输入1以增加工作站信息，如下所示：输入2以增加铁路路线信息，如下所示：输入3，然后查询工作站信息，如下所示：要查询最短路径，请输入4，如下所示：要退出界面，请输入5:2.时间复杂性分析在程序中，图的存储结构是加权邻接矩阵，其相邻矩阵初始化的时间复杂度为O(n*n)。寻找最短路径时使用弗洛伊德算法，时间复杂性主要是寻找从所有站到任意站的最短路径是for循环，for循环是3，所以时间复杂性是O(n3)。3.机械和解决方案问题(1)弗洛伊德算法一看到标题就想起来了，但不知道怎么做，在网站上查找并修改了类似的代码，最终得到了源代码。(2)运行源程序时忘记添加相关文本文件，因此在运行文件时，文件打开失败，显示一条消息，提示您无法使用以下功能，如果您认为此时需要手动添加相关文本文档，则可以解决此问题。(3)在way.text文本文档中添加每个工作站权重时，从一开始就不知道如何添加，思考，查看教科书后添加权重时，理解了工作站编码代表每个工作站的事实，因为有自己的图表，所以需要添加两个工作站往返权重。4)由于输入文字时输入汉字，系统不稳定，屏幕注射效果好的这个问题，向前辈求助，解决了。算法的改进假设1.程序界面不微妙，需要改进，作为人机交互的界面，要尽量提高人机交互体验。2.铁路交通网络管理也有很多方面，例如删除一些铁路线或火车站五、用户用户手册首先运行可执行文件。可执行文件为test.exe。根据需要选择相应的数字代码。1要增加工作站信息，请选择1。首先输入新工作站的id，输入数字(必须大于给定的提示信息)，输入新工作站的名称、文字、新工作站编号、数字(必须大于给定的信息)，输入新工作站的缩写，输入英文字母(通常为新工作站拼音前缀)，输入新工作站经过的路径，然后输入文字。最后，选择是否继续，然后输入n(否)或y(是)。2要增加铁路路线信息，请选择2。首先，输入新铁路路线信息的Lid，输入数字(必须大于给定的信息)，输入新铁路路线的名称，输入文字，输入新铁路路线的起点id和终点id，输入数字，输入距离，输入数字，然后输入交通标志。输入00B客运线、01B货船、10B客运专线、11