简介一份面向数据结构课程设计场景的C迷宫求解项目适合计算机相关专业学生完成课设或练习图、栈、DFS/BFS等算法时参考项目把迷宫抽象为二维数组表示的图用0/1标记通路与墙体以老鼠走迷宫为线索完整演示从随机迷宫生成、DFS寻路到可视化展示的过程。数据结构设计上二维数组保存格子状态老鼠维护当前位置与方向DFS配合栈回溯生成连通且仅有一条解的无环迷宫源码包含头文件、实现文件与可直接运行的exe程序便于对照理解递归、回溯与栈的配合。压缩包共27个文件涵盖cpp/h源码、VS工程配置、mp4使用说明与素材演示视频、png/jpg贴图及pdb/ilk/obj等调试生成文件整体约148.59MB文件类型与目录划分较清晰可帮助还原编译环境、定位随机迷宫生成、路径替换和用户自定义迷宫参数等关键模块。已有1390人学习下载对需要快速上手课设或想借鉴完整工程组织方式的读者较有参考价值。1. 老鼠走迷宫课设一道题吃透栈、队列与图遍历A同学把老鼠走迷宫这个数据结构课设题目拿回来时以为只是画一条线的事做完才发现它同时考了数组建模、栈、队列、回溯和路径输出五件事。这个题目本质上是在一张二维地图上让老鼠从起点走到终点输出一条可行路径要求再高一点还要证明这条路径是最短的。它能解决的实际问题是把学过的数据结构变成能跑通、能验收的代码并顺手练会 DFS 和 BFS 两个高频考点。适合正在做课设、准备验收或者想拿一个经典案例复习图遍历的读者。下面按做这个题目的完整路径来讲先定建模约定再写两种搜索最后补测试和排坑。2. 迷宫建模与数据结构选型先定四个边界约定再谈算法2.1 二维数组存迷宫外圈墙与方向数组是必须统一的约定迷宫最常见的存法就是二维数组maze[r][c] 0 表示通路1 表示墙。但怎么存这件事如果不定清楚后面所有算法都会跟着乱。我第一次做的时候直接在 maze[R][C] 里判断边界代码越写越长最后全是一段接一段的 if (nx 0 nx R ny 0 ny C maze[nx][ny] 0)。后来改成外圈墙方案数组开成 maze[R2][C2]四周各留一圈全为 1 的墙有效区域从下标 1 开始。这样每次搜索只需要判断 maze[nx][ny] 是否为 0越界访问被墙天然挡住负下标这种内存事故也不会发生。#include iostream #include queue #include stack #include vector #include cstring #include cstdio using namespace std; const int R 8; // 有效行数不含外圈墙 const int C 8; // 有效列数 int maze[R 2][C 2]; // 四周各多一圈墙 int dir[4][2] { {0, 1}, // 向右 {1, 0}, // 向下 {0, -1}, // 向左 {-1, 0} // 向上 };逻辑说明迷宫有效区域的行号从 1 到 R、列号从 1 到 C起点定为 (1,1)终点定为 (R,C)。这套约定贯穿所有代码包括文件读入。dir 方向数组把四个方向的移动抽象成行、列偏移量配合循环就能把往四个方向试探写成统一代码不用复制四段 if。参数说明R 和 C 根据课设要求的迷宫大小改如果迷宫的入口或出口本身贴墙外圈墙的约定要提前和读入数据的格式对齐否则起点下标对不上。方向顺序会影响 DFS 找到的是哪条路径但对是否存在路径没有影响。迷宫地图从文件读入是课设最常见的输入方式读入代码也要遵循同一套坐标约定// 从文件读迷宫第一行是有效行数 r 和列数 c之后 r 行 0/1 字符串 void loadMaze(const char* filename, int r, int c) { FILE* fp fopen(filename, r); if (fp NULL) { printf(迷宫文件不存在\n); exit(1); } fscanf(fp, %d %d, r, c); memset(maze, 1, sizeof(maze)); // 先全部填成墙外圈墙自然成立 for (int i 1; i r; i) { char line[256]; fscanf(fp, %s, line); // 每行是一个 0/1 字符串 for (int j 1; j c; j) { maze[i][j] line[j - 1] - 0; // 字符 0/1 转为数字 } } fclose(fp); }逻辑说明先 memset 成 1 再往内部填 0/1保证外圈墙不需要在文件里写文件只保存有效区域。读入循环里 i 从 1 开始、j 从 1 开始正好对应外圈墙方案的坐标系统。参数说明r、c 是从文件读出的有效行列数它们必须小于等于编译期定义的 R 和 C如果课设要求支持任意大小迷宫就把 maze 改成 vector 动态分配。line[j-1]-0 是把字符转成数字这是文件读入里最容易写错下标的地方后面避坑章会详细说。2.2 栈选 DFS、队列选 BFS两种搜索策略的适用边界DFS 的直觉是一条道走到黑老鼠走进一个格子先挑一个方向一直钻钻到死胡同就退回上一个格子换方向。这个走进、退回、换方向的流程用栈实现最直观——栈顶就是老鼠当前所在的格子走不下去就 pop 回退。BFS 的直觉是水波扩散从起点出发把能一步到达的格子全部标记再标记两步能到达的逐层向外扩第一次碰到终点的那一层就是最短距离。这个逐层扩展天生就是队列的活。两种算法都要保证每个格子只被处理一次所以都要有个访问标记后面代码里我直接用 maze[nx][ny] 2 当标记。差别在于DFS 找到的是一条可行路径不保证最短BFS 因为逐层扩展第一次到达终点时走过的层数一定是最少步数。适用边界很清楚课设要求输出任意一条路径DFS 就够了要求输出最短路径必须上 BFS两个都实现并对比是课设里常见的加分结构。这里有个选型上的常见误区有人觉得 DFS 也是找路就强行用它输出最短路径——那需要在找到终点后不立刻返回继续遍历整张图并记录所有到达终点时的步数最坏情况把全图搜索一遍复杂度从 O(R×C) 变成多次重复比较在小地图上能蒙对在 100x100 迷宫上时间和代码量都不划算。所以结论干脆一点要最短就 BFS。2.3 路径记录三种方案标记法、前驱数组、显式路径栈算法跑完不等于课设交差还得把路径打出来。路径记录有三种常见方案按实用程度排序讲。第一种是涂色标记法搜索时把走到的格子置 2最后把值是 2 的格子连起来当路径。问题在于 DFS 探索过的死胡同分支也全被涂成 2输出结果里会混进一大片去过但没走通的格子看起来像蜘蛛网。它只适合演示访问过哪些格子不适合当最终路径。第二种是前驱数组法开一个 pre[R2][C2]每个格子存我从哪个格子过来。BFS 每扩展一个格子 nx,ny 时就把 pre[nx][ny] 记为当前格子 x,y搜索结束后从终点顺着 pre 倒推回起点再反转顺序输出。这是最短路径输出的标准做法代码量小而且能顺带算出最短步数——只要再开一个 dist 数组记录距离。第三种是显式路径栈在迭代式 DFS 里栈的内容天然就是从起点到当前格子的整条路径找到终点时把栈里元素全部倒出来就是答案。这个方法最省内存不需要 pre 数组但只有迭代版 DFS 适用——递归版拿不到调用栈只能用 pre 或全局路径数组。第三章给的就是迭代版 DFS 显式路径栈配合 BFS 前驱数组刚好覆盖两种输出风格。3. DFS 与 BFS 核心代码从探路到输出完整路径3.1 迭代式 DFS用栈模拟老鼠一条道走到黑// 迭代式 DFS返回 true 表示找到路径此时栈 st 中保存完整路径 bool dfsIterative(int sx, int sy, int ex, int ey, stackpairint, int st) { st.push({sx, sy}); maze[sx][sy] 2; // 入栈立刻标记防止重复访问 while (!st.empty()) { auto cur st.top(); int x cur.first, y cur.second; if (x ex y ey) { return true; // 到达终点栈底到栈顶就是路径 } bool moved false; for (int i 0; i 4; i) { int nx x dir[i][0]; int ny y dir[i][1]; if (maze[nx][ny] 0) { // 只有通路且未访问才走 st.push({nx, ny}); maze[nx][ny] 2; // 入栈即标记时机很关键 moved true; break; // 一次只深入一个方向 } } if (!moved) { st.pop(); // 四个方向都走不了回溯 } } return false; } // 把栈中路径正序输出栈顶是终点先倒到 vector 再反转 void printStackPath(stackpairint, int st) { vectorpairint, int path; while (!st.empty()) { path.push_back(st.top()); st.pop(); } reverse(path.begin(), path.end()); for (auto pos : path) { printf((%d,%d) - , pos.first, pos.second); } printf(终点\n); }逻辑说明栈顶始终是老鼠现在站着的格子。当栈顶是终点时直接返回此时栈底到栈顶恰好是从起点到终点的完整路线。moved 标记这一轮是否真的走了新格子走了就继续循环没走说明当前格子四面全是墙或已访问pop 回退到上一个格子这就是回溯的栈实现。参数说明sx、sy、ex、ey 是起点和终点坐标需要保证 maze[sx][sy] 和 maze[ex][ey] 都是 0。st 用引用传入是为了在函数返回后还能把栈里的路径倒出来打印。dir 数组的顺序决定了优先试探的方向{右,下,左,上} 会先往右下方钻你改成 {上,右,下,左} 就会得到一条形态不同的路径——这也是课设验收时一个很好的提问点。如果课设要求输出所有可行路径迭代版要改递归版递归进入子格子后回溯时把 maze[nx][ny] 恢复成 0这样其他分支还能再访问它。注意恢复的只是当前分支的格子别把整张图都清了。3.2 BFS 最短路径队列逐层扩展的关键写法// BFS第一次到达终点即为最短路径pre 记录每个格子的前驱 int dist[R 2][C 2]; // 到起点的步数-1 表示未访问 pairint, int pre[R 2][C 2]; // 前驱坐标起点存 {-1,-1} bool bfs(int sx, int sy, int ex, int ey) { queuepairint, int q; memset(dist, -1, sizeof(dist)); // 全部初始化为未访问 q.push({sx, sy}); dist[sx][sy] 0; pre[sx][sy] {-1, -1}; // 起点没有前驱倒推时用它做终止 while (!q.empty()) { auto cur q.front(); q.pop(); int x cur.first, y cur.second; if (x ex y ey) { return true; // 第一次出队到达终点即最短 } for (int i 0; i 4; i) { int nx x dir[i][0]; int ny y dir[i][1]; if (maze[nx][ny] 0 dist[nx][ny] -1) { dist[nx][ny] dist[x][y] 1; // 步数加一 pre[nx][ny] {x, y}; // 记录前驱 q.push({nx, ny}); } } } return false; }逻辑说明dist[nx][ny] -1 同时承担了 visited 的角色省掉一个单独标记数组。每个格子被第一次扩展时它离起点的距离就是当前格子距离加 1这就是逐层扩散的数学含义。因为 BFS 是按层扩展的所以终点第一次被访问时dist[ex][ey] 就是最短步数此时立刻返回就行。参数说明pre 数组的元素是 pairint,int存的是上一个格子的坐标而不是距离。dist 用 -1 初始化而不是 0这是最容易踩的坑起点距离恰好是 0如果用 0 表示未访问起点会被当成还差一步没处理后文避坑章会展开。队列容量最坏是 O(R×C)100x100 迷宫最多入队一万个坐标内存上没有任何压力。3.3 路径还原前驱数组倒推与正序输出// 从终点顺着 pre 倒推回起点再反转成正序输出 void printShortestPath(int sx, int sy, int ex, int ey) { vectorpairint, int path; int x ex, y ey; // 只要还没回到起点就继续往前驱方向走 while (!(x sx y sy)) { path.push_back({x, y}); auto p pre[x][y]; x p.first; // 走到前驱格子 y p.second; } path.push_back({sx, sy}); // 把起点补进去 reverse(path.begin(), path.end()); printf(最短步数: %d\n, (int)path.size() - 1); for (auto pos : path) { printf((%d,%d) - , pos.first, pos.second); } printf(终点\n); }逻辑说明打印函数必须在 bfs 返回 true 之后调用否则 pre 里没有有效前驱循环会一直找不到起点。倒推终止条件用的是坐标等于起点而不是前驱等于 {-1,-1}因为在到达起点之前前驱都是合法坐标用坐标判断更稳。参数说明path.size()-1 就是最短路径经过的格子数减一也就是步数。如果课设要求输出每一步的方向比如右下左上在打印循环里对比相邻两个坐标的差值就能映射到 dir 数组的下标这个方法在后面验证部分会再提到。提示如果终点不可达pre 数组里可能残留上次搜索的数据调用打印前一定要检查 bfs 的返回值。4. 测试用例与复杂度分析答辩前必填的三块拼图4.1 五个必测迷宫从 3x3 最小地图到 100x100 压力场景课设翻车最惨的不是算法写错而是小地图能跑、大数据没见过。我一般会准备五张固定地图每张都有明确的验收目标。第一张是 3x3 最小迷宫验证程序和约定本身1 1 1 1 1 1 0 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1起点 (1,1)终点 (3,3)唯一路径是 (1,1)-(1,2)-(1,3)-(2,3)-(3,3)。这张图用来确认读入、搜索、输出三个环节全部正常尤其是文件行号和数组下标的对应关系。第二张是无解迷宫把起点围成一圈墙比如 maze[1][2] 1、maze[2][1] 1。DFS 和 BFS 都必须返回 false 并优雅退出不能死循环、不能段错误。测试无解分支的价值在于很多同学只在有解地图上测过一遇到 false 分支就漏了 pre 数组被判空的情况。第三张是蛇形单通道迷宫整张图只有一条弯弯曲曲的通路。这张图用来对比 DFS 和 BFS 的输出——因为是单通道两条路径必然完全重合步数也一样可以用它验证两种算法没写反。第四张是全通路迷宫除了边界全是 0。DFS 会走出一条绕远路BFS 会走出明显更短的路这是展示 BFS 优势最直观的图。第五张是 100x100 随机迷宫通路密度约 40%。它用来验证三件事递归版 DFS 是否会爆栈这个项目里直接用迭代版、BFS 的 dist 数组在一万个格子上是否都正确、程序总运行时间是否在肉眼可接受的范围内。每张图测完把步数、路径首尾是否合法、每步是否只走相邻格子输出留档这些都是验收现场的证据。4.2 复杂度对照表DFS 与 BFS 的代价差异一目了然三种写法的复杂度对比如下建议直接抄进课设报告的复杂度分析部分。算法时间复杂度空间复杂度是否保证最短路径适合场景递归 DFSO(R×C)O(R×C) 递归栈深度否小地图演示回溯思想迭代 DFS显式栈O(R×C)O(R×C) 栈空间否大地图、避免爆栈BFS队列O(R×C)O(R×C) 队列 dist pre是要求最短路径每个格子最多被访问一次所以三者时间上界都是 O(R×C)差别主要在空间和是否最短。这张表还能回答验收时最常被问的问题BFS 比 DFS 好在哪——BFS 用 O(R×C) 的队列空间换来了最短路径保证DFS 省掉部分空间但不能保证最短。4.3 课设报告三段式把为什么选这个结构写明白一份能过验收的报告不需要花哨但要把三件事讲清楚。第一段是需求分析和数据设计迷宫用二维数组存、0 是通路 1 是墙、外圈墙避免越界配一张标注坐标的地图。第二段是算法设计写 DFS 和 BFS 的流程描述贴核心代码重点写清楚为什么选栈做 DFS、队列做 BFS——这句话是验收问答时的命门说清楚它后面的提问基本都在射程内。第三段是测试与分析放 4.1 的五个用例、4.2 的复杂度表再加一段DFS 找到的路径不保证最短BFS 保证最短的实验对比结论。报告里有个小技巧把 dir 方向数组顺序变化对路径形态的影响写成一段实验观察。比如 {右,下,左,上} 和 {上,左,下,右} 在同一个地图上会走出不同的 DFS 路径但 BFS 的最短步数不变。这种细节最能体现你确实在动手做而不只是抄了一段代码。5. 老鼠走迷宫避坑指南5 个最容易翻车的细节5.1 起点终点坐标与墙约定不一致路径永远找不到现象程序跑完返回 false但人眼盯着打印出来的地图明明有一条肉眼可见的路。原因坐标系统没对齐。最常见的是迷宫文件里没有包含外圈墙文件第 1 行第 1 列对应数组哪个下标两套约定打架。也有人把起点选在值为 1 的格子上算法当然一步都走不出去。解决把坐标约定写进文件格式说明里文件存的是有效区域第 i 行第 j 列字符对应 maze[1i][1j]起点 (1,1)、终点 (r,c)。读入后立刻检查起点和终点都是 0不满足就直接报错退出别让错误数据流到搜索阶段——这一步能省掉一整晚的查错时间。5.2 递归 DFS 在大迷宫里爆栈段错误直接翻车现象3x3、5x5 都正常换成 100x100 的地图一运行就段错误或程序直接闪退。原因递归 DFS 的调用深度等于路径长度蛇形迷宫或全通路迷宫里最深处可能走几千上万步每层递归都要占用栈帧系统默认栈空间撑不住。解决课设代码一律用第三章的迭代式 DFS显式栈分配在堆上不受系统调用栈大小限制。如果课设非要递归版本展示回溯思想就把它限制在 30x30 以内的演示地图上并在报告里写明这个边界免得验收时被问住了没有后悔药。5.3 visited 标记时机错了死循环绕不出来现象程序卡死控制台疯狂滚动看起来像老鼠在迷宫里来回打转。原因标记时机放在了出栈时而不是入栈时。一个格子被入栈后在它出栈之前的这段时间里其他分支还能再次把它当成通路入栈于是同一个格子被反复访问。解决入栈或进入递归调用的瞬间立刻把 maze[nx][ny] 置为 2。记住一个口诀入栈即标记出栈不再管。这个问题看着像玄学实际上就是一条语句放错位置。5.4 文件读入迷宫时行列颠倒地图莫名转了 90 度现象打印出来的迷宫和原图对不上要么横竖翻转要么整个右转 90 度。读入逻辑像黑匣子只能瞎猜问题出在哪。原因读入循环里把 i、j 的对应关系写反了。常见写法是外层循环按行读字符串内层按列取字符但往 maze 里填的时候把两个下标交换了还有一种是在文件里按列存代码却按行读。解决准备一个 5x5 的已知迷宫读入后立刻完整打印一遍和原图逐行比对。比对通过再跑算法不通过就检查 line[j-1]-0 和 maze[i][j] 的下标。读入后打印这一步是做课设时养成的第一个习惯几乎所有读入类问题都能在十秒内暴露。5.5 BFS 距离数组初始化不当最短距离全是错的现象BFS 能找到终点但输出的步数比人眼数的少或者 dist 数组里出现大量 0。原因dist 初始化成 0然后用 dist[nx][ny] 0 判断是否访问过。问题是起点 dist 也是 0导致起点周围的格子第一次扩展时条件判断把起点误判成已经访问过整个扩散从第一层就乱了。解决dist 用 -1 表示未访问memset(dist, -1, sizeof(dist))。起点置 0 之后所有未访问和距离为 0就能严格分开。这条坑基本每个人都踩过属于课设必考题。6. 进阶玩法随机迷宫生成与结果验证的三个习惯6.1 用并查集生成完美迷宫的最小代码如果课设还要求迷宫由程序生成不能手敲常见做法是并查集加随机拆墙把每个格子看成一个集合收集所有相邻格子之间的墙随机打乱顺序逐墙判断——如果它隔开的两个格子不在同一集合就拆掉这堵墙并把两个集合合并在同集合就跳过。处理完全部墙之后任意两个格子之间有且仅有一条路径这种迷宫叫完美迷宫。int parent[(R 2) * (C 2)]; int find(int x) { return parent[x] x ? x : (parent[x] find(parent[x])); // 路径压缩 } bool tryBreak(int ax, int ay, int bx, int by) { int ra find(ax * (C 2) ay); int rb find(bx * (C 2) by); if (ra rb) return false; // 已连通拆了会产生环 parent[ra] rb; // 合并两个集合 return true; // 表示这堵墙可以拆 }逻辑说明find 的路径压缩让每次查询接近 O(1)tryBreak 是拆墙的唯一入口。生成时把墙的位置单独存成一张表拆墙就是在对应位置标记为通路跑完后再回到前面的 DFS/BFS 代码搜索逻辑完全不用改。参数说明id 映射用 x*(C2)y 把二维坐标压成一维如果迷宫改成动态大小parent 长度也要跟着变并先在迷宫四周围好外圈墙保证和前面的约定一致。6.2 验证 DFS 与 BFS 结果正确性的三个习惯第一个习惯每次跑算法前打印一次迷宫确认起点终点坐标和地图上的实际位置一致这一步能挡掉一半的坐标类问题。第二个习惯把 DFS 和 BFS 的结果在同一张图上人工走一遍从起点沿输出的坐标序列一个个看每步都必须落在值为 0 且与上一步相邻的格子上。第三个习惯对比两条输出——BFS 的步数一定小于等于 DFS 的步数如果反过来说明 visited 标记或前驱记录肯定有一个写错了。需要输出方向时用下一个坐标减当前坐标求出差值和 dir 数组比对就能得到方向名比如 {0,1} 对应右、{1,0} 对应下。我做这个题目时最大的教训是把起点写到了数组的 (0,0)结果所有迷宫都无解查了一整天才发现是外圈墙占了下标 0。从那以后我养成了两个固定习惯读入地图后先原样打印再写搜索代码测试永远从 3x3 小图起步。这两个习惯帮我挡掉了很多次翻车希望帮到你。本文还有配套的精品资源点击获取