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

数据库课程设计

—全国铁路咨询系统

目录

一． 需求分析****************************************** 3

二． 概要设计****************************************** 6

三． 储存结构设计************************************** 8

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

五． 用户手册****************************************** 17

六． 测试数据****************************************** 18

七．心得体会****************************************** 26

一、 需求分析

1、 问题描述

由于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中 的时间尽可能短，出门旅游的游客则期望旅费尽可能省。编制一个全国城市间的交通咨询程 序，为旅客提供两种最优决策的交通咨询。
根据铁路的特征，数据的储存需要使用图的结构。每个城市之间有不同的车次，每个车次的始发站、路过车站和终点站都不一样，所以两个城市之间就有指向明确的边，是一个有向图；而由于车次的不一样，所以发车时间，到站时间，价格等也会不一样；所以每两个点之间不止两条边，可能存在不同的多条边。

2、 功能需求

铁路咨询的对象是用户，所以，需要一个对用户友好的功能菜单，根据用户可能需要的实际需求，功能菜单中可能会包括以下要点：

1：显示所有车站信息

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

3: 查询车站信息

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

5: 增加或删除车站

6: 增加或删除铁路信息

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

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

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

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

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

12：退出咨询系统

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

3、 输入及输出格式

(1) :输入格式：

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

以下从information.txt中节选部分
出发城市编号 到达城市编号 车次 里程 费用 出发时刻 到达时刻
0 2 1000 287 62.5 0000 0246
0 2 1016 287 72 0060 0275
0 8 1001 137 23.5 0000 0117
0 8 1017 137 28.5 0060 0163
0 13 1002 1199 156.5 0000 1028
1 6 1008 1257 162.5 0000 1077

以下从railway.txt中节选部分
各条铁路线上城市编号（此行可去掉）
京广线 0 2 3 4 5 6 1
京九线 0 13 14 12
京沪线 0 8 9 10 11 7
陇海线 18 10 3 20 24 19

B：用户要求输入
用户在使用本程序时，会要求用户输入各种数据，如城市编号id、抉择选项y/n等；用户只需要按照程序菜单的要求输入即可。如城市编号id就是初始化数据（文本数据）中每个城市就有的编号，用户在不知道城市编号之前先查看一下城市信息就可以清楚明了的知道城市id了。

(2) :输出格式

在系统的管理下，为了用户的查询方便，需要有多重输出方式。如每条铁路线上信息的输出。这里面就包括了，在每条铁路上所有车次信息，每个车次始发站信息、过站信息和终点站信息。
样例如下：
兰新线中有以下车次：
1005次列车运行情况：
出发城市 到达城市 车次 距离(km) 出发时间 到达时间 费用(元)
兰州 酒泉 1005 748 0：0 10：41 102
酒泉 乌鲁木齐 1005 797 10：51 22：14 152.5
乌鲁木齐 阿拉山口 1005 477 22：24 5：13 64.5

1013次列车运行情况：
出发城市 到达城市 车次 距离(km) 出发时间 到达时间 费用(元)
阿拉山口 乌鲁木齐 1013 477 0： 0 6：49 64.5
乌鲁木齐 酒泉 1013 797 6：59 18：22 152.5
酒泉 兰州 1013 748 1832 5：13 102

对于每个城市信息的输出，只需要输出经过每个城市的铁路新路即可，当然必须得输出城市站点的id，方便用户的查询和管理

样例如下：
城市编号 城市名称 过站铁路线
0 北京 京广线 京九线 京沪线
1 广州 京广线
2 石家庄 京广线
3 郑州 京广线 陇海线
4 武汉 京广线
5 长沙 京广线
6 株洲 京广线 沪昆线
7 上海 京沪线 沪昆线

二、 概要设计

1. 数据特性分析
（1） ：整体结构分析
铁路交通咨询模拟系统管理的是全国的各个城市间的铁路信息。对于整体的全
国铁路信息来说，每一个城市站点就是一个顶点节点，城市与城市之间的每一个车
次信息就是一条有向边。所有整个咨询系统应该是一个有向图结构。从A城市出发
到B城市，可能会有多个车次。
如下例：

出发城市 到达城市 车次 距离(km) 出发时间 到达时间 费用(元)
北京 石家庄 1000 287 0： 0 4： 6 62.5
北京 石家庄 1016 287 1： 0 4：35 72

所以每两个城市顶点之间就可能会有多条有向边，所以这个图也不会是 一个有
向简单图了。为了城市节点能够动态的扩充和删除不受影响，我对于顶点的储存采
用链表结构不使用顺序表结构，定义一个顶点链表类VertexList。这样，虽然链表查
询和其节点的删除的时间复杂度受到了一定的影响，但这样设计出来的铁路网图才
更具有一般性个实用性。对于查找的时间复杂度问题的解决，我在后面也会给出方案。

（2）：城市顶点分析
对于每一城市来说，在全国的铁路网中，它就是一个火车站节点。每一个火车，
它都应该会有自己的名字，过站的铁路线等。为了咨询系统管理和维护的方便，在
文本数据中，我们就人为的给每一个城市都编上序号id，每一个不同id对应了一
个不同的城市节点。由于每个城市的id都是唯一的，所以在顶点的链表结构里面，
完全可以定义一个哈希表haxi[n]，对于haxi[i]来说，它存储的就是id为i的城市
在内存中地址。 这样，顶点链表在哈希表的支持下，就能完美解决查找、添加、
删除的时间复杂度问题了。
在整个铁路网中，每一个城市就是顶点，每一个顶点，就是应该有一个边链表
用于储存此城市能到达所有城市的各个不同车次的信息，也就是各个不同的边。如：

出发城市编号 到达城市编号 车次 里程 费用 出发时刻 到达时刻
0 2 1000 287 62.5 0000 0246
0 2 1016 287 72 0060 0275

从上例我们可以看出，对于每个顶点的不同边来说，每一个不同的边就有一个独有
的车次。所以这样，对于边的储存，我们也可以采用哈希表结构。经观察发现，每
一车次都大于1000，所以，哈希表的id=车次-1000；对于编号为a的城市节点haxi[k]
来说，它储存的是为城市a中车次为：1000+k的一条边，边里面就有到达城市、
出发和到达时间、费用、距离等等。

（3）：边数据分析
对于图来讲，边就是一个逻辑结构，沟通顶点与顶点之间的关系。同时了，
边还有其物理特性。他需要储存边的权值等，它需要开辟储存空间来存储数
据。在铁路网中，每两个城市之间不同的车次信息就是一条不同的边，所以，
我需要把物理特性给单独列出来，成为一个类LineInformation，用于表示边
的物理信息。对于图中抽象的边，也需要定义一个类EdgeNode，用于沟通
图中原本孤立的顶点，使之变成一个完整的图

2.整体概要设计

前面，我提到了有顶点类station、顶点链表类VertexList、边的物理类LineInformation和边的逻辑类EdgeNode、火车线路类railway；对于整个完整的图类来说，还有两个主要的类没有提及，那就是图类RailwayNet和管理图类的类management。当然对于图中需要完成各个不同功能的时候，我还写了许多的辅助类。如查找两个车站之间所有路径时需要用到的LinStack，当然还有LinStack的类的基石StackNode类。整个咨询系统还有许多的结构体，这些结构体的功能我就不一一叙述了，详细可见源代码的注释。下面我就列出各个类的关系图

三． 储存结构设计
1、 存储结构的确定

数据结构的目的是有效组织和处理数据。为了有效组织和处理数据，先要分析多项式操作的特点和指针所占空间比例，然后确定最优的存储结构。

1. 铁路网是由铁路和火车站构成，每个火车站相当于一个定点，每新建一条铁路就相当于新建定点之间的边
2. 车站之间可以任意到达，可直接相连，也可以间接相连，且怎么连接是不固定的。
3. 综上所述，资源管理器的存储结构采用树形结构。

2、 类的结构设计图：

management类图：

RailWay类图：

VertexList类图：

RailWay类图：

LineInformation类图：

EdgeNode结构图：

Station类图；

四、详细设计

1. 管理类management

class management{
private:
vector m_city;
vector m_edge;
vector m_rail;
RailwayNet m_graph;
public:
void input();
void VertexDisplay();
//边的输出函数，输出一条边的信息
void EdgeDisplay(EdgeNode *edge);
//输出函数，被 RailwayDisplay（）调用
void NextDisplay(EdgeNode* edge, LinStack & UsedTrainNumber, int a);
void RailwayDisplay();
void SearchStation();
void SearchRail();
void EditStation();
void EditRail();
void EditInformation();
void ShortestCost();
void ShortestTime();
void SearchAll(vector & AllPath);
void PathDispaly(vector & path);
void OrderOnCost();
void OrderOnTime();

2. 图类RailwayNet
//全国铁路信息网类（邻接表图类）
class RailwayNet{
private:
VertexList vertex; //顶点链表
vector m_rail;

//私有的函数，以深度优先遍历的方式寻找两点之间的所有路径
void DepthFirstSearchPath(vector & pa, time_and_cost_path & p, EdgeNode *edge, int terminal, LinStack & UsedVertex);
//私有函数，以Dijkastra算法寻找最节省时间的路径
void ShortestCost(vector & OptimalPath, int origin, int terminal);
// 获取起点origin到终点terminal的最少用时
void ShortestTime(int origin, int terminal);
void ShortestTime2(vector & OptimalPath, int origin, int terminal);
//快速排序
void QuickSort(vector & AllPath, int low, int high, int option);

public:
VertexList & Vertex(){ return vertex; }
vector & GetRail(){ return m_rail; }
//插入顶点
void InsertVertex(station* s);
//在顶点v1和v2之间插入一条边( 边的起点为v1，终点为v2 )
void InsertEdge(int v1, int v2, EdgeNode* & ed);
//删除编号为id的城市顶点
void DeleteVertex(int id);
//删除边edge
void DeleteEdge(int v1, int v2);
//创建一个邻接表图
void CreateGraph(RailwayNet & graph, vector> & city, vector & edge, vector & rail);
//输出图
void display(RailwayNet & graph);
//返回顶点v1和v2的第一条边
EdgeNode* const GetFirstEdge(int v1, int v2);
//获取起点origin到终点terminal的最少费用
float GetShortestCost(int origin, int terminal, LineInformation & edge);
//获取边路径path中的用时
int GetPathTime(vector & path);
//获取边路径path中的费用
float GetPathCost(vector & path);
//对vector中的元素按照要求排序【option为 1 表示以最省钱方式，为 2 表示以最省时方式】
void Sort(vector & AllPath, int option);
//求点origin到terminal的所有路径
void GetAllPath(vectornd_cost_path> & AllPath, int origin, int terminal);
//求点origin到terminal的最短“路径”（路程最短或时间最省）【使用Dijkastra算法】
void BestOption(vector & OptimalPath, int option, int origin, int terminal);

};

3. 顶点链表类
//顶点链表类
class VertexList{
private:
station *head; //头指针
int size; //链表的大小（元素的个数）
station* haxi[1000]; //哈希表，内存有节点的地址(哈希表中的下标与对应城市节点的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(){ return haxi; }
int IsVertexExist(int id);
};

4. 顶点类
class station{
private:
string m_name;
int m_id;
vector m_rail;

station* prior; //指向上一个车站
station *next; //指向下一个车站
EdgeNode *head; //指向第一条边节点

int m_size; //边链表的大小
EdgeNode* haxi[100]; //以此车站为始发站的边的哈希表(下标为：车次-1000)
vector ha2; //以此车站为终点的边在其哈希表中的下标
public:
station();//默认构造函数
station(string na, int i);//构造函数
station(const station & sta);//复制构造函数
void Delete();//删除函数
//接口函数
string & GetName(){ return m_name; }
int & GetId(){ return m_id; }
vector & GetRail(){ return m_rail; }
station* & GetPrior(){ return prior;}
station* & GetNext(){ return next; }
EdgeNode* & GetHead(){ return head; }
int & GetSize(){ return m_size; }
EdgeNode** GetHaxi(){ return haxi; }
vector & GetHa(){ return ha2; }
};

5. 边节点类EdgeNode
//边结点结构体
struct EdgeNode{
LineInformation information;
EdgeNode *next; //下一个边结点
EdgeNode *prior; //上一个边节点
};

6. 边物理类LineInformation

class 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 Train = 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_ArriveTime; }
int & GetTrainNumber(){ return m_TrainNumber; }
int & GetDepartId(){ return m_DepartId; }
int & GetArriveId(){ return m_ArriveId; }
int & GetDistance(){ return m_distance; }
float & GetCost(){ return m_cost; }

};

7. 火车线路类railway

class railway{
private:
string m_name; //火车线名
vector<int> m_station; //线路进过的火车站的id
public:
railway(string s = " ") :m_name(s){}
string & GetName();
vector & GetStation();
void Delete(int a);
};

8.自定义栈类

template class LinStack; //前视定义,否则友元无法定义
template //模板类型为T
class StackNode{
friend class LinStack; //定义类LinStack为友元
private:
T data; //数据元素
StackNode *next; //指针
public:
//构造函数1,用于构造头结点
StackNode(StackNode *ptrNext = NULL);
//构造函数2,用于构造其他结点
StackNode(const T& item, StackNode *ptrNext = NULL);
~StackNode(){};
};

template
class LinStack{
private:
StackNode *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操作系统下，VS2013，按F7编译，F5运行。

2. 在程序运行前有预设函数，最好选择预设函数，然后进行测试。

3. 在菜单中选择你想进的功能，然后输入前面的数字即可。

用户菜单如下：
**全国铁路交通咨询模拟****************************
1: 显示所有车站信息
2: 显示所有车次信息（包括时刻表）
3: 查询车站信息"
4: 查询两个城市之间的铁路信息
5: 增加或删除车站
6: 增加或删除铁路信息
7: 增加、删除或修改时刻表、距离和价格
8: 寻找两城市间最省钱的一条路径
9: 寻找两城市间最省时间的一条路径
10:寻找两城市间所有路径(按费用从低到高排序输出)
11:寻找两城市间所有路径(按所用时间从少到多排序输出)
12: 退出咨询系统"
**************************************************"

六、 测试数据

1. 用户菜单

在输入指令一栏输入你想要使用的功能的数字编号。
如：输入1
功能为：显示所有车站信息

由于数据过多，这里只截取部分输出

输入指令：2
功能：查询所有车次信息

数据量太大，也只截取部分输出。

输入指令：3
功能：查询车站信息

车站信息有：
1. 从此车站出发各个车次信息。
2. 从其他车站出发到达此车站的信息

输入指令：4
功能：查询两个车站之间的信息

查询的时候，是由先后顺序的，先输入的是出发城市，后输入的到达城市

输入指令：5
功能：增加或删除车站

样例1：增加成功

样例2：增加失败

错误原因：编号输入错误
编号id为12：九龙
所以此编号已有城市占用，输入错误

样例3：删除成功

现在可查询广州的信息

发现广州此时已不存在，删除成功

样例4：删除失败

错误原因：id为31 的城市不存在

输入指令：6
功能：增加或删除铁路信息

样例1：增加失败

失败原因：id为1的城市已删除，不能再城市1余城市6之间增加铁路

样例2增加成功

此时新建铁路状态：还有铁路线，没有车次
注：想要铁路线有火车运行，必须补充车次信息

样例3：删除成功

样例4：删除失败

失败原因：不存在从城市9到城市13的铁路

输入指令：7
功能：增加、删除或修改时刻表、距离和价格

测试样例：

可查询修改后的价格
出发城市：6 株洲
到达城市：5 长沙

车次为：1022的信息中
价格：999
修改成功！

输入指令：8
功能：寻找两城市间最省钱的路劲

输入指令：9
功能：寻找两城市间最省时间的路劲

输入指令：10
功能：寻找两城市间所有路径(按费用从低到高排序输出)

数据过多，取前二十条显示，我也只截取前一部分数据

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

数据过多，取前二十条显示，我也只截取前一部分数据

注：后面的测试时前面面修改后的结果，所以，计算的结果和初始化数据计算的结果可能会不一致，这是因为只是可能计算会用到我修改后的数据，所以存在不一致的问题。

七、心得体会