简介这份面向C与数据结构学习者的课设资料以老鼠走迷宫为主题可用于课程设计参考、图与搜索算法练习及项目复盘帮助读者把二维数组迷宫建模、路径搜索和回溯过程落到可运行工程中。压缩包共27个文件约148.59MB内含cpp/h源码、sln与vcxproj工程配置、exe可执行程序、txt使用说明以及mp4演示与替换素材、png/jpg界面截图和调试日志等覆盖从编译运行到效果展示的完整链路。已有1391人学习下载说明该课设在同类数据结构项目中具有一定参考价值。读者可据此理解随机迷宫生成中DFS的连通性处理、唯一解构造以及用栈或递归完成路径搜索、用队列拓展BFS思路、终点判定和失败回溯等关键环节也能结合演示视频与说明文档核对运行效果、排查工程配置问题。1. 一道迷宫题为什么值得写两套搜索数据结构课设里「老鼠走迷宫」几乎是最容易被低估的一题。多数人拿到题目后第一反应是写个递归能跑出结果就交答辩时被问一句「你这条路径是最短的吗」就卡住了。这道题真正要练的是两套线性结构的对照用栈模拟深度优先搜索的回溯过程用队列做广度优先搜索拿到最短路径同一张地图跑出两种结果再比一比谁快、谁省、谁更贴近工程里的真实用法。C 实现、控制台可演示、地图支持随机生成与文件读入适合正在赶课设、又不想只交一份「能跑就算完」的读者也适合想把数据结构从考试题拉回可运行代码的人。2. 迷宫的数据表示与总体分层一张二维数组怎么撑起两套搜索在写搜索之前先把地图和坐标定死。课设里翻车的项目九成不是算法写错而是表示层没统一有人用 0 表示墙、1 表示路有人反过来有人在 (x, y) 里塞行列有人塞列行有人数组从 0 开始算边界有人额外加了一圈墙。等到 DFS 和 BFS 两份代码放在一起坐标含义不一致调半天都调不通。所以这一章先把「地图长什么样、坐标怎么数、模块怎么分」拍板后面两章的实现才有共同语言。2.1 地图约定把围墙砌在数组边界上约定只有三条写进注释里全项目不准再改0表示通路1表示墙2表示搜索过程中已访问过的格子只用于打印轨迹不参与判定。坐标用(row, col)行向下增长列向右增长起点(1,1)、终点(n,m)。读入地图时为四周补一圈墙把n × m的原始地图变成(n2) × (m2)。第三条是整套实现里最值钱的一处偷懒。补边之后「越界」这个分支在逻辑上消失了——走出地图边界等于撞墙方向判断只剩一句maze[nx][ny] ROAD。代价是多花两行两列的内存换来 DFS、BFS 里所有边界特判全部省掉也让后面用代码逐格对比路径时少一层心理负担。// 读入 n 行 m 列的 0/1 地图四周补一圈墙返回 (n2) x (m2) 的数组 std::vectorstd::vectorint loadMaze(int n, int m, std::istream in) { std::vectorstd::vectorint maze(n 2, std::vectorint(m 2, WALL)); for (int i 1; i n; i) for (int j 1; j m; j) in maze[i][j]; // 0 通路1 墙 return maze; // maze[0][*] 和 maze[n1][*] 天然是墙 }参数只有三个原始行数n、列数m、输入流in。返回值是补边后的新地图调用方拿到的坐标已经「偏移过」所以起点固定写(1,1)而不是(0,0)。这个偏移量建议定义成常量const int OFF 1;否则后期加一个「从文件读起点终点」的功能又要满项目改坐标。2.2 方向增量表四个方向写成一个数组迷宫搜索里最啰嗦的代码是「上、下、左、右」四段几乎一样的 if。解决办法是方向增量表把行偏移、列偏移各存一个长度 4 的数组循环 4 次就等价于写 4 段分支。它的好处不止是短还在于扩展性——哪天要求老鼠可以斜着走8 方向只改数组内容搜索逻辑一行不动。const int WALL 1; const int ROAD 0; const int VISITED 2; // 上、下、左、右顺序会直接影响 DFS 首次找到的路径形态 const int DX[4] {-1, 1, 0, 0}; const int DY[4] { 0, 0, -1, 1}; const char* DIR_NAME[4] {上, 下, 左, 右};方向顺序不是随便排的。DFS 会优先沿排在前面的方向一路钻到底所以把「上」放在第一位老鼠会表现出明显的「先往上贴、撞墙再折」的行为。这不是 bug而是答辩时可以主动讲的一个点同一张图换一个方向顺序找到的路径就变了但「是否可达」不变——正好用来解释 DFS 的解为什么不唯一、也不最优。2.3 三层结构输入层、搜索层、输出层各自管什么课设项目规模不大但结构要立住否则最后所有代码挤在main里改一个参数要全文搜。我一般拆成三层层与层之间只通过地图数组和路径数组通信层模块输入输出说明输入层文件读入文本文件补边后的地图一行一行读 0/1格式错误直接报错退出输入层随机生成行列数、墙密度连通性可验证的地图生成后必须跑一次 BFS 验通不通就重生成搜索层DFS 求解地图、起点、终点一条可行路径用栈不保证最短搜索层BFS 求解地图、起点、终点最短路径 步数用队列保证最短输出层文本渲染地图、路径控制台字符画用*画路径#画墙输出层统计输出两次搜索结果步数、访问格数、耗时答辩时的对比素材把「随机生成」放在输入层而不是搜索层是为了让搜索函数保持纯函数性质传进去什么地图就按什么地图算不掺任何随机性。这样单元测试好写也方便固定几张小地图当验收用例。2.4 核心类型与通行判断栈里存什么直接决定了回溯能不能写对。只存(x, y)是不够的——回退到某个格子时你不知道上一次已经试到第几个方向只能从「上」重新试一遍于是同一格被反复压栈轻则变慢重则死循环。所以要存三元组坐标加「下一个该尝试的方向下标」。struct Block { int x, y; // 当前格坐标 int dir; // 下一次尝试的方向下标 0..3等于 4 表示四个方向都试过了 }; // 补边之后这个函数理论上永远返回 true保留它是为了防御性编程 bool inMaze(const std::vectorstd::vectorint m, int x, int y) { return x 0 x (int)m.size() y 0 y (int)m[0].size(); } bool passable(const std::vectorstd::vectorint m, int x, int y) { return inMaze(m, x, y) m[x][y] ROAD; // 只有通路才可走 }passable里只判ROAD不判VISITED因为「已访问」的语义在两套算法里不一样DFS 里访问过的格子不能再进否则绕圈BFS 里用dist -1判首次到达更自然。把这两条判断拆开写比在一个函数里塞三个条件清楚得多。3. 栈实现深度优先搜索回溯法的骨架就在这三行深度优先搜索在教材里通常写成递归十几行就能出结果。但课设要求「用栈实现」很多人第一反应是「递归不就是栈吗」然后把递归函数原样抄一遍交上去答辩时被要求现场手写非递归版本就露馅了。更实际的问题是递归版本看不到「老鼠当前走过的整条路」而这条路由栈里所有元素组成恰恰是演示效果最好的东西。所以这一章把递归拆开用显式栈重写一遍。3.1 递归能跑为什么还要显式栈递归的调用栈由系统托管你只能看到「当前这一层」看不到整条路径。想在中途打印「老鼠现在走到哪、之前走过哪些格」递归得靠额外传一个路径数组还得在每层进出时手动维护代码反而更长。显式栈把这条路径摊开摆在眼前栈底是起点栈顶是老鼠当前位置中间就是它走过的轨迹。演示时每压一次栈打印一遍地图动画效果自然就出来了。另一个理由是可控性。递归深度受系统栈限制虽然迷宫题规模小到不会真的爆栈但「用显式栈可以随时限制最大深度、可以中途导出状态」这个说法在答辩里是加分的——它说明你知道两种写法的差别在哪而不是只会背代码。3.2 栈元素为什么必须是三元组前面定了Block{x, y, dir}这里说清dir的用法。核心动作只有一句取栈顶元素把dir从当前值往后扫找到第一个可走的方向就dir并把新格子压栈如果四个方向都扫完还走不通弹出栈顶回溯到上一格。关键在于dir要写回栈顶元素本身而不是拷贝一份局部变量改。如果写成Block cur st.top();那么cur.dir改的是副本栈里那份还是 0回退到这一格时会从「上」重新开始试——重复探索、路径错乱、严重时死循环。这是一行引用符号的差别也是这套实现里最容易翻车的地方。3.3 完整实现入栈即标记出栈不撤销#include stack #include vector #include algorithm // 返回是否找到通路path 按从起点到终点的顺序存放路径坐标 bool dfsFindPath(std::vectorstd::vectorint maze, int sx, int sy, int ex, int ey, std::vectorstd::pairint,int path) { std::stackBlock st; st.push({sx, sy, 0}); maze[sx][sy] VISITED; // 入栈前就标记杜绝同一格重复入栈 while (!st.empty()) { Block cur st.top(); // 必须用引用dir 的修改要写回栈里 if (cur.x ex cur.y ey) { path.clear(); std::stackBlock tmp st; // 复制一份再逐个弹出避免破坏原栈 while (!tmp.empty()) { path.push_back({tmp.top().x, tmp.top().y}); tmp.pop(); } std::reverse(path.begin(), path.end()); // 弹出顺序是终点到起点 return true; } bool moved false; while (cur.dir 4) { // 依次试四个方向 int d cur.dir; int nx cur.x DX[d]; int ny cur.y DY[d]; if (passable(maze, nx, ny)) { // 未越界且是通路且没访问过 maze[nx][ny] VISITED; st.push({nx, ny, 0}); moved true; break; } } if (!moved) st.pop(); // 四个方向全试完回溯标记不撤销 } return false; // 栈空仍未到终点不可达 }几处参数和写法要交代清楚。maze是按值传递的函数内部随便改VISITED都不会污染调用方的原始地图调用方想再跑一次 BFS 直接传原图即可如果在意拷贝开销改成传引用然后在函数内自己复制一份语义一样。path是输出参数由调用方负责分配函数只在找到路径时清空重填。返回值用bool而不是「返回路径长度」是因为「不可达」和「路径长度为 0」在语义上必须区分开。cur.dir那行是后置自增d拿到当前要试的方向dir同时前进一格。这样即使这个方向走不通下一次循环也不会重复试同一个方向。3.4 回溯时到底要不要撤销标记这是课设里被问得最多的问题答案取决于你要什么。如果只问「从起点能不能到终点」标记不需要撤销。理由很直接一个格子只要被探索过从它出发能到达的所有格子就已经被探索完了第二次走到它结果必然一样撤销标记只会让搜索量指数级膨胀。但如果你要「枚举所有通路」或者「找出全部路径里最短的那条」就必须撤销——因为一条路径用过的格子另一条路径可能还要用。这时候标记要改成「当前栈内标记」出栈时恢复成ROAD。这个改动只有一行但语义完全不同答辩时能主动说出这个区别比背十遍算法定义都管用。// 枚举全部路径时的回溯写法出栈时把格子恢复成通路 if (!moved) { maze[st.top().x][st.top().y] ROAD; // 撤销标记 st.pop(); }复杂度方面每个格子最多入栈一次每次最多试 4 个方向时间是O(n·m)空间最坏情况栈里存下整条路径也是O(n·m)。这个结论要能当场推而不是背。4. 队列实现广度优先搜索最短路径靠两张表还原DFS 找到的路径能用但不好看——它经常贴着墙一路钻到死角再折回来路径长度可能是最短路径的两三倍。课设里加上 BFS 这一半「同一张地图、两种结果」的对比就成立了答辩时也有了可以量化的东西步数、访问格数、耗时。BFS 的代码比 DFS 短但要写对路径还原得先把两张辅助表想明白。4.1 BFS 在迷宫里的物理含义把迷宫看成一张无权图每个通路格子是一个节点上下左右相邻的通路之间有一条边。BFS 就是从这个图上按「层」向外扩散第一层是离起点 1 步的格子第二层是 2 步的依此类推。因为是按层扩展的任何格子第一次被访问到时用的步数一定是最少的——这就是「BFS 保证最短」的全部理由不需要额外证明。落到代码上「层」这个概念体现为队列队首出队时把它所有没访问过的邻居入队这些邻居的步数等于当前格步数加一。队列先进先出的特性天然保证了步数小的格子先被处理。4.2 dist 与 pre两张表撑起路径还原BFS 本身只能告诉你「最少几步」说不出「具体怎么走」。要还原路径得在扩散过程中记两样东西dist[x][y]起点到(x,y)的最少步数初始化为-1表示未访问。它同时兼任「访问标记」一举两得。pre[x][y](x,y)是从哪个格子走过来的用来从终点倒推回起点。用dist -1当访问标记比额外开一个bool visited更省事也更不容易出「标记了但忘了改 dist」这类不一致的 bug。#include queue // 返回最短步数不可达返回 -1path 为最短路径起点到终点 int bfsShortest(const std::vectorstd::vectorint maze, int sx, int sy, int ex, int ey, std::vectorstd::pairint,int path) { int n maze.size(), m maze[0].size(); std::vectorstd::vectorint dist(n, std::vectorint(m, -1)); std::vectorstd::vectorstd::pairint,int pre( n, std::vectorstd::pairint,int(m, {-1, -1})); std::queuestd::pairint,int q; dist[sx][sy] 0; q.push({sx, sy}); while (!q.empty()) { auto [x, y] q.front(); // 需要 -stdc17 q.pop(); if (x ex y ey) break; for (int d 0; d 4; d) { int nx x DX[d]; int ny y DY[d]; if (passable(maze, nx, ny) dist[nx][ny] -1) { dist[nx][ny] dist[x][y] 1; pre[nx][ny] {x, y}; q.push({nx, ny}); } } } if (dist[ex][ey] -1) return -1; // 终点没被访问到 path.clear(); for (std::pairint,int p {ex, ey}; p.first ! -1; p pre[p.first][p.second]) path.push_back(p); std::reverse(path.begin(), path.end()); return dist[ex][ey]; }maze传的是常引用因为 BFS 不需要修改地图dist已经承担了标记职责这跟 DFS 的按值传递形成对比可以在答辩时点一句两个函数对地图的权限需求不同所以参数形式也不同。pre用二维pair数组存前驱内存是O(n·m)对课设规模完全够用。如果换成大图可以改成用一个整数编码x * m y省一半空间——这是个可讲可不讲的优化点讲了显得有余量。结构化绑定auto [x, y]是 C17 才有的语法编译要加-stdc17。如果你的环境还停在 C11改成int x q.front().first; int y q.front().second;即可逻辑不变。4.3 路径还原从终点倒着走回去for循环那三行是路径还原的全部从终点出发每次用pre跳到前驱直到前驱为(-1,-1)也就是起点。收集出来的顺序是「终点 → 起点」所以要reverse一次。这一步漏掉不会报错只会让打印出来的路径看着像从终点出发的验收时被一眼看穿。起点那一格的前驱保持(-1,-1)是循环的终止条件。这里有个隐含前提起点的pre必须是初始值不能被搜索过程改掉。BFS 里只有「第一次访问某格」时才写pre起点一开始就被标记为已访问所以不会被覆盖这个不变式成立。// 把路径叠加到地图上打印# 墙* 路径S/E 起终点. 通路 void printMaze(const std::vectorstd::vectorint maze, const std::vectorstd::pairint,int path, int sx, int sy, int ex, int ey) { std::vectorstd::vectorchar g(maze.size(), std::vectorchar(maze[0].size(), )); for (size_t i 0; i maze.size(); i) for (size_t j 0; j maze[i].size(); j) g[i][j] (maze[i][j] WALL) ? # : .; for (auto p : path) g[p.first][p.second] *; g[sx][sy] S; g[ex][ey] E; for (auto row : g) { for (char c : row) std::cout c; std::cout \n; } }实际演示时把maze传成「未被 DFS 污染的原图」就行因为VISITED只影响判定不影响WALL/ROAD的区分打印函数里只判WALL即可。4.4 两套搜索的取舍对比项栈 DFS队列 BFS辅助结构std::stackBlockstd::queuepairint,int额外空间路径长度量级distpre两张表路径是否最短否取决于方向顺序是按层扩展保证典型步数偏长常贴墙绕行最短视觉上更「直」是否可达判定能能适用场景只要一条通路、内存紧要最优解、要步数统计表格可以直接搬进课设报告的「算法对比」一节。有了它「为什么写两套」这个问题就不用临场编了。5. 避坑与排查五个最容易翻车的点代码跑通和代码写对是两件事。下面这五条是我在课设里见过、自己也踩过的坑按「现象 → 原因 → 解决」写照着对一遍能省下大半个通宵。5.1 搜索阶段的三个坑坑一程序卡死不动或者跑出来的路径长到离谱。现象是控制台光标一直闪几秒后要么超时要么输出一条几百步的路径。原因几乎总是标记时机错了——在st.pop()之后才把格子标成VISITED或者干脆忘了标记于是同一个格子被反复压栈形成 A→B→A 的死循环。解决方式很明确入栈之前就标记一行maze[nx][ny] VISITED;必须写在st.push(...)的上方。顺序反了逻辑就反了。坑二访问到边界外面程序直接崩。现象是段错误或者打印出一堆乱码。原因有两个一是没做补边方向推进后坐标变成 -1 或 n直接拿去索引数组二是做了补边但随机生成地图时把墙写到了外圈上破坏了「边界必为墙」的不变式。解决补边在loadMaze里统一做生成器只允许改[1..n][1..m]范围内的格子passable里保留inMaze判断作为第二道防线多一次比较换一个不会崩的程序很值。坑三回退之后路径乱跳明明走不通的格子出现在结果里。现象是打印出来的路径不连续两个相邻坐标差好几格。原因通常是栈元素里没有dir字段回退后从「上」重新试把一个早就试过的方向又走了一遍或者把局部变量当成栈顶元素的副本改改动没写回栈里。解决Block必须带dir取栈顶时用Block cur st.top();确认这行有。5.2 结果输出阶段的两个坑坑四最短路径打印出来是反的。现象是 BFS 报的步数没错但画在地图上的路径从终点出发往起点走S和E之间还断了一截。原因是从终点沿pre倒推收集得到的是逆序忘了std::reverse。解决收集完立刻翻转并在函数注释里写明「path 按起点到终点顺序返回」让调用方不必猜。坑五随机生成的迷宫十次里有三次无解演示当场尴尬。现象是同一个生成函数有时 BFS 返回 -1屏幕上就一个孤零零的S。原因是随机撒墙不保证连通性起点和终点可能被墙彻底隔开。解决生成之后立刻跑一次 BFS 验通不通就重新生成加一个重试上限比如 50 次防止密度设得太高时无限循环。这一段别省答辩现场点「重新生成」按钮点出个无解地图比代码写错还难受。// 随机生成 连通性校验最多重试 50 次 std::vectorstd::vectorint generateMaze(int n, int m, double wallRate) { std::mt19937 rng(std::random_device{}()); std::uniform_real_distributiondouble dist(0.0, 1.0); for (int attempt 0; attempt 50; attempt) { std::vectorstd::vectorint maze(n 2, std::vectorint(m 2, WALL)); for (int i 1; i n; i) for (int j 1; j m; j) maze[i][j] (dist(rng) wallRate) ? WALL : ROAD; maze[1][1] ROAD; maze[n][m] ROAD; // 起终点强制打通 std::vectorstd::pairint,int tmp; if (bfsShortest(maze, 1, 1, n, m, tmp) 0) return maze; // 连通才返回 } return {}; // 空表示生成失败由调用方兜底 }wallRate建议取 0.25 到 0.35 之间太低地图太空BFS 和 DFS 的结果几乎一样对比失去意义太高则连通概率骤降重试次数飙升。这个区间是试出来的经验值写进报告里也算一条实验结论。6. 验收与答辩把「能跑」变成「能讲清楚」课设的分数有一半在演示和问答上。代码能跑只是入场券真正决定评价的是你能不能解释清楚每一步为什么这么写。我一般让学生按下面这张表自测一遍能全部答上来再去答辩。验收项操作合格标准固定小地图手画一张 5×5 全通路图DFS 步数 9BFS 步数 9有障碍地图中间放一堵墙逼出绕行DFS 步数 BFS 步数两者都可通行不可达地图把终点用墙围死两个函数都返回失败程序不崩单格地图1×1起点即终点步数为 0路径只含一个坐标随机地图连点十次重新生成十次都能出解无卡顿边界地图起点贴左上角终点贴右下角无越界、无乱码答辩问题基本围着三个方向转提前把答案写成一句话「为什么 DFS 找到的不是最短路径」因为它一碰到可走的格子就往里钻钻到死路才回头找到的第一条通路只保证「通」不保证「短」。最短性需要按层扩展那是 BFS 的活。「复杂度怎么算的」每个格子最多入队或入栈一次每次检查 4 个方向与格子总数成正比所以时间O(n·m)辅助数组和栈/队列最坏存下全部格子空间也是O(n·m)。「两份代码有重复为什么不合并」可以合并抽象出一个「容器接口」栈和队列各实现一版。但课设的规模下合并带来的间接层反而让代码难读不如保持两份独立实现把共性部分方向表、通行判断、打印抽成公共函数。这个回答体现的是取舍意识比硬套设计模式更容易得分。还有一个容易被忽略的细节演示时先用固定小地图跑再用随机大地图跑。固定图便于核对步数随机图出效果。顺序反了一上来就是 30×30 的随机图观众看不清路径你也讲不清对错。从那以后我每次带这类课设都强制走一遍「先写验收表、再写代码」的流程——表格里那六行先填好代码写完照着逐行勾比事后想起「还没测不可达的情况」要从容得多。上面这套结构和代码可以直接拿去改把地图换成你题目要求的尺寸、把起终点改成从文件读剩下的部分基本不用动。希望帮到你。本文还有配套的精品资源点击获取
设计与优化实战指南)
