基于C++的全国交通咨询系统

nomatter

发布日期: 2018-11-09 15:14:54 浏览量: 1414
评分:
star star star star star star star star star_border star_border
*转载请注明来自write-bug.com

一. 设计目的

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

二. 设计内容

提供用户以及管理员功能,用户可以对交通图进行查询,而管理员可以对交通图进行增删查改,同时管理员可以登陆、修改密码等待操作,界面采用字符界面。这样操作,更加真实地模拟了交通咨询系统。关于要求的功能,实现了城市线路的增加、删除、显示,基于 Dijkstra 的从源点到汇点的最小费用算法与最小时间算法。

三.概要设计

3.1 功能模块图

3.2 各个模块详细的功能描述

  • 查询城市编号:头结点建立顶点表时存储的是城市对应的序号

    • 手动添加城市
    • 从文件读取以添加城市
  • 删除城市:删除城市时需要删除与该城市相关的所有线路

    • 输出所有城市
  • 更新城市列表:当新建城市个数加原本已存在城市个数大于 MAXSIZE 时,需要开辟空间存储新城市并 ++MAXSIZE

    • 手动添加线路
  • 插入线路:由于线路信息存于表结点里,所以需要新建表结点并加入对应起始城市的边表

    • 从文件中读取线路
    • 删除线路
    • 求最少花费路径
    • 求最少时间路径

四.详细设计

4.1 功能函数的调用关系图

4.2 各功能函数的数据流程图

4.3 重点设计及编码

用优先队列优化的基于dijkstra 算法的最小费用与最小时间算法,代码如下:

  1. //最少花费路径struct Node
  2. {
  3. int id; //源顶点 id
  4. float money; //估算距离(费用)
  5. //由于stl 中优先队列的第三个参数是greater,而我们需要的是小顶堆,所以因重载运算符 <
  6. friend bool operator < (struct Node a, struct Node b)
  7. {
  8. return a.money > b.money;
  9. }
  10. };
  11. void ALGraph::dijkstra_Money (int v0, int *parent, Node *dis) { priority_queue<Node> q;
  12. //优化插入(更新)和取出最小值两个操作,队列存储最短距离与索引的编号
  13. //parent[]记录每个顶点的父亲结点
  14. //dis[]记录源点到每个估算距离,最后更新为源点到所有顶点的最短距离
  15. bool visited[MaxCityNum]; //判断下标对应的顶点是否算出最短路径或者说是否在最短路径树中
  16. //初始化int i;
  17. for (i = 0; i < CityNum; ++i)
  18. {
  19. dis[i].id = i;
  20. dis[i].money = INF;
  21. parent[i] = -1; //每个顶点都没有父结点
  22. visited[i] = false; //都未找到最短路
  23. }
  24. dis[v0].money = 0; //源点到源点最短路权值为 0 q.push(dis[v0]); //压入队列
  25. while (!q.empty())
  26. { //队列空说明完成了求解v0 到其余各顶点的最短路径
  27. Node cd = q.top(); //取最小估算距离顶点q.pop();
  28. int u = cd.id;
  29. if (visited[u])
  30. { //被标记了,就无需对其进行更新最短距离等等操作continue;
  31. }
  32. visited[u] = true;
  33. LineNode *p = CityList[u].FirstLine;
  34. //松弛操作
  35. while(p) {
  36. //找所有与它相邻的顶点,进行松弛操作,更新估算距离,压入队列int v = searchCityNum(p->EndName);
  37. float m = p->Info->SpendMoney;
  38. if (!visited[v] && dis[v].money > dis[u].money + m) {
  39. dis[v].money = dis[u].money + m;parent[v] = u;
  40. q.push(dis[v]);
  41. }
  42. p = p->NextLine;
  43. }
  44. }// while (!q.empty())
  45. }//dijkstra_Money
  46. //最少时间路径struct Node1
  47. {
  48. int id; //源顶点 id
  49. int tt; //估算距离(时间)
  50. Time et; //到达时间
  51. friend bool operator < (struct Node1 a, struct Node1 b)
  52. {
  53. return a.tt > b.tt;
  54. }
  55. };
  56. int ALGraph::timeTransWeight (const Time& t)
  57. {
  58. return (t.day*24 + t.hour)*60 + t.minute;
  59. }
  60. void ALGraph::dijkstra_Time (int v0, int *parent, Node1 *dis)
  61. {
  62. priority_queue<Node1> q1;
  63. //parent[]记录每个顶点的父亲结点
  64. //dis[]记录源点到每个估算距离,最后更新为源点到所有顶点的最短距离
  65. bool visited[MaxCityNum]; //判断下标对应的顶点是否算出最短路径或者说是否在最短路径树中
  66. int i;
  67. for (i = 0; i < CityNum; ++i)
  68. {
  69. dis[i].id = i;
  70. dis[i].tt = INF; dis[i].et = {0, 0, 0};
  71. parent[i] = -1; //都一个顶点都没有父结点
  72. visited[i] = false; //都未找到最短路径
  73. }
  74. dis[v0].tt = 0; q1.push(dis[v0]);
  75. while (!q1.empty()) {
  76. Node1 cd = q1.top(); //取出最短距离的点的序号q1.pop();
  77. int u = cd.id;
  78. if (visited[u])
  79. {
  80. continue;
  81. }
  82. visited[u] = 1;
  83. LineNode *p = CityList[u].FirstLine;
  84. //找出所有相邻点,进行松弛操作,即更新 dis
  85. while (p) {
  86. int v = searchCityNum(p->EndName);
  87. int t = timeTransWeight(p->Info->SpendTime);
  88. Time st = p->Info->StartTime; //本条线路开始时间
  89. //计算中转的时间开销
  90. if (u != v0) { //注意源点到任何点都没有中转时间
  91. int change = timeTransWeight(st - dis[u].et);
  92. //当前路线的开车时间-始发站的上一到站时间
  93. t += change;
  94. }
  95. if (!visited[v] && dis[v].tt > dis[u].tt + t)
  96. {
  97. dis[v].tt = dis[u].tt + t;
  98. dis[v].et = p->Info->EndTime;
  99. parent[v] = u;
  100. q1.push(dis[v]);
  101. }
  102. p = p->NextLine;
  103. }//while (p)
  104. }//while (!q1.empty())
  105. }//dijkstra_Time

五. 测试数据及运行结果

5.1 正常测试数据和运行结果

要求提供 3 组正常测试数据和运行结果

  • 昆明 成都 (最小花费)

  • 导入线路

  • 删除线路

5.2 异常测试数据及运行结果

显示所有线路:输出格式异常

上传的附件 cloud_download 基于C++全国交通咨询系统.zip ( 15.54kb, 176次下载 )
error_outline 下载需要8点积分

发送私信

最好的人生状态,安于得失,淡于成败,依旧向前

7
文章数
16
评论数
最近文章
eject