数据结构课程设计-全国铁路交通咨询模拟

1、数据库课程设计全国铁路咨询系统目录.需求分析 *二概要设计 *四.详细设计*11五.用户手册*17六.测试数据*18七.心得体会*26一、需求分析1、问题描述由于不同目的的旅客对交通工具有不同的要求.例如,因公出差的旅客希望在旅途中的时间尽可能短,出门旅游的游客那么期望旅费尽可能省.编制一个全国城市间的交通咨询程 序,为旅客提供两种最优决策的交通咨询.根据铁路的特征,数据的储存需要使用图的结构. 每个城市之间有不同的车次,每个车次的始发站、路过车站和终点站都不一样,所以两个城市之间就有指向明确的边,是一个有向图；而由于车次的不一样,所以发车时间,到站时间,价格等也会不一样；所以每两个点 之间不

2、止两条边,可能存在不同的多条边.2、功能需求铁路咨询的对象是用户,所以,需要一个对用户友好的功能菜单,根据用户 可能需要的实际需求,功能菜单中可能会包括以下要点： 1:显示所有车站信息2:显示所有车次信息包括时刻表3:查询车站信息4:查询两个城市之间的铁路信息5:增加或删除车站6:增加或删除铁路信息7:增加、删除或修改时刻表、距离和价格8:寻找两城市间最省钱的一条路径9:寻找两城市间最省时间的一条路径10:寻找两城市间所有路径(按费用从低到高排序输出)11:寻找两城市间所有路径(按所用时间从少到多排序输出)12:退出咨询系统图的初始数据从文本中读入,文本是老师给的标准数据.3、输入及输出格式(

3、1)：输入格式：A:图的初始数据输入数据的初始化是需要从文本中读入的,所以不需要有专门的文本输入函数,只需要给 出读文本的函数input ();使用input ()函数从测试数据的三个文本中读入数据,然后使 用创立图的函数 CreateGraph ()创立起整个图.初始数据的读入,分别是从 station.txt中读 入每个城市站点的名称的城市编号,从 iinformation.txt中读入每个城市间的铁路信息,从 railway.txt中读入所有铁路线的信息.如：以下从station.txt中节选局部0北京1广州2石家庄3郑州4武汉5长沙以下从information.txt中节选局部出发城市

4、编号到达城市编号车次里程费用出发时刻到达时刻02100028762.500000246021016287720060027508100113723.50000011708101713728.50060016301310021199156.5000010281610081257162.500001077以下从railway.txt中节选局部各条铁路线上城市编号(此行可去掉)京广线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等;

5、 用户只需要根据程序菜单的要求输入即可.如城市编号id就是初始化数据(文本数据)中每个城市就有的编号,用户在不知道城市编号之前先查看一下城市信息就可以清楚明了的知 道城市id 了.:输出格式在系统的治理下,为了用户的查询方便,需要有多重输出方式.如每条铁路线上信息的输出.这里面就包括了,在每条铁路上所有车次信息,每个车次始发站信息、过站信息和终点站信息.样例如下:兰新线中有以下车次:1005次列车运行情况:出发城市到达城市车次距离(km)出发时间到达时间费用(元)兰州酒泉10057480 : 010: 41102酒泉乌鲁木齐100579710: 5122: 14152.5乌鲁木齐阿拉山口100

6、547722: 245: 1364.51013次列车运行情况：出发城市到达城市车次距离(km)出发时间到达时间费用(元)阿拉山口乌鲁木齐10134770: 06: 4964.5乌鲁木齐酒泉10137976: 5918: 22152.5酒泉兰州101374818: 325: 13102对于每个城市信息的输出,只需要输出经过每个城市的铁路新路即可,当然必须得输出城市站点的id,方便用户的查询和治理样例如下：城市编号:城市名称过站铁路线0北京京广线京九线京沪线1广州京广线2石家庄京广线3郑州京广线陇海线4武汉京广线5长沙京广线6株洲京广线沪昆线7上海京沪线沪昆线概要设计1.数据特性分析(1):整体结

7、构分析铁路交通咨询模拟系统治理的是全国的各个城市间的铁路信息.对于整体的全 国铁路信息来说,每一个城市站点就是一个顶点节点,城市与城市之间的每一个车 次信息就是一条有向边.所有整个咨询系统应该是一个有向图结构.从A城市出发到B城市,可能会有多个车次.如下例：出发城市到达城市车次距离(km)出发时间到达时间费用(元)北京石家庄10002870:04: 662.5北京石家庄10162871:04: 3572所以每两个城市顶点之间就可能会有多条有向边,所以这个图也不会是一个有向简单图了.为了城市节点能够动态的扩充和删除不受影响,我对于顶点的储存采 用链表结构不使用顺序表结构,定义一个顶点链表类 Ve

8、rtexList.这样,虽然链表查询和其节点的删除的时间复杂度受到了一定的影响,但这样设计出来的铁路网图才 更具有一般性个实用性.对于查找的时间复杂度问题的解决,我在后面也会给出方 案.(2):城市顶点分析对于每一城市来说,在全国的铁路网中,它就是一个火车站节点. 每一个火车, 它都应该会有自己的名字,过站的铁路线等.为了咨询系统治理和维护的方便,在文本数据中,我们就人为的给每一个城市都编上序号id,每一个不同id对应了一个不同的城市节点.由于每个城市的id都是唯一的,所以在顶点的链表结构里面,完全可以定义一个哈希表haxin,对于haxii来说,它存储的就是id为i的城市在内存中地址. 这样

9、,顶点链表在哈希表的支持下,就能完美解决查找、添加、 删除的时间复杂度问题了.在整个铁路网中,每一个城市就是顶点, 每一个顶点,就是应该有一个边链表用于储存此城市能到达所有城市的各个不问车次的信息,也就是各个不同的边.如出发城市编号到达城市编号车次里程费用出发时刻到达时刻021000 28762.500000246021016 2877200600275从上例我们可以看出,对于每个顶点的不同边来说,每一个不同的边就有一个独有的车次.所以这样,对于边的储存,我们也可以采用哈希表结构.经观察发现,每一车次都大于1000,所以,哈希表的id=车次-1000;对于编号为a的城市节点haxik 来说,它

10、储存的是为城市 a中车次为：1000+k的一条边,边里面就有到达城市、 出发和到达时间、费用、距离等等.(3):边数据分析对于图来讲,边就是一个逻辑结构,沟通顶点与顶点之间的关系.同时了, 边还有其物理特性.他需要储存边的权值等,它需要开辟储存空间来存储数据.在铁路网中,每两个城市之间不同的车次信息就是一条不同的边, 所以, 我需要把物理特性给单独列出来,成为一个类Lineinformation ,用于表示边的物理信息.对于图中抽象的边,也需要定义一个类EdgeNode,用于沟通图中原本孤立的顶点,使之变成一个完整的图2. 整体概要设计前面,我提到了有顶点类station、顶点链表类 Vert

11、exList、边的物理类 Lineinformation和边的逻辑类EdgeNode、火车线路类railway ;对于整个完整的图类来说,还有两个主要的 类没有提及,那就是图类RailwayNet和治理图类的类 management.当然对于图中需要完成各个不同功能的时候,我还写了许多的辅助类.如查找两个车站之间所有路径时需要用到的LinStack,当然还有LinStack的类的基石StackNode类.整个咨询系统还有许多的结构体, 这些结构体的功能我就不一一表达了,详细可见源代码的注释.下面我就列出各个类的关系图三.储存结构设计1、存储结构确实定数据结构的目的是有效组织和处理数据.为了有效

12、组织和处理数据,先要分析多项式操 作的特点和指针所占空间比例,然后确定最优的存储结构.1. 铁路网是由铁路和火车站构成,每个火车站相当于一个定点,每新建一条铁路就相当于新建定点之间的边2. 车站之间可以任意到达,可直接相连,也可以间接相连,且怎么连接是不固定的.3. 综上所述,资源治理器的存储结构采用树形结构.2、类的结构设计图：managemen供图：Railway 类图：VertexList 类图：Railway 类图：LineInformation 类图：EdgeNode结构图：Station 类图；四、详细设计1. 治理类 managementclass management priv

13、ate :vector <station > m_city;vector <LineInformation > m_edge;vector <railway > m_rail;RailwayNet m graph;public :void input();void VertexDisplay(); |/边的输出函数,输出一条边的信息void EdgeDisplay( EdgeNode*edge);/输出函数,被 RailwayDisplay ()调用void NextDisplay( EdgeNode edge, LinStack <int >

14、& UsedTrainNumber, int a);void RailwayDisplay();void SearchStation();void SearchRail();void EditStation();void EditRail();void EditInformation();void ShortestCost();|void ShortestTime(); |void SearchAll( vector <time_and_cost_path > & AllPath);void PathDispaly( vector <LineInformati

15、on > & path);void OrderOnCost();void OrderOnTime();2. 图类 RailwayNet/全国铁路信息网类(邻接表图类)class RailwayNet private :VertexList vertex; / 顶点链表 vector <railway > m_rail;/私有的函数,以深度优先遍历的方式寻找两点之间的所有路径void DepthFirstSearchPath( vector <time_and_cost_path > & pa, time_and_cost_path & p,

16、 EdgeNode*edge, int terminal, LinStack <int > & UsedVertex);/私有函数,以Dijkastra 算法寻找最节省时间的路径void ShortestCost( vector <LineInformation > & OptimalPath, int origin, int terminal);/获取起点origin到终点terminal的最少用时void ShortestTime( int origin, int terminal);void ShortestTime2( vector <Li

17、neInformation > & OptimalPath, int origin, int terminal);快速排序void QuickSort( vector <time_and_cost_path > & AllPath, int low, int high, int option); public :VertexList & Vertex() return vertex; vector <railway > & GetRail() return m_rail; /插入顶点void InsertVertex( statio

18、n * s);/在顶点v1和v2之间插入一条边(边的起点为v1,终点为v2 )void InsertEdge( int v1, int v2, EdgeNod白 & ed);/删除编号为id的城市顶点void DeleteVertex( int id);/删除边edgevoid DeleteEdge( int v1, int v2);/创立一个邻接表图void CreateGraph( RailwayNet & graph, vector <station > & city, vector <LineInformation >& edge

19、, vector <railway > & rail); |/输出图void display( RailwayNet & graph);/返回顶点v1和v2的第一条边EdgeNod仓 const GetFirstEdge( int v1, int v2);/获取起点origin 到终点terminal的最少费用float GetShortestCost( int origin, int terminal, LineInformation & edge);/获取边路径path中的用时int GetPathTime( vector <LineInforma

20、tion > & path);/获取边路径path中的费用float GetPathCost( vector <LineInformation > & path);/对vector中的元素根据要求排序option为1表示以最省钱方式,为2表示以最省时方式】void Sort( vector <time_and_cost_path > & AllPath, int option);/求点origin 到terminal的所有路径void GetAllPath( vector <time_and_cost_path > &

21、AllPath, int origin, int terminal);/求点origin到terminal的最短"路径(路程最短或时间最省)【使用Dijkastra 算法】void BestOption( vector <LineInformation > & OptimalPath, int option, int origin, int terminal);3. 顶点链表类/顶点链表类|class VertexList private :station *head; / 头指针int size;/链表的大小(元素的个数)station * haxi1000;/

22、哈希表,内存有节点的地址(哈希表中的下标与对应城市节点的ID相等)public :VertexList();VertexList();station * & GetHead() return head; int & GetSize() return size; /根据id从小到大的顺序将city插入链表中void insert( station * city);/删除城市编号为id的节点void Delete( int id); |/根据城市的id获取城市节点station * GetVertex( int id);station * GetVertexHaxi() retur

23、n haxi; int IsVertexExist( int id);4. 顶点类class station private :string m name;int m_id;vector <string > m_rail;station * prior;/指向上一个车站station *next;/指向下一个车站EdgeNode*head; /指向第一条边节点 int m_size;/边链表的大小EdgeNodc* haxi100;/以此车站为始发站的边的哈希表(下标为：车次-1000)vector <HAXI> ha2; /以此车站为终点的边在其哈希表中的下标 pub

24、lic :station(); /默认构造函数station( string na, int i); / 构造函数 station( const station & sta); / 复制构造函数 void Delete(); / 删除函数/接口函数string & GetName() return m_name; int & GetId() return m_id; vector <string > & GetRail() return m_rail; station * & GetPrior() return prior; station

25、* & GetNext() return next; |EdgeNod仓 & GetHead()return head; int & GetSize() return m_size; EdgeNode* GetHaxi() return haxi; | vector <HAXI> & GetHa() return ha2; )；5. 边节点类EdgeNode/边结点结构体struct EdgeNodeLineinformation information;EdgeNode*next;/下一个边结点EdgeNode*prior;/上一个边节点;6.边物

26、理类 Lineinformationclass Lineinformation private :int m_Departid;/出发城市编号int m_Arriveid;/到达城市编号int m_TrainNumber;/车次int m_distance;/车程float m_cost;/费用int m_DepartTime;/出发时间int m_ArriveTime;/到达时间public :/ 默认构造函数 int DepartId=0, int ArriveId=0,Lineinformation(int Departid = 0, int Arriveid = 0, int Trai

27、n = 0, int distance = -1,float cost = 0,int DepartTime = -1, int ArriveTime = -1);/复制构造函数Lineinformation( const Lineinformation & l);LineInformation();Lineinformation operator=( const Lineinformation & e); |/接口函数int & GetDepartTime()return m_DepartTime; int & GetArriveTime()return m_

28、ArriveTime; int & GetTrainNumber() return m_TrainNumber; int&GetDepartid()returnm_Departid; int&GetArriveid()returnm_Arriveid; int&GetDistance()returnm_distance; float & GetCost() return m_cost; ;7.火车线路类railwayclass railway private :string m_name; / 火车线名vector <int > m_stat

29、ion; /线路进过的火车站的idpublic :railway( string s = " " ) :m_name( s)string & GetName();vector <int > & GetStation();void Delete( int a);)；/前视定义,否那么友元无法定义8.自定义栈类template < class T> class LinStack ;template < class T>/ 模板类型为 Tclass StackNode |friend class LinStack <T&g

30、t; private :/定义类LinStack<T>为友元T data;/数据元素StackNode<T> *next;/指针public : |/构造函数1,用于构造头结点StackNode( StackNode<T> * ptrNext = NULL;/构造函数2,用于构造其他结点StackNode( const T& item ,StackNode<T> * ptrNext = NULI);StackNode(););template < class T>class LinStack private :StackNod

31、e<T> *head;/头指针int size;/数据元素个数public :LinStack( void );/构造函数LinStack( void );/析构函数void Push( const T& item);/入栈T Pop( void );/出栈T GetTop( void ) const;/取栈顶元素int NotEmpty( void ) const;/堆栈非空否bool IsInStack( T a);/判断元素a是否在栈中void Empty();/清空栈int GetSize();/获取栈中元素的个数void display();/输出栈中元素；;五、用户手册1.本程序运行在 Windows操作系统下,VS2021,按F7编译,F5运行.2.任程序运行刖有预设函教,取好送择预攻函