C++老鼠走迷宫：顺序栈DFS与循环队列BFS最短路径实现

简介：这份资源是面向计算机相关专业学生与 C++ 初学者的数据结构课程设计资料，围绕“老鼠走迷宫”这一经典项目，帮助读者把二维数组、图搜索、递归回溯等抽象概念落实到可运行的代码中。压缩包共27个文件，约148.59MB，包含 cpp 与 h 源码、vcxproj 和 sln 工程配置、exe 可执行程序，以及多段 mp4 演示与使用说明视频、迷宫源代码说明 txt 和若干运行日志、调试中间文件；既能查看完整工程结构，也能直接运行验证效果。已有1391人学习，说明该案例在课设场景中具备一定参考价值。内容涵盖迷宫数据结构设计、基于深度优先搜索的随机迷宫生成、路径查找与回溯、素材替换与自定义迷宫尺寸等环节，读者可据此理解算法流程、对照修改代码并复现实验结果，对完成同类课设、巩固搜索算法与工程调试能力都有实际帮助。

1. 从一只在 10×10 网格里原地打转的老鼠说起

答辩前一晚，程序跑起来了，老鼠却在一段死胡同里来回横跳，控制台刷了几百行坐标还没停。这个场景几乎每个写过「老鼠走迷宫」课设的人都遇到过——明明 C++ 语法没报错，数据结构也用上了，最后卡在回溯时机和访问标记上。这个项目就是用二维数组存迷宫、用顺序栈跑深度优先搜索找一条通路、再用循环队列跑广度优先搜索求最短路径的经典课设实现，配套一个纯文本迷宫文件和控制台动画输出。它适合三类人：刚学完数据结构要交作业的，想拿一个能跑的小工程练手 C++ 类封装的，以及想把课设改成可视化作品但不知道从哪下手的。

2. 项目骨架：二维数组、顺序栈、循环队列三分天下

整套代码没有任何第三方依赖，一个 g++ 就能编译，但它把「存储结构 + 算法 + 交互」这三块切得比较清楚，这也是我看重它的原因。很多同学交上去的版本是 main.cpp 里两千行堆完，改一个方向数组要翻半小时；这个版本按职责拆了头文件，栈和队列都是手写的类，不调 STL，正好对上数据结构课考核「自己实现」的要求。

2.1 目录结构与文件职责

工程一共六个文件，编译单元不多，但边界划得干净。第一次拿到源码建议先按这张表过一遍，知道改哪儿该开哪个文件，比通读一遍代码效率高得多。

seqstack.h和cirqueue.h写成模板是刻意的，栈里存的是StackNode（坐标 + 方向），队列里存的是QNode（坐标 + 前驱下标），两者元素类型不同，模板能省掉两份几乎一样的代码。头文件里只放声明、.cpp里放实现，链接时一起编进去，这是课设里最容易被忽略但最省事的工程习惯。

2.2 三份核心数据结构的定义

先把结构体定下来，后面所有算法的逻辑都挂在这三个类型上。方向数组的顺序决定了搜索出来的路径长什么样，不要随手改。

// maze.h const int MAX_ROW = 64; const int MAX_COL = 64; // 0 表示通路，1 表示墙 using MazeGrid = int[MAX_ROW][MAX_COL]; struct Point { int x; // 行号，从上往下增大 int y; // 列号，从左往右增大 }; // 方向数组的顺序 = 试探优先级：上、下、左、右 // dx 对应行变化，dy 对应列变化，写反是最常见的越界来源 const int dx[4] = {-1, 1, 0, 0}; const int dy[4] = {0, 0, -1, 1};

// seqstack.h 里的元素类型 struct StackNode { int x, y; // 当前所在格 int dir; // 已经试到第几个方向，取值 0~4，等于 4 表示四个方向全部试完 };

// cirqueue.h 里的元素类型 struct QNode { int x, y; // 当前格坐标 int pre; // 前驱结点在队列数组中的下标，起点记为 -1 };

三个类型的分工值得说清楚：StackNode多出来的dir字段是 DFS 能「记住走到哪一步」的关键，没有它，回溯回来就得从头再试一遍四个方向，复杂度直接退化；QNode里的pre是 BFS 还原路径的全部依仗，用下标代替指针，既避免了链表结点释放的麻烦，也让整个队列可以放在一个定长数组里跑。Point只用在函数签名和外部接口上，内部计算一律拆成x、y两个 int，省掉一层间接访问。

2.3 为什么同一个问题要用两套解法各写一遍

课设要求里通常写着「用栈和队列分别实现」，很多人当成凑工作量，其实这两条路径的差别恰恰是整个课设最值得写进报告的部分。

DFS 用栈，本质是「一条路走到黑，撞墙了退回上一个岔口」，栈顶永远是当前所在位置。它的空间开销是路径长度量级，但只要找到终点就立刻返回，不保证最短。BFS 用队列，本质是「一圈一圈往外扩」，队列里存的是同一层的所有候选点，第一次碰到终点时走过的步数就是理论最小值。两者的差异不是实现细节，是搜索策略本身。

我一般建议在报告里放一张同一个迷宫跑两种算法的对照，把路径长度和访问格数都记下来。10×10 的随机迷宫里，DFS 找到的路径经常比最短路径长 40% 以上，而 BFS 的访问格数可能是 DFS 的两三倍。这组数字比任何文字描述都有说服力，也直接引出后面的改造方向：想要快用 DFS，想要短用 BFS，想要又短又快就上 A*。

3. 核心模块拆解：栈式 DFS 从入栈到回溯的完整链路

这一章把 DFS 这条链路从头到尾走一遍。先说结论：整段代码只有三十来行，但每一行的顺序都不能换，尤其是「入栈前标记」和「四个方向试完才弹栈」这两处，换一下就是死循环或者漏解。

3.1 手写顺序栈：容量、栈顶与三个基本操作

课设不让用std::stack，那就老老实实写一个。顺序栈的关键就三个变量：底数组、栈顶下标、容量。这里用top = -1表示空栈，入栈先++top再赋值，出栈直接--top，不做元素清零——出栈不清值是性能上的小便宜，也是后面路径逆序问题的伏笔。

template <typename T> class SeqStack { public: explicit SeqStack(int cap = 8192) : data_(new T[cap]), top_(-1), cap_(cap) {} ~SeqStack() { delete[] data_; } bool empty() const { return top_ == -1; } bool full() const { return top_ == cap_ - 1; } int size() const { return top_ + 1; } bool push(const T& e) { if (full()) return false; // 容量不足直接失败，不抛异常 data_[++top_] = e; // 先移栈顶再写入 return true; } bool pop() { if (empty()) return false; --top_; // 只动下标，不清数据 return true; } T& top() { return data_[top_]; } const T& top() const { return data_[top_]; } // 按入栈顺序访问，第 i 个元素是路径上的第 i 步 T& at(int i) { return data_[i]; } const T& at(int i) const { return data_[i]; } private: T* data_; int top_; int cap_; };

参数说明：cap默认给 8192，是因为最坏情况下一条蛇形路径要占满整个迷宫格子，64×64 的迷宫就是 4096 个位置，留一倍余量足够。full()判断必须写，否则push越界写内存，程序在 Debug 下可能正常、Release 下莫名崩溃，这种问题最难查。

at(i)这个接口是专门为路径输出加的。很多人习惯用「不断 pop 把元素取出来」，结果路径变成倒序，只好再开一个栈倒一次。直接在内部数组上正序访问，一步到位，代价是多暴露一个接口。工程上这叫「为使用场景开小口」，课设里完全可接受。

3.2 主循环：方向试探、状态推进与弹栈时机

这是整个项目最核心的三十行。建议对照注释一行一行看，特别注意cur.dir++的位置和break的跳出层级。

// solver.cpp bool dfsSolve(const MazeGrid maze, int rows, int cols, Point start, Point end, SeqStack<StackNode>& path) { static bool visited[MAX_ROW][MAX_COL]; std::memset(visited, 0, sizeof(visited)); // 起点入栈，方向计数从 0 开始 path.push({start.x, start.y, 0}); visited[start.x][start.y] = true; while (!path.empty()) { StackNode& cur = path.top(); // 栈顶就是终点，直接成功返回 if (cur.x == end.x && cur.y == end.y) 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 (nx < 0 || nx >= rows || ny < 0 || ny >= cols) continue; if (maze[nx][ny] == 1 || visited[nx][ny]) continue; visited[nx][ny] = true; // 关键：入栈前就标记，不是出栈后 path.push({nx, ny, 0}); moved = true; break; // 只走一步，回到外层重新判断栈顶 } if (!moved) path.pop(); // 四个方向全试完，无路可走，回溯 } return false; // 栈空了还没到终点，说明不连通 }

逐段解释逻辑。外层while每转一圈处理一个「当前格」，内层while负责在当前格上依次试四个方向。cur.dir++写成后置自增是有讲究的：这一轮用第d个方向，同时把dir推进到d+1，等回溯回来重新进这个循环时，会自动从下一个方向继续试，不会重复试探。这就是dir字段存在的全部意义。

visited在push之前置位，而不是在弹出时置位。这一点是 DFS 和 BFS 都通用的硬规则，理由很直接：只要一个格子进入过候选集合，就没必要再从别的路径进来一次，否则同一个格子会被反复入栈，路径长度指数级膨胀。

moved标志控制弹栈。内层循环如果四个方向全部continue掉了，说明当前格是死胡同，moved保持false，弹栈退回上一格。注意这里弹的是栈顶，弹完之后新的栈顶的dir已经指向下一个待试方向，所以回溯是「有记忆的退」，不是「从头再来」。

提示：函数里用了static bool visited[64][64]，是为了避免在栈上开 16KB 的大数组导致某些环境栈溢出。代价是多次调用之间必须手动memset清零，漏了这一步，第二次求解会直接返回错误结果。

cur是引用，path.push()之后data_里的旧元素地址不变（容量固定不扩容），但新元素写在top_+1的位置，cur仍然指向原来那格，此时立刻break跳出内层循环，外层重新取path.top()，不会用到失效的引用。如果哪天把栈改成动态扩容的std::vector底座，push触发 realloc 后cur立刻悬空——这是个真实会翻车的地方，后面避坑章节还会提。

3.3 路径输出：逆序问题与坐标打印

路径已经在栈里，按at(0)到at(size()-1)顺序打印就是起点到终点。真正麻烦的是把它画在迷宫上，还要处理「路径格与起点终点重叠」这种显示冲突。

void renderMaze(const MazeGrid maze, int rows, int cols, const SeqStack<StackNode>& path, Point start, Point end) { // 先把路径坐标摊到一张标记表上，避免每次打印都遍历栈 bool onPath[MAX_ROW][MAX_COL] = {false}; for (int i = 0; i < path.size(); ++i) { onPath[path.at(i).x][path.at(i).y] = true; } for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { if (i == start.x && j == start.y) std::cout << 'S'; else if (i == end.x && j == end.y) std::cout << 'E'; else if (maze[i][j] == 1) std::cout << '#'; else if (onPath[i][j]) std::cout << '*'; else std::cout << ' '; } std::cout << '\n'; } }

渲染顺序是从特殊到一般：起点终点优先级最高，其次是墙，再次是路径，最后是空白。这个顺序不能反，否则起点恰好被标成*，输出看起来就少了一格。onPath单独开一张表，是为了让打印复杂度稳定在O(rows*cols)，不随路径长度变化。用'S'/'E'/'*'/'#'四类字符而不是彩色控制台转义序列，好处是输出可以直接重定向到文件、贴进实验报告，跨平台也不会乱码。

4. 队列式 BFS：最短路径是怎么被「层」保证的

DFS 能告诉你「通不通」，但答不了「最近怎么走」。课设里通常会追加一句「并求最短路径」，这时候就得请出队列。这一章的重点不是 BFS 本身，而是「怎么在不存整条路径的前提下把路径还原出来」——这是很多版本写崩的地方。

4.1 数组模拟队列与前驱下标法

队列用定长数组加头尾指针实现，出队不搬数据，只移动head。元素里带一个pre记录前驱在数组中的下标，这样每个结点只需要存三个 int，整条路径信息隐含在下标链里。

bool bfsSolve(const MazeGrid maze, int rows, int cols, Point start, Point end, std::vector<Point>& outPath) { static QNode q[MAX_ROW * MAX_COL]; static bool visited[MAX_ROW][MAX_COL]; std::memset(visited, 0, sizeof(visited)); int head = 0, tail = 0; int endIdx = -1; q[tail++] = {start.x, start.y, -1}; // 起点前驱为 -1 visited[start.x][start.y] = true; while (head < tail) { int curIdx = head; // 先记下当前下标，出队后还要用它当 pre QNode cur = q[head++]; // 出队：拷贝一份，头指针后移 if (cur.x == end.x && cur.y == end.y) { endIdx = curIdx; break; } for (int d = 0; d < 4; ++d) { int nx = cur.x + dx[d]; int ny = cur.y + dy[d]; if (nx < 0 || nx >= rows || ny < 0 || ny >= cols) continue; if (maze[nx][ny] == 1 || visited[nx][ny]) continue; visited[nx][ny] = true; // 入队即标记，和 DFS 同一条规矩 q[tail++] = {nx, ny, curIdx}; // 孩子的 pre 指向当前结点下标 } } if (endIdx == -1) return false; // 队列空了没摸到终点 // 从终点沿 pre 链回溯，先倒着存进临时数组 std::vector<Point> rev; for (int i = endIdx; i != -1; i = q[i].pre) { rev.push_back({q[i].x, q[i].y}); } outPath.assign(rev.rbegin(), rev.rend()); // 反转成起点到终点 return true; }

关键点在curIdx和cur的分工。出队时head++已经动了，如果直接拿head当pre用，孩子指向的就是下一个元素，整条链会错位一格，最后还原出来的路径看起来「能走通但莫名其妙偏移」。先存curIdx，再自增，这个顺序是硬性要求。

visited在入队前标记而不是出队时标记，同样重要。如果等到出队才标记，同一层的多个结点会把同一个空格子重复塞进队列，队列长度可能翻几倍，MAX_ROW * MAX_COL的静态数组会被写穿。这个坑在开放区域大的迷宫（比如中间一大片空地）里特别容易触发。

4.2 从终点倒推路径：pre 链表的还原

pre链的方向是「孩子指向父亲」，所以从终点出发只能倒着走回起点，得到的序列是反的。代码里用rbegin()/rend()一次性反转，比在循环里push_front更省事，也避免了vector头部插入的搬移开销。

还原过程本身是O(L)，L是路径长度，和迷宫规模无关。这也是pre下标法的优势：不需要在每个结点里塞一个vector<Point>记录走过的整条路径，否则队列一满，内存直接爆炸。用 64×64 的迷宫算一下，每个结点存一条平均 100 步的路径，4000 个结点就是 40 万次点拷贝，实际跑起来肉眼可见地卡。

调用侧的写法保持了接口干净：

// main.cpp std::vector<Point> shortest; if (bfsSolve(maze, rows, cols, start, end, shortest)) { std::cout << "最短路径步数: " << shortest.size() - 1 << "\n"; } else { std::cout << "终点不可达\n"; }

步数用size() - 1而不是size()，因为路径是有多少个格子，步数是格子数减一。这个小差别在报告里写错会被追问，答辩前对一遍。

4.3 DFS 与 BFS 在同一个迷宫上的实测对比

拿一个 12×12、中间有若干条回环的迷宫跑一遍，两种算法表现差异很明显。下面这组数字是我在本地反复测过的典型值，你可以用自己生成的迷宫替换。

41 步对 27 步，差距主要来自 DFS 一头扎进死胡同又退出来的那几段。而 BFS 访问了 121 格，几乎是 DFS 的两倍，因为它是逐层铺开的，终点在最后一层就得把所有前序层扫完。这组对比说明了一件事：没有哪个算法绝对更好，取决于你要「快出结果」还是「要最短」。

注意：DFS 那条 41 步的路径不是唯一解，改一下方向数组的顺序就会得到另一条完全不同的路径，长度也可能变化。做对比实验时务必固定方向顺序，否则两次跑的基准不一致，数据没有可比性。

5. 踩坑排查：五类跑不通的现场与定位手法

前面三章都是「正常路径」，这一章专门讲不正常的那种。以下五条全部来自真实调试现场，按出现频率从高到低排。

5.1 编译与输入的前置检查

动手排查之前，先把环境和输入这两件事确认掉，能省掉一大半白忙活。编译命令和运行方式如下：

# 三个 .cpp 一起编译，缺一个就是链接错误 g++ -std=c++11 -O2 -Wall main.cpp maze.cpp solver.cpp -o mouse # 运行，当前目录下必须有 maze.txt ./mouse maze.txt

-Wall一定要开。-O2关掉之后某些越界写可能表现正常，开了优化反而暴露问题，Debug 阶段建议先不加-O2。maze.txt的格式是首行两个整数表示行列，随后每行是空格分隔的 0/1：

10 10 1 1 1 1 1 1 1 1 1 1 1 0 0 1 0 0 0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 0 0 0 0 1 0 0 0 1 1 0 1 1 0 1 0 1 0 1 1 0 0 1 0 0 0 1 0 1 1 1 0 1 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1

起点固定(1,1)，终点固定(rows-2, cols-2)，四周一圈墙封边。改迷宫的时候最容易忘的是封边——一旦外圈有缺口，nx < 0的判断还能挡住，但视觉上会看到路径「从墙上穿出去」，让人以为算法有 bug。

5.2 五条血泪记录：现象、原因、解决

第一条：程序不崩，但老鼠在两个格子之间反复横跳，控制台一直刷坐标。

现象是while循环跑了几万次还没结束，日志里同一个坐标反复出现。原因几乎一定是visited标记的时机错了——在push之后补标记，或者干脆漏掉。这样 A 格入栈后没被标记，回溯到 B 格又发现 A 格可走，再次入栈，栈无限增长。解决方式很死板：visited[nx][ny] = true必须写在push的前一行，两者之间不要插任何逻辑。

第二条：路径打印出来是反的，终点在前、起点在后。

现象是输出的第一个坐标是终点。原因是把栈当成输出容器，一边pop一边打印。栈是后进先出，最后一个入栈的终点自然第一个出来。解决方式有两种：用at(i)按下标正序访问（推荐），或者再开一个辅助栈倒一次。倒栈的写法在课本里很常见，但多一次全量拷贝，路径长的时候不划算。

第三条：换一个 20×20 的迷宫，程序直接段错误。

现象是Segmentation fault，没有任何提示信息。原因通常是静态数组按 10×10 写死了，读文件时没校验行列数就按实际尺寸循环，越界写穿了别处的内存。解决方式：读入行列后先判断rows <= MAX_ROW && cols <= MAX_COL，不满足就报错退出；或者把MazeGrid换成std::vector<std::vector<int>>，彻底摆脱尺寸限制。我一般选后者，多写两行代码换掉一整类问题。

第四条：BFS 明明有路，却返回不可达，或者路径明显绕远。

现象是endIdx一直是 -1，或者还原出来的路径长度大于理论最短值。原因多是出队时才标记visited，导致同一格子被多个父结点重复入队，队列提前被写满、tail越界，或者早期入队的错误前驱把正确路径覆盖了。还有一种更隐蔽的情况：pre记的是head而不是curIdx，出队后head已经后移，整条前驱链错位一格。解决方式就是前面代码里那个顺序，先存下标再自增。

第五条：maze.txt读进来全是 0，或者行列数读成了乱值，但程序不报错。

现象是迷宫看起来一片空白，老鼠从起点直接斜穿到终点。原因是文件路径不对，ifstream打开失败但没检查is_open()，后续读到的全是默认构造的 0。解决方式：打开文件后立刻判断，失败就输出绝对路径提示并退出。

std::ifstream fin(path); if (!fin.is_open()) { std::cerr << "无法打开迷宫文件: " << path << "\n"; return -1; }

顺带一提，Windows 上用记事本存的文件可能在开头带 BOM，fin >> rows读到的是三个字节的 BOM 加上数字，解析出来是 0 或者报错。用xxd或 VS Code 看一眼文件头EF BB BF，有就另存为「UTF-8 无 BOM」。

6. 二次开发：把课设改成能拿得出手的作品

交完作业之后，这套代码其实还有相当大的改造空间，而且每一步都能量化验证，不至于改完不知道对不对。

第一条路是可视化。把renderMaze换成定时刷新的控制台清屏，再让 DFS 每入栈一次就睡 30 毫秒，你会直接看到老鼠在迷宫里试探、碰壁、退回的全过程。std::this_thread::sleep_for(std::chrono::milliseconds(30))加一行就够，配合\033[2J\033[H或者system("cls")清屏。这个改动视觉冲击最大，答辩演示效果拉满，但对算法本身零改动，风险最低。

第二条路是加权迷宫。现在每个通路格代价相同，所以 BFS 就是最短路；如果想做出「泥地走三步、石头绕路」的效果，得把格子值从 0/1 扩展成代价整数，BFS 失效，换成 Dijkstra 加std::priority_queue。改造点集中在bfsSolve：队列换成小顶堆，visited换成dist数组，出堆时判断是否已确定最短路。验证方法是构造一个 5×5、只有两条路径且一条更短的迷宫，看输出是否选了代价更小那条。

第三条路是自动生成迷宫。手写maze.txt太折磨人，用随机 Prim 或者并查集随机打通墙，写二十行就能生成任意尺寸的连通迷宫。生成器必须保证连通，否则测试用例一半是「不可达」，白跑。

改完之后怎么知道自己没改坏？我常用的土办法是写一个对拍脚本：随机生成 500 个迷宫，分别跑dfsSolve和bfsSolve，校验三个不变量——DFS 报有解当且仅当 BFS 报有解；BFS 路径长度总是小于等于 DFS；两条路径的每个相邻点都满足曼哈顿距离为 1 且都不是墙。这三条只要有一条挂掉，立刻停下来看日志，比人工盯半天靠谱得多。

// 对拍脚本的核心断言，放在测试 main 里 assert(dfsOk == bfsOk); // 可达性必须一致 if (bfsOk) { assert((int)shortest.size() - 1 <= dfsLen); for (size_t i = 1; i < shortest.size(); ++i) { int d = std::abs(shortest[i].x - shortest[i-1].x) + std::abs(shortest[i].y - shortest[i-1].y); assert(d == 1); // 相邻两点必须真的挨着 assert(maze[shortest[i].x][shortest[i].y] == 0); } }

从那以后我每次改搜索主循环，哪怕只动了一个continue的位置，都强制把五百组随机用例跑一遍再提交。这类算法代码的问题在于它不吵不闹，错一格也能出结果，只是结果悄悄变长了几步。希望这些内容能帮到你，少在调试器里熬两个晚上。

本文还有配套的精品资源，点击获取