♻️ 资源
大小：829KB
➡️资源下载：https://download.csdn.net/download/s1t16/87450312
全国交通咨询系统
数据结构课程设计报告
设计目的
全国交通咨询模拟。处于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能的短，出门旅游的游客则期望旅费尽可能省，而老年旅客则需要中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。
设计内容
提供用户以及管理员功能，用户可以对交通图进行查询，而管理员可以对交通图进行增删查改，同时管理员可以登陆、修改密码等待操作，界面采用字符界面。这样操作，更加真实地模拟了交通咨询系统。关于要求的功能，实现了城市线路的增加、删除、显示，基于 Dijkstra 的从源点到汇点的最小费用算法与最小时间算法。
概要设计
功能模块图
各个模块详细的功能描述。
查询城市编号：头结点建立顶点表时存储的是城市对应的序号手动添加城市从文件读取以添加城市删除城市：删除城市时需要删除与该城市相关的所有线路输出所有城市更新城市列表：当新建城市个数加原本已存在城市个数大于 MAXSIZE 时，需要开辟空间存储新城市并 ++MAXSIZE 手动添加线路插入线路：由于线路信息存于表结点里，所以需要新建表结点并加入对应起始城市的边表从文件中读取线路
删除线路求最少花费路径求最少时间路径
详细设计
功能函数的调用关系图
各功能函数的数据流程图
重点设计及编码
用优先队列优化的基于 dijkstra 算法的最小费用与最小时间算法，代码如下：
//最少花费路径 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); //当前路线的开车时间-始发站的上一到站时间
+= 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->NextLine; }//while (p) }//while (!q1.empty()) }//dijkstra_Time测试数据及运行结果
正常测试数据和运行结果
要求提供 3 组正常测试数据和运行结果
昆明 成都 （最小花费）
导入线路
删除线路
异常测试数据及运行结果
显示所有线路：输出格式异常
调试情况，设计技巧及体会 1．改进方案
打印最小路径的方法过于冗长，不易修改，在 Debug 时屡屡出现困难，需要再进行优化，去除一些不必要的变量。由于只有三天的开发时间，完成的进度不令我满意，最小中转还没有写完，之后将添加上基于 BFS 的最小中转算法。
体会
对于常见的算法比如单源最短路经算法 Dijkstra 要有自己的理解，不能止于记住步骤，只有这样才可能高效地去开发并优化基于它的实际算法。写函数的时候注意“高内聚，低耦合”，尽可能写出易懂、出错后易修改的代码。注意给程序适当增加注释，方便之后的修改。
参考文献
Thomas H.Cormen Charles E.Leiserson Ronald L.Rivest Clifford Stein 著. 《算法导论》. 第三版. P383 Dijkstra 算法 机械工业出版社.
Stanley B.Lippman joseeLajoie Barbara E.Moo 著. 《C++ Primer》. 第五版. P373 关联容器 电子工业出版社.
王曙燕 主编 王春梅 副编. 《数据结构与算法》. 第二版. P169 邻接表 P188 最短路径算法 人民邮电出版社.
