# 全国交通咨询系统
# 数据结构课程设计报告
## 设计目的
全国交通咨询模拟。处于不同目的的旅客对交通工具有不同的要求。例如,因公出差的旅客希望在旅途中的时间尽可能的短,出门旅游的游客则期望旅费尽可能省,而老年旅客则需要中转次数最少。编制一个全国城市间的交通咨询程序,为旅客提供两种或三种最优决策的交通咨询。
## 设计内容
提供用户以及管理员功能,用户可以对交通图进行查询,而管理员可以对交通图进行增删查改,同时管理员可以登陆、修改密码等待操作,界面采用字符界面。这样操作,更加真实地模拟了交通咨询系统。关于要求的功能,实现了城市线路的增加、删除、显示,基于 Dijkstra 的从源点到汇点的最小费用算法与最小时间算法。
概要设计
![](https://www.writebug.com/myres/static/uploads/2022/6/16/8f58400150c0be1bae87dec5132daa6f.writebug)
### 功能模块图;
各个模块详细的功能描述。
查询城市编号:头结点建立顶点表时存储的是城市对应的序号手动添加城市从文件读取以添加城市删除城市:删除城市时需要删除与该城市相关的所有线路输出所有城市更新城市列表:当新建城市个数加原本已存在城市个数大于 MAXSIZE 时,需要开辟空间存储新城市并 ++MAXSIZE 手动添加线路插入线路:由于线路信息存于表结点里,所以需要新建表结点并加入对应起始城市的边表从文件中读取线路
删除线路求最少花费路径求最少时间路径
详细设计
![](https://www.writebug.com/myres/static/uploads/2022/6/16/3ae4e79a66425274bfe74034264c289a.writebug)
功能函数的调用关系图
### 各功能函数的数据流程图
![](https://www.writebug.com/myres/static/uploads/2022/6/16/b5f9fbc9aa58410c05a8b31c83df1ff3.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/6/16/4199c0bdebeec23a6c0eb3f147abcda0.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/6/16/8a8804ac2beae480c65013cbff1f1660.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/6/16/f4c9bf56124fa4aa359fa304f0c9e952.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/6/16/c5d609e3fdc439ede2cbe68ff27f3d16.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/6/16/21811a47d7edec61392c3e7729190ecd.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/6/16/8c5a6df0380b2b1b63e1835af6df7ac8.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/6/16/0caf399bb218e472be4e054542277bc3.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/6/16/16252170c25a29728a11aebdb99bef42.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/6/16/103396ea6dba05d906c6085f7913f9b5.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/6/16/bca8e112956807da23c0f248d4ba8031.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/6/16/238331f8b0a71d8311300ea2bd54ca7a.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/6/16/18a193e2b5c18af4ac328d3a72fa243b.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/6/16/f98e05a194dac2ae0bee5dc48332c1c7.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/6/16/6df4380b56ca2f1fcba1984bf2077625.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/6/16/94fd7f4ed4a7f7e2043aa58cf65c6b22.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/6/16/0bbf99d4fe2ee5c3d89d81a02135ab70.writebug)
![](https://www.writebug.com/myres/static/uploads/2022/6/16/d54dacdde8d5006caf1e4464509262cd.writebug)
### 重点设计及编码
用优先队列优化的基于 dijkstra 算法的最小费用与最小时间算法,代码如下:
```c++
//最少花费路径 struct Node { int id; //源顶点 id float money; //估算距离(费用)
//由于 stl 中优先队列的第三个参数是 greater,而我们需要的是小顶堆,所以因重载运算符 <
friend bool operator < (struct Node a, struct Node b) {
return a.money > b.money;
}
};
void ALGraph::dijkstra_Money (int v0, int *parent, Node *dis) {
priority_queue<Node> q; //优化插入(更新)和取出最小值两个操作,队列存储最短距离与索引的编号
//parent[]记录每个顶点的父亲结点
//dis[]记录源点到每个估算距离,最后更新为源点到所有顶点的最短距离
bool visited[MaxCityNum]; //判断下标对应的顶点是否算出最短路径或者说是否在最短路径树中
//初始化
int i;
for (i = 0; i < CityNum; ++i) {
dis[i].id = i;
dis[i].money = INF;
parent[i] = -1; //每个顶点都没有父结点
visited[i] = false; //都未找到最短路
}
dis[v0].money = 0; //源点到源点最短路权值为 0
push(dis[v0]); //压入队列
while (!q.empty()) { //队列空说明完成了求解 v0 到其余各顶点的最短路径 Node cd = q.top(); //取最小估算距离顶点
pop();
int u = cd.id;
if (visited[u]) { //被标记了,就无需对其进行更新最短距离等等操作 continue; }
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) {
dis[v].money = dis[u].money + m;
parent[v] = u;
push(dis[v]);
}
= p->NextLine;
}
}// while (!q.empty())
}//dijkstra_Money
//最少时间路径
struct Node1 {
int id; //源顶点 id int tt; //估算距离(时间) Time et; //到达时间
friend bool operator < (struct Node1 a, struct Node1 b) {
return a.tt > b.tt;
}
};
int ALGraph::timeTransWeight (const Time& t) {
return (t.day*24 + t.hour)*60 + t.minute;
}
void ALGraph::dijkstra_Time (int v0, int *parent, Node1 *dis) {
priority_queue<Node1> q1;
//parent[]记录每个顶点的父亲结点
//dis[]记录源点到每个估算距离,最后更新为源点到所有顶点的最短距离
bool visited[MaxCityNum]; //判断下标对应的顶点是否算出最短路径或者说是否在最短路径树中 int i;
for (i = 0; i < CityNum; ++i) {
dis[i].id = i;
dis[i].tt = INF;
dis[i].et = {0, 0, 0};
parent[i] = -1; //都一个顶点都没有父结点
visited[i] = false; //都未找到最短路径
}
dis[v0].tt = 0;
q1.push(dis[v0]);
while (!q1.empty()) {
Node1 cd = q1.top(); //取出最短距离的点的序号
pop();
int u = cd.id;
if (visited[u]) {
continue;
}
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) { //注意源点到任何点都没有中转时间
int change = timeTransWeight(st - dis[u].et); //当前路线的开车时
```
间-始发站的上一到站时间
```c++
+= change;
}
if (!visited[v] && dis[v].tt > dis[u].tt + t) {
dis[v].tt = dis[u].tt + t;
dis[v].et = p->Info->EndTime;
parent[v] = u;
push(dis[v]);
}
= p->
没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
资源包含文件:设计报告word+源码+运行说明 提供用户以及管理员功能,用户可以对交通图进行查询,而管理员可以对交通图进行增删查改,同时管理员可以登陆、修改密码等待操作,界面采用字符界面。这样操作,更加真实地模拟了交通咨询系统。关于要求的功能,实现了城市线路的增加、删除、显示,基于 Dijkstra 的从源点到汇点的最小费用算法与最小时间算法。 详细介绍参考:https://biyezuopin.blog.csdn.net/article/details/125331516
资源推荐
资源详情
资源评论
收起资源包目录
基于C语言的全国交通咨询系统模拟.zip (15个子文件)
main.cpp 10KB
README.md 10KB
FlightCity.txt 103B
ALGraph.cpp 30KB
LICENSE 1KB
makefile 216B
Flight.txt 1KB
ALGraph.h 4KB
DataCopy
FlightCity.txt 106B
Flight.txt 1KB
运行说明.md 2KB
设计报告.docx 1.36MB
Train.txt 5KB
Report
report.pdf 930KB
TrainCity.txt 197B
共 15 条
- 1
shejizuopin
- 粉丝: 9538
- 资源: 1288
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
- 1
- 2
- 3
- 4
- 5
- 6
前往页