简介来自福州大学数计学院的《数据结构》上机实验报告主题为利用栈实现迷宫求解适合正在学习数据结构中栈与队列应用的本科生或编程爱好者参考。报告基于C语言完整实现了以链表为存储结构的栈类型并编写非递归求解程序能够对任意m×n迷宫求出一条从入口到出口的通路并以三元组(i,j,d)形式输出路径坐标与方向。内容涵盖实验目的、问题描述、程序设计的核心代码、实验结果与结论并附有迷宫示例和完整实验代码有助于理解栈的后进先出特性在实际搜索问题中的运用。压缩包仅含1个PDF文件大小136KB便于阅读和打印。已有383人学习浏览可作为课程实验报告撰写或算法实现的参考。1. 迷宫求解实验报告这份PDF里到底装了什么东西在数据结构的上机实验里“利用栈实现迷宫求解”几乎是每个学校都会布置的经典题。这份实验报告PDF就是一个把完整上机实验过程整理成规范文档的样本从题目要求、需求分析、算法设计思路、核心数据结构定义到C语言源码、运行结果和实验总结全部按实验报告格式排好。换句话说它既是一份可以直接对照复现的实验代码也是一份可以帮你应付期末实验验收的文档模板。它解决的问题很具体栈和迷宫求解表面上不好搭上关系但这个实验会告诉你栈就是为“回溯”而生的数据结构。你只需要一个二维数组当迷宫一个栈顺序栈或链栈都行记录走过的坐标配合方向探测就能走出迷宫并把路径打印出来。这份资料适合三类人。第一类是正在被这门实验课卡住、需要一个能跑通的完整参考的人第二类是期末复习数据结构时想把栈这部分彻底弄明白的人第三类是考研复试上机前拿它练手、想快速复习一次栈操作的人。下面几章我按“原理—拆解—避坑—扩展”的顺序把这个实验从头到尾过一遍。2. 栈为什么适合迷宫求解先弄清回溯搜索的逻辑很多人拿到这道题第一反应是“用递归不就行了吗”。递归确实能解但实验要求永远比实现方式多一层它逼着你把“回溯”这个抽象概念用栈这种具体的线性结构表达出来。理解了这一层后面所有代码都是顺理成章的。2.1 迷宫问题的本质每一步都是“尝试 决定是否回头”迷宫求解的本质是“在一个二维状态空间里找一条从入口到出口的路径”。你站在某个位置能做的选择只有四个方向最多去掉来路剩下三个方向。但问题在于你并不知道哪条路通往出口所以只能一条一条试。试通了继续往前试不通就得退回上一个岔路口换另一个方向再试。这个过程在算法上叫“深度优先搜索”DFS而深度优先搜索天然对应一种“后进先出”的记录方式最后一次存入的试探位置最先需要被取回。这种记录方式的物理载体就是栈。你每往前走一步就把当前位置入栈某条路走到尽头就出栈让栈顶变成上一个位置继续试探它剩下的方向。很多人把栈理解成“存路径”这不完全准确。栈真正做的是“维护搜索进度”——栈里存的既是已经走过的路也是当前还有哪些方向没试完的节点集合。这个理解如果不建立起来后面看代码会把退栈逻辑看成一团乱麻。2.2 栈的“回溯”动作压栈、弹栈与死路标记迷宫实验里栈的具体操作分三种入栈、出栈、取栈顶。对应到走迷宫的行为就是入栈等于走进一个新位置出栈等于从死路退回取栈顶则是查看一下“我现在站在哪”从而决定下一步往哪走。这里有一个关键设计迷宫数组里通常用数字表示状态1代表墙壁0代表通路。走进某个位置后为了避免下一次探测时又把这里当新路线走回去需要把走过的位置改成另一个值比如2表示“已走过”。如果这里是一条死路最后回溯离开时有的实现会把它改成3表示“死路”。为什么要区分“已走过”和“死路”核心原因是调试方便。如果你只标记“已走过”迷宫跑完你会发现所有遍历过的路和最终路径混在一起。而区分开了最终输出的时候只要遍历迷宫数组把所有值为2的格子连起来就是一条干净的路径。下面这张表可以直观看出栈和迷宫状态的配合关系栈动作程序行为迷宫状态变化push尝试走进一个新格子当前位置标记为2取top并探测方向在当前格子四周找可走的下一步无变化pop当前格四个方向都无路可走当前格子标记为3退回上一格检查栈空入口也被标记为死路迷宫无解注意第四行如果栈被弹空说明连入口出发的所有方向都被证明走不通迷宫无解。这个状态在实验报告里通常是单独输出一行“No path found”而不是什么都不做。2.3 为什么实验都选“栈”而不是“队列”数据结构实验把“迷宫求解”和“栈”绑在一起不是随意为之。用队列同样可以搜索迷宫那叫广度优先搜索BFS能找到最短路径用栈则是深度优先找到的路径不一定最短但它能体现“一条路走到底不行就原路退回”这种最朴素的回溯思想。“回溯”这个词很多人在考试里背过定义但真正理解它靠的就是亲手玩一次栈的入栈出栈。栈顶在不断变化的过程中你实际是在模拟一个“如果这里走不通我怎么回到上次的分岔口”的过程。这就是栈最经典的应用场景——函数调用时的return机制本质上也是回溯栈帧一层层弹出程序控制权一层层归还。3. 手工推演一个完整迷宫从入栈出栈到路径输出在贴代码之前我强烈建议你先在一个微型迷宫上把所有入栈出栈动作手推一遍。只有当你看到栈自身的变化和迷宫状态的联动代码里的每一个判断语句才有意义。3.1 4×4微型迷宫的手工推演假设迷宫用一个4×4的二维数组表示1是墙0是路约定入口在(0,0)出口在(3,3)1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0等等上面这个迷宫入口位置(0,0)是墙但很多教材里入口设计是特殊的。我们把入口改成通路0 0 0 1 1 0 1 0 0 0 1 0 0 1 0 0从入口(0,0)开始推演。步骤记录如下——每一行代表一次“当前栈顶位置执行方向探测”的结果。为了简洁我用E/S/W/N代表东南西北四个方向方向探测顺序统一按“东、南、西、北”。步骤当前栈顶试探方向结果动作栈内容1(0,0)东可达(0,1)push(0,1)[(0,0),(0,1)]2(0,1)东边界跳过无动作[(0,0),(0,1)]3(0,1)南(1,1)可达push(1,1)[(0,0),(0,1),(1,1)]4(1,1)东(1,2)是墙无动作同上5(1,1)南(2,1)是墙无动作同上6(1,1)西(1,0)是墙无动作同上7(1,1)北已走过判断已标记同上8(1,1)无路可走标记为死路pop[(0,0),(0,1)]9(0,1)西(0,0)已走过跳过[(0,0),(0,1)]10(0,1)北边界跳过[(0,0),(0,1)]11(0,1)无路可走死路pop[(0,0)]12(0,0)南边界跳过[(0,0)]13(0,0)西边界跳过[(0,0)]14(0,0)北边界跳过[(0,0)]15(0,0)东已走过跳过无[(0,0)]这就很尴尬了入口四个方向都无路可走栈即将弹空迷宫无解。这个微型迷宫其实从(0,0)只能走到(0,1)、(1,1)之后确实没有出路。推演的价值就在于你亲眼看到了“无解”是用什么条件判断出来的——不是靠什么特殊函数而是栈弹空。为了继续推演有解的情况我们把迷宫第一行和第三行各打通一个位置改成0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0这样从(0,0)一路向东到(0,3)再往下就能到达(3,3)。推演步骤就不再完整展开只展示几个关键节点当(0,0)向东到(0,1)、(0,2)、(0,3)后栈内容为[(0,0),(0,1),(0,2),(0,3)]。此时(0,3)向南可达(1,3)继续入栈直到(3,3)是出口程序在入栈之前先检查坐标是否等于出口如果等于直接输出整条栈路径。输出时的问题是栈是反的——栈底是入口栈顶是出口。如果直接打印栈出口会出现在第一行不符合“从入口到出口”的阅读习惯。解决办法有两个要么把栈内容倒进临时数组再逆序输出要么递归打印栈底到栈顶。实验报告里常见做法是后一种写一个递归函数先递归弹出再打印这样天然实现逆序。3.2 一套能直接跑通的C语言实现完整代码是这个实验报告的核心资产。我按教材常见风格给出一个顺序栈版本代码经过简化保留核心逻辑可以直接复制到Dev-C或Code::Blocks里跑通。#include stdio.h #include stdlib.h #define M 6 // 迷宫行数 #define N 6 // 迷宫列数 #define MAXSIZE 100 // 栈容量按最坏情况——走遍所有格子——预留 // 迷宫地图1表示墙0表示通路 // 边缘补一圈1作为天然边界避免大量坐标越界判断 int maze[M][N] { {1, 1, 1, 1, 1, 1}, {1, 0, 0, 0, 1, 1}, {1, 0, 1, 0, 0, 1}, {1, 0, 1, 1, 0, 1}, {1, 0, 0, 0, 0, 1}, {1, 1, 1, 1, 1, 1} }; // 方向数组依次为东、南、西、北 // 每个元素是一个坐标偏移move[0] {0,1} 表示向东走一步 int move[4][2] { {0, 1}, // 东 {1, 0}, // 南 {0, -1}, // 西 {-1, 0} // 北 }; typedef struct { int x, y; // 坐标 int di; // 记录下一步要尝试的方向下标0~3 } Box; typedef struct { Box data[MAXSIZE]; int top; // 栈顶指针 } SeqStack; void initStack(SeqStack *s) { s-top -1; } int push(SeqStack *s, Box e) { if (s-top MAXSIZE - 1) { return 0; // 栈满 } s-top; s-data[s-top] e; return 1; } int pop(SeqStack *s, Box *e) { if (s-top -1) { return 0; // 栈空 } *e s-data[s-top]; s-top--; return 1; } int getTop(SeqStack *s, Box *e) { if (s-top -1) { return 0; } *e s-data[s-top]; return 1; } // 判断当前位置是否可走不是墙、没走过、没被标记为死路 int canPass(int x, int y) { if (maze[x][y] 0) { return 1; } return 0; } void printPath(SeqStack s) { // 用递归实现倒序输出保证从入口打印到出口 if (s.top -1) { return; } Box tmp s.data[s.top]; s.top--; printPath(s); printf((%d, %d) , tmp.x, tmp.y); } int main() { SeqStack stack; initStack(stack); // 入口坐标题目默认入口在(1,1) int startX 1, startY 1; // 出口坐标 int endX 4, endY 4; Box now; now.x startX; now.y startY; now.di 0; push(stack, now); maze[startX][startY] 2; // 入口标记为已走过 Box cur; while (stack.top ! -1) { int flag 0; // 当前格子是否找到新出路 getTop(stack, cur); // 检查是否到达出口 if (cur.x endX cur.y endY) { printf(Path found: ); printPath(stack); printf(\n); return 0; } // 按东、南、西、北依次尝试 while (cur.di 4) { int nextX cur.x move[cur.di][0]; int nextY cur.y move[cur.di][1]; if (canPass(nextX, nextY)) { // 找到可走方向入栈 Box next; next.x nextX; next.y nextY; next.di 0; push(stack, next); maze[nextX][nextY] 2; flag 1; break; } cur.di; // 当前格子这个方向不可走试下一个方向 } if (!flag) { // 四个方向都试完当前格子是死路 pop(stack, cur); maze[cur.x][cur.y] 3; // 标记为死路 if (stack.top ! -1) { // 栈不为空时把栈顶格子的方向游标往后挪一位 // 因为回到的上一格还得继续尝试下一个方向 stack.data[stack.top].di; } } } printf(No path found!\n); return 0; }这段代码的结构完全对应第2章的原理描述。先看canPass函数它只判断maze[x][y] 0也就是说只有值为0的格子才能走。值为2的是已走过的值为3的是标记为死路的值为1的是墙一律不能走。这保证了程序不会在已经验证过走不通的路上反复横跳。再看主循环。每次循环先取栈顶记录当前站在哪个格子。如果当前格子就是出口坐标直接打印路径并退出。如果没到出口就尝试它的四个方向——这里“当前格子方向还没试完”的信息是存在栈元素自身的di字段里的。程序通过修改栈顶元素的di值实现了“记住这个格子的下一个未试方向”的效果。最值得注意的设计是当一格四方向全部无路可走时弹出栈顶然后把新栈顶元素的di加1。这个动作对应“回溯到上一格并跳过已经被证明走不通的那个方向”。如果没有这个设计回到上一格后程序会重复尝试刚才那个死路方向形成死循环。很多初版代码跑不出结果问题正是出在这一行上。栈容量的参数MAXSIZE设为100对于6×6迷宫是绰绰有余的。如果迷宫尺寸放大到10×10最坏情况下栈深也不过100但为了避免边界条件的偶然性习惯上会把MAXSIZE设为M * N 10。这个细节在实验报告的“测试结果”部分可以作为优化点写进去。3.3 迷宫的边界处理与“外圈围墙”设计代码里的maze数组第一行和最后一行、第一列和最后一列都是1这组“外圈围墙”不是装饰。如果去掉这圈围墙程序在迷宫边缘格子做方向探测时nextX或nextY可能变成负数或超出数组下标导致访问越界。虽然C语言不检查数组越界但越界的随机值会让程序要么崩溃、要么意外地“穿墙”走出地图。这种设计的代价是多占了一圈数组空间。以6×6数组为例实际可用迷宫区域只有中间的4×4。好处是换取一组清晰干脆的边界处理——根本不需要写if (nextX 1 || nextX M - 2)这种判断因为围墙本身就是“墙”会被canPass直接拒绝。如果你不想用围墙可以保留边界判断但每个方向都要写一个检查条件代码会多出将近一倍而且稍不注意就写错。我见过好几个同学的手写版本都是因为边界条件少写了一个等号导致程序“愉快地穿墙而出”。相比之下围墙方案几乎不会出边界错误。4. 实验报告核心拆解方向数组、死路标记与路径回显4.1 move数组的四方向优先级与实验结论move数组的定义是迷宫实验里最容易忽略、但最重要的常量之一int move[4][2] { {0, 1}, // 东 {1, 0}, // 南 {0, -1}, // 西 {-1, 0} // 北 };这个数组的含义是把“方向”这个概念量化成坐标偏移。向东一步横坐标不变、纵坐标加1向南一步横坐标加1、纵坐标不变。这样程序不再用“东”“南”这些字面量而是统一用move[cur.di][0]和move[cur.di][1]计算下一步坐标。方向顺序的选择会影响最终路径。东、南、西、北的优先级会让程序尽量向右下角走因为向右和向下更接近出口。如果你把顺序改成北、西、南、东路径形态会完全不同甚至可能找不到路径——在深度优先搜索里方向优先级决定搜索路径形态。如果实验报告要求你分析“不同探测顺序对结果的影响”你可以直接改move数组的顺序对比两次运行结果。一般会看到方向优先级越偏向出口方向搜索路径越短。但这不是绝对的因为深度优先搜索本身的路径质量还受障碍物分布影响不具备最优性保证。4.2 走过标记与死路标记为什么必须分开代码中用2表示已走过用3表示死路。这个区分是报告作者有意为之。如果混为同一个值程序能跑通但输出路径时会看到大量冗余的试探分支——所有被遍历过的格子都会出现在“路径”上无法区分“走过的尝试路”和“真正的路径”。迷宫值含义输出时处理1墙不输出0未走过的通路不输出2最终路径含正在尝试的当前路线输出3死路或已回溯的废弃路线不输出分开标记还有一个实际好处你可以在程序运行结束时额外打印一次整个迷宫数组把2和1的分布画出来一眼就能看出迷宫的通路走向。很多实验报告附带的“运行结果截图”里那个打印出来的迷宫图就是基于这套标记系统实现的。4.3 出栈后方向游标自增的语义代码里有一行很容易被忽略stack.data[stack.top].di;这行的含义是退回上一格后把上一格已试过的方向跳过。假设上一格的位置是(2,1)它的di值为1表示已经试过方向0东和方向1南当前正卡在方向2西。如果你在(3,1)踩到死路弹栈回到(2,1)此时如果直接把当前循环重跑一遍(2,1)会从di1继续也就是尝试方向2——这是正确的。但如果代码在弹栈时把栈顶di清零那(2,1)就会从头再从东试起而东边那个格子明明刚走过会造成无效的重复探测。这个细节是很多人写迷宫代码时翻车的高发点。从逻辑上来讲栈里每个元素的di应该被视作“这个格子未来要继续尝试的方向下标”而不是“已经试过多少次”。实验报告如果画了流程图这一步通常是流程图上“弹栈”分支旁写的那个小备注。5. 避坑调试迷宫程序最常见的五个问题上机实验最耗时的从来不是写代码而是代码写完不知道怎么调。这里把我见过的五类典型故障整理出来每条都按现象、原因、解决三步写清。5.1 现象程序陷入死循环CPU占用飙升控制台疯狂滚动这是最常见的问题。原因通常有两种一是回溯后没有修改栈顶元素的di导致每次回到该格子都从方向0开始试而方向0通向的格子极可能是一个已经走过的位置二是走到了一个已走过的格子但入口和出口之间的路径存在闭环程序在环路里反复进出。解决方法是先排查hasPassed这个判断是否生效——确认maze数组的值2是否参与canPass判断。然后在关键位置加打印比如每次push和pop都打印一次当前坐标和多条栈顶内容。打印个几十行基本能定位到是哪一步产生了重复循环。最常见的处理办法就是确保弹栈后执行stack.data[stack.top].di这个动作把回溯后的探测起点拨到未试过的方向。5.2 现象路径能输出但明显绕了远路甚至包含回头路这是因为“死路标记为3”的逻辑没有生效或者根本没有写。程序把所有走过的格子统一标记成了2出栈时没有把它改成3。于是出口找到之后整条打印出来的“路径”里混入了一大堆探索过的废弃分支视觉上就像一条疯狂绕圈的线。解决办法是在弹栈分支中把当前格子置为3pop(stack, cur); maze[cur.x][cur.y] 3;再跑一遍输出路径会立刻干净很多。如果还是包含回头路检查出栈后是否立即对栈顶元素的di进行了递增确认没有走回同一方向。5.3 现象程序提前结束输出“No path found”但迷宫肉眼可见有通路这个问题的原因是方向搜索顺序把“可达出口的路径”排在了“漫长的死路分支”之后而栈容量又被设得太小探索死路时提前栈溢出。注意栈满时push返回0但代码里没有处理这个返回值于是新坐标根本没有入栈程序还误以为当前位置走不了直接返回失败。解决方法是扩大MAXSIZE更规范的做法是在push返回0时增加报错输出避免“登山式调试”。常见的健壮性改进是把MAXSIZE设置为M * N或M * N 1保证迷宫所有格子都被探索时也不会溢出。5.4 现象算法栈弹出后出口坐标已经入栈但输出路径为空这种问题出在路径打印函数上。常见写法是从栈底往栈顶输出但栈底是入口栈顶是出口如果先输出栈底走的方向就完全反了。要输出从入口到出口的顺序必须先把栈底元素先打印。解决方法是像我上面代码那样写成递归输出void printPath(SeqStack s) { if (s.top -1) return; Box tmp s.data[s.top]; s.top--; printPath(s); printf((%d, %d) , tmp.x, tmp.y); }这段递归每次先弹出栈顶再递归打印剩余部分等触底回退时再打印当前坐标天然形成了栈底先输出、栈顶后输出的顺序。注意我用的是值传递不是指针传递这样递归过程中栈的临时副本被一层层剥开而原栈不受影响。5.5 现象换了个迷宫就出问题原迷宫运行正常这是典型的参数化不足问题。很多同学把迷宫尺寸、入口、出口直接硬编码成常量换迷宫就要改代码、调数组大小。实际上迷宫实验的验收环节经常要求现场换迷宫测试硬编码会当场翻车。解决方案是把迷宫定义、入口坐标、出口坐标和行列数都做成可配置数据。最常见的做法是读文件迷宫文件第一行写行数和列数第二行写入口和出口的坐标后面几行写迷宫矩阵。这样所有迷宫都可以用同一套二进制逻辑处理。这个问题我会在下一章给一个文件输入版本的参考片段。6. 把报告变成自己的模板三个扩展方向6.1 给迷宫加文件输入一次编译到处换图把迷宫数据从代码里搬出来放到一个文本文件里例如maze.txt6 6 1 1 4 4 1 1 1 1 1 1 1 0 0 0 1 1 1 0 1 0 0 1 1 0 1 1 0 1 1 0 0 0 0 1 1 1 1 1 1 1第一行是行列数第二行是入口和出口坐标之后是迷宫矩阵。代码里只需要用fscanf逐行读入动态分配二维数组其余搜索逻辑完全不用动。这一步能让实验验收时换地图的环节从容不少。6.2 增加一步运行轨迹输出用来验证中间状态在push和pop两个动作上各加一条打印语句输出当前坐标、动作类型、栈深度。这样运行一次就能看到回溯过程的全貌也方便写进实验报告的“算法执行过程”部分。上机验收时老师看到这种输出会觉得你是真正理解了栈而不仅仅是把代码跑通。6.3 理解与实际输出的路径对比拿到一条输出路径后建议你在纸上画出迷宫用笔描一遍输出路径。如果描出来头尾连贯、没有跨越墙壁算法就基本正确。这一步看似原始却是我调试迷宫程序时最有效的验证手段——路径是否合法肉眼一秒就能判断。其实在做完这个实验之后你会发现栈的思路还会延伸到很多场景比如单调栈求最大矩形、backtrace栈回溯定位程序异常调用链核心都是“记录现场、遇到困境就还原现场”。希望帮到你。从那以后我每写一个用到栈的程序都会先想清楚“栈顶元素代表什么”再动键盘。迷宫求解的代码逻辑并不复杂但如果你能把这个实验中“栈顶的角色变化”彻底想明白数据结构里栈这一章就基本拿下了。本文还有配套的精品资源点击获取