《数据结构课程设计安徽省铁路运输网最佳经由》由会员分享，可在线阅读，更多相关《数据结构课程设计安徽省铁路运输网最佳经由（19页珍藏版）》请在金锄头文库上搜索。
1、学号学号13080101071308010107数据结构数据结构课程设计报告课程设计报告题目：题目：安徽省铁路运输网最佳经由安徽省铁路运输网最佳经由专业：专业：计算机科学与技术计算机科学与技术班级：班级：1313（1 1）班）班姓名：姓名：丁鑫丁鑫指导教师：指导教师：王源王源成绩：成绩：计算机与信息工程系2014-2015 学年学年 第一学期第一学期计算机与信息工程系 数据结构课程设计报告1 二 0 一四年十一月二十日计算机与信息工程系数据结构课程设计报告0目录目录1 1 需求分析需求分析221.1 问题描述21.2 设计任务与要求22 2 概要设计概要设计222.1 程序流程图32.2 数据
2、结构设计33 3 详细设计详细设计553.1 程序设计思想53.2 软件模块结构64 4 程序调试分析程序调试分析774.1 测试数据74.2 功能测试图84.3 时间复杂度分析.104.4 上机过程中出现的问题及其解决案.115 5 小结小结1111致谢.12参考文献.12附：核心代码.13计算机与信息工程系 数据结构课程设计报告11 1 需求分析需求分析1.11.1问题描述问题描述该题目采用安徽省铁路运输网的数据进行编程和运行验证。详细可在网上搜索安徽省铁路局管辖线路示意图 ，只要安徽的主干线就可以了。铁路运输网络中由铁路线和火车站的两个主要概念，譬如：1 号铁路线表示京广线，2 号铁路线
3、表示京沪线等。铁路线对象包括铁路线编号,铁路线名称，起始站编号,终点站编号,该铁路线长度，通行标志(00B 客货运禁行,01B 货运通行专线，10B 客运通行专线，11B 客货运通行)。火车站对象包括所属铁路线编号，车站代码，车站名，车站简称，离该铁路线起点站路程及终点站路程。1.21.2 设计任务与要求设计任务与要求（1）查询某站所属的铁路线（2）要求具备新增铁路线的管理功能(3)要求具备新增车站的管理功能(4)针对客运，货运情况能计算任何一个起始车站到任何一个终点站之间的最短路径。并且要求能够显示出该最短路径的各个火车站的经由顺序2 2 概要设计概要设计2.12.1 程序流程图程序流程图在
4、这里简单介绍弗洛伊德算法的核心思想：从图的带权邻接矩阵开始，假设从 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 的最短路径。
5、将它和已经得到的 Vi 到 Vj 的中间顶点的序号不大于 0 的最短路径相比较，从中选出中间顶点的序号不大于 1 的最短路径之后，再增加一个 V2 继续试探，以此类推，经过 n 次比较后，即可求出从计算机与信息工程系 数据结构课程设计报告2Vi 到 Vj 的最短路径。menu=1 menu=4menu=2 menu=3menu=5图 1：程序流程图2.22.2 数据结构设计数据结构设计存储结构：本程序部分函数采用的是文件进行数据的存储，所以采用的是顺 序存储结构，如要添加数据，直接在文件里面进行操作就行了。弗洛伊德算法 中采用的存储结构是图的邻接矩阵。 A.如下为抽象数据类型定义的模板以及抽象
6、数据类型线性表的定义： ADT List 数据对象：D=ai| ai ElemSet,i=1,2,3,n,n0 数据关系：R1=| ai-1,ai D,i=1,2,3,n 基本操作：void readviews() 初始条件:views.txt 已经存在。开 始mainshort_path(); floyed();search（） ；readviews（） ；readways（） ；readlines（） ；switch（menu ）addview（） ；addline（） ；addway（） ；输出谢谢 使用再 会结 束计算机与信息工程系 数据结构课程设计报告3操作结果:将 views.tx
7、t 里面的数据一次存入数组 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 sea
8、rch(); 初始条件：viewsSIZE_view存在，且里面放有相关信息。 操作结果：根据用户输入的车站名查找该车站的相关信息并输出；void addview() 初始条件:views.txt 已经存在。 操作结果:将 views.txt 里面的数据一次存入数组 viewsSIZE_view里，并 将数组里面的存储数据的个数赋值给全局变量 view_count；void addway() 初始条件:ways.txt 已经存在。 操作结果:将 ways.txt 里面的数据一次存入数组 waysSIZE_way里，并将 数组里面的存储数据的个数赋值给全局变量 way_count；void ad
9、dline() 初始条件：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_l
10、istSIZE_viewSIZE_view存储相关的数据；操作结果：输出输入的两个站的最短距离及经过的所有站；void addadta(int menu) 初始条件：views.txt、ways.txt、lines.txt 已经存在。 操作结果：如果 menu=1，则添加车站数据，如果 menu=2，则添加路线数据；计算机与信息工程系 数据结构课程设计报告4B.弗洛伊德算法中，数据结构所用到的思想为图的思想，所以数据结构的设 计主要的目的为便于图的操作的设计。因此我们用了下面这些数据定义。 struct view_info /*城市信息结构*/ int id; char name20; int
11、 code; char shortname20; char LName100;/经过此站的铁路线名称viewsSIZE_view;struct line_info/铁路线信息结构 int Lid; char LName20; int start_id; /始发站 int end_id; /终点 站 int dist; /铁路线长 char sign5; /通行标志linesSIZE_line; struct way_info /铁路度的信息结构 int station1; int station2; int dist; waysSIZE_way; struct path_info /用于最短路
12、径的查询 ;3 3详细设计详细设计3.13.1 程序设计思想程序设计思想设计思路:核心问题：求最短路径(弗洛伊德算法)数据模型(逻辑结构)：带权有向图输入输出：初始数据是从 views.txt、lines.txt、way.txt 三个文件中读入，在读入数据后，用户可以根据选项选择相应的功能，不同的功能有不同的数据输入/输出，比如：查询的功能是要求输入要查询的站的名称，然后输出是该站的相关信息；查询最 int count; int pathSIZE_view；短路径的功能则是输入起点站、终点站的名称，输出则是该段路线距离和经由站等。程序的输入：计算机与信息工程系 数据结构课程设计报告5（1）铁路
13、线信息的输入：依次输入“铁路线代码,铁路线名称，起始站代码, 终点站代码，该铁路线长度、通行标志” ，并且中间以空格隔开。（2）火车站信息的输入：依次输入“车站代码，车站名，车站编号、车站简称，所属铁路线编号” ，并且中间以空格隔开。程序的输出格式；（1）当显示铁路线或者火车站的信息时，与输入时的格式完全一致 ；（2）输出最短路径的长度，以及最短路径的经由顺序；按照程序功能要求，设计了一下各个功能模块：（1）文件读取模块文件读取模块包括读取车站信息模块 readviews、路段权值信息读取模块readlines、铁路线信息读取模块 readlines。这些模块的主要功能为从文件中读取所需的信息
14、。（2）添加信息模块 adddata添加信息模块又包括以下子功能模块：A、添加站点信息模块 addview。B、添加路段权值模块 addway。C、添加铁路线信息模块 addline。（3）查询模块根据用户需求，查询站点信息（4）最短路径查询模块该模块为本软件设计的核心部分。根据该模块可以很方便的找出两个城市的最短路径。该最短路径的算法为常用的弗洛伊德算法。（5）操作菜单模块该模块主要用于与用户的交互，一个界面友好的菜单可以提高软件的人机交互体验。3.23.2 软件模块结构软件模块结构(1)主程序模块，其中主函数为：oid main() 新增火车站；新增铁路线；查询火车站的信息； 针对客运、货
15、运情计算机与信息工程系 数据结构课程设计报告6况，求两站之间的最短路径及其经由顺寻；退出界面 (2)文件模块为:void readways()； void readviews()； void readlines() (3)图模块为：void short_path()；void floyed() (4)查询函数和添加函数 void search()；void adddata(in menu)； void addway()； void addline()；void addview() 函数的调用：进入主函数，调用文件模块各函数以读取数据；选择 1 或 2，则调用 void adddata(in m
16、enu),其中若选择 1，则调用 void addview()函数；若选择 2，则调用 void addline()和 void addway()函数；选择 3，调用 void search()函数进行查询；选择 4，调用 void short_path()和 void floyed()函数以得到最短路径。4 4 程序调试分析程序调试分析4.14.1 测试数据测试数据数据读取如下：计算机与信息工程系 数据结构课程设计报告7图 2：数据读取显示图 3：操作界面显示4.24.2功能测试截图：功能测试截图：计算机与信息工程系 数据结构课程设计报告8输入 1，增加车站信息如下：图 4：增加车站信息 输入 2，增
