C++数据结构-全国交通咨询模拟报告

数据结构课程设计报告

班级：195182 学号：20181003991 姓名：钟欢 日期：2019.12

一、课程设计题目与要求

1. 课程设计题目：全国交通咨询模拟 2. 问题描述：

出于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能短，出门旅游的游客则期望旅费尽可能省，而老年旅客则要求中转次数最少。 编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。 3. 基本要求：

3.1提供对城市信息进行编辑（如添加或删除）的功能。 3.2城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑 （增 加或删除）的功能。

3.3提供两种最优决策：最快到达或最省钱到达。全程只考虑一种交通工具。 3.4旅途中耗费的总时间应该包括中转站的等候时间。 3.5咨询以用户和计算机的对话方式进行。

二、需求分析 1. 问题描述

搭建一个全国交通咨询模拟系统，可以实现简单的人机互动从而达到咨询的效果。需要完成的功能有，对城市、列车时刻表、航班时刻表进行编辑（手动/文件添加，删除），能够根据出发城市以及到达城市进行相关线路推荐（花费最少线路、耗时最短线路），其中整个线路的耗时总时长包括中转等待时间。 2. 程序的功能：

2.1维护功能：

2.1.1航班操作 2.1.2列车操作 2.1.3更改密码 2.2咨询功能

2.2.1选择出行交通工具 2.2.2选择要查询的信息：

1查询花费最小的路径 ○

2查询耗时最短的路径 ○

2.2.3进行进一步的输入得到所需要的结果

三、设计 1. 设计思想

1.1数据结构设计

1.1.1逻辑结构设计

采用图结构来表示该全国交通网络，用一个结构体来表示时间，结构体内有标准化的（天，时，分）的相关表示以及操作，重载的运算符“-”。全国交通网络中的城市用结点表示，两个城市之间的航线或者列车线用两个结点之间的边来表示。城市结点中包含城市名字、城市编号、第一条航线/列车线以及航线/列车线的数目；边结点中包含到达城市名称，指向下一航线/列车线的指针，以及指向该边所指代航线/列车线信息的指针；航班线/列车线信息结点包含航班号/列车号，出发时间，到达时间，花费时间，花费金额。 1.1.2存储结构设计

采用链式存储结构—邻接表来存储该交通网络图，建立一个城市结点表，相当于顶点表，表示出现在全国交通网络图中的城市的信息，并用指针指向他们之间的相关关系。每一个城市结点又会指出一个指针指向它所包含的相关航线/列车线的信息，相当于邻接矩阵中的边结点，若干航线/列车结点通过指针的链接构成边链表。 1.2算法设计

该交通网络咨询模拟系统包含的主要算法有搜索城市编号，手动增加城市，文件方式增加城市，插入航线/列车线，增加线路，文件方式增加线路，重置图的大小（顶点表/城市表的大小），删除城市，删除线路，更新文件中的信息，输出所有城市，输出所有线路，最小花费路径算法，时间转换成权值的算法，最少耗时路径算法，输出最短路径，核心算法为Dijkstra算法。 1.3菜单设计

菜单分为几个模块。用户模块用于提供给用户进行相关咨询使用，包含交通工具选择，查询最小花费线路，最少耗时路线；维护模块用于提供给管理员进行相关信息维护功能，包含航班，列车操作，更改密码操作（初始密码为 zhonghuan ）。而这些相关操作通过调用相关函数来实现。

2. 设计表示

2.1函数调用关系图

2.1.1主程序流程以及各模块之间调用关系

2.1.2函数调用关系图

2.1.3函数接口规格说明

函数//函数说明（函数接口）

int searchCityNum(const string CityName); //搜索城市编号（城市名称） void addCity(const string CityName);//手动添加城市（城市名称）

void addCityFromFile(const char FileName[MAXFILESIZE]);//文件添加城市（文件名）

void insert(string StartName, LineNode* temp, string EndName);//插入线路（开始地址，线路指针，到达地址） void addLine();//添加线路

void addLineFromFile(const char FileName[MAXFILESIZE]); //文件添加线路（文件名）

void reSize(int size); //重置大小（新的大小） void delCityLine(int i); //删除城市线路（编号） void delLine();//删除线路

void delCity(string CityName);//删除城市（城市名字）

void updateFile(const char FileName[MAXFILESIZE], const string type);//更新文件 void showCity(); //输出城市 void showLine(); //输出线路

void dijkstra_Money(int v0, int* parent, Node* dis); //Dijkstra算法求最小花费路径（城市编号，遍历指针，优先队列的顶点结点）

int timeTransWeight(const Time& t); //时间转化为相应权值（时间）

void dijkstra_Time(int v0, int* parent, Node1* dis); //Dijkstra算法求最短耗时路径（城市编号，遍历指针，优先队列的顶点结点）

void showShortestPath(const string type);//输出最短路径（类型：最小花费/最短耗时）

3. 详细设计

3.1类的数据成员与函数成员设计

//时间

struct Time { int day; int hour; int minute;

friend Time operator - (Time& endtime, Time& st); //\"-\"重载，两个时间相减 };

//边（线路信息） struct Line {

string LineName;

Time StartTime, EndTime; Time SpendTime; float SpendMoney; };

//边结点(存放到达城市地点，以及下一条线路的指针)

struct LineNode { string EndName;

struct LineNode* NextLine; Line* Info; };

//顶点表（城市表）城市结点 struct HeadNode { string CityName; int CityNum;

LineNode* FirstLine; int Amount; };

//顶点节点，保存id和到源顶点的估算距离,优先队列需要的类型 struct Node; //最小花费 struct Node1; //最小路径 //图

class ALGraph { private:

HeadNode* CityList; //城市表 int CityNum; //城市数目

int MaxCityNum; //最大城市数目 int ArcNum; //城市所含线路数目

public:

ALGraph(int size); ~ALGraph();

int searchCityNum(const string CityName); //搜索城市编号 void addCity(const string CityName);//手动添加城市

void addCityFromFile(const char FileName[MAXFILESIZE])//文件添加城市; void insert(string StartName, LineNode* temp, string EndName); //插入线路 void addLine(); //插入线路

void addLineFromFile(const char FileName[MAXFILESIZE]);//文件插入线路 void reSize(int size); //重置图的大小 void delCityLine(int i); //删除城市线路 void delLine(); //删除线路

void delCity(string CityName);//删除城市

void updateFile(const char FileName[MAXFILESIZE], const string type);//更新文件

void showCity();//输出文件 void showLine(); //输出线路

void dijkstra_Money(int v0, int* parent, Node* dis);//Dijkstra算法求最小花费路

径

int timeTransWeight(const Time& t); //时间权值转换

void dijkstra_Time(int v0, int* parent, Node1* dis); //Dijkstra算法求最少耗时路径

void showShortestPath(const string type); //输出最短路径 };

3.1.1主要算法的伪码描述

void dijkstra_Money(int v0, int* parent, Node* dis);//Dijkstra算法求最小花费路径 { priority_queue q; //优化插入和取出最小值两个操作，队列存储最短距离与索引的编号，parent[]记录每个顶点的父亲结点，dis[]记录源点到每个点的估算距离，最后更新为源点到所有顶点的最短距离

bool visited[MaxCityNum]; //判断下标对应的顶点是否算出最短路径或者说是否在最短路径树中

vector visited(MaxCityNum, false);//初始化 dis[v0].money = 0; //源点到源点最短路权值为0 q.push(dis[v0]); //压入队列

while (!q.empty()) {}//队列空说明完成了求解v0到其余各顶点的最短路径 取最小估算距离顶点；

被标记了，就无需对其进行更新最短距离等操作； //松弛操作

while (p) //找所有与它相邻的顶点，进行松弛操作，更新估算距离，压入队列 }

void dijkstra_Time(int v0, int* parent, Node1* dis)//Dijkstra算法求最少耗时路径 { priority_queue q1; parent[]记录每个顶点的父亲结点，di[]记录源点到每个估算距离，最后更新为源点到所有顶点的最短距离

bool visited[MaxCityNum]; //判断下标对应的顶点是否算出最短路径或者说是否在最短路径树中

vector visited(MaxCityNum, false); //初始化 dis[v0].evaluatetime = 0; //源点到源点最短路权值为0 q1.push(dis[v0]); //压入队列

while (!q1.empty()) {}//队列空说明完成了求解v0到其余各顶点的最短路径 取最小估算距离顶点；

被标记了，就无需对其进行更新最短距离等操作； 找出所有相邻点，进行松弛操作，即更新dis //计算中转的时间开销

if (u != v0) { //注意源点到任何点都没有中转时间

int change = timeTransWeight(st - dis[u].et); //当前路线的开车时间-始发站的上一到站时间 t += change; //松弛操作

while (p) //找所有与它相邻的顶点，进行松弛操作，更新估算距离，压入队列}

3.2界面设计及其他模块设计

3.2.1交通模拟咨询系统主界面设计

cout << endl << \"·全国交通咨询系统··\" << endl; cout << setw(28)<<\"请输入您的操作类型：\" << endl; cout << setw(20) << \"1.咨询\" << endl; cout << setw(20) << \"2.维护\" << endl; cout << setw(20) << \"3.退出\" << endl; cout << \"·\" << endl;

3.2.2维护界面设计

while (func) { }

cout << \"1.从文件中添加城市\" << endl; cout << \"2.手动添加城市\" << endl; cout << \"3.删除城市\" << endl;

cout << \"4.从文件中添加线路\" << endl; cout << \"5.手动添加线路\" << endl; cout << \"6.删除线路\" << endl; cout << \"7.显示所有城市\" << endl; cout << \"8.显示所有线路\" << endl; cout << \"9.保存文件\" << endl; cout << \"10.返回\"; cout << endl; cin >> func; ……

3.2.3咨询界面设计 选择出行的交通工具

选择条件（花费最少/耗时最短）

选择出发到达城市显示结果

四、调试分析

1. 调试遇到的问题及问题的解决

1.1程序敲完并且能够成功编译之后，对于程序各个功能测试的时候发现了一些问题：

○1维护板块中的问题主要是文件输入线路时，导入结果总是一些乱码，然后对比分析了文件输入城市时并未出现这样的问题，经过对代码的分析通过不断调试发现问题所在，文件输入内容时是一行一行读入并且输入给相对应的存储变量上去，对于城市的输入，每一行只有编号和城市名称两个内容，结构简单容易读取，而对于文件输入线路时，有各种数字符号时间等的相互交错穿插着，在设置读取内容时，格式设置得并不严格，且导入的文件内容是从网上寻找的航班资料/列车资料等格式不统一，最终我把导入文件做了格式统一化处理，并且代码中文件输入部分也做了相应的格式调整，最终文件输入线路也没有了问题，文件导入城市和线路均能很好地完成。

2用户咨询板块中的主要问题是通过交通模拟咨询之后提供的线路信息出现了莫名其○

妙的错误——花费时间是负值，按照常理这肯定是错的，经过不同调试发现不是输入数据有误，而是程序的本身逻辑有误，在对时间结构体的‘-’操作符进行重载时，没有考虑清楚两个时间之间的多一天少一天的进位关系，从而导致最后的计算结果出现错误，由于默认日期的问题会造成不同天的时刻相减可能为负数，所以当时刻表相减为负数时需要让天数加一，最后通过代码修改，在相关代码后面加了一个判断语句，如果两个时间相减为负值那么就在天数上加一，否则不做处理，最终问题得到有效解决。

2. 算法的时间空间复杂度分析 相关操作函数 int searchCityNum(const string CityName) void addCity(const string CityName) void addCityFromFile(const char FileName[MAXFILESIZE]) void insert(string StartName, LineNode* temp, string EndName) void addLine() void addLineFromFile(const char FileName[MAXFILESIZE]) void reSize(int size) void delCityLine(int i) void delLine() void delCity(string CityName); void updateFile(const char FileName[MAXFILESIZE], const string type) void showCity() void showLine() void dijkstra_Money(int v0, int* parent, Node* dis) int timeTransWeight(const Time& t); //时间转化为相应权值（时间） void dijkstra_Time(int v0, int* parent, Node1* dis) void showShortestPath(const string type)

时间复杂度 空间复杂度 O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) O(n) 五、用户手册

该全国交通咨询模拟系统主要通过键入式人机交互来进行维护与咨询，即通过键盘的输入来获取想要的信息以及达到想要进行的操作。

1. 系统初始化：通过维护界面导入全国交通咨询模拟系统的相关信息从而使得能够提供

有效准确的解决方案。

维护界面登录（初始密码：zhonghuan） 1.航班操作——>1.从文件中添加城市 2.手动添加城市 3.删除城市

4.从文件中添加线路 5.手动添加线路 6.删除线路 7.显示所有城市 8.显示所有线路 9.保存文件 10.返回 2.列车操作同航班操作 3.更改密码 4.返回 2. 用户咨询

通过主界面键入‘1’进入咨询界面 2.1通过键盘输入选择出行交通工具:

1.飞机 2.火车 3.返回

2.2通过键盘输入选择要查询的信息：

1.查询花费最小的路径 2.查询耗时最短的路径 3.返回

2.3根据界面提示完成相关输入（城市名称等）即可得到咨询结果 2.4感谢您使用全国交通咨询模拟系统

六、测试数据及测试结果

测试用例表 测试输入 2->1->1 测试目的 从文件中添加航班城市 2->1->2->手动添加航武汉 班城市 2->1->4 从文件中添加航班 2->2->7 显示所有列车城市 正确输出 城市导入完毕 无输出 无输出 带编号的城市表 实际输出 城市导入完毕 无输出 无输出 带编号的城市表 当前状态 通过 通过 通过 通过 2->2->3->删除列车城阳新 市 2->2->8 显示所有列车线路 2->2->9 保存列车相关线路与城市文件 1->1->1-> 查询花费最武汉->北少的武汉->京 北京的航班 1->1->2-> 查询耗时最三亚->恩短的三亚->施 恩施的航班 无输出 列车时刻表 文件夹相关文本发生更新 无输出 列车时刻表 文件夹相关文本发生更新 通过 通过 通过 1->2->1-> 查询花费最武汉->阳少的武汉->新 阳新的航班 1->2->2-> 查询花费最温州南->少的温州南成都东 ->成都东的列车 武汉 北京 武汉 北京 MU2455 17:55,+0 MU2455 17:55,+0 19:55,+0 02:00,+0 19:55,+0 02:00,+0 459.000 459.000 三亚 武汉 三亚 武汉 JD5627 10:25,+0 JD5627 10:25,+0 12:45,+0 02:20,+0 12:45,+0 02:20,+0 568.000 568.000 中转需要等待 520中转需要等待 520分钟！ 分钟！ 武汉 恩施 武汉 恩施 CZ65 21:25,+0 CZ65 21:25,+0 22:40,+0 01:15,+0 22:40,+0 01:15,+0 863.000 863.000 武汉 阳新 武汉 阳新 D7001 06:12,+0 D7001 06:12,+0 07:08,+0 00:56,+0 07:08,+0 00:56,+0 65.5000 65.5000 温州南 武汉 温州南 武汉 G590 06:14,+0 G590 06:14,+0 13:56,+0 07:42,+0 13:56,+0 07:42,+0 599.000 599.000 中转需要等待 中转需要等待 10621062分钟！ 分钟！ 武汉 成都东 武汉 成都东 D366 07:38,+0 D366 07:38,+0 17:08,+0 09:30,+0 17:08,+0 09:30,+0 592.500 592.500 通过 通过 通过 通过 七、源程序清单：

1.Graph.h//Graph头文件 2.menu.h//菜单头文件

3.Graph.cpp//交通图的相关操作函数源文件 4.main.cpp//主程序源文件

#其他文件

Plane.txt/Train.txt//航班列车文本文件PCity.txt/TCity.txt//城市文本文件

#附录1——全国交通咨询模拟系统源代码

-------------------------------------------------------------------------------

//Graph.h #ifndef _GRAPH_H #define _GRAPH_H #include

#include #include #define MAXFILESIZE 100 using namespace std; //时间 struct Time { }; //边

}

t.hour = t.hour + endtime.hour - st.hour; if (t.hour < 0) { }

//由于默认日期的问题会造成不同天的时刻相减可能为负数，所以当时刻表相减为负数时需要让//比如甘肃到北京 T100 8:00,+0 10:00,+1 北京到长春 T101 7:00,+0 T102 8:30,+0 15:10,+0 //实际上需要到北京后要再等待一天才能到，中途等待时间应该是 '7:00,+1' - '10:00,+1' if (endtime.day < st.day) { }

t.day = t.day + endtime.day - st.day; return t;

t.day++; t.hour += 24; t.day--;

int day; int hour; int minute; //\"-\"重载

friend Time operator - (Time& endtime, Time& st) {

Time t = { 0, 0, 0 };

t.minute = endtime.minute - st.minute; if (t.minute < 0) { }

t.minute += 60; t.hour--;

天数加一

struct Line { }; //边结点 struct LineNode { };

struct HeadNode { };

//顶点节点，保存id和到源顶点的估算距离,优先队列需要的类型 struct Node; //最小花费 struct Node1; //最小路径

class ALGraph { private: public:

int searchCityNum(const string CityName); void addCity(const string CityName);

void addCityFromFile(const char FileName[MAXFILESIZE]); void insert(string StartName, LineNode* temp, string EndName); void addLine();

void addLineFromFile(const char FileName[MAXFILESIZE]); void reSize(int size); ALGraph(int size); ~ALGraph(); HeadNode* CityList; int CityNum; int MaxCityNum; int ArcNum; string CityName; int CityNum; LineNode* FirstLine; int Amount; string EndName; struct LineNode* NextLine; Line* Info; string LineName; Time StartTime, EndTime; Time SpendTime; float SpendMoney;

};

void delCityLine(int i); void delLine();

void delCity(string CityName);

void updateFile(const char FileName[MAXFILESIZE], const string type); void showCity(); void showLine();

void dijkstra_Money(int v0, int* parent, Node* dis); int timeTransWeight(const Time& t);

void dijkstra_Time(int v0, int* parent, Node1* dis); //void bfs_Transit (); //最小中转次数以及路径 void showShortestPath(const string type);

#endif

------------------------------------------------------------------------------- //Graph.cpp #include\"Graph.h\" #include #include #include #include #include #include #include #include #include using namespace std; #define INF 0xffffff

//'>>' 重载

istream& operator >> (istream& in, Time& time) { }

//'<<'重载

char c1, c2, c3; int hour, minute, day;

in >> hour >> c1 >> minute >> c2 >> c3 >> day; time.day = day; time.minute = minute; time.hour = hour; return in;

ostream& operator << (ostream& out, Time& time) {

//数据之间空白用'0'填充 cout.fill('0');

//数据的右对齐与天数的'+'号

out << setw(2) << setiosflags(ios_base::right) << time.hour << \":\" << setw(2) << time.minute <<

<<

\

<<

setiosflags(ios_base::showpos)

<<

time.day

<<

resetiosflags(ios_base::right) }

ALGraph::ALGraph(int size) { }

ALGraph::~ALGraph() { }

//查询城市编号

delete[]CityList;

resetiosflags(ios_base::showpos); //setiosflags(ios_base::showpos) 表示 \"+\" 正号

cout.fill(' '); //fill setiosflags 需手动关闭 return out;

CityList = new HeadNode[size]; int i;

for (i = 0; i < size; ++i) { }

CityNum = 0; MaxCityNum = size; ArcNum = 0;

CityList[i].CityName = \"NULL\"; CityList[i].CityNum = i; CityList[i].FirstLine = NULL; CityList[i].Amount = 0;

int ALGraph::searchCityNum(const string CityName) { }

void ALGraph::reSize(int size) {

if (size <= CityNum) {

return; int i;

for (i = 0; i < CityNum; ++i) { } return -1;

if (CityList[i].CityName == CityName) { }

return i;

}

}

HeadNode* NewList = new HeadNode[size]; int i;

for (i = 0; i < CityNum; ++i) { }

for (i = CityNum; i < size; ++i) { }

delete[]CityList; CityList = NewList; MaxCityNum = size;

CityList[i].CityName = \"NULL\"; CityList[i].CityNum= i; CityList[i].FirstLine = NULL; CityList[i].Amount = 0;

NewList[i] = CityList[i]; //C++可以直接赋值

//手动添加城市

void ALGraph::addCity(const string CityName) { }

//从文件中读取以添加城市

void ALGraph::addCityFromFile(const char FileName[MAXFILESIZE]) {

//cout << \"开始从 \" << FileName << \"中读入并添加城市！\" << endl; ifstream file(FileName); //打开失败返回NULL if (!file) { }

cout << \"打开失败!\" << endl; return; //已存在城市

if (searchCityNum(CityName) != -1) { }

//空间已满

if (CityNum >= MaxCityNum) { }

CityList[CityNum].CityName = CityName; CityList[CityNum].CityNum = CityNum; CityList[CityNum].FirstLine = NULL; CityList[CityNum].Amount = 0; ++CityNum;

++MaxCityNum; reSize(MaxCityNum);

cout << \"The city has in the list!!!\" << endl; return;

}

//添加线路

void ALGraph::addLine() {

string StartName, EndName; //信息输入

cout << \"请输入起点城市：\" << endl; cin >> StartName;

cout << \"请输入终点城市：\" << endl; cin >> EndName;

LineNode* temp = new LineNode; Line* info = new Line; temp->EndName = EndName; cout << \"请输入班次名：\"; cin >> info->LineName;

cout << \"请输入出发时间:(hh:mm,+d)\"; cin >> info->StartTime;

cout << \"请输入到达时间：(hh:mm,+d)\"; cin >> info->EndTime;

info->SpendTime = info->EndTime - info->StartTime; cout << \"请输入票价：\"; cin >> info->SpendMoney; temp->Info = info; //空间已满

if (CityNum + count >= MaxCityNum) { }

//从第二行开始读取城市名字 while (getline(file, line)) { }

cout << \"城市导入完毕！\" << endl; file.close(); //读取后关闭文件

istringstream istr2(line); //利用istringstream类直接将string输入到name string name; istr2 >> name; addCity(name);

MaxCityNum = CityNum + count; reSize(MaxCityNum);

string line; //读取第一行数据，第一行是城市总个数 getline(file, line);

istringstream istr(line); //利用stringstream简化 string 到 int 的类型转换 int count; istr >> count;

insert(StartName, temp, EndName);

}//addLine //插入线路

void ALGraph::insert(string StartName, LineNode* temp, string EndName) { }

string UTF8ToGB(const char* str) {

//获得临时变量的大小

int i = MultiByteToWideChar(CP_UTF8, 0, str, -1, NULL, 0); strSrc = new WCHAR[i + 1]; string result; WCHAR* strSrc; LPSTR szRes;

//原本没有线路的情况 if (p == NULL) { }

//原本有线路的情况 else { }

CityList[StartNum].Amount++; ArcNum++;

q = p->NextLine;

while (q != NULL && EndName != q->EndName) { }

p->NextLine = temp; temp->NextLine = q;

p = q;

q = q->NextLine;

CityList[StartNum].FirstLine = temp; temp->NextLine = NULL;

int StartNum = searchCityNum(StartName); if (StartNum == -1) { }

if (searchCityNum(EndName) == -1) { }

LineNode* p, * q;

p = CityList[StartNum].FirstLine;

addCity(EndName); addCity(StartName);

StartNum = searchCityNum(StartName);

MultiByteToWideChar(CP_UTF8, 0, str, -1, strSrc, i); //获得临时变量的大小

i = WideCharToMultiByte(CP_ACP, 0, strSrc, -1, NULL, 0, NULL, NULL); szRes = new CHAR[i + 1];

WideCharToMultiByte(CP_ACP, 0, strSrc, -1, szRes, i, NULL, NULL); result = szRes; delete[]strSrc; delete[]szRes; return result;

}

//从文件中读取以添加线路

void ALGraph::addLineFromFile(const char FileName[MAXFILESIZE]) { //cout << \"从\" << FileName << \"中读取并导入线路！\" << endl; ifstream file(FileName); if (!file) { cout << \"不能打开文件！\" << endl; return;

}

string catalogue; //存储第一行的目录 getline(file, catalogue);

//从第二行开始读取真正需要存储的信息 string line;

while (getline(file, line)) { istringstream istr(UTF8ToGB(line.c_str()).c_str());; LineNode* temp = new LineNode; Line* info = new Line; temp->Info = info;

string StartName, EndName;

istr >> StartName >> EndName >> info->LineName info->EndTime >>info->SpendMoney;

info->SpendTime = info->EndTime - info->StartTime; temp->EndName = EndName; insert(StartName, temp, EndName);

}

file.close();

}

>> info->StartTime >> //删除i城市为起点的所有路线 void ALGraph::delCityLine(int i) { }

//删除城市，并删除以城市为起点的航班和列车 void ALGraph::delCity(string CityName) { }

void ALGraph::delLine() {

string StartName, EndName; int StartNum;

cout << \"请输入起点城市: \"; cin >> StartName; if (i == -1) { } else { }

delCityLine(i);

for (j = i; j < CityNum - 1; ++j) { }

--CityNum;

//cout << \"删除 \" << CityName << \" 成功！ \" << endl;

CityList[j] = CityList[j + 1]; cout << \"没有找到该城市!\" << endl; int i, j;

i = searchCityNum(CityName); if (p->NextLine == NULL) { }

delete p->Info; delete p; while (p->NextLine) { }

q = p;

p = q->NextLine; delete q->Info; delete q; LineNode* p, * q; p = CityList[i].FirstLine; if (p == NULL) { }

return;

StartNum = searchCityNum(StartName); if (StartNum == -1) { }

cout << \"请输入终点城市: \"; cin >> EndName;

//显示起点城市的所有线路，并判断是否能到达该终点城市 bool flag = false; LineNode* p, * q;

cout << \"起点城市与终点城市的路线有: \" << endl;

cout << \"【出发城市】【到达城市】【班次名】【出发时间】【到达时间】【用时】【票价】\" << endl; for (p = CityList[StartNum].FirstLine; p != NULL; p = p->NextLine) {

if (p->EndName == EndName) {

cout << setw(8) << StartName << \" \" << setw(8) << EndName << \" \" << setw(6) << cout << \"未找到该城市!\" << endl; return;

p->Info->LineName << \" \" << p->Info->StartTime << \" \" << p->Info->EndTime << \" \" << p->Info->SpendTime << \" \" << setiosflags(ios_base::showpoint) << p->Info->SpendMoney << resetiosflags(ios_base::showpoint);

//一条路 if (q == NULL) {

if (p->Info->LineName != LineName) { } else {

CityList[StartNum].FirstLine = q; CityList[StartNum].Amount--; cout << \"没有该班次！\" << endl; return;

//该出发城市能到达到达城市，开始删除线路 string LineName;

cout << \"请输入你想要删除的班次：\" << endl; cin >> LineName;

p = CityList[StartNum].FirstLine; q = p->NextLine; }

cout << endl; if (flag == false) { }

cout << \"该出发城市没有通往到达城市的班次！\" << endl; return; }

flag = true;

}

}

}

ArcNum--; delete p->Info; delete p; p = NULL; return;

//多条路

while (q->Info->LineName != LineName && q->NextLine) { }

//线路遍历完成

if (q->Info->LineName != LineName) { }

//寻找成功 else { }

p->NextLine = q->NextLine; CityList[StartNum].Amount--; ArcNum--; delete q->Info; delete q; return;

cout << \"没有该班次！\" << endl; return; p = q;

q = q->NextLine;

//更新文件

void ALGraph::updateFile(const char FileName[MAXFILESIZE], const string type) {

int i;

LineNode* p = NULL;

if (type == \"City\" || type == \"城市\") {

//第一行导出城市个数 file << CityNum << endl; ofstream file(FileName); if (!file) { }

cout << \"不能打开文件\" << FileName << endl; return;

}

for (i = 0; i < CityNum; ++i) { }

//cout << \"城市信息更新到\" << FileName << \" 完成!\" << endl;

file << CityList[i].CityName << endl;

else if (type == \"Line\" || type == \"线路\") {

file << \"【出发城市】【到达城市】【班次名】【出发时间】【到达时间】【用时】【票价】\" << endl; for (i = 0; i < CityNum; ++i) {

for (p = CityList[i].FirstLine; p != NULL; p = p->NextLine) {

file << setw(8) << CityList[i].CityName << \" \" << setw(8) << p->EndName << \" \" << cout.fill('0');

file << p->Info->StartTime << \" \" << p->Info->EndTime << \" \" <<

setw(6) << p->Info->LineName << \" \";

p->Info->SpendTime << \" \" << setiosflags(ios_base::showpoint) << p->Info->SpendMoney << resetiosflags(ios_base::showpoint); }

//输出城市

void ALGraph::showCity() { }

//输出线路

void ALGraph::showLine() {

if (ArcNum == 0) {

cout << \"系统中没有任何线路！\" << endl; return; int i; string a;

if (CityNum == 0) { }

//cout << \"系统中有 \" << CityNum << \" 座城市的信息\" << endl; for (i = 0; i < CityNum; ++i) { }

cout << endl;

cout << i << CityList[i].CityName << endl; cout << \"系统中没有任何城市!\" << endl; return; }

file.close();

}

//cout << \"将线路信息更新到 \" << FileName << \" 完成!\" << endl;

}

cout.fill(' ');

}

//cout << \"系统中有 \" << ArcNum << \" 条线路的信息\" << endl;

cout << \"【出发城市】【到达城市】【航班号/列车号】【出发时间】【到达时间】【用时】【票价】\" << int i;

LineNode* p = NULL; for (i = 0; i < CityNum; ++i) {

p = CityList[i].FirstLine; while (p) {

cout << setw(8) << CityList[i].CityName << \" \" << setw(11) << p->EndName << \" \" << cout.fill('0');

cout <Info->StartTime << \" \" << p->Info->EndTime << \" \" <<

<<

\"

\"

<<<

p->Info->SpendMoney

<<

endl;

setw(15) << p->Info->LineName << \" \";

p->Info->SpendTime }

//最少花费路径 struct Node { };

}

cout << endl;

}

endl;//setiosflags(ios_base::showpoint)

cout.fill(' '); p = p->NextLine;

int id; //出发城市编号 float money; //估算费用

friend bool operator < (struct Node a, struct Node b) {//由于stl中优先队列的第三个参数是greater,而 }

return a.money > b.money;

我们需要的是小顶堆，所以重载运算符 <

void ALGraph::dijkstra_Money(int v0, int* parent, Node* dis) {

vector visited(MaxCityNum, false);//初始化 int i;

for (i = 0; i < CityNum; ++i) {

dis[i].id = i; dis[i].money = INF; parent[i] = -1;

priority_queue q; //优化插入和取出最小值两个操作，队列存储最短距离与索引的编号 //parent[]记录每个顶点的父亲结点

//dis[]记录源点到每个点的估算距离，最后更新为源点到所有顶点的最短距离

//bool visited[MaxCityNum]; //判断下标对应的顶点是否算出最短路径或者说是否在最短路径树中

}

}

visited[i] = false; //未找到最短路径

dis[v0].money = 0; //源点到源点最短路权值为0 q.push(dis[v0]); //压入队列

while (!q.empty()) { //队列空说明完成了求解v0到其余各顶点的最短路径 }

Node cd = q.top(); //取最小估算距离顶点 q.pop(); int u = cd.id;

if (visited[u]) { //被标记了，就无需对其进行更新最短距离等操作 }

visited[u] = true;

LineNode* p = CityList[u].FirstLine; //松弛操作

while (p) { //找所有与它相邻的顶点，进行松弛操作，更新估算距离，压入队列 }

int v = searchCityNum(p->EndName); float m = p->Info->SpendMoney;

if (!visited[v] && dis[v].money > dis[u].money + m) { }

p = p->NextLine;

dis[v].money = dis[u].money + m; parent[v] = u; q.push(dis[v]); continue;

//最少时间路径 struct Node1 { };

int ALGraph::timeTransWeight(const Time& t) { }

void ALGraph::dijkstra_Time(int v0, int* parent, Node1* dis) {

priority_queue q1;

return (t.day * 24 + t.hour) * 60 + t.minute; int id;

int evaluatetime; Time et;

friend bool operator < (struct Node1 a, struct Node1 b) { }

return a.evaluatetime > b.evaluatetime;

//parent[]记录每个顶点的父亲结点

//dis[]记录源点到每个估算距离，最后更新为源点到所有顶点的最短距离

//bool visited[MaxCityNum]; //判断下标对应的顶点是否算出最短路径或者说是否在最短路径树中 vector visited(MaxCityNum, false); int i;

for (i = 0; i < CityNum; ++i) { }

dis[v0].evaluatetime = 0; q1.push(dis[v0]); while (!q1.empty()) {

Node1 cd = q1.top(); q1.pop(); int u = cd.id; if (visited[u]) { }

visited[u] = 1;

LineNode* p = CityList[u].FirstLine;//找出所有相邻点，进行松弛操作，即更新dis while (p) { }

int v = searchCityNum(p->EndName);

int t = timeTransWeight(p->Info->SpendTime); Time st = p->Info->StartTime; //计算中转的时间开销

if (u != v0) { //注意源点到任何点都没有中转时间 }

if (!visited[v] && dis[v].evaluatetime > dis[u].evaluatetime + t) { }

p = p->NextLine;

dis[v].evaluatetime = dis[u].evaluatetime + t; dis[v].et = p->Info->EndTime; parent[v] = u; q1.push(dis[v]);

int change = timeTransWeight(st - dis[u].et); //当前路线的开车时间-始发站的上一到t += change; continue; dis[i].id = i;

dis[i].evaluatetime = INF; dis[i].et = { 0, 0, 0 }; parent[i] = -1;

visited[i] = false; //都未找到最短路径

站时间

}

}

//调用并打印最短路经

void ALGraph::showShortestPath(const string type) {

//若v0到EndCity不存在路，即EndCity在最短路径树中没有父结点 if (path[EndNum] == -1) {

cout << \"未找到相关路线！\" << endl; if (type == \"Money\") { } else { }

Node1* dis = new Node1[MaxCityNum]; dijkstra_Time(StartNum, path, dis); mintime = dis[EndNum].evaluatetime; Node* dis = new Node[MaxCityNum]; dijkstra_Money(StartNum, path, dis); minmoney = dis[EndNum].money; string StartCity, EndCity; int StartNum, EndNum; showCity();

cout << \"请输入出发城市：\"; cin >> StartCity;

StartNum = searchCityNum(StartCity); while (StartNum == -1) { }

//showCity();

cout << \"请输入到达城市：\"; cin >> EndCity;

EndNum = searchCityNum(EndCity); while (EndNum == -1) { }

// int path[MaxCityNum]; //记录每个顶点的父亲结点，相当于是一条路径 int* path = new int[MaxCityNum]; int mintime = 0; float minmoney = 0;

cout << \"输入错误！请重新输入：\" << endl; cin >> EndCity;

EndNum = searchCityNum(EndCity); cout << \"输入错误！请重新输入：\" << endl; cin >> StartCity;

StartNum = searchCityNum(StartCity);

{

}

return;

else {

stack s; int step = EndNum; while (step != StartNum) { }

int father = step; int child;

//输出花费最小路径 if (type == \"Money\") {

cout << \"花费最小路径\" << endl; int evaluatetime = 0; //总时间 Time et = { 0, 0, 0 }; while (!s.empty()) {

child = s.top(); s.pop();

LineNode* p = CityList[father].FirstLine; float mm = INF; //min money int i = 0;

int count; //记录指针移动的次数，方便定位 while (p) { }

p = CityList[father].FirstLine; i = 0;

while (i != count) { }

evaluatetime += timeTransWeight(p->Info->SpendTime); if (father != StartNum) {

p = p->NextLine; ++i;

if (p->EndName == CityList[child].CityName && mm >= p->Info->SpendMoney) }

p = p->NextLine; ++i;

mm = p->Info->SpendMoney; count = i;

s.push(step); step = path[step];

}

}

}

evaluatetime = evaluatetime + timeTransWeight(p->Info->StartTime - et); int a = timeTransWeight(p->Info->StartTime - et); if (a < 0) { a += 24 * 60; };

cout << \"中转等待 \" << a<< \"分钟！\" << endl;

cout << setw(8) << CityList[father].CityName << \" \" << setw(8) << p->EndName << cout.fill('0');

cout << p->Info->StartTime << \" \" << p->Info->EndTime << \" \" << cout.fill(' ');

et = p->Info->EndTime; father = child;

\" \" << setw(6) << p->Info->LineName << \" \";

p->Info->SpendTime << \" \" << setiosflags(ios_base::showpoint) << p->Info->SpendMoney << endl;

//cout << \"花费\" << minmoney << \"元和\" << evaluatetime << \"分钟！\" << endl;

//输出耗时最短路径

else {

cout << \"耗时最短路径: \" << endl; float mm = 0; Time et = { 0, 0, 0 }; while (!s.empty()) {

child = s.top(); s.pop();

LineNode* p = CityList[father].FirstLine; int evaluatetime = INF; //暂时最小时间 int ot = 0; //总最小时间

int i = 0, count; //count记录指针移动的次数，方便定位 while (p) {

if (p->EndName == CityList[child].CityName) {

if (!s.empty() && child != EndNum) { } else { }

if (evaluatetime >= ot) { }

evaluatetime = ot; count = i;

ot = timeTransWeight(p->Info->SpendTime); int a = timeTransWeight(p->Info->StartTime - et); if (a < 0) { a += 24 * 60; }

ot = timeTransWeight(p->Info->SpendTime) + a;

}

}

p = p->NextLine; ++i;

p = CityList[father].FirstLine; i = 0;

while (i != count) { }

if (father != StartNum) { }

cout << setw(8) << CityList[father].CityName << \" \" << setw(8) << p->EndName << cout.fill('0');

cout << p->Info->StartTime << \" \" << p->Info->EndTime << \" \" <<

int a = timeTransWeight(p->Info->StartTime - et); if (a < 0) { a += 24 * 60; };

cout << \"中转需要等待 \" << a<< \"分钟！\" << endl; p = p->NextLine;

mm += p->Info->SpendMoney; ++i;

\" \" << setw(6) << p->Info->LineName << \" \";

p->Info->SpendTime << \" \" << setiosflags(ios_base::showpoint) << p->Info->SpendMoney << endl; //showpoint只对float有效,不用手动取消 }

------------------------------------------------------------------------------- //menu.h #pragma once #include #include #include #include\"Graph.h\" using namespace std;

//string Account = \"123456\"; string Password = \"zhonghuan\";

ALGraph ALG[2] = { ALGraph(30), ALGraph(50) }; char vehicle[2][10] = { \"Flight\

}

}

}

//cout << \"一共花费\" << mm << \"元和\" << mintime << \"分钟！\" << endl;

et = p->Info->EndTime; father = child;

cout.fill(' ');

char cityfile[2][10] = { \"PCity.txt\char linefile[2][10] = { \"Plane.txt\bool login(); void user(); void admin();

void changePassword(); void adminALG(int option); //咨询 void user() {

system(\"cls\"); int t = 1, func = 1; while (t) {

cout << \"请选择出行交通工具:\" << endl; cout << \"1.飞机\" << endl; cout << \"2.火车\" << endl; cout << \"3.返回\" << endl; cin >> t; if (t==3) { }

if (t != 1 && t != 2) { }

system(\"cls\"); while (func) {

cout << \"请选择您要查询的信息：\" << endl; cout << \"1.查询花费最小的路径\" << endl; cout << \"2.查询耗时最短的路径\" << endl; //cout << \"3.显示所有城市\" << endl; //cout << \"4.显示所有线路\" << endl; cout << \"3.返回\"; cin >> func; if (func==3) { }

cout << endl; switch (func) { case 1:

cout << \"花费最小路径：\" << endl; ALG[t - 1].showShortestPath(\"Money\"); break; break;

cout << \"错误输入，请重新输入！\" << endl; continue; break;

case 2:

}

}

}

}

cout << \"耗时最短路径！\" << endl; ALG[t - 1].showShortestPath(\"Time\"); break;

cout << \"3.显示所有城市！\" << endl; ALG[t - 1].showCity(); break;

cout << \"4.显示所有线路！\" << endl; ALG[t - 1].showLine(); break;*/

cout << \"错误输入，请重新输入！\" << endl; break;

/*case 3:

case 4:

default:

//维护界面 void admin() {

while (!login()) { }

system(\"cls\"); int option = 1; while (option) {

cout << \"请输入您要进行的操作:\" << endl; cout << \"1.航班操作\" << endl; cout << \"2.列车操作\" << endl; cout << \"3.更改密码\" << endl; cout << \"4.返回\" << endl; cin >> option; cout << endl; system(\"cls\");

if (option==4) { break; } switch (option) { case 1: case 2:

adminALG(option); system(\"cls\"); break;

changePassword();

cout << endl << \"输入错误，请重新输入：\" << endl;

case 3:

}

}

}

break;

cout << \"输入错误！\" << endl; break;

default:

//登入维护界面 bool login() { }

//修改管理员

void changePassword() {

string NewPassword1 = \"1\while (NewPassword1 != NewPassword2) {

cout << \"请输入新的维护密码：\"; system(\"stty -echo\"); cin >> NewPassword1; system(\"stty echo\");

cout << \"请再次输入新的维护密码：\"; system(\"stty -echo\"); cin >> NewPassword2; system(\"stty echo\"); system(\"cls\");

string account, password; //cout << \"请输入账户：\"; //cin >> account;

cout << \"请输入维护密码：\"; //system(\"stty -echo\"); cin >> password; //system(\"stty echo\");

/*if (account == Account && password == Password) { } else { }*/

if (password == Password) { } else { }

return false; return true; return false; return true;

}

}

if (NewPassword1 != NewPassword2) { }

cout << \"输入错误，请重新输入！\" << endl;

Password = NewPassword1;

cout << \"修改维护密码成功！\" << endl;

//航班、列车维护 void adminALG(int option) {

int func = 1; while (func) {

cout << \"1.从文件中添加城市\" << endl; cout << \"2.手动添加城市\" << endl; cout << \"3.删除城市\" << endl; cout << \"4.从文件中添加线路\" << endl; cout << \"5.手动添加线路\" << endl; cout << \"6.删除线路\" << endl; cout << \"7.显示所有城市\" << endl; cout << \"8.显示所有线路\" << endl; cout << \"9.保存文件\" << endl; cout << \"10.返回\"; cout << endl; cin >> func; cout << endl; system(\"cls\"); string name; if (func==10) { }

switch (func) { case 1:

ALG[option - 1].addCityFromFile(cityfile[option - 1]); break;

cout << \"请输入城市名称：\" << endl; cin >> name;

ALG[option - 1].addCity(name); break;

cout << \"请输入城市名称：\" << endl; cin >> name;

ALG[option - 1].delCity(name); break; break;

case 2:

case 3:

}

}

case 4: }

ALG[option - 1].addLineFromFile(linefile[option - 1]); break;

ALG[option - 1].addLine(); break;

ALG[option - 1].delLine(); break;

ALG[option - 1].showCity(); break;

ALG[option - 1].showLine(); break;

ALG[option - 1].updateFile(cityfile[option - 1], \"City\"); ALG[option - 1].updateFile(cityfile[option - 1], \"Line\"); break;

cout << \"输入有误，请重新输入！\" << endl; break;

case 5:

case 6:

case 7:

case 8:

case 9:

default:

------------------------------------------------------------------------------- //main.cpp

#include #include #include #include\"Graph.h\" #include\"menu.h\" using namespace std;

int main(void) {

system(\"cls\"); int id = 1; while (id) {

cout << endl << \"·全国交通咨询系统··\" << endl; cout << setw(28)<<\"请输入您的操作类型：\" << endl; cout << setw(20) << \"1.咨询\" << endl; cout << setw(20) << \"2.维护\" << endl; cout << setw(20) << \"3.退出\" << endl; cout << \"·\" << endl;

}

}

cin >> id; if (id==3) { break; } switch (id) { case 1: }

user(); system(\"cls\"); break; admin(); system(\"cls\"); break;

cout << \"错误输入，请重新输入！\" << endl; break;

case 2:

default:

system(\"cls\");

cout << endl << \"·\" << endl; return 0;