老鼠走迷宫：栈与队列实现DFS/BFS寻路可视化-北京尧图网络

简介这份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 -stdc11 # 多文件编译 g -o maze main.cpp maze.cpp -stdc11 # 运行 ./mazeWindows 下用 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] 2BFS 在入队时标记。标记之后这个格子就不会再被其他节点加入。记住一个原则什么时候把这个格子放进数据结构就什么时候标记。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 一次出问题直接回滚。从那以后我每次做课设改造都强制走一遍“改一处、编一次、跑一遍”的流程再也不敢攒着一起改。希望这个项目能帮你把数据结构课设顺利跑通也能成为你后续改造的起点。本文还有配套的精品资源点击获取

老鼠走迷宫：栈与队列实现DFS/BFS寻路可视化

相关推荐

系统分析师真题拆解：从硬件到数据库的知识地图与避坑指南

OVS源码入门：从流表匹配到datapath内核转发原理

技术面试知识地图：Java、C++、数据库与Web开发核心考点全梳理

更多资讯

ChatGPT技术全景解析：从大模型原理到RLHF对齐的工程实践

DeepSeek-R1：链式推理固化的白盒大模型

DeepSeek本地知识库RAG部署与调优实战

本地大模型长期记忆实现：KV缓存层改造技术解析

微调数据集后门水印检测：利用模型梯度归因与神经元显著图逆向排查恶意权重

办公设备管理系统OAMS源码解析：从台账设计到扫码盘点落地

今日更新

MATLAB缩进快捷键与批量格式化实战指南

用Poco实现Qt风格信号与槽的跨平台C++方案

ESXi裸机虚拟化安装指南：从硬件兼容到虚拟机部署

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？