简介一份基于C与数据结构课程设计的“老鼠走迷宫”完整项目资源适合高校学生在学习图、栈、队列与搜索算法时参考实践。资源将迷宫抽象为二维数组图结构以0表示可通行路径、1表示墙壁借助随机迷宫生成、深度优先搜索DFS回溯等思路实现从起点到终点的路径求解并配有代码工程、运行录屏与使用说明便于对照源码理解算法落地过程。压缩包共27个文件主要包括cpp/h源码、sln/vcxproj工程文件、exe可执行程序、mp4操作演示视频、png/jpg界面截图以及pdb调试信息等整体大小约148.59MB目录结构清晰便于定位源码、工程配置与演示素材。目前已有1390人学习下载适合需要完成同类课设、梳理迷宫生成与搜索算法实现细节的读者可直接参考工程结构、复用核心代码并快速运行体验。1. 课设选题这么挑栈与图遍历在迷宫里的落地老鼠走迷宫拿到手上多数人的第一反应是“这不就是一个DFS嘛”。但真把它当成一个C数据结构课设完整写完你会发现难点根本不在算法而在三件事路径记录用什么结构、回溯时栈和标记状态怎么保持一致、随机生成的迷宫怎么保证有且仅有一条通路。这个课设项目把二维数组、方向表、std::stack、递归回溯、图遍历全部串在了一条线上核心代码能控制在200行上下入口出口、随机迷宫、寻路演示、路径回放一应俱全。适合正在挑数据结构课设题目的同学也适合想把栈和图遍历从“会背”变成“会用”的开发者。2. 迷宫数据结构选型二维数组、方向表与栈的配合这一章先回答一个最容易被忽略的问题迷宫用什么样的数据结构来存。课设答辩时老师大概率会问“你为什么选二维数组而不选链表”这个问题想清楚了后面写代码才不会翻车。2.1 二维数组和链表课设场景里应该选哪个迷宫本身是一个规则网格每个格子只有“墙”和“通路”两种状态二维数组的下标天然就是坐标。用链表当然也能表示比如每个节点存四个方向的指针但写起来绕、调试起来更绕你在IDE里看一个int二维数组值一清二楚换成链表就得一个个节点跳。所以课设场景我毫不犹豫选二维数组。代码上的选择是用vectorvector 而不是C风格int[][]。后者在栈上开固定大小想动态指定行列很别扭vector可以用参数指定大小、可以resize、遍历时还能用auto对课设这种“今天10x10明天20x20”的场景友好得多。vectorvectorint maze; // 0表示通路1表示墙 vectorvectorbool visited; // 记录某个格子是否被走过 int rows, cols; // 迷宫的行数和列数参数约定maze[r][c]里r是行号、c是列号行号从0开始第一行和最后一行通常是墙。访问标记单独开一个同尺寸的二维数组和maze分离不混在一起改这是为了让“地图”和“搜索状态”两个概念在代码里分得清。2.2 方向数组让代码短一半方向表的定义与边界检查新手最容易写成四个if块分别处理上下左右不仅代码重复而且一旦要加斜向移动就得全盘重写。这里用一个方向偏移数组把所有可能移动统一成一张表int dir[4][2] { {0, 1}, // 右行不变列1 {1, 0}, // 下行1列不变 {0, -1}, // 左行不变列-1 {-1, 0} // 上行-1列不变 };定义好之后一个循环就能遍历四个方向先算新坐标nr r dir[i][0]、nc c dir[i][1]再判断这个新坐标能不能走。方向数组是可配置的如果之后想做“允许斜着走”的变体把它扩成8行就行主逻辑一行不用改。配合方向表还需要一个边界检查函数。C里数组越界不一定会立刻崩溃但会读到随机内存这是典型的“看起来没报错、结果全是玄学”的问题bool inBound(int r, int c) { return r 0 r rows c 0 c cols; }我在写递归时每一次方向探测都会先过inBound再判断墙和访问标记顺序固定为先边界、再墙、最后visited。这个顺序不能乱因为越界数组访问是未定义行为必须先拦在门外。2.3 为什么是栈路径记录与递归回溯的天然对应老鼠走迷宫最自然的解法是“走一步记一步走不通就退一步”。这个“退一步”的动作在数据结构上的对应物就是栈前进时压栈回退时弹栈栈里的内容始终是“从入口到当前位置的完整路径”。递归调用本身也是栈——每次调用压一帧每层返回弹一帧两者叠加在逻辑上非常自洽。stackpairint,int path; // 存放从入口到当前格子的路径 pairint,int start {1, 1}; path.push(start); // 入口进栈 visited[1][1] true; // 入口立即标记为已访问 bool found dfs(start.first, start.second);push和visited必须同时做这是整段代码最容易漏的细节。只压栈不标记同一个格子会被反复当作新节点走进来递归直接爆栈只标记不压栈最后的路径栈就是空的打印时什么都出不来。理解了这一点你在答辩时就能把“为什么用栈”“为什么访问标记要和压栈同步”这两个问题一次性讲清楚。提示把push和visited放在同一个代码块里写是规避“栈空但有路径”这类隐藏bug最直接的方式。3. 核心算法落地递归回溯找一条通路有了数据结构和方向表接下来就是让老鼠动起来。这一章从主流程开始把一个标准深搜递归函数拆成六步每一步都讲清楚什么时候该return true、什么时候该弹栈。3.1 入口出口与主流程迷宫边界我默认围一圈墙所以入口取(1,1)出口取(rows-2, cols-2)。这样入口和出口天然在迷宫内部且不会被边界问题干扰。主流程分成三段初始化迷宫、调用递归深搜、打印结果。int main() { srand(time(0)); initMaze(11, 11); // 生成一张11行11列的随机迷宫 generateMaze(); // 随机Prim拆墙具体实现在第4章 visited.assign(rows, vectorbool(cols, false)); stackpairint,int path; pairint,int start {1, 1}; pairint,int target {rows - 2, cols - 2}; visited[start.first][start.second] true; path.push(start); if (dfs(start.first, start.second, target, path)) { printMazeWithPath(path); } else { cout 没有找到通路 endl; } return 0; }这里把target作为参数传进dfs而不是用全局变量看着是小事但让这个递归函数变成“可复用的搜索函数”之后想改成多出口只要多传几个参数。path也用引用传入所有递归层级共享同一个栈回溯时弹栈才能正确反映“退一步”。3.2 DFS函数拆分边界、探测、压栈与递归核心递归函数是这个项目的心脏我把它拆成六个步骤来看bool dfs(int r, int c, pairint,int target, stackpairint,int path) { // 第一步先判断当前格子是不是出口 if (r target.first c target.second) { return true; } // 第二步遍历四个方向 for (int i 0; i 4; i) { int nr r dir[i][0]; int nc c dir[i][1]; // 第三步边界、墙、访问标记三层过滤 if (!inBound(nr, nc)) continue; if (maze[nr][nc] 1) continue; if (visited[nr][nc]) continue; // 第四步标记并压栈 visited[nr][nc] true; path.push({nr, nc}); // 第五步递归深入找到出口就层层上抛 if (dfs(nr, nc, target, path)) { return true; } // 第六步此路不通弹栈回退 path.pop(); } return false; }第一步和第六步是成对出现的。第一步把“当前位置是终点”这个判断放在循环外面只有当前格子确实是出口才返回true如果四方向都探测完仍没返回说明当前分支是死路把刚才压进去的格子弹掉返回false让上一层继续尝试别的方向。整个函数的return语义只有两条true表示“这条路走通了”false表示“这个死胡同走不通”非常干净。递归层数和栈的深度是一致的。入口压栈后进入第一层递归每走进一个新格子压一次栈走到底发现没路就一层层弹栈返回。路径栈在任意时刻正好对应“从入口到当前深度”的完整序列这也是打印路径时直接遍历path就能看到完整轨迹的原因。3.3 四个方向的探测顺序会怎样影响结果方向表的顺序不是随便排的。右、下、左、上会让搜索优先向右下方向探索视觉上老鼠倾向于先往出口方向冲如果改成上、右、下、左找到的路径大概率会先从上方绕一圈。两种结果都是合法通路差别只是“长什么样”。如果你想让每次演示都不一样可以在每次调用前把dir数组打乱顺序。这里可不要以为打乱顺序就能让路径变短——DFS天然不关心路径长度它只关心“有没有路”。想找最短路径得换BFS这个我在最后二次开发章再展开。对于课设演示来说固定的右、下、左、上顺序反而有一个好处结果可复现。同一个迷宫每次跑出来的路径完全一致讲代码时比对着屏幕大家好理解。我一般会写一个参数来控制是否打乱方向默认不打乱答辩演示时再手动切到随机模式。4. 随机迷宫生成与可视化让课设能演示起来如果只是贴一张写死的固定地图程序能跑但演示效果会大打折扣。这一章讲怎么用随机Prim生成一张有且仅有一条通路的迷宫以及怎么把搜索结果打印成控制台字符画。4.1 手写生成器而不是贴固定地图固定地图的问题有三个每台机器上看到的都一样、地图可能藏有多条通路、还有可能画着画着就画出了一块走不到的孤岛。课设要做的是“随机生成 自动寻路”这个完整闭环生成器是演示的起点也是工作量里最能讲出东西的一块。在几种迷宫生成算法里我推荐随机Prim。它写起来短、效果自然、而且天然保证生成的是树形迷宫任意两个格子之间有且仅有一条通路。这个性质对“验证寻路算法”特别友好因为DFS找到的一定是唯一解不会出现“你绕远了但明明有近路”的尴尬场面。另一种常见的递归回溯生成法是沿着一条路深挖到底再回头生成的迷宫容易出现又长又直的长走廊随机Prim每次从全局候选墙里抽一堵来拆分支更均匀路径也更蜿蜒演示观感明显更好。两种算法在课设里都能讲但Prim在“随机性”这个点上更容易让人信服。4.2 随机Prim拆墙候选墙与连通区域的约束算法的核心思路是“从起点开始长出一棵树”把起点设为通路把起点周围的墙放进候选列表反复从候选列表里随机抽一堵墙如果这堵墙恰好把“已连通的通路”和“还没连通的墙格”隔开就把墙拆掉、并入新的格子然后把这个新格子周围的墙也加入候选。直到候选列表为空整张迷宫就长满了一棵通路树。void generateMaze() { walls.clear(); for (int r 0; r rows; r) for (int c 0; c cols; c) maze[r][c] 1; // 先把整张图填满墙 maze[1][1] 0; // 起点设为通路 walls.push_back({1, 2}); // 起点的邻居墙 walls.push_back({2, 1}); while (!walls.empty()) { int pos rand() % walls.size(); // 随机抽一堵候选墙 int r walls[pos].first; int c walls[pos].second; if (countPassageAround(r, c) 1) { // 恰好有一边连着通路 maze[r][c] 0; // 拆掉这堵墙 addWallsAround(r, c); // 把新格子周围的墙加入候选 } walls.erase(walls.begin() pos); // 这堵墙处理完毕移出列表 } }countPassageAround统计的是当前格子四个方向中“已经是通路”的格子数量。等于1时拆墙新空地才会和现有通路连成一个连通区域不产生环等于0说明这堵墙四面都是墙拆了会冒出一块游离的孤岛等于2或更多说明拆了会形成环路破坏树的性质。这三个分支是随机Prim的精华也是答辩时最容易讲出深度的点。addWallsAround函数的实现也不复杂顺着方向表遍历新格子四周把所有仍是墙的邻居追加进候选列表即可void addWallsAround(int r, int c) { for (int i 0; i 4; i) { int nr r dir[i][0]; int nc c dir[i][1]; if (inBound(nr, nc) maze[nr][nc] 1) { walls.push_back({nr, nc}); } } }候选墙允许重复加入这不影响正确性只是多几次随机抽取而已但如果你把迷宫尺寸改到50×50以上walls会膨胀得很厉害建议换set自动去重。注意main循环里update walls时一定要用整数索引再erase不要边遍历边删迭代器否则会出现诡异的卡死。4.3 控制台字符画与路径标记打印是整个项目最直观的输出环节。我用三个可见字符#表示墙两个空格表示通路*表示走过的路径。path是stack不能线性遍历打印前先把它拷进一个set这样就能用count()在O(1)时间内判断某个点是否在路径上void printMazeWithPath(stackpairint,int path) { setpairint,int pathSet; while (!path.empty()) { pathSet.insert(path.top()); path.pop(); } for (int r 0; r rows; r) { for (int c 0; c cols; c) { if (pathSet.count({r, c})) cout * ; else if (maze[r][c] 1) cout # ; else cout ; } cout \n; } }这里有个小细节打印时行列两层循环要严格对应maze的访问顺序外层是行、内层是列否则迷宫会整体旋转90度。路径格子的优先级最高其次是墙、通路三个分支的顺序不要写反。如果想做动态演示只需要在寻路的压栈处插入一个清屏重绘就能看到老鼠一步一个脚印往外探的过程这段逻辑可以作为第6章动画扩展的基础。void showScan(stackpairint,int path) { system(cls); // Windows下清屏 printMazeWithPath(path); Sleep(100); // 单位毫秒数值越大动画越慢 }步进时间Sleep控制在100毫秒左右观感最舒服太快看不清回溯过程太慢则演示枯燥。放在压栈和弹栈两个位置分别调用就能同时展示“前进”和“回退”两段完整动作。5. 课设常见问题与排查四个让我翻车的细节这一章把我在实际跑这个项目时踩过的坑整理成四条记录每一条都是先看到现象、再定位原因、最后给出解决方式。写代码的过程中遇到类似情况直接对照排查会省很多时间。5.1 路径只打印到一半就停了现象程序从入口出发走了四五个格子就停下不走了控制台里看不到完整路径也没有报错有时候同一个迷宫换台机器结果还不一样。原因把出口判断写进了for循环里形如“if (nr target.first nc target.second) return true; ”。这等于说只有“往出口方向走的那一步”才能触发返回而方向表里出口方向未必排在最前。更糟的是如果递归先往别的方向越走越深出口判断根本不会被触发最终整条路径栈被弹空函数返回false。解决把出口判断提到for循环之前先确认当前格子本身是不是出口是就返回true。也就是3.2节的第一步。这个顺序调整只有两行代码的差别但对正确性的影响是决定性的。5.2 生成迷宫时程序卡死或直接退出现象调用generateMaze()之后程序无响应、CPU占用拉满或者跑了一段时间直接崩掉。原因两个。第一个是我曾经用迭代器遍历walls边遍历边eraseerase之后迭代器失效后面再解引用就是未定义行为表现就是谜之死循环。第二个是把countPassageAround(r, c) 1误写成 0结果拆的全是“四面都还是墙”的孤立墙迷宫永远长不成连通区域主循环无限转下去。解决改用整数索引pos rand() % walls.size()在while循环末尾执行walls.erase(walls.begin() pos)不要边遍历边删。判断条件写对之后可以在generateMaze末尾临时加一段从入口向出口的BFS验证能BFS到就说明迷宫连通连不上就说明拆墙条件有误这个方法在调试期特别好用。5.3 输出乱码与迷宫镜像反转现象Windows控制台里出现“锟斤拷”一类的中文乱码或者迷宫整体左右/上下颠倒路径完全对不上。原因乱码多半是把“墙”“路”这类中文双字节字符直接用cout输出控制台代码页是GBK而源文件是UTF-8两者不一致就乱码。镜像反转则是打印时把行号和列号搞混了内层循环遍历的应该是列方向外层应该是行方向一旦调换整个迷宫就被转置了。解决打印字符统一只用英文符号#和空格都是单字节从根上绕开编码问题。迷宫打印在代码上写成外层for遍历行、内层for遍历列并在变量名上用r和c区分行、列。还有一个排查技巧先打印一张极小的3x3迷宫手动检查四个角的位置对不对转置问题一眼就能看出。5.4 第二次运行结果不对visited状态没恢复现象第一次运行迷宫能走出路径接着第二次运行同一张迷宫要么提示无路要么路径乱串。看起来像“同一段代码结果不稳定”。原因visited是全局数组第一次寻路结束后大量格子被标记成true。第二次再跑递归直接跳过这些格子搜索空间被上一轮的“脚印”污染了。这是全局状态残留问题比局部bug更难发现因为第一轮往往是对的。解决每次寻路前重置visited。对vector用fill是更安全的选择因为memset对非平凡类型的vector不保证有效。我一般写一个resetVisited()函数主流程里在每次调用dfs之前先把它调一遍代码结构清晰也方便以后扩展成“多次寻路对比不同路径”。从那以后我每写一个带全局状态的搜索程序都会把重置动作放在调用入口而不是放在算法内部。6. 二次开发从单路径到多出口与最短路径这个项目跑通只是起点课设想拿高分通常要做一两个“超出基本要求”的扩展。这里给出三个投入产出比最高的方向找所有路径、BFS求最短路径、加演示动画。先说找所有路径。把dfs里“找到出口就return true”改成“找到出口就记录当前路径然后继续回溯”再加一个vectorvectorpairint,int allPaths存结果。注意记录时要深拷贝path快照不能直接push一个引用因为后续弹出会改动它。这个改造能让答辩展示“一张迷宫有多条通路可选”的图景配合5.4的重置逻辑体验会顺很多。BFS最短路径是另一个高频考点。换成队列做层序扩展加一个prev数组记录前驱格子到达出口后沿prev回溯就能从整棵搜索树里抽出最短路径queuepairint,int q; int prev[ROWS][COLS][2]; // 记录每个格子从哪走过来 memset(prev, -1, sizeof(prev)); q.push({1, 1}); prev[1][1][0] 1; prev[1][1][1] 1; while (!q.empty()) { auto [r, c] q.front(); q.pop(); if (r rows - 2 c cols - 2) break; for (int i 0; i 4; i) { int nr r dir[i][0], nc c dir[i][1]; if (inBound(nr, nc) maze[nr][nc] 0 prev[nr][nc][0] -1) { prev[nr][nc][0] r; prev[nr][nc][1] c; q.push({nr, nc}); } } }prev数组初始化为-1的作用和visited一样是防重复但它多存了一层“我从哪来”的信息所以BFS不需要递归也不需要栈队列弹完就自然结束。演示动画可以让课设观感上一个档次。做法是在dfs的压栈处调用showScan就能看到老鼠一格一格往前探路、碰壁回退的完整过程。加上随机方向表之后每次展示的路径都不重样演示效果会更加“随机”。这轮课设做完我最大的收获不是把DFS背下来了而是意识到课设的核心不是写一个能跑的算法而是让每一个启动入口都处于可见、可控、可重置的状态。从那以后我每次做系统类项目都强制先写一个最小demo验证数据结构选型再往里面堆功能。希望帮到你。本文还有配套的精品资源点击获取