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

数据库课程设计

一全国铁路咨询系统

目录

'~I_*--I~*/\-4*I.*1**!*•，,*!**1**!**!•*1**1*»1**1**1**!**1**!**?**1**!**1**!*“，*!*“■—>•1*•£,*1**!**!*»!<*?<•*1**!**1**?**!*•»*1*

_■、U八/广Jnl**j»q.*j»*j»*j»»j*q.*jw*j**T»*j»q.*7**T**7**T**j»*j**7*»Y**7**j**7**j»*7**j**7**j»q.«■»j»*j»q、

而刁、刀1/13

I卜******************************************6

储存结构设.计**************************************8

四详细设计******************************************11

五IIIIj▲_||||.卜.「rj».**.»、r*j1»****.「rj%.卜rj*r*j1***3**1*K1>r*j1**rjw.!卜*r*j2»*r*j4«**1*K1««I»»•****KJ**rIj«»•***rj1«**2^.♦「!**rji»>«A**1**2^17

xJiill'•I•-A.-/r-4-f-T««t*«£««t««?««£»**««t««f««£««X**1^*1**1^

川川TT\</V您“"不不不不不*********不*****不"***********不****18

»*I/-jfr--<1*»£**t«■的«£«■”■曲^4»£*^4*L«•船■”一»*t«■»■曲

七心待体会*********宇****宇*********宇****宇************26

一、需求分析

1、问题描述

由于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中

的时间尽可•能短，出门旅游的游客则期望旅费尽可能省。编制一个全国城市间的交通咨询程

序，为旅客提供两种最优决策的交通咨询。

2、根据铁路的特征，数据的储存需要使用图的结构。每个城市之间有不同的车次，每个

车次的始发站、路过车站和终点站都不一样，所以两个城市之间就有指向明确的边，是一个

有向图；而由于车次的不一样，所以发车时间，至ij站时间，价格等也会不一样；所以每两个

点之间不止两条边，可能存在不同的多条边。

3、功能需求

铁路咨询的对象是用户，所以，需要一个对用户友好的功能菜单，根据用户可能

需要的实际需求，功能菜单中可能会包括以下要点：

1：显示所有车站信息

2:显示所有车次信息（包括时刻表）

3:查询车站信息

4:查询两个城市之间的铁路信息

5:增加或删除车站

6:增加或删除铁路信息

7:增加、删除或修改时刻表、距离和价格

8:寻找两城市间最省钱的一条路径

9:寻找两城市间最省时间的一条路径

10:寻找两城市间所有路径(按费用从低到高排序输出)

11：寻找两城市间所有路径(按所用时间从少到多排序输出)

12:退出咨询系统

3、图的初始数据从文本中读入，文本是老师给的标准数据。

4、输入及输出格式

:输入格式：

A:图的初始数据输入

数据的初始化是需要从文本中读入的，所以不需要有专门的文本输入函数，只需要给

出读文本的函数input()；使用input()函数从测试数据的三个文本中读入数据，然后使用

创建图的函数CreateGraph()创建起整个图。初始数据的读入，分别是从stalion.txt中读入

每个城市站点的名称的城市编号，从iinfonnation.txt中读入每个城市间的铁路信息，从

railway.txt中读入所有铁路线的信息。

如：

以下从station.txt中节选部分

0北京

1广州

2石家庄

3郑州

4武汉

5长沙

以下从mtorniation.txt中选部分

出发城市编号到达城市编号车次里程费用出发时刻到达时刻

02100028762.500000246

0210162877200600275

08100113723.500000117

08101713728.5()06()0163

01310021199156.500001028

1610081257162.5()0001077

以下从railway.txt中节选部分

各条铁路线上城市编号(此行可去掉)

京广线0234561

京九线0131412

京沪线08910II7

陇海/p>

B:用户要求输入

(1)用户在使用本程序时，会要求用户输入各种数据，如城市编号id、抉择选项y/n等；用户

只需要按照程序菜单的要求输入即可。如城市编号id就是初始化数据(文本数据)中每个

城市就有的编号，用户在不知道城市编号之前先查看一下城市信息就可以清楚明了的知道

城市id了。

⑵:输出格式

在系统的管理下，为了用户的查询方便，需要有多重输出方式。如每条铁路

线上信息的输出。这里面就包括了，在每条铁路上所有车次信息，每个车次始发

站信息、过站信息和终点站信息。

样例如下：

兰新线中有以下车次：

1005次列车运行情况：

出发城市到达城市车次距离(km)出发时间到达时间费用(元)

兰州酒泉10057480:010:41102

酒泉乌鲁木齐100579710:5122:14152.5

乌鲁木齐阿拉山口100547722:245:1364.5

1013次列车运行情况：

出发城市到达城方车次距离(km)出发时间到达时间费用(元)

阿拉山口乌鲁木齐10134770:06:4964.5

乌鲁木齐酒县10137976:5918:22152.5

酒泉兰州101374818:325:13102

对于每个城市信息的输出，只需要输出经过每个城市的铁路新路即可，当然必须得输出

城市站点的id,方便用户的查询和管理

样例如下：

城市编号城市名称过站铁路线

0北京京广线京九线京沪线

1广州京广线

2石家庄京广线

3郑州京广线陇海线

4武汉京广线

3长沙京广线

6株洲京广线沪昆线

7上海京沪线沪昆线

—、概要设计

L数据特性分析

：整体结构分析

铁路交通咨询模拟系统管理的是全国的各个城市间的铁路信息。对于整体的全

国铁路信息来说，每一个城市站点就是一个顶点节点，城市与城市之间的每一个车

次信息就是一条有向边。所有整个咨询系统应该是一个有向图结构。从A城市出发

到B城市，可能会有多个车次。

如下例：

出发城市到达城市车次距离(km)出发时司到达时间费用(元)

北京石家庄10002870:04:662.5

北京石家庄1016287I:04:3572

所以每两个城市顶点之间就可能会有多条有向边，所以这个图也不会是一个

有

向简单图了。为了城市节点能够动态的扩充和删除不受影响，我对于顶点的储存采

用链表结构不使用顺序表结构，定义一个顶点链表类VertexList。这样，虽然链表查

询和其节点的删除的时间复杂度受到了一定的影响，但这样设计出来的铁路网图才

更具有一般性个实用性。对于查找的时间复杂度问题的解决，我在后面也会给出方

案。

（2）:城市顶点分析

对于每一城市来说，在全国的铁路网中，它就是一个火车站节点。每一个火车,

它都应该会有自己的名字，过站的铁路线等。为了咨询系统管理和维护的方便，在

文木数据中，我们就人为的给每一个城市都编上序号id,每一个不同id对应了一

个不同的城市节点。由于每个城市的id都是唯一的，所以在顶点的链表结构里面，

完全可以定义一个哈希表haxi[n],对于haxi[i]夹说，它存储的就是id为i的城市

在内存中地址。这样，顶点链表在哈希表的支持下，就能完美解决查找、添加、

删除的时间复杂度问题了.

在整个铁路网中，每一个城市就是顶点，每一个顶点，就是应该有一个边琏表

用于储存此城市能到达所有城市的各个不同车次的信息，也就是各个不同的边。

如：

出发城市编号到达城市编号乍次里程费用出发时刻到达时刻

02100028762.500000246

0210162877200600275

从上例我们可以看出，对于每个顶点的不同边来说，每一个不同的边就有一个独有

的车次。所以这样，对于边的储存，我们也可以采用哈希表结构。经观察发现，每

一车次都大于1000,所以，哈希表的id=车次-1000；对于编号为a的城市节点

haxifkl

来说，它储存的是为城市a中车次为：1000+k的一条边，边里面就有到达城市、

出发和到达时间、费用、距离等等。

（3）:边数据分析

对于图来讲，边就是一个逻辑结构，沟通顶点与顶点之间的关系。问时了，

边还有其物理特性。他需要储存边的权值等，它需要开辟储存空间来存储数

据。在铁路网中，每两个城市之间不同的车次信息就是一条不同的边，所以,

我需要把物理特性给单独列出来，成为一个类Lineinformation,用于表示边

的物理信息。对于图中抽象的边，也需要定义一个类EdgeNodc,用于沟通

图中原木孤立的顶点，使之变成一个完整的图

2.整体概要设计

三.前面，我提到了有顶点类station.顶点链表类VertexList.边的物理类

Lineinformalion和边的逻辑类EdgeNode、火车线路类railway；对于整个完整的图类来说，还

有两个主要的类没有提及.那就是图类RailwayNet和管理图类的类management,,当然对于

图中需要完成各个不同功能的时候，我还写了许多的辅助类。如查找两个车站之间所有路径

时需要用到的LinStack.当然还有LinStack的类的基石StackNode类。整个咨询系统还有许

多的结构体，这些结构体的功能我就不一一叙述了，详细可见源代码的注释。卜.面我就列出

各个类的关系图

四.储存结构设计

1、存储结构的确定

1.数据结构的目的是有效组织和处理数据。为了有效组织和处理数据,

先要分析多项式操作的特点和指针所占空间比例，然后确定最优的存储结构。

2.铁路网是由铁路和火车站构成，每个火车站相当于一个定点，每新建一条铁路就相当

于新建定点之间的边

2、车站之间可以任意到达，可直接相连，也可以间接相连，且怎么连接是不固定的。

3.综上所述，资源管理器的存储结构采用树形结构。

类的结构设计图：

management类图：

Railway类图：

VcrtcxList类图:

Railway类图：

Lineinforination类图:

EdgeNode结构图：

Station类图;

U!详细设计

1.管理类management

classmanagement(

private:

vector<station>m_city;

vector<LineInformation>medge;

vector<rai1way>m_rai1;

Rai^wayNetmgraph;

public:

voidinput();

voidVertex!)isplay();

〃边的愉出闲数，输出一条边的信息

voidEdgeDisp1ay(Edg?Node*edge);

〃输出函数，被RaiIwayDisplay()调用

voidNextDisplay(EdgeNode*edge,LinStack<int>&UsedTrainNumber,inta);

voidRaiIwayDisplay();

voidSearchStation();

voidSearchRai1()：

voidEditSlationO;

voidEditRai1();

voidEditInformal!on();

voidShortestCost();

voidShortestTimeO;

voidSearchAll(vector<timeandcostpath>&AlIPath);

voidPathDispaly(vector<l.ineInformation>&path);

voidOrderOnCost();

voidOrderOnTime();

2.图类RailwayNet

〃全国铁路信息网类（邻接友图类）

classRailwayNet{

private:

VertexListvertex;//顶点链表

vector<railway>m_rai1：

〃私有的函数，以深度优先遍历的方式寻找两点之间的所有路径

voidDepthFirstSearchPath(vector<timeandcostpath>&pa,time_and_cost_path&p,

EdgeNode*edge,intterminal,LinStack<int>&UsedVertex);

〃私有函数，以Dijkasira算法寻找最节省时间的路径

voidShortestCost(vectorO.ineInformation>&Optima1Path,intorigin,intterminal);

//获取起点origin到终点terminal的最少用时

voidShortestTime(intorigin,intterminal);

voidShortest?ime2(vector<l.ineInformation>&OptimalPath,intorigin,intterminal);

〃快速排序

voidQuicksort(vecto：'<timeandcostpath>&AllPath,intlow,inthigh,intoption);

public:

VertexList&Vertex0{returnvertex;}

vector<railway>&GetRail(){returnm_rai1;}

〃插入顶点

voidInsertVertex(station*s)：

〃在顶点vl和v2之间插入一条边(边的起点为vl,终点为v2)

voidInsertEdge(intvl,intv2,EdgeNode*&ed);

〃删除编号为id的城市顶点

voidDeleteVertex(intid);

〃删除边edge

voidDeleteEdge(intvl,intv2);

〃创建一个邻接表图

voidCreateGraph(RaiIwctyXel&graph,veclor<st<iticn>&city,vcctor<LincInlormalion>

&.edge,vector<railway>&rai1);

//输出图

voiddisplay(RaiIwayXet&graph);

〃返回顶点vl和v2的第一条边

EdgeNode*constGetFirstEdge(intvl,intv2);

〃获取起点origin到终点terminal的最少费用

floatGctShortcstCost(intorigin,intterminal,Linelnformation&edge);

〃获取边路径path中的用时

intGotPathTime(vector<LincInformation>&path);

〃获取边路径path中的费用

floatGetPathCost(vector<LineInformation>&path)：

〃对vector中的元素按照要求排序［option为1表示以最行钱方式，为2表示以最行时方式】

voidSort(vector<timeandcostpath〉&AllPath,intoption)：

〃求点origin到terminal的所有路径

voidGetAl1Path(vector<timeandcostpath>&Al(Path,intorigin,intterminal);

//求点origin到terminal的最短“路径”(路程最短或时间最省)【使用Dijkastra算法】

voidBestOption(vector<LineInformation>&OptimalPath,intoption,intorigin,int

terminal);

}；

3.顶点链表类

〃顶点链表类

classVertexList{

private:

station*head;〃头指针

intsize;〃堆表的大小(元素的个数)

station*haxi[1000]：〃哈希表，内存右.节点的地址(哈希表中的下标与对应城市节点的ID

相等)

public:

VertexList();

'VertcxListO;

station*&GetHeadO{returnhead;}

int&GetSizeO{returnsize;}

〃按照id从小到大的限序将city插入链表中

voidinsert(station*city);

〃删除城市编号为id的节点

voidDelete(intid);

〃根据城市的id获取城市节点

station*GetVertex(intid);

station**GetVertexHaxi(){returnhaxi;}

intIsVertexExist(intid);

}；

4.顶点类

classstation{

private:

stringmname;

intm_id;

vector<string>mrail;

station*prior;〃指向上一个车站

station*next;.//指向下一个车站

l：(lge\'ode*head;//指向第一条边节点

intm_sizc：〃边捱表的大小

EdgeNode*haxi[100];〃以此车•站为始发站的边的哈希表(下标为：车次7000)

vcctor<IIAXI>ha2;//以此车站为终点的边在其哈希表中的卜标

public:

station。；〃默认构造函数

station(stringna,i.iti);〃构造函数

station(conststation&sta);〃复制构造函数

voidDelete。"/删除函数

〃接口函数

string&GetName(){returnm_name：}

int&GetId(){returnmid;}

vector<string>&Get?ail0{returnm_rail;}

station*&GetPrior(){returnprior;}

station*&GetNext(){returnnext;}

EdgcNodc*&GetHead0{returnhead;}

int&GetSizeO{returnmsize;}

EdgcNodc**GctHaxi(){returnhaxi;}

vector<HAXl>&GetHaO{returnha2;}

)；

5.边节点类EdgeNode

〃边结点结构体

structEdgcNodc{

UneInformationinformation;

EdgcNodc*ncxt://下一个边结点

EdgeNode*prior;〃上一个边节点

}；

6.边物理类Lineinformation

classl.inelnformation{

private:

intm_Depart!d;〃出发城市编号

intm_ArriveId：〃到达城市编号

intm_TrainNumber;〃车次

intm_distance;〃车程

floatmcost;〃费用

intm_DepartTime;//出发时间

intm_ArriveTime;//到达时间

publie:

//默认构造出数int.DepartId=0,intArriveId=O,

LineInformation(intDepartId=0,int/\rriveld=0.intTrain=0,intdistance=-1,

floatcost=0,intDcpartTimc=-1,intArrivcTine=-1);

//复制构造函数

Lineinformation(constI.ineInformation&1);

,Lineinformation(){};

I.inohiformationoperator=(constI.inelnformation&e);

〃接口函数

int&GetDepartTime(){returnmDepartTime;}

int&GctArrivcTimc(){returnm_ArrivcTimc;}

int&GetTrainNumberO{returnmTrainNumber;}

int&GetDepartldO{returnm_DepartId;}

int&GetArriveld(){returnmArriveld;}

int&GetDistance()(returnmdistance;}

float&GetCost(){returnm_cost;)

)：

7.火车线路类railway

classraiIway{

private:

stringmname;〃火车线名

vector<int>mstation;〃线路进过的火车站的id

public:

raiIway(strings=*"):m_name(s){}

string&GetName();

vector<int>&GetStationO;

voidDelete(inta);

}:

8.自定义栈类

template<classT>classI.inStack;〃前视定义，否则友元无法定义

template〈classT>〃模板类型为T

classStackNode{

friendclassLinStac<<T>;〃定义类LinStack〈T》为友元

private:

Tdata;〃数据元素

StackXode<T>*next;〃指针

public:

〃构造函数1,用于构造头结点

StackNode(StackNodc<T>*plrNext=NULL);

〃构造函数2,用于构造其他结点

StackNode(constT&icem,=NULL);

^StackNode(){};

)；

template<classT>

classI.inStack(

private:

Stack\ode<T>*head;〃头指针

intsize;〃数据元素个数

public:

LinStack(void);〃构造函数

'LinStack(void);〃析构函数

voidPush(constT&item);//入栈

TPop(void);〃出栈

TGetTop(void)const;//取栈顶元素

intNotEmpty(void)const;〃堆栈非空否

boolIsInStack(Ta);〃判断元素a是否在栈中

voidEmpty0;〃清空栈

intGetSizeO