简介：这份C++数据结构课设资源围绕“老鼠走迷宫”展开，面向正在学习数据结构与算法、需要完成课程设计或想通过实战巩固搜索算法的学生与开发者。项目以二维数组抽象迷宫，用0和1区分通路与墙壁，并借助深度优先搜索实现随机迷宫生成与路径求解，帮助读者理解图、栈、队列等结构在实际问题中的落地方式。压缩包共27个文件，约148.59MB，包含cpp与h源码、sln与vcxproj工程文件、exe可执行程序、mp4使用说明与素材替换视频、png与jpg示意图，以及pdb、ilk、obj等调试编译中间文件，另附txt说明文档，便于直接运行和二次修改。目前已有1391人学习下载。资源提供完整源码、随机迷宫生成逻辑、路径搜索实现与操作录屏，读者可据此掌握DFS递归与回溯、迷宫数据结构设计及C++工程组织方法，适合作为课设参考与算法练习素材。

1. 老鼠走迷宫：一个把栈和队列跑出画面的数据结构课设

很多同学做数据结构课设，最头疼的不是写不出代码，而是写完了不知道对错——控制台黑框里跑出一堆坐标，到底哪条路径是最优的，回溯有没有问题，全凭脑补。这个“老鼠走迷宫”项目就是来解决这个痛点的：它把经典的迷宫求解问题做成了可视化演示，用 C++ 实现，核心是栈和队列两种数据结构的对比应用。DFS 用栈实现，BFS 用队列实现，两条路径同时跑，谁长谁短一目了然。适合正在做课设的本科生、想复习数据结构基础的同学，以及需要一份能直接编译运行的 C++ 项目参考的开发者。整个项目不依赖任何第三方图形库，纯控制台字符画输出，拿到源码就能跑。

2. 核心架构拆解：栈与队列如何驱动两种寻路策略

2.1 迷宫的数据表示与坐标系统

迷宫本质上是一个二维网格，每个格子有两种状态：可走（通路）和不可走（墙壁）。项目里用二维数组来存储，0 表示墙壁，1 表示通路，这样初始化简单，调试时也方便直接看。

// 迷宫最大尺寸，可根据需要调整 const int MAX_ROW = 20; const int MAX_COL = 20; // 迷宫地图：0-墙壁，1-通路 int maze[MAX_ROW][MAX_COL]; // 方向数组：上、右、下、左（顺时针） // 注意这里顺序会影响DFS的搜索路径形态 const int dx[4] = {-1, 0, 1, 0}; const int dy[4] = {0, 1, 0, -1};

方向数组dx和dy是这类题目的标配，四个方向分别对应行减一、列加一、行加一、列减一。这里有个细节：方向的遍历顺序会直接影响 DFS 找到的第一条路径长什么样。如果先走上再走右，老鼠会倾向于贴着上边界走；如果先走右再走下，路径形态完全不同。这不是 bug，是 DFS 的特性——它只保证找到一条路，不保证最短。BFS 则不受方向顺序影响，因为它是逐层扩展的，第一次到达终点时一定是最短路径。

坐标用(row, col)表示，起点通常设在左上角(1,1)，终点设在右下角(MAX_ROW-2, MAX_COL-2)。迷宫外围留一圈墙壁，这样在判断越界时只需要检查数组下标是否在[0, MAX_ROW)范围内，不用额外处理边界条件，少写一堆 if。

2.2 DFS 寻路：用栈模拟递归回溯

DFS 的核心思想是“一条路走到黑，走不通就退回来换方向”。递归写法最直观，但课设通常要求用栈手动模拟，因为要考察对栈的理解。

// 栈节点：记录当前位置和已尝试的方向编号 struct StackNode { int x, y; // 当前坐标 int dir; // 下一个要尝试的方向索引(0-3) }; // 用数组模拟栈 StackNode stack[MAX_ROW * MAX_COL]; int top = -1; bool dfsWithStack(int startX, int startY, int endX, int endY) { // 入栈起点 top++; stack[top] = {startX, startY, 0}; maze[startX][startY] = 2; // 2表示已访问 while (top >= 0) { StackNode &cur = stack[top]; // 到达终点 if (cur.x == endX && cur.y == endY) { return true; } // 尝试下一个方向 bool moved = false; while (cur.dir < 4) { int nx = cur.x + dx[cur.dir]; int ny = cur.y + dy[cur.dir]; cur.dir++; // 当前节点方向指针后移 if (maze[nx][ny] == 1) { // 是通路且未访问 maze[nx][ny] = 2; // 标记已访问 top++; stack[top] = {nx, ny, 0}; moved = true; break; } } // 四个方向都走不通，出栈回溯 if (!moved) { top--; } } return false; // 栈空还没到终点，无解 }

这段代码有几个关键点。第一，栈里存的不是简单的坐标，而是StackNode，多了一个dir字段。这个字段记录当前节点已经尝试到第几个方向了，回溯回来的时候不用从头再试，直接从上次的位置继续。第二，maze[nx][ny] = 2这个标记很关键，它防止老鼠在原地打转。第三，cur用了引用StackNode &cur = stack[top]，这样修改cur.dir就是直接改栈顶元素，不需要出栈再入栈。

参数说明：startX, startY是起点坐标，endX, endY是终点坐标。返回值bool表示是否找到路径。如果找到，栈里从底到顶就是完整路径；如果没找到，栈会逐步清空。

DFS 找到的路径不一定最短，这是它的固有特性。在迷宫这种场景下，它可能绕很大一圈才到终点。但 DFS 的优势是实现简单，空间开销小——栈的最大深度不会超过通路格子总数。

2.3 BFS 寻路：队列逐层扩展保证最短路径

BFS 的思路是“一层一层往外扩”，用队列实现。每从队头取出一个节点，就把它的所有未访问邻居加入队尾。这样保证第一次到达终点时，走过的步数一定是最少的。

// 队列节点：记录坐标和父节点在队列中的索引 struct QueueNode { int x, y; int parent; // 父节点在队列数组中的下标，用于回溯路径 }; QueueNode queue[MAX_ROW * MAX_COL]; int front = 0, rear = 0; bool bfsWithQueue(int startX, int startY, int endX, int endY) { // 起点入队 queue[rear] = {startX, startY, -1}; rear++; maze[startX][startY] = 2; while (front < rear) { QueueNode cur = queue[front]; int curIndex = front; front++; // 到达终点，通过parent回溯路径 if (cur.x == endX && cur.y == endY) { return true; } // 尝试四个方向 for (int i = 0; i < 4; i++) { int nx = cur.x + dx[i]; int ny = cur.y + dy[i]; if (maze[nx][ny] == 1) { maze[nx][ny] = 2; queue[rear] = {nx, ny, curIndex}; rear++; } } } return false; }

BFS 的队列节点多了一个parent字段，记录父节点在队列数组中的下标。因为队列是用数组模拟的，每个节点的下标就是它在数组中的位置，所以可以用整数索引来追溯。找到终点后，从终点节点开始，沿着parent一路往回找，就能还原出完整路径。

这里有个容易翻车的地方：maze[nx][ny] = 2必须在入队时就标记，不能等出队再标记。如果等出队才标记，同一个格子可能被多个节点重复加入队列，导致队列爆炸式增长，内存直接爆掉。这是 BFS 实现中最常见的坑。

BFS 的空间开销比 DFS 大，因为队列里可能同时存着很多层的节点。但在迷宫问题里，格子总数有限，这个开销完全可以接受。换来的好处是路径一定最短，这在很多实际场景下比省内存更重要。

2.4 路径回溯与可视化输出

找到路径后，需要把路径标记出来并打印。DFS 的路径直接在栈里，从栈底到栈顶就是完整路径。BFS 的路径需要从终点沿着parent往回找，找到后反转一下。

// 打印迷宫，路径用 '*' 表示 void printMaze(int pathX[], int pathY[], int pathLen) { // 先把路径坐标标记到迷宫上 for (int i = 0; i < pathLen; i++) { maze[pathX[i]][pathY[i]] = 3; // 3表示路径 } for (int i = 0; i < MAX_ROW; i++) { for (int j = 0; j < MAX_COL; j++) { if (maze[i][j] == 0) cout << "# "; // 墙壁 else if (maze[i][j] == 3) cout << "* "; // 路径 else cout << " "; // 通路 } cout << endl; } }

可视化输出用字符画，#表示墙，*表示路径，空格表示可走但没走的通路。这样在控制台里一眼就能看出路径形态。如果想更直观，可以在路径上加上方向箭头，但课设通常字符画就够了。

路径回溯时要注意，DFS 的栈里存的是从起点到终点的顺序，直接遍历即可。BFS 需要从终点节点开始，不断找parent，直到parent == -1，然后把收集到的坐标反转。反转可以用一个临时数组，也可以用std::reverse。

3. 从源码到运行：编译、测试与参数调整

3.1 项目文件结构与编译命令

这个项目结构很简单，适合课设提交。常见做法是分成三个文件：maze.h放数据结构和函数声明，maze.cpp放具体实现，main.cpp放测试入口。也可以直接写成一个.cpp文件，看课设要求。

# 单文件编译 g++ -o maze maze.cpp -std=c++11 # 多文件编译 g++ -o maze main.cpp maze.cpp -std=c++11 # 运行 ./maze

Windows 下用 MinGW 或者 Visual Studio 都可以。Visual Studio 建空项目，把.cpp文件加进去直接 F5 就行。注意如果用了std::reverse，需要#include <algorithm>。

编译时建议加上-Wall看警告，有些数组越界或者未初始化变量编译器会提醒。课设代码虽然不要求工业级健壮性，但能跑对是底线。

3.2 测试用例设计与手动验证

迷宫数据可以硬编码在代码里，也可以从文件读。硬编码适合快速测试，文件读入适合批量验证。常见做法是准备几个不同形态的迷宫：简单直路、多岔路、有环、无解。

// 测试用例：一个 10x10 的迷宫 int testMaze[10][10] = { {0,0,0,0,0,0,0,0,0,0}, {0,1,1,0,1,1,1,0,1,0}, {0,1,0,0,1,0,1,0,1,0}, {0,1,1,1,1,0,1,1,1,0}, {0,1,0,0,0,0,0,0,1,0}, {0,1,1,1,1,1,1,0,1,0}, {0,0,0,0,0,0,1,0,1,0}, {0,1,1,1,1,1,1,0,1,0}, {0,1,0,0,0,0,0,0,1,0}, {0,0,0,0,0,0,0,0,0,0} };

手动验证时，先自己走一遍，数一数最短路径多少步。然后跑 BFS，看输出的路径步数是否一致。再跑 DFS，看路径是否合法（每一步都是相邻格子，不穿墙）。如果 BFS 和 DFS 结果一样长，说明迷宫没有岔路；如果 DFS 更长，说明 BFS 确实找到了更优解。

无解迷宫也要测。把终点用墙围死，看程序是否正常返回“无解”而不是死循环。DFS 在无解时会遍历所有可达格子然后栈空退出，BFS 会队列空退出，都不会死循环，但前提是标记逻辑写对了。

3.3 参数调整：迷宫尺寸与方向顺序

迷宫尺寸由MAX_ROW和MAX_COL控制，改大之后栈和队列的数组也要跟着改。如果不想手动改，可以用std::vector动态分配，但课设通常要求用原生数组，考察静态内存管理。

方向顺序影响 DFS 路径形态。把dx和dy的顺序换一下，比如改成下、右、上、左，DFS 找到的路径会完全不同。这不是错误，是 DFS 的非确定性。如果想固定路径形态，可以在找到路径后按坐标排序，但没必要。

BFS 的路径长度不受方向顺序影响，但路径具体走法可能不同。因为同一层的节点扩展顺序变了，到达终点时可能有多条等长路径，先被扩展到的会被记录。

提示：修改方向顺序后，记得重新跑一遍测试用例，确认路径仍然合法。有时候方向顺序变了，某些边界条件会暴露出来。

4. 避坑与排查：课设里最容易翻车的几个点

4.1 死循环：标记时机不对

现象：程序跑起来卡住不动，CPU 占用飙升，等半天不出结果。

原因：DFS 里忘记标记已访问，或者 BFS 里出队才标记。老鼠在两个格子之间来回走，永远走不到终点。

解决：DFS 在入栈时标记maze[nx][ny] = 2，BFS 在入队时标记。标记之后，这个格子就不会再被其他节点加入。记住一个原则：什么时候把这个格子放进数据结构，就什么时候标记。

4.2 路径错误：回溯时坐标顺序反了

现象：打印出来的路径从终点到起点，或者路径中间断开了。

原因：BFS 回溯时从终点往起点找，收集到的坐标是反的，忘记反转。或者 DFS 栈里存的路径顺序理解错了。

解决：BFS 回溯后一定要反转数组。DFS 的栈底是起点，栈顶是终点，从栈底遍历到栈顶就是正确顺序。可以在打印前加一句输出路径长度，和预期对比。

4.3 数组越界：边界检查漏了

现象：程序崩溃，报段错误，或者输出乱码。

原因：迷宫外围没有留墙壁，老鼠走到边界时nx或ny超出数组范围。

解决：初始化迷宫时，最外圈全部设为 0（墙壁）。这样任何从内部格子出发的移动，最多走到外圈墙壁就被挡住了，不会越界。如果迷宫是从文件读的，读入后手动把外圈覆盖成 0。

4.4 栈溢出：递归 DFS 深度太大

现象：用递归写 DFS 时，迷宫稍微大一点就崩溃。

原因：递归深度等于路径长度，迷宫 100x100 时递归深度可能上千，默认栈空间不够。

解决：改用栈模拟递归，就是 2.2 节的做法。如果坚持用递归，可以调大栈空间，但课设通常不允许改编译选项。栈模拟是更稳妥的方案。

4.5 结果不一致：BFS 和 DFS 路径长度比较

现象：BFS 和 DFS 输出的路径长度一样，怀疑 BFS 没起作用。

原因：迷宫太简单，没有岔路，或者岔路都是死路，两种算法找到的是同一条路。

解决：换一个有多条等长路径的迷宫测试。比如一个 3x3 的方格，从左上到右下有两条路，BFS 会选其中一条，DFS 可能选另一条，但长度一样。要验证 BFS 的最短性，需要找一个 DFS 会绕远的迷宫，比如有长死胡同的。

5. 二次开发：把课设变成能拿得出手的项目

课设做完只是起点，如果想让它更有说服力，可以在这几个方向改造。

第一个方向是加图形界面。用 EasyX 或者 SDL2 把字符画换成真正的图形，墙壁画方块，路径画线，老鼠用一个小圆点表示。这样演示效果直接提升一个档次。EasyX 在 Windows 上配置简单，适合课设答辩。改造时把printMaze换成绘图函数，其他逻辑不动。

第二个方向是支持从文件读迷宫。定义一个简单的文本格式，第一行是行列数，后面是 0/1 矩阵。这样不用改代码就能换迷宫，测试方便很多。读文件时注意处理行末换行符和空格。

// 从文件读迷宫 bool loadMaze(const string &filename) { ifstream fin(filename); if (!fin) return false; int rows, cols; fin >> rows >> cols; for (int i = 0; i < rows; i++) for (int j = 0; j < cols; j++) fin >> maze[i][j]; return true; }

第三个方向是加性能统计。记录两种算法扩展了多少个节点、耗时多少毫秒。用clock()函数就能测。这样在答辩时可以拿出数据说“BFS 扩展节点更多但路径更短，DFS 扩展少但路径可能更长”，比空口说更有说服力。

第四个方向是支持多起点多终点。把起点和终点做成数组，循环调用寻路函数，输出每一对的最短路径。这个改造能体现对算法接口的抽象能力。

改造时有个血泪经验：每次只改一个地方，改完立刻跑测试用例。我见过太多人一口气改了三四个功能，结果跑不起来，不知道是哪个改坏了。用 git 管理代码，每改完一个功能就 commit 一次，出问题直接回滚。

从那以后我每次做课设改造，都强制走一遍“改一处、编一次、跑一遍”的流程，再也不敢攒着一起改。希望这个项目能帮你把数据结构课设顺利跑通，也能成为你后续改造的起点。

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