《数据结构课程设计-全国铁路交通咨询模拟》由会员分享，可在线阅读，更多相关《数据结构课程设计-全国铁路交通咨询模拟（26页珍藏版）》请在金锄头文库上搜索。
1、 数据库课程设计数据库课程设计全国铁路咨询系统目录目录1需求分析* 32概要设计* 63储存结构设计* 84详细设计* 115用户手册* 176测试数据* 18七心得体会* 26一、一、 需求分析需求分析 1、 问题描述问题描述由于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中 的时间尽可能短，出门旅游的游客则期望旅费尽可能省。编制一个全国城市间的交通咨询 程 序，为旅客提供两种最优决策的交通咨询。 根据铁路的特征，数据的储存需要使用图的结构。每个城市之间有不同的车次，每个 车次的始发站、路过车站和终点站都不一样，所以两个城市之间就有指向明确的边，是一 个有向图；而由于
2、车次的不一样，所以发车时间，到站时间，价格等也会不一样；所以每 两个点之间不止两条边，可能存在不同的多条边。2、 功能需求功能需求铁路咨询的对象是用户，所以，需要一个对用户友好的功能菜单，根据用 户可能需要的实际需求，功能菜单中可能会包括以下要点：1：显示所有车站信息2: 显示所有车次信息（包括时刻表）3: 查询车站信息4: 查询两个城市之间的铁路信息5: 增加或删除车站6: 增加或删除铁路信息7: 增加、删除或修改时刻表、距离和价格8：寻找两城市间最省钱的一条路径9：寻找两城市间最省时间的一条路径10：寻找两城市间所有路径(按费用从低到高排序输出)11：寻找两城市间所有路径(按所用时间从少到
3、多排序输出)12：退出咨询系统图的初始数据从文本中读入，文本是老师给的标准数据。3、 输入及输出格式输入及输出格式(1):输入格式：A：图的初始数据输入 数据的初始化是需要从文本中读入的，所以不需要有专门的文本输入函数，只需要给 出读文本的函数 input（） ；使用 input（）函数从测试数据的三个文本中读入数据，然后使 用创建图的函数 CreateGraph（）创建起整个图。初始数据的读入，分别是从 station.txt 中 读入每个城市站点的名称的城市编号，从 iinformation.txt 中读入每个城市间的铁路信息， 从 railway.txt 中读入所有铁路线的信息。 如：以
4、下从 station.txt 中节选部分0 北京1 广州2 石家庄3 郑州4 武汉5 长沙以下从 information.txt 中节选部分出发城市编号 到达城市编号 车次 里程 费用 出发时刻 到达时刻0 2 1000 287 62.5 0000 02460 2 1016 287 72 0060 02750 8 1001 137 23.5 0000 01170 8 1017 137 28.5 0060 01630 13 1002 1199 156.5 0000 10281 6 1008 1257 162.5 0000 1077以下从 railway.txt 中节选部分各条铁路线上城市编号（此
5、行可去掉）京广线 0 2 3 4 5 6 1京九线 0 13 14 12京沪线 0 8 9 10 11 7陇海线 18 10 3 20 24 19B：用户要求输入 用户在使用本程序时，会要求用户输入各种数据，如城市编号 id、抉择选项 y/n 等； 用户只需要按照程序菜单的要求输入即可。如城市编号 id 就是初始化数据（文本数据）中 每个城市就有的编号，用户在不知道城市编号之前先查看一下城市信息就可以清楚明了的 知道城市 id 了。(2):输出格式在系统的管理下，为了用户的查询方便，需要有多重输出方式。如每条铁路线上信 息的输出。这里面就包括了，在每条铁路上所有车次信息，每个车次始发站信息、过
6、站信 息和终点站信息。样例如下：兰新线中有以下车次：1005 次列车运行情况：出发城市 到达城市 车次 距离(km) 出发时间 到达时间 费用(元)兰州 酒泉 1005 748 0：0 10：41 102酒泉 乌鲁木齐 1005 797 10：51 22：14 152.5乌鲁木齐 阿拉山口 1005 477 22：24 5：13 64.51013 次列车运行情况：出发城市 到达城市 车次 距离(km) 出发时间 到达时间 费用(元)阿拉山口 乌鲁木齐 1013 477 0： 0 6：49 64.5乌鲁木齐 酒泉 1013 797 6：59 18：22 152.5酒泉 兰州 1013 748 1
7、8：32 5：13 102对于每个城市信息的输出，只需要输出经过每个城市的铁路新路即可，当然必须得输出城 市站点的 id，方便用户的查询和管理样例如下：城市编号 城市名称 过站铁路线0 北京 京广线 京九线 京沪线1 广州 京广线2 石家庄 京广线3 郑州 京广线 陇海线4 武汉 京广线5 长沙 京广线6 株洲 京广线 沪昆线7 上海 京沪线 沪昆线2、 概要设计概要设计1.数据特性分析数据特性分析（1）：整体结构分析铁路交通咨询模拟系统管理的是全国的各个城市间的铁路信息。对于整体的全国铁路信息来说，每一个城市站点就是一个顶点节点，城市与城市之间的每一个车次信息就是一条有向边。所有整个咨询系统
8、应该是一个有向图结构。从 A 城市出 发到 B 城市，可能会有多个车次。如下例：出发城市 到达城市 车次 距离(km) 出发时间 到达时间 费用(元)北京 石家庄 1000 287 0： 0 4： 6 62.5北京 石家庄 1016 287 1： 0 4：35 72所以每两个城市顶点之间就可能会有多条有向边，所以这个图也不会是 一个 有向简单图了。为了城市节点能够动态的扩充和删除不受影响，我对于顶点的储存采用链表结构不使用顺序表结构，定义一个顶点链表类 VertexList。这样，虽然链表 查询和其节点的删除的时间复杂度受到了一定的影响，但这样设计出来的铁路网图才更具有一般性个实用性。对于查找
9、的时间复杂度问题的解决，我在后面也会给出方 案。（2）：城市顶点分析对于每一城市来说，在全国的铁路网中，它就是一个火车站节点。每一个火 车，它都应该会有自己的名字，过站的铁路线等。为了咨询系统管理和维护的方便， 在文本数据中，我们就人为的给每一个城市都编上序号 id，每一个不同 id 对应了一个不同的城市节点。由于每个城市的 id 都是唯一的，所以在顶点的链表结构里面，完全可以定义一个哈希表 haxin，对于 haxii来说，它存储的就是 id 为 i 的城市在内存中地址。 这样，顶点链表在哈希表的支持下，就能完美解决查找、添加、删除的时间复杂度问题了。在整个铁路网中，每一个城市就是顶点，每一
10、个顶点，就是应该有一个边链 表用于储存此城市能到达所有城市的各个不同车次的信息，也就是各个不同的边。如：出发城市编号 到达城市编号 车次 里程 费用 出发时刻 到达时刻0 2 1000 287 62.5 0000 02460 2 1016 287 72 0060 0275从上例我们可以看出，对于每个顶点的不同边来说，每一个不同的边就有一个独 有的车次。所以这样，对于边的储存，我们也可以采用哈希表结构。经观察发现， 每一车次都大于 1000，所以，哈希表的 id=车次-1000；对于编号为 a 的城市节点 haxik来说，它储存的是为城市 a 中车次为：1000+k 的一条边，边里面就有到达城市
11、、出发和到达时间、费用、距离等等。（3）：边数据分析对于图来讲，边就是一个逻辑结构，沟通顶点与顶点之间的关系。同时了，边还有其物理特性。他需要储存边的权值等，它需要开辟储存空间来存储 数据。在铁路网中，每两个城市之间不同的车次信息就是一条不同的边，所 以，我需要把物理特性给单独列出来，成为一个类 LineInformation，用于表示 边的物理信息。对于图中抽象的边，也需要定义一个类 EdgeNode，用于沟通图中原本孤立的顶点，使之变成一个完整的图2.整体概要设计整体概要设计前面，我提到了有顶点类 station、顶点链表类 VertexList、边的物理类 LineInformation
12、 和边的逻辑类 EdgeNode、火车线路类 railway；对于整个完整的图类来说，还有两个主要 的类没有提及，那就是图类 RailwayNet 和管理图类的类 management。当然对于图中需要 完成各个不同功能的时候，我还写了许多的辅助类。如查找两个车站之间所有路径时需要 用到的 LinStack，当然还有 LinStack 的类的基石 StackNode 类。整个咨询系统还有许多的 结构体，这些结构体的功能我就不一一叙述了，详细可见源代码的注释。下面我就列出各 个类的关系图3储存结构设计储存结构设计1、存储结构的确定存储结构的确定数据结构的目的是有效组织和处理数据。为了有效组织和处
13、理数据，先要分析多项式 操作的特点和指针所占空间比例，然后确定最优的存储结构。1. 铁路网是由铁路和火车站构成，每个火车站相当于一个定点，每新建一条铁路就相 当于新建定点之间的边 2. 车站之间可以任意到达，可直接相连，也可以间接相连，且怎么连接是不固定的。 3. 综上所述，资源管理器的存储结构采用树形结构。2、类的结构设计图：类的结构设计图：management 类图：RailWay 类图：VertexList 类图：RailWay 类图：LineInformation 类图：EdgeNode 结构图：Station 类图；四、详细设计四、详细设计 1.管理类 managementclass managementprivate:vector m_city;vector m_edge;vector m_rail;RailwayNet m_graph;public:void input();void VertexDisplay();/边的输出函数，输出一条边的信息void EdgeDisplay(EdgeNode *edge);/输出函数，被 RailwayDisplay（）调用void NextDisplay
