数据结构课程设计报告
班级：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;
};
//边结点(存放到达城市地点，以及下一条线路的指针)
