简介：这份C++数据结构课设资源以“老鼠走迷宫”为主题，面向正在学习数据结构与算法、需要完成课程设计或希望强化搜索算法实践的学生。项目将迷宫抽象为二维数组，用0和1区分通路与墙壁，并借助深度优先搜索实现随机迷宫生成与路径求解，帮助读者理解图、栈、递归与回溯等核心概念。压缩包共27个文件，约148.59MB，包含cpp与h源码、sln与vcxproj工程文件、exe可执行程序、mp4使用说明与素材替换视频、png与jpg示意图，以及pdb、ilk、obj等调试编译中间文件，覆盖从源码阅读到直接运行演示的完整链路。目前已有1391人学习下载。读者可据此获得一套可编译运行的课设方案，掌握迷宫数据结构设计、DFS递归实现、随机迷宫生成与素材替换方法，并参考使用说明快速上手，适合作为算法思维训练与课程设计参考。

1. 从老鼠走迷宫说起：一份能直接交差的数据结构课设方案

老鼠走迷宫是数据结构课设里被选得最多、也最容易被做得最水的题目之一。多数人拿到题第一反应是“用栈回溯就行”，然后花两天写一个能跑通的 demo，交上去发现同组三个人思路一模一样，答辩时被问一句“为什么不用队列”就卡住了。这份方案要解决的不是“能不能跑”，而是“怎么把迷宫问题拆成数据结构能讲清楚的完整设计”——从需求分析、存储结构选型、核心算法实现，到界面交互和测试验收，每一步都有可复现的代码和可答辩的设计说明。适合正在做 C++ 数据结构课设的学生，也适合需要一份完整迷宫求解方案做参考的开发者。整套方案围绕 C++ 实现，核心数据结构涉及栈、队列和二维数组，算法覆盖深度优先搜索和广度优先搜索两条路线，最终给出最短路径和全部可行路径两种输出。

2. 需求分析与技术选型：为什么用栈和队列而不是递归

2.1 功能需求拆解

迷宫求解这件事，表面上是“从入口走到出口”，拆开来看其实包含四层需求。第一层是迷宫数据的表示：怎么把一张迷宫图存进程序里，墙、通路、入口、出口分别用什么值标记。第二层是路径搜索：从入口出发，按什么策略探索相邻格子，遇到死路怎么退回。第三层是结果输出：找到路径后怎么显示，是打印坐标序列还是可视化画出路线。第四层是扩展需求：能不能找最短路径，能不能找出所有可行路径，能不能支持手动编辑迷宫。

这四层需求对应到数据结构课程的知识点，分别是二维数组、栈与递归、队列、图的遍历。课设的评分点通常也落在这几个地方——老师看的不是你跑出了什么结果，而是你用了什么结构、为什么用这个结构、复杂度是多少。

我一般会建议在需求分析阶段就把功能分成必做和选做两档。必做包括迷宫加载、单条路径求解、路径输出；选做包括最短路径、多路径、手动编辑、步数统计。这样写设计文档时层次清晰，答辩时也有东西可讲。

2.2 存储结构选型：二维数组 + 栈 + 队列

迷宫的存储用二维数组是最自然的选择。约定 0 表示通路，1 表示墙，2 表示已走过的路径，3 表示死路标记。入口固定在左上角 (0,0)，出口固定在右下角 (rows-1, cols-1)，也可以改成从文件读取任意入口出口。

// 迷宫数据结构定义 const int MAX_ROWS = 20; const int MAX_COLS = 20; struct Maze { int grid[MAX_ROWS][MAX_COLS]; // 0=通路 1=墙 2=路径 3=死路 int rows, cols; int entryRow, entryCol; // 入口坐标 int exitRow, exitCol; // 出口坐标 };

路径搜索用两种结构分别实现。深度优先搜索用栈来模拟递归回溯——每走到一个格子就入栈，遇到死路就出栈退回上一个格子。广度优先搜索用队列来保证按层扩展，第一次到达出口时走过的步数就是最短路径。

// 方向数组：上右下左四个方向 const int DIR[4][2] = {{-1,0},{0,1},{1,0},{0,-1}}; // 栈节点：记录当前位置和已尝试的方向编号 struct StackNode { int row, col; int dirIndex; // 下一个要尝试的方向，0~3 };

这里有个设计细节值得在课设文档里写清楚：栈里存的不是简单的坐标，而是“坐标 + 当前方向索引”。因为回溯回来之后，需要知道这个格子还有哪些方向没试过，否则会重复探索同一个方向导致死循环。这个点在答辩时经常被问到，提前想清楚能省不少事。

2.3 算法路线对比：DFS 与 BFS 的取舍

DFS 和 BFS 在这个项目里各有用途，不是二选一的关系。DFS 适合找“一条可行路径”，实现简单，用栈就能搞定，缺点是找到的路径不一定最短。BFS 适合找“最短路径”，按层扩展保证第一次到达出口就是最少步数，缺点是需要额外的 visited 数组记录访问状态，空间开销比 DFS 大。

课设里通常的做法是两种都实现，用同一个迷宫分别跑，对比输出结果和步数。这样既覆盖了栈和队列两个知识点，又能在答辩时展示算法对比分析，比只做一种要扎实得多。

3. 核心模块实现：栈回溯与队列广搜的完整代码

3.1 迷宫初始化与文件加载

迷宫数据不建议硬编码在程序里，从文本文件读取更灵活，也方便测试不同规模的迷宫。文件格式约定第一行是行数和列数，后面每行是迷宫的一行，用空格分隔每个格子的值。

#include <fstream> #include <iostream> using namespace std; bool loadMaze(const string& filename, Maze& maze) { ifstream fin(filename); if (!fin.is_open()) { cerr << "无法打开迷宫文件: " << filename << endl; return false; } fin >> maze.rows >> maze.cols; if (maze.rows > MAX_ROWS || maze.cols > MAX_COLS) { cerr << "迷宫尺寸超出上限" << endl; return false; } for (int i = 0; i < maze.rows; i++) { for (int j = 0; j < maze.cols; j++) { fin >> maze.grid[i][j]; } } // 默认入口左上角，出口右下角 maze.entryRow = 0; maze.entryCol = 0; maze.exitRow = maze.rows - 1; maze.exitCol = maze.cols - 1; fin.close(); return true; }

加载函数里做了边界检查，防止文件里的行列数超过数组上限导致越界。入口和出口默认取对角，如果课设要求支持任意入口出口，可以扩展文件格式在第二行加四个整数表示坐标。这个函数返回 bool 而不是 void，调用方可以根据返回值决定是否继续，比直接崩掉要体面。

3.2 栈实现深度优先搜索

DFS 的栈实现是整个课设的核心代码，也是答辩时最容易被要求手写的部分。思路是：起点入栈，循环取栈顶，如果栈顶是出口就结束；否则按方向数组尝试下一个可走方向，能走就标记并入栈，四个方向都试完还不能走就出栈并标记为死路。

#include <stack> bool dfsSolve(Maze& maze, vector<pair<int,int>>& path) { stack<StackNode> stk; // 起点入栈，方向从0开始 stk.push({maze.entryRow, maze.entryCol, 0}); maze.grid[maze.entryRow][maze.entryCol] = 2; // 标记为路径 while (!stk.empty()) { StackNode& top = stk.top(); // 到达出口，收集路径 if (top.row == maze.exitRow && top.col == maze.exitCol) { while (!stk.empty()) { path.push_back({stk.top().row, stk.top().col}); stk.pop(); } reverse(path.begin(), path.end()); return true; } // 尝试下一个方向 bool moved = false; while (top.dirIndex < 4) { int nr = top.row + DIR[top.dirIndex][0]; int nc = top.col + DIR[top.dirIndex][1]; top.dirIndex++; // 检查边界和可通行性 if (nr >= 0 && nr < maze.rows && nc >= 0 && nc < maze.cols && maze.grid[nr][nc] == 0) { maze.grid[nr][nc] = 2; // 标记为已走 stk.push({nr, nc, 0}); moved = true; break; } } // 四个方向都走不通，回溯 if (!moved) { maze.grid[top.row][top.col] = 3; // 标记为死路 stk.pop(); } } return false; // 无解 }

这段代码有几个关键点。StackNode里存dirIndex是为了回溯后不重复尝试已经走过的方向，这是栈实现 DFS 最容易翻车的地方——如果只存坐标不存方向索引，回溯回来会从方向 0 重新试，直接死循环。标记 2 和 3 的区别也要注意：2 是当前路径上的格子，3 是确认走不通的格子，回溯时把 2 改成 3，但不要动其他路径上的 2。

3.3 队列实现广度优先搜索求最短路径

BFS 用队列实现，核心是保证按层扩展。每个节点除了坐标还要记录步数和父节点，最后从出口反向追溯得到完整路径。

#include <queue> struct BFSNode { int row, col; int step; int parentIndex; // 在节点数组中的父节点下标，-1表示起点 }; bool bfsSolve(Maze& maze, vector<pair<int,int>>& path) { queue<BFSNode> que; vector<BFSNode> visitedNodes; // 保存所有访问过的节点，用于回溯路径 bool visited[MAX_ROWS][MAX_COLS] = {false}; que.push({maze.entryRow, maze.entryCol, 0, -1}); visited[maze.entryRow][maze.entryCol] = true; visitedNodes.push_back({maze.entryRow, maze.entryCol, 0, -1}); while (!que.empty()) { BFSNode cur = que.front(); que.pop(); // 到达出口，通过 parentIndex 反向追溯 if (cur.row == maze.exitRow && cur.col == maze.exitCol) { int idx = visitedNodes.size() - 1; while (idx != -1) { path.push_back({visitedNodes[idx].row, visitedNodes[idx].col}); idx = visitedNodes[idx].parentIndex; } reverse(path.begin(), path.end()); return true; } for (int d = 0; d < 4; d++) { int nr = cur.row + DIR[d][0]; int nc = cur.col + DIR[d][1]; if (nr >= 0 && nr < maze.rows && nc >= 0 && nc < maze.cols && maze.grid[nr][nc] == 0 && !visited[nr][nc]) { visited[nr][nc] = true; int parentIdx = visitedNodes.size() - 1; visitedNodes.push_back({nr, nc, cur.step + 1, parentIdx}); que.push({nr, nc, cur.step + 1, parentIdx}); } } } return false; }

BFS 里visitedNodes数组的作用是保存所有访问过的节点，每个节点记录父节点下标。找到出口后从最后一个节点往前追溯，就能还原出最短路径。这里有个容易忽略的点：parentIndex存的是visitedNodes里的下标，不是队列里的位置，因为队列会不断 pop，下标会变。用单独的数组保存所有节点，下标就稳定了。

3.4 路径输出与可视化

路径找到之后，输出方式直接影响课设的观感。最基础的是打印坐标序列，稍微好一点的是在迷宫图上用符号标出路径。

void printMazeWithPath(const Maze& maze, const vector<pair<int,int>>& path) { // 复制一份用于显示 int display[MAX_ROWS][MAX_COLS]; for (int i = 0; i < maze.rows; i++) for (int j = 0; j < maze.cols; j++) display[i][j] = maze.grid[i][j]; // 标记路径 for (auto& p : path) { display[p.first][p.second] = 2; } // 打印 for (int i = 0; i < maze.rows; i++) { for (int j = 0; j < maze.cols; j++) { switch (display[i][j]) { case 0: cout << " "; break; // 通路 case 1: cout << "██"; break; // 墙 case 2: cout << "··"; break; // 路径 case 3: cout << "xx"; break; // 死路 } } cout << endl; } cout << "路径长度: " << path.size() << " 步" << endl; }

用··表示路径、██表示墙、xx表示死路，在控制台里视觉效果比较清晰。如果课设要求图形界面，可以把这套逻辑平移到 Qt 或 EasyX 上，用不同颜色画格子，核心算法完全不用改。我一般会建议先做控制台版本跑通，再考虑加界面，不然容易在 UI 上耗掉太多时间。

4. 避坑与常见问题：那些让课设翻车的细节

4.1 回溯后重复探索同一方向

现象：程序跑起来一直在原地打转，输出路径里同一个格子反复出现，或者直接死循环不结束。

原因：栈节点只存了坐标没存方向索引，回溯到某个格子后从方向 0 重新开始尝试，而方向 0 对应的格子之前已经走过了，但因为标记被改回通路又走了进去。

解决：StackNode里必须加dirIndex字段，每次尝试方向后递增，回溯回来从上次的位置继续。这个字段是栈实现 DFS 和递归实现 DFS 最大的区别，递归靠函数调用栈自动保存了循环变量，手动用栈就得自己维护。

4.2 标记数组和迷宫数组混用

现象：BFS 跑出来的路径不是最短的，或者明明有路却报无解。

原因：直接在迷宫数组上标记 visited，导致后续搜索时把已访问的格子当成墙，影响了其他分支的探索。DFS 里用 2 和 3 标记问题不大，因为 DFS 只找一条路；但 BFS 要探索所有分支，在迷宫数组上标记会破坏原始数据。

解决：BFS 单独开一个visited二维数组，迷宫数组只读不写。路径输出时再根据visitedNodes里的记录去标记显示。DFS 如果也要找多条路径，同样建议分开标记。

4.3 边界检查漏掉导致越界

现象：程序在某些迷宫上崩溃，报段错误或者输出乱码。

原因：方向数组扩展坐标后没有检查nr和nc是否在[0, rows)和[0, cols)范围内，直接访问了数组外的内存。

解决：每次计算新坐标后，第一件事就是边界检查。条件写成nr >= 0 && nr < maze.rows && nc >= 0 && nc < maze.cols，四个条件缺一不可。这个检查在 DFS 和 BFS 里都要做，不能只在其中一个里写。

4.4 入口或出口本身就是墙

现象：程序直接返回无解，但迷宫文件看起来没问题。

原因：迷宫文件里入口 (0,0) 或出口 (rows-1, cols-1) 的值是 1，表示墙，但加载函数没有校验。

解决：加载迷宫后加一步校验，如果入口或出口是墙，直接报错提示迷宫数据非法。这个检查花不了几行代码，但能省掉大量调试时间。

// 加载后校验入口出口 if (maze.grid[maze.entryRow][maze.entryCol] == 1 || maze.grid[maze.exitRow][maze.exitCol] == 1) { cerr << "入口或出口被墙堵住，迷宫数据非法" << endl; return false; }

4.5 路径输出顺序反了

现象：打印出来的路径从出口到入口，跟预期相反。

原因：DFS 用栈收集路径时，出栈顺序是反的；BFS 从出口往前追溯父节点，收集顺序也是反的。

解决：收集完路径后统一做一次reverse。这个操作放在路径收集函数的末尾，不要在每个调用点单独处理，不然容易漏。

5. 测试验收与答辩准备：怎么证明你的课设是完整的

5.1 测试用例设计

课设验收时老师通常会现场跑几个迷宫看结果，提前准备好测试用例能让你从容很多。我一般会准备五组：3x3 简单迷宫验证基本功能，5x5 带死路的迷宫验证回溯逻辑，10x10 多路径迷宫验证最短路径，20x20 大规模迷宫验证性能，以及一组无解迷宫验证异常处理。

每组用例记录 DFS 和 BFS 的输出结果、路径长度、运行时间。把这些数据整理成表格放进课设报告，比只贴代码有说服力得多。

5.2 复杂度分析与答辩要点

答辩时被问得最多的三个问题：为什么用栈不用递归、DFS 和 BFS 的复杂度分别是多少、怎么保证找到的是最短路径。

第一个问题的回答思路：递归本质上是系统栈，手动用栈能更清楚地展示数据结构的操作过程，也方便在栈里附加额外信息（比如方向索引）。第二个问题：DFS 时间复杂度 O(4^(mn)) 最坏情况，但实际有标记剪枝会低很多；BFS 时间复杂度 O(mn)，每个格子最多入队一次。第三个问题：BFS 按层扩展，第一次到达出口时的步数一定是最少的，这是队列先进先出特性保证的。

5.3 课设报告结构建议

报告按需求分析、总体设计、详细设计、测试与分析、总结与展望五部分写。需求分析写清楚功能点和性能要求；总体设计给出模块划分图和数据流描述；详细设计贴核心代码加注释说明；测试与分析放测试用例表和结果对比；总结写遇到的问题和解决过程。代码不要全贴，挑栈实现 DFS 和队列实现 BFS 这两段核心的就行，其他函数说明功能即可。

答辩前把代码跑一遍，确保演示环境没问题。我习惯在 U 盘里存一份可执行文件和测试迷宫数据，再在邮箱里备一份源码，防止现场电脑编译环境出问题。从那以后我每次交课设都强制走一遍“换机器编译 + 跑全部测试用例”的流程，翻车概率能降到零。希望帮到你。

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