简介这套基于MFC的南京地铁查询系统是一份完整的Visual C 6.0工程面向正在学习MFC框架或需要开发桌面信息查询系统的学生和开发者。系统实现了地铁线路与站点数据的存储、查询和可视化展示并提供了可直接运行的exe程序方便查看实际运行效果。整个压缩包包含43个文件大小仅2.44MB其中8个头文件和7个CPP文件构成主要源码配合Dlg、Prop等类完成界面交互与查询逻辑bmp、ico、rc等资源用于界面美化dsp、dsw、clw等工程配置便于直接编译调试readme和txt则提供必要的说明。目前已有962人学习下载。通过阅读完整源码能够清晰理解MFC的CWinApp程序入口、CDialog对话框设计、消息映射与事件处理以及数据读取和列表展示等关键步骤同时项目中的地铁图位图展示和路线查询逻辑也可为其他地理信息查询类软件提供可复用的设计参考。1. 基于MFC的南京地铁查询系统为什么一个课程设计值得认真做很多人第一次看到“基于MFC的南京地铁查询系统”这个题目第一反应是“又是MFC老掉牙了”。但真把需求拆开你会发现它恰好覆盖了MFC里最值得练的三件事文档数据怎么进内存、图算法怎么在UI线程里跑、自绘控件怎么画得又快又对。这篇文章要拆的就是这样一套完整的系统用VS MFC对话框搭出查询窗口把南京地铁的线路站点数据读进邻接表再用Dijkstra算最少站数、用BFS算最少换乘最后把最优路线画在自绘区里。新手能照着把环境跑起来老手可以重点看编码、算法引擎和重绘这三类坑。2. 工程结构先把“查询系统”拆成三层再动手2.1 为什么选MFC对话框而不是单文档视图常见做法是新建一个MFC对话框程序而不是用单文档视图SDI。原因很简单地铁查询系统的主界面就是“两个下拉框 一个按钮 一个结果列表”没有复杂的文档概念。对话框的DoModal循环天然适合这种交互生成菜单、工具栏那些代码都是噪音。但有个地方要用到视图框架的能力自绘线路图。对话框里放一个自定义的Picture Control或者直接重写对话框的OnPaint让它在指定区域绘图。如果你把绘图区域封装成一个继承自CWnd的控件类那么对话框和单文档的差别就不大了。我的建议是对话框为主体自绘控件单独拆成类方便以后如果要做成大窗口直接换成CScrollView。2.2 三层结构数据层、算法层、界面层别把CSV解析、Dijkstra、OnPaint全塞在对话框类里否则一个文件能写到三千行。拆三层数据层 MetroData负责读文件、存站点、建邻接表、提供查询接口。算法层 RouteFinder接受MetroData的图结构返回最短路径或最少换乘结果。界面层 CMetroQueryDlg只负责收集用户输入、调用算法层、刷新列表和绘图。这样做的最大好处是调试时可以单独给RouteFinder写控制台测试不用启动界面。MFC工程里加一个命令行入口不是不行但我一般直接加一个“自检”按钮把几条已知路径的结果弹出来。2.3 初始化文件与界面骨架代码先看数据加载。南京地铁站点数据我建议存成一个CSV格式如下每行一条记录line_id,station_name,order 1,迈皋桥,1 1,红山动物园,2 1,南京站,3 ... 2,油坊桥,1 2,雨润大街,2读取时需要注意如果用MFC的CStdioFile的ReadString按Unicode读UTF-8文件会乱码。下面这段代码先把文件按UTF-8字节读进来再手动转成宽字符最后用CString存站名bool MetroData::LoadFromFile(const CString path) { std::ifstream in(CT2A(path.GetString())); if (!in.is_open()) return false; std::string utf8Line; while (std::getline(in, utf8Line)) { if (utf8Line.empty()) continue; // 计算UTF-8字节串转成宽字符所需长度 int wLen MultiByteToWideChar(CP_UTF8, 0, utf8Line.c_str(), (int)utf8Line.size(), nullptr, 0); if (wLen 0) continue; std::wstring wBuf(wLen, L\0); MultiByteToWideChar(CP_UTF8, 0, utf8Line.c_str(), (int)utf8Line.size(), wBuf[0], wLen); CString line(wBuf.c_str()); int pos1 line.Find(_T(,)); int pos2 line.Find(_T(,), pos1 1); if (pos1 0 || pos2 0) continue; int lineId _ttoi(line.Left(pos1)); CString station line.Mid(pos1 1, pos2 - pos1 - 1); int order _ttoi(line.Mid(pos2 1)); m_stations.push_back(StationRecord{ lineId, station, order }); } BuildGraph(); return true; }逻辑说明先用std::ifstream按二进制方式读UTF-8文本避免CStdioFile默认按本地代码页读取然后用MultiByteToWideChar把每行UTF-8转成UTF-16。这样在Unicode项目中CString拿到的就是正确的中文站名。要注意find查找分隔符的结果是相对位置截取站名时Mid的长度要算对否则最后一个中文字符会被吞掉。参数说明CP_UTF8指源字符串编码wBuf是转换目标缓冲区MultiByteToWideChar的第五个参数传-1表示字符串以\0结尾但这里显式传长度更规范因为getline的结果里没结尾符。转换成功后wBuf末尾会有\0CString构造会自动处理。2.4 BuildGraph从站点表到邻接表读取完成后必须把“线路-站点-顺序”转换成适合寻路的邻接表。我一般用站点名做全局IDvoid MetroData::BuildGraph() { // 先给每个站点分配ID int id 0; for (auto rec : m_stations) { if (m_stationId.find(rec.station) m_stationId.end()) { m_stationId[rec.station] id; m_idToName.push_back(rec.station); } } m_graph.assign(m_idToName.size(), {}); m_stationLines.assign(m_idToName.size(), {}); // 按线路分组然后组内相邻站建边 std::mapint, std::vectorStationRecord byLine; for (auto rec : m_stations) byLine[rec.lineId].push_back(rec); for (auto kv : byLine) { auto vec kv.second; std::sort(vec.begin(), vec.end(), [](const StationRecord a, const StationRecord b) { return a.order b.order; }); for (size_t i 0; i 1 vec.size(); i) { int u m_stationId[vec[i].station]; int v m_stationId[vec[i 1].station]; m_graph[u].push_back({ v, kv.first }); m_graph[v].push_back({ u, kv.first }); } // 记录每个站经过的所有线路 for (auto rec : vec) m_stationLines[m_stationId[rec.station]].push_back(kv.first); } }逻辑说明m_stationId是map把中文站名映射到连续整数IDm_idToName用于反查站名。m_graph是邻接表边结构里除了目标站点ID还存这条边属于哪条线路这样在结果输出时能告诉用户“乘坐1号线从A到B”。m_stationLines后面算最少换乘要用。参数说明m_graph[u].push_back({v, kv.first})里的kv.first是线路ID。这里用vector存邻接表站点数量不超过300内存占用无所谓但排序按order能保证同一条线上顺序正确。如果数据文件里线路ID重复或order有乱序排序这步很重要。3. 数据是黑匣子先谈编码、再谈结构3.1 为什么地铁查询系统要纠结CSV编码MFC工程在VS 2019/2022上默认字符集是UnicodeCString是UTF-16宽字符。而大多数数据文件来源是Excel另存的CSVExcel在国内保存默认是GBK从网页复制出来的可能是UTF-8。如果直接ifstream读进std::string再赋给CString中文字符串全部变成问号。这个坑我在第二节代码里已经绕过去了统一要求数据文件是UTF-8读取时用MultiByteToWideChar转成宽字符。有人问那用CStdioFile的typeText模式读Unicode编码的文件不就行了吗CStdioFile在Unicode项目里确实读UTF-16文件没问题但要求文件带BOMFF FE。问题是很多GIS或爬虫导出的CSV是UTF-8 no BOM打开就是乱码。所以我的习惯是数据文件保存为UTF-8有BOM更稳程序里用字节流读取后手动转码。这样不管VS工程是ANSI还是Unicode都能兼容。3.2 数据结构为什么要建双向边和换乘站表上面的BuildGraph里我建的是双向边因为地铁可以坐反向。换乘站不需要特殊标记它的特点是在邻接表里同时出现多条线路的边。比如新街口站在1号线和2号线都有记录那么它的邻接节点既包括1号线的相邻站也包括2号线的相邻站Dijkstra跑的时候自然能“换乘”。但要注意如果单纯用Dijkstra找最少站数换乘次数不会被惩罚。一个从A到B的方案可能是“坐1号线2站到换乘站再坐2号线1站”共3站另一个方案“坐3号线直通”共4站最少站数会选择前者。如果你的需求是“优先换乘少”那不能只用Dijkstra要改算法。3.3 查询接口数据层对外屏蔽细节数据层给界面层提供三个接口就够了// 获取所有站名用于下拉框 std::vectorCString GetAllStations() const { return m_idToName; } // 获取某站的ID不存在返回-1 int GetStationId(const CString name) const { auto it m_stationId.find(name); return it m_stationId.end() ? -1 : it-second; } // 获取某站经过的线路列表 std::vectorint GetLinesOfStation(int stationId) const { return m_stationLines[stationId]; }界面层拿到站名填充CComboBox用户选完站后调GetStationId然后交给算法层。这样的好处是后续如果要换数据库只需要改MetroData内部实现RouteFinder和界面类不用动。4. 换乘算法最少站数和最少换乘是两套逻辑4.1 最少站数Dijkstra的等权实现因为地铁每坐一站代价是1理论上BFS也能求最少站数。但Dijkstra写出来以后可以扩展“换乘惩罚权重”所以我还是选择Dijkstra。实现时用优先队列做小顶堆struct RouteNode { int stationId; int dist; bool operator(const RouteNode other) const { return dist other.dist; // 注意方向 } }; void RouteFinder::ShortestPath(int start, int end, std::vectorint outPath, int outDist) { const int INF 1e9; int n (int)_graph.size(); std::vectorint dist(n, INF); std::vectorint prev(n, -1); std::priority_queueRouteNode pq; dist[start] 0; pq.push({ start, 0 }); while (!pq.empty()) { RouteNode cur pq.top(); pq.pop(); if (cur.dist ! dist[cur.stationId]) continue; // 跳过过期节点 if (cur.stationId end) break; for (const auto edge : _graph[cur.stationId]) { int nd cur.dist 1; if (nd dist[edge.to]) { dist[edge.to] nd; prev[edge.to] cur.stationId; pq.push({ edge.to, nd }); } } } outDist dist[end]; // 回溯路径 outPath.clear(); for (int v end; v ! -1; v prev[v]) { outPath.push_back(v); if (v start) break; } std::reverse(outPath.begin(), outPath.end()); }逻辑说明RouteNode重载了小于号但内容写的是dist other.dist这样priority_queue的默认大顶堆会被反转成小顶堆每次弹出当前距离最小的节点。cur.dist ! dist[cur.stationId]这个判断是核心因为同一个节点可能被多次入队只有最新最短的记录才需要处理。参数说明INF设置成1e9对站点数量300以内的图足够。prev数组记录路径前驱回溯时从终点逆推最后reverse得到从起点到终点的顺序。outPath里的元素是站点ID界面层再用m_idToName转成站名显示。4.2 最少换乘把“线路”当节点做BFS最少换乘问题的图不是站点图而是“线路图”。线路是节点换乘站是边如果某站同时属于线路1和线路2那么线路1和线路2之间连一条边。从起点站所在的线路出发BFS逐层扩散直到碰到终点站所在线路BFS的层数就是换乘次数。但这样只能算出换乘次数不能直接给站点路径。我一般这样实现int RouteFinder::MinTransfer(int start, int end, std::vectorstd::vectorint outRoutes) { if (start end) return 0; auto startLines _stationLines[start]; auto endLines _stationLines[end]; // 线路邻接表lineAdj[a] {b, transferStationId} // transferStationId是能让a、b两条线换乘的站点ID std::vectorstd::vectorLineEdge lineAdj; BuildLineAdj(lineAdj); std::queueint q; std::vectorint dist(lineAdj.size(), -1); std::vectorint prevLine(lineAdj.size(), -1); std::vectorCString transferInfo; // 调试用 // 起点站的所有线路作为初始层 for (int line : startLines) { dist[line] 0; q.push(line); } int targetLine -1; while (!q.empty()) { int curLine q.front(); q.pop(); // 如果当前线路包含终点站结束 for (int line : endLines) if (line curLine) { targetLine curLine; break; } if (targetLine ! -1) break; for (const auto e : lineAdj[curLine]) { if (dist[e.toLine] -1) { dist[e.toLine] dist[curLine] 1; prevLine[e.toLine] curLine; q.push(e.toLine); } } } int transfers targetLine -1 ? -1 : dist[targetLine]; // 回溯线路路径 std::vectorint linePath; for (int l targetLine; l ! -1; l prevLine[l]) { linePath.push_back(l); if (l startLines[0]) break; } std::reverse(linePath.begin(), linePath.end()); // 把线路路径转成站点路径这里只给线路列表 outRoutes.push_back(linePath); return transfers; }逻辑说明BuildLineAdj内部遍历每个站点把该站点所属的所有线路两两连边。这是个简化版实现实际问题里还需要考虑同一条线路有两个换乘站的情况但对于课程设计这个量级每个换乘站只记录一条边就够了。参数说明dist初始化为-1表示未访问这天然充当了visited数组。prevLine记录线路前驱最后回溯得到的是线路序列比如[1号线, 2号线]界面层再根据1号线和2号线的换乘站生成“坐1号线→新街口换2号线”这样的文字提示。4.3 两种算法如何结合我的习惯是界面层给两个单选按钮“最少站数”和“最少换乘”。最少站数直接调Dijkstra最少换乘调BFS线路图。如果用户要求在“换乘不超过1次的情况下站数最少”则需要在Dijkstra代价里加重换乘惩罚比如每次换乘加5站代价然后统一跑Dijkstra。实现细节在下一节展开但核心思路就是改边权。5. 界面实现让用户看见线路图和数据结果5.1 自绘控件映射坐标到屏幕线路图自绘不建议用静态图片。用GDI画线数据变化时重绘即可。我封装了一个MetroMapView类继承CWnd在对话框里把它作为一个自定义控件放置。核心是把站点真实坐标映射到控件客户区CPoint MetroMapView::MapToScreen(int stationId) { double minX _minLng, maxX _maxLng; double minY _minLat, maxY _maxLat; double sx (_coordX[stationId] - minX) / (maxX - minX); double sy 1.0 - (_coordY[stationId] - minY) / (maxY - minY); CRect rc; GetClientRect(rc); int px (int)(rc.left sx * (rc.Width() - 40) 20); int py (int)(rc.top sy * (rc.Height() - 40) 20); return CPoint(px, py); }逻辑说明这里假设每个站点数据文件里有经纬度坐标字段。如果没有真实坐标可以退化为按order把站点排成直线布局。映射公式里的1.0 -是为了把纬度从南到北翻转成屏幕的从下到上。参数说明减40留边距是为了避免站点圆点画到控件边缘。坐标归一化后乘可用宽度再加边距偏移。_coordX和_coordY是double数组在数据加载时填充。5.2 OnDraw画线、画站点、画当前路线void MetroMapView::OnPaint() { CPaintDC dc(this); dc.SetBkMode(TRANSPARENT); // 画所有线路底图 for (const auto line : _lines) { CPen pen(PS_SOLID, 2, line.color); CPen* pOld dc.SelectObject(pen); for (size_t i 0; i 1 line.stations.size(); i) { CPoint p1 MapToScreen(line.stations[i]); CPoint p2 MapToScreen(line.stations[i 1]); dc.MoveTo(p1); dc.LineTo(p2); } dc.SelectObject(pOld); } // 画站点圆 for (int id 0; id (int)_coords.size(); id) { CPoint pt MapToScreen(id); dc.Ellipse(pt.x - 3, pt.y - 3, pt.x 3, pt.y 3); } }逻辑说明CPen设置线宽2像素颜色来自线路配置表。画站点时用Ellipse画小圆正常站半径3像素换乘站可以半径5像素并画成空心。如果要高亮查询出的路径可以维护一个vector highlightPath在OnPaint里先画普通线再画一条粗红线段重描路径。参数说明dc.SelectObject返回旧画笔画完立即恢复否则画笔泄漏导致内存增长。DC本身由CPaintDC析构时释放不用手动DeleteObject。5.3 重绘策略尽量用InvalidateRect而不是Invalidate用户点“查询”后路径结果出现在CListCtrl里同时线路图上高亮路径。不要调用Invalidate()无条件全量重绘那会闪烁。正确做法是只失效路径所在区域CRect rcInvalid m_mapView.GetHighlightArea(); m_mapView.InvalidateRect(rcInvalid);逻辑说明GetHighlightArea返回高亮路径包围盒向外扩10像素的矩形。InvalidateRect只标记这个区域为无效WM_PAINT时通过裁剪区只重绘这一块效率提升明显。如果只是刷新CListCtrl不需要重绘地图。6. 避坑常见问题与调试技巧6.1 三个必踩的坑坑一数据文件乱码。现象下拉框里站名全是问号。原因CSV是UTF-8编码而工程Unicode下直接用CStdioFile读成了UTF-16。解决用第二节的MultiByteToWideChar转换流程或者统一把CSV另存为Unicode编码再读。坑二CListCtrl插入速度慢。现象一次性插入几百条路径点窗口卡住几秒。原因每调一次InsertItem都会触发控件重绘。解决批量插入前调SetRedraw(FALSE)插入完成后再SetRedraw(TRUE)并Invalidate()或使用虚拟列表风格设置LVS_OWNERDATA。坑三Dijkstra路径绕圈。现象明明有直达车算法输出的路径却来回换乘。原因优先队列里比较运算符方向写反导致每次弹出的是最大距离节点或者prev数组在松弛时覆盖了正确前驱。解决按4.1节代码写operator并加cur.dist ! dist[cur.stationId]的过期判断。我遇到过最隐蔽的是前后两条线路共用同一站点ID但没去重导致邻接表里出现自环边。6.2 验证算法结果的土办法动手前先准备一个三条线的极简数据1号线“火车站-广场-大学城”2号线“广场-机场”3号线“机场-景区”。手动验证最少站数火车站到机场应返回“火车站→广场→机场”2站。最少换乘火车站到景区应返回“坐1号线到广场换2号线到机场换3号线到景区”换乘2次。在代码里加一个自检按钮直接断言这些预期值输出“通过/失败”即可。6.3 一个绘画性能技巧自绘地铁图如果线路多OnPaint里Pen创建销毁会拖慢帧率。我的做法是把所有普通线路一次性画到一个内存DC位图上查询高亮时才覆盖红色粗线。MoveTo和LineTo只发生在重绘时平时拖动窗口不会闪烁。从那以后我每次做自绘控件都会强制先画底图缓存再处理动态高亮查询响应时间从肉眼可见的卡顿降到几乎无感。这个习惯让我少走很多弯路希望帮到你。本文还有配套的精品资源点击获取
简介这套基于MFC的南京地铁查询系统是一份完整的Visual C 6.0工程面向正在学习MFC框架或需要开发桌面信息查询系统的学生和开发者。系统实现了地铁线路与站点数据的存储、查询和可视化展示并提供了可直接运行的exe程序方便查看实际运行效果。整个压缩包包含43个文件大小仅2.44MB其中8个头文件和7个CPP文件构成主要源码配合Dlg、Prop等类完成界面交互与查询逻辑bmp、ico、rc等资源用于界面美化dsp、dsw、clw等工程配置便于直接编译调试readme和txt则提供必要的说明。目前已有962人学习下载。通过阅读完整源码能够清晰理解MFC的CWinApp程序入口、CDialog对话框设计、消息映射与事件处理以及数据读取和列表展示等关键步骤同时项目中的地铁图位图展示和路线查询逻辑也可为其他地理信息查询类软件提供可复用的设计参考。1. 基于MFC的南京地铁查询系统为什么一个课程设计值得认真做很多人第一次看到“基于MFC的南京地铁查询系统”这个题目第一反应是“又是MFC老掉牙了”。但真把需求拆开你会发现它恰好覆盖了MFC里最值得练的三件事文档数据怎么进内存、图算法怎么在UI线程里跑、自绘控件怎么画得又快又对。这篇文章要拆的就是这样一套完整的系统用VS MFC对话框搭出查询窗口把南京地铁的线路站点数据读进邻接表再用Dijkstra算最少站数、用BFS算最少换乘最后把最优路线画在自绘区里。新手能照着把环境跑起来老手可以重点看编码、算法引擎和重绘这三类坑。2. 工程结构先把“查询系统”拆成三层再动手2.1 为什么选MFC对话框而不是单文档视图常见做法是新建一个MFC对话框程序而不是用单文档视图SDI。原因很简单地铁查询系统的主界面就是“两个下拉框 一个按钮 一个结果列表”没有复杂的文档概念。对话框的DoModal循环天然适合这种交互生成菜单、工具栏那些代码都是噪音。但有个地方要用到视图框架的能力自绘线路图。对话框里放一个自定义的Picture Control或者直接重写对话框的OnPaint让它在指定区域绘图。如果你把绘图区域封装成一个继承自CWnd的控件类那么对话框和单文档的差别就不大了。我的建议是对话框为主体自绘控件单独拆成类方便以后如果要做成大窗口直接换成CScrollView。2.2 三层结构数据层、算法层、界面层别把CSV解析、Dijkstra、OnPaint全塞在对话框类里否则一个文件能写到三千行。拆三层数据层 MetroData负责读文件、存站点、建邻接表、提供查询接口。算法层 RouteFinder接受MetroData的图结构返回最短路径或最少换乘结果。界面层 CMetroQueryDlg只负责收集用户输入、调用算法层、刷新列表和绘图。这样做的最大好处是调试时可以单独给RouteFinder写控制台测试不用启动界面。MFC工程里加一个命令行入口不是不行但我一般直接加一个“自检”按钮把几条已知路径的结果弹出来。2.3 初始化文件与界面骨架代码先看数据加载。南京地铁站点数据我建议存成一个CSV格式如下每行一条记录line_id,station_name,order 1,迈皋桥,1 1,红山动物园,2 1,南京站,3 ... 2,油坊桥,1 2,雨润大街,2读取时需要注意如果用MFC的CStdioFile的ReadString按Unicode读UTF-8文件会乱码。下面这段代码先把文件按UTF-8字节读进来再手动转成宽字符最后用CString存站名bool MetroData::LoadFromFile(const CString path) { std::ifstream in(CT2A(path.GetString())); if (!in.is_open()) return false; std::string utf8Line; while (std::getline(in, utf8Line)) { if (utf8Line.empty()) continue; // 计算UTF-8字节串转成宽字符所需长度 int wLen MultiByteToWideChar(CP_UTF8, 0, utf8Line.c_str(), (int)utf8Line.size(), nullptr, 0); if (wLen 0) continue; std::wstring wBuf(wLen, L\0); MultiByteToWideChar(CP_UTF8, 0, utf8Line.c_str(), (int)utf8Line.size(), wBuf[0], wLen); CString line(wBuf.c_str()); int pos1 line.Find(_T(,)); int pos2 line.Find(_T(,), pos1 1); if (pos1 0 || pos2 0) continue; int lineId _ttoi(line.Left(pos1)); CString station line.Mid(pos1 1, pos2 - pos1 - 1); int order _ttoi(line.Mid(pos2 1)); m_stations.push_back(StationRecord{ lineId, station, order }); } BuildGraph(); return true; }逻辑说明先用std::ifstream按二进制方式读UTF-8文本避免CStdioFile默认按本地代码页读取然后用MultiByteToWideChar把每行UTF-8转成UTF-16。这样在Unicode项目中CString拿到的就是正确的中文站名。要注意find查找分隔符的结果是相对位置截取站名时Mid的长度要算对否则最后一个中文字符会被吞掉。参数说明CP_UTF8指源字符串编码wBuf是转换目标缓冲区MultiByteToWideChar的第五个参数传-1表示字符串以\0结尾但这里显式传长度更规范因为getline的结果里没结尾符。转换成功后wBuf末尾会有\0CString构造会自动处理。2.4 BuildGraph从站点表到邻接表读取完成后必须把“线路-站点-顺序”转换成适合寻路的邻接表。我一般用站点名做全局IDvoid MetroData::BuildGraph() { // 先给每个站点分配ID int id 0; for (auto rec : m_stations) { if (m_stationId.find(rec.station) m_stationId.end()) { m_stationId[rec.station] id; m_idToName.push_back(rec.station); } } m_graph.assign(m_idToName.size(), {}); m_stationLines.assign(m_idToName.size(), {}); // 按线路分组然后组内相邻站建边 std::mapint, std::vectorStationRecord byLine; for (auto rec : m_stations) byLine[rec.lineId].push_back(rec); for (auto kv : byLine) { auto vec kv.second; std::sort(vec.begin(), vec.end(), [](const StationRecord a, const StationRecord b) { return a.order b.order; }); for (size_t i 0; i 1 vec.size(); i) { int u m_stationId[vec[i].station]; int v m_stationId[vec[i 1].station]; m_graph[u].push_back({ v, kv.first }); m_graph[v].push_back({ u, kv.first }); } // 记录每个站经过的所有线路 for (auto rec : vec) m_stationLines[m_stationId[rec.station]].push_back(kv.first); } }逻辑说明m_stationId是map把中文站名映射到连续整数IDm_idToName用于反查站名。m_graph是邻接表边结构里除了目标站点ID还存这条边属于哪条线路这样在结果输出时能告诉用户“乘坐1号线从A到B”。m_stationLines后面算最少换乘要用。参数说明m_graph[u].push_back({v, kv.first})里的kv.first是线路ID。这里用vector存邻接表站点数量不超过300内存占用无所谓但排序按order能保证同一条线上顺序正确。如果数据文件里线路ID重复或order有乱序排序这步很重要。3. 数据是黑匣子先谈编码、再谈结构3.1 为什么地铁查询系统要纠结CSV编码MFC工程在VS 2019/2022上默认字符集是UnicodeCString是UTF-16宽字符。而大多数数据文件来源是Excel另存的CSVExcel在国内保存默认是GBK从网页复制出来的可能是UTF-8。如果直接ifstream读进std::string再赋给CString中文字符串全部变成问号。这个坑我在第二节代码里已经绕过去了统一要求数据文件是UTF-8读取时用MultiByteToWideChar转成宽字符。有人问那用CStdioFile的typeText模式读Unicode编码的文件不就行了吗CStdioFile在Unicode项目里确实读UTF-16文件没问题但要求文件带BOMFF FE。问题是很多GIS或爬虫导出的CSV是UTF-8 no BOM打开就是乱码。所以我的习惯是数据文件保存为UTF-8有BOM更稳程序里用字节流读取后手动转码。这样不管VS工程是ANSI还是Unicode都能兼容。3.2 数据结构为什么要建双向边和换乘站表上面的BuildGraph里我建的是双向边因为地铁可以坐反向。换乘站不需要特殊标记它的特点是在邻接表里同时出现多条线路的边。比如新街口站在1号线和2号线都有记录那么它的邻接节点既包括1号线的相邻站也包括2号线的相邻站Dijkstra跑的时候自然能“换乘”。但要注意如果单纯用Dijkstra找最少站数换乘次数不会被惩罚。一个从A到B的方案可能是“坐1号线2站到换乘站再坐2号线1站”共3站另一个方案“坐3号线直通”共4站最少站数会选择前者。如果你的需求是“优先换乘少”那不能只用Dijkstra要改算法。3.3 查询接口数据层对外屏蔽细节数据层给界面层提供三个接口就够了// 获取所有站名用于下拉框 std::vectorCString GetAllStations() const { return m_idToName; } // 获取某站的ID不存在返回-1 int GetStationId(const CString name) const { auto it m_stationId.find(name); return it m_stationId.end() ? -1 : it-second; } // 获取某站经过的线路列表 std::vectorint GetLinesOfStation(int stationId) const { return m_stationLines[stationId]; }界面层拿到站名填充CComboBox用户选完站后调GetStationId然后交给算法层。这样的好处是后续如果要换数据库只需要改MetroData内部实现RouteFinder和界面类不用动。4. 换乘算法最少站数和最少换乘是两套逻辑4.1 最少站数Dijkstra的等权实现因为地铁每坐一站代价是1理论上BFS也能求最少站数。但Dijkstra写出来以后可以扩展“换乘惩罚权重”所以我还是选择Dijkstra。实现时用优先队列做小顶堆struct RouteNode { int stationId; int dist; bool operator(const RouteNode other) const { return dist other.dist; // 注意方向 } }; void RouteFinder::ShortestPath(int start, int end, std::vectorint outPath, int outDist) { const int INF 1e9; int n (int)_graph.size(); std::vectorint dist(n, INF); std::vectorint prev(n, -1); std::priority_queueRouteNode pq; dist[start] 0; pq.push({ start, 0 }); while (!pq.empty()) { RouteNode cur pq.top(); pq.pop(); if (cur.dist ! dist[cur.stationId]) continue; // 跳过过期节点 if (cur.stationId end) break; for (const auto edge : _graph[cur.stationId]) { int nd cur.dist 1; if (nd dist[edge.to]) { dist[edge.to] nd; prev[edge.to] cur.stationId; pq.push({ edge.to, nd }); } } } outDist dist[end]; // 回溯路径 outPath.clear(); for (int v end; v ! -1; v prev[v]) { outPath.push_back(v); if (v start) break; } std::reverse(outPath.begin(), outPath.end()); }逻辑说明RouteNode重载了小于号但内容写的是dist other.dist这样priority_queue的默认大顶堆会被反转成小顶堆每次弹出当前距离最小的节点。cur.dist ! dist[cur.stationId]这个判断是核心因为同一个节点可能被多次入队只有最新最短的记录才需要处理。参数说明INF设置成1e9对站点数量300以内的图足够。prev数组记录路径前驱回溯时从终点逆推最后reverse得到从起点到终点的顺序。outPath里的元素是站点ID界面层再用m_idToName转成站名显示。4.2 最少换乘把“线路”当节点做BFS最少换乘问题的图不是站点图而是“线路图”。线路是节点换乘站是边如果某站同时属于线路1和线路2那么线路1和线路2之间连一条边。从起点站所在的线路出发BFS逐层扩散直到碰到终点站所在线路BFS的层数就是换乘次数。但这样只能算出换乘次数不能直接给站点路径。我一般这样实现int RouteFinder::MinTransfer(int start, int end, std::vectorstd::vectorint outRoutes) { if (start end) return 0; auto startLines _stationLines[start]; auto endLines _stationLines[end]; // 线路邻接表lineAdj[a] {b, transferStationId} // transferStationId是能让a、b两条线换乘的站点ID std::vectorstd::vectorLineEdge lineAdj; BuildLineAdj(lineAdj); std::queueint q; std::vectorint dist(lineAdj.size(), -1); std::vectorint prevLine(lineAdj.size(), -1); std::vectorCString transferInfo; // 调试用 // 起点站的所有线路作为初始层 for (int line : startLines) { dist[line] 0; q.push(line); } int targetLine -1; while (!q.empty()) { int curLine q.front(); q.pop(); // 如果当前线路包含终点站结束 for (int line : endLines) if (line curLine) { targetLine curLine; break; } if (targetLine ! -1) break; for (const auto e : lineAdj[curLine]) { if (dist[e.toLine] -1) { dist[e.toLine] dist[curLine] 1; prevLine[e.toLine] curLine; q.push(e.toLine); } } } int transfers targetLine -1 ? -1 : dist[targetLine]; // 回溯线路路径 std::vectorint linePath; for (int l targetLine; l ! -1; l prevLine[l]) { linePath.push_back(l); if (l startLines[0]) break; } std::reverse(linePath.begin(), linePath.end()); // 把线路路径转成站点路径这里只给线路列表 outRoutes.push_back(linePath); return transfers; }逻辑说明BuildLineAdj内部遍历每个站点把该站点所属的所有线路两两连边。这是个简化版实现实际问题里还需要考虑同一条线路有两个换乘站的情况但对于课程设计这个量级每个换乘站只记录一条边就够了。参数说明dist初始化为-1表示未访问这天然充当了visited数组。prevLine记录线路前驱最后回溯得到的是线路序列比如[1号线, 2号线]界面层再根据1号线和2号线的换乘站生成“坐1号线→新街口换2号线”这样的文字提示。4.3 两种算法如何结合我的习惯是界面层给两个单选按钮“最少站数”和“最少换乘”。最少站数直接调Dijkstra最少换乘调BFS线路图。如果用户要求在“换乘不超过1次的情况下站数最少”则需要在Dijkstra代价里加重换乘惩罚比如每次换乘加5站代价然后统一跑Dijkstra。实现细节在下一节展开但核心思路就是改边权。5. 界面实现让用户看见线路图和数据结果5.1 自绘控件映射坐标到屏幕线路图自绘不建议用静态图片。用GDI画线数据变化时重绘即可。我封装了一个MetroMapView类继承CWnd在对话框里把它作为一个自定义控件放置。核心是把站点真实坐标映射到控件客户区CPoint MetroMapView::MapToScreen(int stationId) { double minX _minLng, maxX _maxLng; double minY _minLat, maxY _maxLat; double sx (_coordX[stationId] - minX) / (maxX - minX); double sy 1.0 - (_coordY[stationId] - minY) / (maxY - minY); CRect rc; GetClientRect(rc); int px (int)(rc.left sx * (rc.Width() - 40) 20); int py (int)(rc.top sy * (rc.Height() - 40) 20); return CPoint(px, py); }逻辑说明这里假设每个站点数据文件里有经纬度坐标字段。如果没有真实坐标可以退化为按order把站点排成直线布局。映射公式里的1.0 -是为了把纬度从南到北翻转成屏幕的从下到上。参数说明减40留边距是为了避免站点圆点画到控件边缘。坐标归一化后乘可用宽度再加边距偏移。_coordX和_coordY是double数组在数据加载时填充。5.2 OnDraw画线、画站点、画当前路线void MetroMapView::OnPaint() { CPaintDC dc(this); dc.SetBkMode(TRANSPARENT); // 画所有线路底图 for (const auto line : _lines) { CPen pen(PS_SOLID, 2, line.color); CPen* pOld dc.SelectObject(pen); for (size_t i 0; i 1 line.stations.size(); i) { CPoint p1 MapToScreen(line.stations[i]); CPoint p2 MapToScreen(line.stations[i 1]); dc.MoveTo(p1); dc.LineTo(p2); } dc.SelectObject(pOld); } // 画站点圆 for (int id 0; id (int)_coords.size(); id) { CPoint pt MapToScreen(id); dc.Ellipse(pt.x - 3, pt.y - 3, pt.x 3, pt.y 3); } }逻辑说明CPen设置线宽2像素颜色来自线路配置表。画站点时用Ellipse画小圆正常站半径3像素换乘站可以半径5像素并画成空心。如果要高亮查询出的路径可以维护一个vector highlightPath在OnPaint里先画普通线再画一条粗红线段重描路径。参数说明dc.SelectObject返回旧画笔画完立即恢复否则画笔泄漏导致内存增长。DC本身由CPaintDC析构时释放不用手动DeleteObject。5.3 重绘策略尽量用InvalidateRect而不是Invalidate用户点“查询”后路径结果出现在CListCtrl里同时线路图上高亮路径。不要调用Invalidate()无条件全量重绘那会闪烁。正确做法是只失效路径所在区域CRect rcInvalid m_mapView.GetHighlightArea(); m_mapView.InvalidateRect(rcInvalid);逻辑说明GetHighlightArea返回高亮路径包围盒向外扩10像素的矩形。InvalidateRect只标记这个区域为无效WM_PAINT时通过裁剪区只重绘这一块效率提升明显。如果只是刷新CListCtrl不需要重绘地图。6. 避坑常见问题与调试技巧6.1 三个必踩的坑坑一数据文件乱码。现象下拉框里站名全是问号。原因CSV是UTF-8编码而工程Unicode下直接用CStdioFile读成了UTF-16。解决用第二节的MultiByteToWideChar转换流程或者统一把CSV另存为Unicode编码再读。坑二CListCtrl插入速度慢。现象一次性插入几百条路径点窗口卡住几秒。原因每调一次InsertItem都会触发控件重绘。解决批量插入前调SetRedraw(FALSE)插入完成后再SetRedraw(TRUE)并Invalidate()或使用虚拟列表风格设置LVS_OWNERDATA。坑三Dijkstra路径绕圈。现象明明有直达车算法输出的路径却来回换乘。原因优先队列里比较运算符方向写反导致每次弹出的是最大距离节点或者prev数组在松弛时覆盖了正确前驱。解决按4.1节代码写operator并加cur.dist ! dist[cur.stationId]的过期判断。我遇到过最隐蔽的是前后两条线路共用同一站点ID但没去重导致邻接表里出现自环边。6.2 验证算法结果的土办法动手前先准备一个三条线的极简数据1号线“火车站-广场-大学城”2号线“广场-机场”3号线“机场-景区”。手动验证最少站数火车站到机场应返回“火车站→广场→机场”2站。最少换乘火车站到景区应返回“坐1号线到广场换2号线到机场换3号线到景区”换乘2次。在代码里加一个自检按钮直接断言这些预期值输出“通过/失败”即可。6.3 一个绘画性能技巧自绘地铁图如果线路多OnPaint里Pen创建销毁会拖慢帧率。我的做法是把所有普通线路一次性画到一个内存DC位图上查询高亮时才覆盖红色粗线。MoveTo和LineTo只发生在重绘时平时拖动窗口不会闪烁。从那以后我每次做自绘控件都会强制先画底图缓存再处理动态高亮查询响应时间从肉眼可见的卡顿降到几乎无感。这个习惯让我少走很多弯路希望帮到你。本文还有配套的精品资源点击获取
