♻️ 资源大小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_queueNode 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_queueNode1 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 最短路径算法 人民邮电出版社.