数构代码.zip

# 全国交通咨询系统 # 数据结构课程设计报告 ## 设计目的 全国交通咨询模拟。处于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能的短，出门旅游的游客则期望旅费尽可能省，而老年旅客则需要中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。 ## 设计内容 提供用户以及管理员功能，用户可以对交通图进行查询，而管理员可以对交通图进行增删查改，同时管理员可以登陆、修改密码等待操作，界面采用字符界面。这样操作，更加真实地模拟了交通咨询系统。关于要求的功能，实现了城市线路的增加、删除、显示，基于 Dijkstra 的从源点到汇点的最小费用算法与最小时间算法。 概要设计  ### 功能模块图； 各个模块详细的功能描述。 查询城市编号：头结点建立顶点表时存储的是城市对应的序号手动添加城市从文件读取以添加城市删除城市：删除城市时需要删除与该城市相关的所有线路输出所有城市更新城市列表：当新建城市个数加原本已存在城市个数大于 MAXSIZE 时，需要开辟空间存储新城市并 ++MAXSIZE 手动添加线路插入线路：由于线路信息存于表结点里，所以需要新建表结点并加入对应起始城市的边表从文件中读取线路 删除线路求最少花费路径求最少时间路径 详细设计  功能函数的调用关系图 ### 各功能函数的数据流程图                   ### 重点设计及编码 用优先队列优化的基于 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->