尧图网站建设 
简介基于C语言/数据结构课程设计的公交管理系统利用图数据结构模拟城市公交网络以邻接表存储站点与线路关系具备线路信息CRUD、最短路径查询与换乘推荐功能适合高校计算机相关专业学生作为课程设计参考。压缩包内共7个文件涵盖C/C源码.cpp、站点与路线数据.txt、可执行程序.exe及约5000字课程报告.docx整体体积仅664KB目录安排清晰无需复杂环境即可快速定位所需文件。目前在CSDN已有1482人学习/浏览说明其具有一定的参考价值。下载后可获得可直接运行的公交管理系统源码配合数据文件快速还原项目环境报告详细说明了文件读写操作、Dijkstra与Floyd算法在最短路径及换乘推荐中的实际应用并分析了多目标换乘优化思路能帮助读者理解数据结构理论如何落地为可用的城市公交查询系统。1. 一个课程设计里藏着的图算法和文件持久化问题拿到 BusMap.zip 这个压缩包的时候多数人第一反应是「又是一个 C 语言课设」真正打开 busmap.cpp 才发现没那么简单。公交管理系统表面上是站点和线路的增删改查核心难点却在两处第一把公交线路抽象成图之后最短路径和换乘推荐要用到 Dijkstra、BFS 这类数据结构算法第二C 语言没有现成的容器库邻接表、优先队列、文件落盘都得自己维护。这个项目非常适合正在做数据结构课程设计的人也适合想复习图算法和文件操作的老手。下面按我拆这个项目时的思路从建图、查询、持久化到报告优化逐步说清楚。2. 从 busmap.cpp 看系统架构图结构、文件格式与 CRUD 怎么组织2.1 为什么用邻接表而不是邻接矩阵公交网络的站点数量通常上百但每个站点真正相连的邻近站点只有几个属于典型的稀疏图。如果按邻接矩阵存站点数 V 就需要 V^2 个元素假设 200 个站点就要 4 万个整型位置而且大部分位置是 0白白浪费内存。邻接表只需要为每条边分配一个节点空间复杂度是 O(V E)更适合这种场景。busmap.cpp 里的结构体一般这样定义typedef struct EdgeNode { int adjvex; // 邻接点的站点编号 int lineId; // 经过这条边的公交线路编号 int weight; // 站间行驶时间单位分钟 struct EdgeNode *next; } EdgeNode; typedef struct VertexNode { int stationId; // 站点编号 char name[64]; // 站点名称可能包含中文 EdgeNode *firstEdge; // 第一条边 } VertexNode; typedef struct { VertexNode vertices[MAX_STATION]; int vertexNum, edgeNum; } Graph;注意 lineId 这个字段它记录了边属于哪条线路。最短路径只关心「从 A 到 B 要多长时间」但换乘推荐还要知道「坐哪一路车」所以边节点里必须带上线路编号。否则算出了最短时间路径却回答不了「怎么坐车」这个问题。2.2 四个文本文件各自承担什么实际解压后 bus_name.txt、stations.txt、routes.txt、buses.txt 各管一块常见的格式约定如下文件典型格式内容说明stations.txt2,人民广场站点编号与站点名称一行一站routes.txt5,3,10,25,7线路 5 依次经过的站点编号序列逗号分隔bus_name.txt5,10路线路编号与线路名称方便显示buses.txt5,8,60,25线路 5 的发车间隔 8 分钟、平均速度 60km/h、单程时间 25 分钟读文件时别用 fscanf 直接读整行因为站点名是中文字段分隔可能是逗号也可能是空格。我一般先用 fgets 读一行再用 strtok 按分隔符切割这样对格式变化的容忍度更高。下面这段是建图的核心代码。2.3 建图函数从 stations.txt 和 routes.txt 初始化邻接表void buildGraph(Graph *g, const char *stationFile, const char *routeFile) { FILE *fp fopen(stationFile, r); char line[256]; // 先读站点文件把站名挂到顶点上 while (fgets(line, sizeof(line), fp)) { if (line[0] \n || line[0] #) continue; int id; char name[64]; sscanf(line, %d,%63s, id, name); g-vertices[g-vertexNum].stationId id; strcpy(g-vertices[g-vertexNum].name, name); g-vertices[g-vertexNum].firstEdge NULL; g-vertexNum; } fclose(fp); // 再读线路文件把相邻站点连成双向边 fp fopen(routeFile, r); while (fgets(line, sizeof(line), fp)) { if (line[0] \n || line[0] #) continue; int lineId, stations[MAX_STATION]; int count 0; char *token strtok(line, ,\n); lineId atoi(token); while ((token strtok(NULL, ,\n)) ! NULL) { stations[count] atoi(token); } // 从路线上取相邻两个站点建立两条方向相反的边 for (int i 0; i count - 1; i) { addDirectedEdge(g, stations[i], stations[i 1], lineId, calcTime(g, stations[i], stations[i 1])); addDirectedEdge(g, stations[i 1], stations[i], lineId, calcTime(g, stations[i], stations[i 1])); } } fclose(fp); }addDirectedEdge 内部要完成「头插法 去重」两件事。头插法是把新边节点插到 firstEdge 前面时间复杂度 O(1)去重则是遍历当前顶点的边链表如果发现同一对站点已经有同一条线路的边就不再重复插入防止后续路径统计出错。calcTime 可以根据 buses.txt 里的平均速度估算行驶时间也可以直接用 routes.txt 里相邻站点的固定参数。参数含义要分清楚第一个参数是站距第二个是线路均速输出分钟数在实际项目中这些数值都会被写进报告。3. 换乘推荐与最短路径把 Dijkstra 和 BFS 改造成可用的查询3.1 边的权值怎么定义才像真实公交最短路径里的「最短」不一定是距离最短。公交场景下更常见的是「时间最短」和「换乘最少」。如果只把地理距离当权值算出来的方案可能要求乘客走很远去换乘体验很差。我一般把边权定义为行驶时间 停靠站时间其中行驶时间来自站距除以平均速度停靠时间固定按单站 1 分钟计算。换乘本身会额外增加惩罚值比如一次换乘加 10 分钟用来模拟等车和步行时间。权值定义直接影响结果。同样的图换乘惩罚设为 0 时算法会倾向频繁换乘来省时间惩罚设为 20 分钟时又会牺牲时间换少换乘。这个参数建议写成一个常量放在 busmap.cpp 顶部方便调整。课程报告里把惩罚值对推荐结果的影响列一个小表格是很好的分析素材。3.2 Dijkstra 的数组实现不用优先队列也够用课程设计的站点规模不大数组版 Dijkstra 完全够用。优先队列堆优化虽然能把复杂度降到 O(E log V)但代码量会明显增加报告里写清楚「当前规模下 O(V^2E) 可以接受」即可。void dijkstra(Graph *g, int start, int end, int *dist, int *pre) { int visited[MAX_STATION] {0}; for (int i 0; i g-vertexNum; i) { dist[i] INF; pre[i] -1; } dist[start] 0; for (int k 0; k g-vertexNum; k) { int u -1, minDist INF; // 找出当前未访问且距离最小的点 for (int i 0; i g-vertexNum; i) { if (!visited[i] dist[i] minDist) { minDist dist[i]; u i; } } if (u -1) break; // 剩余点都不可达 visited[u] 1; if (u end) break; // 终点已确定提前结束 EdgeNode *e g-vertices[u].firstEdge; while (e ! NULL) { int v e-adjvex; if (!visited[v] dist[u] e-weight dist[v]) { dist[v] dist[u] e-weight; pre[v] u; } e e-next; } } }这段代码里pre 数组保存的是「到达目标站点之前经过的站点」用于回溯路径。提前退出的条件是终点被访问且已确定最短路径这在公交查询里非常实用可以少算很多无关站点。参数上要注意 start 和 end 必须是 stations.txt 里的站点编号而不是数组下标如果文件里站点编号从 1 开始而数组下标从 0 开始使用前要做一次映射这是最容易翻车的地方。3.3 最少换乘在线路图上跑 BFS最短时间和最少换乘是两套逻辑不能简单调整权值来替代。最少换乘问题可以抽象成另一个图把每条线路看成一个大节点站点作为「中转点」。更简单的做法是先建两个映射stationToLines[siteId]表示经过某站点的线路集合lineToStations[lineId]表示某线路经过的站点集合。然后从起始站所在的每条线路出发一层层扩展线路直到扩展出的线路里有终点站。typedef struct { int lineId; int depth; // 经过的线路层数实际换乘次数 depth - 1 } QueueNode; int minTransfer(Graph *g, int start, int end) { int lineVisited[MAX_LINE] {0}; QueueNode queue[MAX_LINE * MAX_STATION]; int head 0, tail 0; // 起点可以上任意经过它的线路 for (int i 0; i g-vertexNum; i) { // 简化遍历所有包含 start 的线路实际应从 stationToLines 取 } // 标准 BFS出队一条线路检查是否覆盖终点否则扩展该线路经过的站点 // 再把这些站点能换乘到的未访问线路入队 return -1; // 不可达 }BFS 的关键是 lineVisited 数组它标记某条线路是否访问过否则会在线路之间死循环。队列里的 depth 是第几层线路而不是站点数。起点站上一次车算 depth1中途换到第二条线时 depth2所以换乘次数是 depth-1。这里容易把 depth 和站点数混在一起调试时打印每个出队线路的 depth 会很直观。3.4 换乘推荐怎么组合两个结果实际查询界面通常要同时给出「最少换乘方案」和「最快方案」。我的做法是先做最少换乘 BFS得到换乘次数 m然后再在限制「最多换乘 m 次」的条件下跑 Dijkstra目标是时间最短。实现方法是在外层枚举每条路径时记录换乘次数当换乘超过 m 时直接剪枝。参数上m 可以是 0、1、2现实中超过 2 次的方案基本没有推荐价值可以在查询入口直接过滤掉。4. 文件读写与数据一致性保存时最容易踩的坑4.1 写入文件的原子性CRUD 里 Delete 和 Update 之后需要把内存里的图写回文件。如果直接在原文件上写中途程序崩溃或磁盘空间不足原文件可能只剩一半。更稳妥的写法是先生成临时文件全部写入成功后再用 rename 覆盖原文件。C 语言里可以这样处理int saveStations(Graph *g) { FILE *tmp fopen(stations.tmp, w); if (!tmp) return -1; for (int i 0; i g-vertexNum; i) { fprintf(tmp, %d,%s\n, g-vertices[i].stationId, g-vertices[i].name); } fclose(tmp); if (rename(stations.tmp, stations.txt) ! 0) { remove(stations.tmp); return -1; } return 0; }注意 rename 在 Windows 和 Linux 上行为略有不同Windows 下如果目标文件已存在rename 会失败所以要先 remove 原文件再 renameLinux 下则是直接替换。为了跨平台可以在 rename 失败后先 remove 再试一次。这里的参数只有顶点数组但保存线路时要注意同步更新 routes.txt 和 buses.txt三个文件必须保持同一时刻的逻辑一致否则下次启动读到一半数据会错乱。4.2 中文站名与编码问题stations.txt 里的站名是中文fprintf 直接写中文没问题但读回来时要注意编码。Windows 控制台默认是 GBK 编码而 Linux 终端是 UTF-8。如果代码里用char name[64]存站名并且只用 printf 显示在 Windows 上编译运行通常正常但如果你把文件拉到 Linux 下或者用 VS Code 的终端运行站名就会变成乱码。解决思路是按行读取后用 strtok 切割不要用fscanf(fp, %d,%s)因为%s会在空格处截断而中文站名虽然一般不含空格但行尾的\r在 Windows 文本模式下会被自动处理在 Linux 下\r会粘到站名后面导致查询时怎么都匹配不上。我建议读取时统一把行尾的\r\n去掉line[strcspn(line, \r\n)] \0;这个函数用字符串扫描跳过换行符属于 C 标准库的常见技巧在报告里提一句能体现出对文件操作细节的敏感度。4.3 删除操作后的悬空边清理删除线路或站点是 CRUD 里最容易留下隐患的地方。比如删除某条线路后邻接表里属于该线路的边如果不清空最短路径算法会把已经取消的线路算进去。反之删除站点时其他顶点的边链表里还残留指向该站点的 EdgeNode遍历图时会访问到不存在的顶点。void removeEdgeByLine(Graph *g, int lineId) { for (int i 0; i g-vertexNum; i) { EdgeNode *p g-vertices[i].firstEdge; EdgeNode *pre NULL; while (p ! NULL) { if (p-lineId lineId) { // 从链表中摘除当前节点释放内存 if (pre NULL) { g-vertices[i].firstEdge p-next; } else { pre-next p-next; } EdgeNode *tmp p; p p-next; free(tmp); } else { pre p; p p-next; } } } }删除站点时要同时清理两处一是顶点数组中的 slot二是所有指向它的边。顶点数组的删除如果采用「把最后一个顶点移过来填补空位」的方式必须同时更新其他边里的编号。如果采用「标记 deleted 字段」的方式Dijkstra 里要跳过被标记的顶点。两种方案各有利弊推荐用后者因为站点编号在文件里保持稳定查询时不会出现编号错位。问题信号常见原因排查方向查询时报站点不存在起点或终点编号是数组下标检查编号到下标的映射最短路径时间小于实际边权只有距离没有停站时间权值定义加停靠时间保存后重启数据错乱三个文件不同步每次写操作统一调用 saveAll中文站名匹配失败文件编码与运行环境不一致按行读并去掉\r5. 验证与扩展把 exe 跑通后再给报告加分5.1 用 exe 验证核心流程拿到 BusMap.exe 后先按「正常查询、边界查询、异常输入」三类设计测试用例。正常查询选一个终点站早收车的线路确认结果时间和真实时刻表一致边界查询选起点和终点相同的情况程序应该直接输出 0 时间和无需换乘而不是进入死循环或被零除。异常输入比如查一个不存在的站名程序要给出友好提示然后回到主菜单不能闪退。花 20 分钟把这些用例跑一遍能过滤掉大半的隐藏 bug。5.2 打印 dist 表定位算法问题如果最短路径结果总是不对别急着看整个路径先在 dijkstra 函数里加一个调试打印每次迭代结束后输出当前 dist 数组和 visited 数组。看到某个站点距离是 INF就知道它没被任何边连到看到终点提前被 visited 但路径不合理就去检查 pre 数组的回溯逻辑。这种验证方法比单点断点更直观因为图的问题往往是整片不连通不是一行代码的问题。5.3 报告加分项把换乘推荐做成两阶段过滤课程报告要求 5k 字最容易写薄的是「算法设计」部分。我的建议是在基础 BFS Dijkstra 之上加一个两阶段过滤的思路第一阶段用 BFS 求出可达的最少换乘次数 m第二阶段在换乘次数不超过 m 的方案里枚举所有满足条件的换乘序列再按总时间排序取第一条。这个逻辑不复杂但能突出「多目标优化」的意识。// 伪代码两阶段换乘推荐 int bestPath[MAX_STATION]; int bestLen INF; findPath(currentStation, targetStation, transferCount, path, pathLen) { if (transferCount maxTransfer) return; if (currentStation targetStation) { if (pathLen bestLen) { copy(path, bestPath); bestLen pathLen; } return; } // 遍历与当前站点同线的相邻站点递归探索 for (eachLine in stationToLines[currentStation]) { for (eachStation in lineToStations[eachLine]) { if (not visited) { mark visited; findPath(eachStation, targetStation, transferCount (lineChanged ? 1 : 0), path, pathLen); unmark visited; } } } }递归搜索的剪枝条件有两个换乘次数超过上界 m累计时间超过 bestLen。报告里分析这个搜索的时间复杂度时可以从线路数和每线站点数入手说明公交车网络平均换乘半径很小实际搜索分支很少。最后一个实用技巧是把 buses.txt 里的发车间隔读进内存在计算总时间时加上等车时间的一半这个细节能让结果更真实也是报告里区别于普通课设的亮点。本文还有配套的精品资源点击获取 C语言公交管理系统：Dijkstra与BFS换乘推荐实战
简介基于C语言/数据结构课程设计的公交管理系统利用图数据结构模拟城市公交网络以邻接表存储站点与线路关系具备线路信息CRUD、最短路径查询与换乘推荐功能适合高校计算机相关专业学生作为课程设计参考。压缩包内共7个文件涵盖C/C源码.cpp、站点与路线数据.txt、可执行程序.exe及约5000字课程报告.docx整体体积仅664KB目录安排清晰无需复杂环境即可快速定位所需文件。目前在CSDN已有1482人学习/浏览说明其具有一定的参考价值。下载后可获得可直接运行的公交管理系统源码配合数据文件快速还原项目环境报告详细说明了文件读写操作、Dijkstra与Floyd算法在最短路径及换乘推荐中的实际应用并分析了多目标换乘优化思路能帮助读者理解数据结构理论如何落地为可用的城市公交查询系统。1. 一个课程设计里藏着的图算法和文件持久化问题拿到 BusMap.zip 这个压缩包的时候多数人第一反应是「又是一个 C 语言课设」真正打开 busmap.cpp 才发现没那么简单。公交管理系统表面上是站点和线路的增删改查核心难点却在两处第一把公交线路抽象成图之后最短路径和换乘推荐要用到 Dijkstra、BFS 这类数据结构算法第二C 语言没有现成的容器库邻接表、优先队列、文件落盘都得自己维护。这个项目非常适合正在做数据结构课程设计的人也适合想复习图算法和文件操作的老手。下面按我拆这个项目时的思路从建图、查询、持久化到报告优化逐步说清楚。2. 从 busmap.cpp 看系统架构图结构、文件格式与 CRUD 怎么组织2.1 为什么用邻接表而不是邻接矩阵公交网络的站点数量通常上百但每个站点真正相连的邻近站点只有几个属于典型的稀疏图。如果按邻接矩阵存站点数 V 就需要 V^2 个元素假设 200 个站点就要 4 万个整型位置而且大部分位置是 0白白浪费内存。邻接表只需要为每条边分配一个节点空间复杂度是 O(V E)更适合这种场景。busmap.cpp 里的结构体一般这样定义typedef struct EdgeNode { int adjvex; // 邻接点的站点编号 int lineId; // 经过这条边的公交线路编号 int weight; // 站间行驶时间单位分钟 struct EdgeNode *next; } EdgeNode; typedef struct VertexNode { int stationId; // 站点编号 char name[64]; // 站点名称可能包含中文 EdgeNode *firstEdge; // 第一条边 } VertexNode; typedef struct { VertexNode vertices[MAX_STATION]; int vertexNum, edgeNum; } Graph;注意 lineId 这个字段它记录了边属于哪条线路。最短路径只关心「从 A 到 B 要多长时间」但换乘推荐还要知道「坐哪一路车」所以边节点里必须带上线路编号。否则算出了最短时间路径却回答不了「怎么坐车」这个问题。2.2 四个文本文件各自承担什么实际解压后 bus_name.txt、stations.txt、routes.txt、buses.txt 各管一块常见的格式约定如下文件典型格式内容说明stations.txt2,人民广场站点编号与站点名称一行一站routes.txt5,3,10,25,7线路 5 依次经过的站点编号序列逗号分隔bus_name.txt5,10路线路编号与线路名称方便显示buses.txt5,8,60,25线路 5 的发车间隔 8 分钟、平均速度 60km/h、单程时间 25 分钟读文件时别用 fscanf 直接读整行因为站点名是中文字段分隔可能是逗号也可能是空格。我一般先用 fgets 读一行再用 strtok 按分隔符切割这样对格式变化的容忍度更高。下面这段是建图的核心代码。2.3 建图函数从 stations.txt 和 routes.txt 初始化邻接表void buildGraph(Graph *g, const char *stationFile, const char *routeFile) { FILE *fp fopen(stationFile, r); char line[256]; // 先读站点文件把站名挂到顶点上 while (fgets(line, sizeof(line), fp)) { if (line[0] \n || line[0] #) continue; int id; char name[64]; sscanf(line, %d,%63s, id, name); g-vertices[g-vertexNum].stationId id; strcpy(g-vertices[g-vertexNum].name, name); g-vertices[g-vertexNum].firstEdge NULL; g-vertexNum; } fclose(fp); // 再读线路文件把相邻站点连成双向边 fp fopen(routeFile, r); while (fgets(line, sizeof(line), fp)) { if (line[0] \n || line[0] #) continue; int lineId, stations[MAX_STATION]; int count 0; char *token strtok(line, ,\n); lineId atoi(token); while ((token strtok(NULL, ,\n)) ! NULL) { stations[count] atoi(token); } // 从路线上取相邻两个站点建立两条方向相反的边 for (int i 0; i count - 1; i) { addDirectedEdge(g, stations[i], stations[i 1], lineId, calcTime(g, stations[i], stations[i 1])); addDirectedEdge(g, stations[i 1], stations[i], lineId, calcTime(g, stations[i], stations[i 1])); } } fclose(fp); }addDirectedEdge 内部要完成「头插法 去重」两件事。头插法是把新边节点插到 firstEdge 前面时间复杂度 O(1)去重则是遍历当前顶点的边链表如果发现同一对站点已经有同一条线路的边就不再重复插入防止后续路径统计出错。calcTime 可以根据 buses.txt 里的平均速度估算行驶时间也可以直接用 routes.txt 里相邻站点的固定参数。参数含义要分清楚第一个参数是站距第二个是线路均速输出分钟数在实际项目中这些数值都会被写进报告。3. 换乘推荐与最短路径把 Dijkstra 和 BFS 改造成可用的查询3.1 边的权值怎么定义才像真实公交最短路径里的「最短」不一定是距离最短。公交场景下更常见的是「时间最短」和「换乘最少」。如果只把地理距离当权值算出来的方案可能要求乘客走很远去换乘体验很差。我一般把边权定义为行驶时间 停靠站时间其中行驶时间来自站距除以平均速度停靠时间固定按单站 1 分钟计算。换乘本身会额外增加惩罚值比如一次换乘加 10 分钟用来模拟等车和步行时间。权值定义直接影响结果。同样的图换乘惩罚设为 0 时算法会倾向频繁换乘来省时间惩罚设为 20 分钟时又会牺牲时间换少换乘。这个参数建议写成一个常量放在 busmap.cpp 顶部方便调整。课程报告里把惩罚值对推荐结果的影响列一个小表格是很好的分析素材。3.2 Dijkstra 的数组实现不用优先队列也够用课程设计的站点规模不大数组版 Dijkstra 完全够用。优先队列堆优化虽然能把复杂度降到 O(E log V)但代码量会明显增加报告里写清楚「当前规模下 O(V^2E) 可以接受」即可。void dijkstra(Graph *g, int start, int end, int *dist, int *pre) { int visited[MAX_STATION] {0}; for (int i 0; i g-vertexNum; i) { dist[i] INF; pre[i] -1; } dist[start] 0; for (int k 0; k g-vertexNum; k) { int u -1, minDist INF; // 找出当前未访问且距离最小的点 for (int i 0; i g-vertexNum; i) { if (!visited[i] dist[i] minDist) { minDist dist[i]; u i; } } if (u -1) break; // 剩余点都不可达 visited[u] 1; if (u end) break; // 终点已确定提前结束 EdgeNode *e g-vertices[u].firstEdge; while (e ! NULL) { int v e-adjvex; if (!visited[v] dist[u] e-weight dist[v]) { dist[v] dist[u] e-weight; pre[v] u; } e e-next; } } }这段代码里pre 数组保存的是「到达目标站点之前经过的站点」用于回溯路径。提前退出的条件是终点被访问且已确定最短路径这在公交查询里非常实用可以少算很多无关站点。参数上要注意 start 和 end 必须是 stations.txt 里的站点编号而不是数组下标如果文件里站点编号从 1 开始而数组下标从 0 开始使用前要做一次映射这是最容易翻车的地方。3.3 最少换乘在线路图上跑 BFS最短时间和最少换乘是两套逻辑不能简单调整权值来替代。最少换乘问题可以抽象成另一个图把每条线路看成一个大节点站点作为「中转点」。更简单的做法是先建两个映射stationToLines[siteId]表示经过某站点的线路集合lineToStations[lineId]表示某线路经过的站点集合。然后从起始站所在的每条线路出发一层层扩展线路直到扩展出的线路里有终点站。typedef struct { int lineId; int depth; // 经过的线路层数实际换乘次数 depth - 1 } QueueNode; int minTransfer(Graph *g, int start, int end) { int lineVisited[MAX_LINE] {0}; QueueNode queue[MAX_LINE * MAX_STATION]; int head 0, tail 0; // 起点可以上任意经过它的线路 for (int i 0; i g-vertexNum; i) { // 简化遍历所有包含 start 的线路实际应从 stationToLines 取 } // 标准 BFS出队一条线路检查是否覆盖终点否则扩展该线路经过的站点 // 再把这些站点能换乘到的未访问线路入队 return -1; // 不可达 }BFS 的关键是 lineVisited 数组它标记某条线路是否访问过否则会在线路之间死循环。队列里的 depth 是第几层线路而不是站点数。起点站上一次车算 depth1中途换到第二条线时 depth2所以换乘次数是 depth-1。这里容易把 depth 和站点数混在一起调试时打印每个出队线路的 depth 会很直观。3.4 换乘推荐怎么组合两个结果实际查询界面通常要同时给出「最少换乘方案」和「最快方案」。我的做法是先做最少换乘 BFS得到换乘次数 m然后再在限制「最多换乘 m 次」的条件下跑 Dijkstra目标是时间最短。实现方法是在外层枚举每条路径时记录换乘次数当换乘超过 m 时直接剪枝。参数上m 可以是 0、1、2现实中超过 2 次的方案基本没有推荐价值可以在查询入口直接过滤掉。4. 文件读写与数据一致性保存时最容易踩的坑4.1 写入文件的原子性CRUD 里 Delete 和 Update 之后需要把内存里的图写回文件。如果直接在原文件上写中途程序崩溃或磁盘空间不足原文件可能只剩一半。更稳妥的写法是先生成临时文件全部写入成功后再用 rename 覆盖原文件。C 语言里可以这样处理int saveStations(Graph *g) { FILE *tmp fopen(stations.tmp, w); if (!tmp) return -1; for (int i 0; i g-vertexNum; i) { fprintf(tmp, %d,%s\n, g-vertices[i].stationId, g-vertices[i].name); } fclose(tmp); if (rename(stations.tmp, stations.txt) ! 0) { remove(stations.tmp); return -1; } return 0; }注意 rename 在 Windows 和 Linux 上行为略有不同Windows 下如果目标文件已存在rename 会失败所以要先 remove 原文件再 renameLinux 下则是直接替换。为了跨平台可以在 rename 失败后先 remove 再试一次。这里的参数只有顶点数组但保存线路时要注意同步更新 routes.txt 和 buses.txt三个文件必须保持同一时刻的逻辑一致否则下次启动读到一半数据会错乱。4.2 中文站名与编码问题stations.txt 里的站名是中文fprintf 直接写中文没问题但读回来时要注意编码。Windows 控制台默认是 GBK 编码而 Linux 终端是 UTF-8。如果代码里用char name[64]存站名并且只用 printf 显示在 Windows 上编译运行通常正常但如果你把文件拉到 Linux 下或者用 VS Code 的终端运行站名就会变成乱码。解决思路是按行读取后用 strtok 切割不要用fscanf(fp, %d,%s)因为%s会在空格处截断而中文站名虽然一般不含空格但行尾的\r在 Windows 文本模式下会被自动处理在 Linux 下\r会粘到站名后面导致查询时怎么都匹配不上。我建议读取时统一把行尾的\r\n去掉line[strcspn(line, \r\n)] \0;这个函数用字符串扫描跳过换行符属于 C 标准库的常见技巧在报告里提一句能体现出对文件操作细节的敏感度。4.3 删除操作后的悬空边清理删除线路或站点是 CRUD 里最容易留下隐患的地方。比如删除某条线路后邻接表里属于该线路的边如果不清空最短路径算法会把已经取消的线路算进去。反之删除站点时其他顶点的边链表里还残留指向该站点的 EdgeNode遍历图时会访问到不存在的顶点。void removeEdgeByLine(Graph *g, int lineId) { for (int i 0; i g-vertexNum; i) { EdgeNode *p g-vertices[i].firstEdge; EdgeNode *pre NULL; while (p ! NULL) { if (p-lineId lineId) { // 从链表中摘除当前节点释放内存 if (pre NULL) { g-vertices[i].firstEdge p-next; } else { pre-next p-next; } EdgeNode *tmp p; p p-next; free(tmp); } else { pre p; p p-next; } } } }删除站点时要同时清理两处一是顶点数组中的 slot二是所有指向它的边。顶点数组的删除如果采用「把最后一个顶点移过来填补空位」的方式必须同时更新其他边里的编号。如果采用「标记 deleted 字段」的方式Dijkstra 里要跳过被标记的顶点。两种方案各有利弊推荐用后者因为站点编号在文件里保持稳定查询时不会出现编号错位。问题信号常见原因排查方向查询时报站点不存在起点或终点编号是数组下标检查编号到下标的映射最短路径时间小于实际边权只有距离没有停站时间权值定义加停靠时间保存后重启数据错乱三个文件不同步每次写操作统一调用 saveAll中文站名匹配失败文件编码与运行环境不一致按行读并去掉\r5. 验证与扩展把 exe 跑通后再给报告加分5.1 用 exe 验证核心流程拿到 BusMap.exe 后先按「正常查询、边界查询、异常输入」三类设计测试用例。正常查询选一个终点站早收车的线路确认结果时间和真实时刻表一致边界查询选起点和终点相同的情况程序应该直接输出 0 时间和无需换乘而不是进入死循环或被零除。异常输入比如查一个不存在的站名程序要给出友好提示然后回到主菜单不能闪退。花 20 分钟把这些用例跑一遍能过滤掉大半的隐藏 bug。5.2 打印 dist 表定位算法问题如果最短路径结果总是不对别急着看整个路径先在 dijkstra 函数里加一个调试打印每次迭代结束后输出当前 dist 数组和 visited 数组。看到某个站点距离是 INF就知道它没被任何边连到看到终点提前被 visited 但路径不合理就去检查 pre 数组的回溯逻辑。这种验证方法比单点断点更直观因为图的问题往往是整片不连通不是一行代码的问题。5.3 报告加分项把换乘推荐做成两阶段过滤课程报告要求 5k 字最容易写薄的是「算法设计」部分。我的建议是在基础 BFS Dijkstra 之上加一个两阶段过滤的思路第一阶段用 BFS 求出可达的最少换乘次数 m第二阶段在换乘次数不超过 m 的方案里枚举所有满足条件的换乘序列再按总时间排序取第一条。这个逻辑不复杂但能突出「多目标优化」的意识。// 伪代码两阶段换乘推荐 int bestPath[MAX_STATION]; int bestLen INF; findPath(currentStation, targetStation, transferCount, path, pathLen) { if (transferCount maxTransfer) return; if (currentStation targetStation) { if (pathLen bestLen) { copy(path, bestPath); bestLen pathLen; } return; } // 遍历与当前站点同线的相邻站点递归探索 for (eachLine in stationToLines[currentStation]) { for (eachStation in lineToStations[eachLine]) { if (not visited) { mark visited; findPath(eachStation, targetStation, transferCount (lineChanged ? 1 : 0), path, pathLen); unmark visited; } } } }递归搜索的剪枝条件有两个换乘次数超过上界 m累计时间超过 bestLen。报告里分析这个搜索的时间复杂度时可以从线路数和每线站点数入手说明公交车网络平均换乘半径很小实际搜索分支很少。最后一个实用技巧是把 buses.txt 里的发车间隔读进内存在计算总时间时加上等车时间的一半这个细节能让结果更真实也是报告里区别于普通课设的亮点。本文还有配套的精品资源点击获取