迷宫求解数据结构实训报告附源代码迷宫与栈小老鼠吃奶酪穷举求解

1、数据结构实训报告设计题目：迷宫的求解（ B）系别：XXXXXXXXXX专业 （方向）：XXXXXXXX年级、班：XXXXXXXXXXXX学生姓名：XXX学生学号：XXXXXX指导教师：XXX日期：XXXX 年 XX 月 XX 号目录一、系统开发的背景 1二、系统分析与设计 1（一）系统的分析 1（二）系统的具体分析设计 2.三、系统的功能要求 2、3（一）系统模块结构设计 3四、系统的设计与实现 4（一）在栈中实现迷宫的具体操作 4.、 7（二）栈的生成 7.、. 8（三）整个系统的生成流程图 9、10五、程序测试与步骤 1.0.（一）测试迷宫与栈问题可通的程序设计 . 10、 11（二）测试

2、迷宫与栈问题不可通的程序设计 .12 六、 总结 .12、13 七、附件（代码、部分图表） 1.4 、19迷宫的求解一、系统开发的背景 迷宫求解其实就是迷宫与栈的问题，训练老鼠在迷宫中寻找食物。 于是，老鼠过迷宫问题就此产生，这是一个很有趣的计算机问题，主要利 用 “栈”是老鼠通过尝试的办法从入口穿过迷宫走到出口。迷宫只有两个 门，一个叫做入口，另一个叫做出口。把一只老鼠从一个无顶盖的大盒子 的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍， 在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达 出口。为了使迷宫更佳富有趣味性，按照设计要求，我还设置地雷，如果 老鼠在

3、前进的过程中踩到地雷，则要重新回到入口，继续寻找能吃到奶酪 的通路。求解迷宫问题，即找出从入口到出口的路径。而数据结构则是数 据的组织形式，可以用来表示特定的对象数据，在计算机中对数据的一种 存储和组织形式，因此选用栈思想实现迷宫游戏的基本操作，也是我设计 迷宫求解的基本背景。二、系统分析与设计（ 一 ） 系统分析： 迷宫问题通常是用“穷举求解”方法解决，即从入口出发，顺着某个 方向进行搜索，若能走通，则继续往前走；否则沿着原路退回，换一个方 向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索 到而未能到达出口，则所设定的迷宫没有通路。另外附加的老鼠踩地雷则 类似于是在通路上埋藏

4、的隐形墙，如果踩到到雷则返回起点，寻找下一条 通路。栈是一个后进先出的结构，可以用来保存从入口到当前位置的路径。 定义迷宫类型来存储迷宫数据，通常设定入口点的下标，出口点的下标， 为处理方便起见，在迷宫的周围加一圈障碍，对于迷宫任何一个位置均约 定为东、西、南、北四个方向，而东北、东南、西北、西南则是需要利用 到两个下标进行移动。（ 二 ） 系统具体设计 在某个点上，按照一定的顺序（在本程序中顺序为上、右、下、左， 而东北、东南、西北、西南利用的是两个下标移动）对周围的墙、路进行 判断（在本程序中分别用 1、0 代替），若周围某个位置为 0，则移动到该 点上，再进行下一次判断；若周围的位置都为

5、 1（即没有通路），则一步步 原路返回并判断有无其他通路，然后再次进行相同的判断，直到走到终点 为止，或者确认没有任何通路后终止程序，附加踩雷（在本程序中用 5 代 替）则返回到起点重新寻找下一条通路，并显示踩雷路线。要实现上述算法，需要用到栈的思想。栈里面压的是走过的路径，若 遇到死路，则将该位置（在栈的顶层）弹出，再进行下一次判断；若遇到 通路，则将该位置压栈并进行下一次判断。如此反复循环，直到程序结束。 此时，若迷宫有通路，则栈中存储的是迷宫通路坐标的倒序排列，再把所 有坐标顺序打印后，即可得到正确的迷宫通路，附加的踩雷则是相当于在 通路上隐形了一道墙，踩雷，则从栈顶弹出，返回起点，再进

6、行二次判断 另一条通路。三、系统功能要求1） 首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷 宫的非归程序。求得的通路以三元组（ i， j，d）的形式输出。其中： （i，j）指示迷宫中的一个坐标， d 表示走到下一坐标的方向。如，对 于下列数据的迷宫，输出一条通路为： （1， 1，1），（ 1，2，2），（2， 2，2），（3，2，3），（3，1，2），。（ 2） 编写递归形式的算法，求得迷宫中所有可能的通路。（ 3） 以方阵形式输出迷宫及其通路。（一）系统模块结构设计通过对系统功能的分析，迷宫与栈问题的功能如图 1 所示。图 1： 迷宫实现的主函数功能图通过上图的功能分析，把整个系

7、统划分为 2 个模块：1、 通过栈后进先出的结构， 实现栈判断， 首先判断栈是否为空， 如果不为空，则实现栈中基本的入栈，出栈的实现。顺序栈是用一组地址连续 的 内存单元依次保存栈中的运算规则，在链式存储中链表首部 head 指针 所指向元素为栈顶元素，栈表尾部指向地址为 NULL为栈底。2、 借助函数的嵌套与使用，由 while 语句对整体进行控制， return 语句控制跳出函数，判断在迷宫中是否有出路，如果有出路，则通过东， 西，南，北的方向进行路径的输出；如果无出路，则说明此迷宫不能走出。四、系统的设计与实现（一） 在栈中实现迷宫的基本操作 分析：首先输出表头，然后依次输入想要实现的步

8、骤。功能图如图 2 所示。4图 2 ：迷宫的实现功能图该模块的具体代码如下所示void Maze:lujing() int i, j, d;int a, b;lianzhan elem, e;PLStack S1, S2, S3;InitStack(S1);InitStack(S2);InitStack(S3);mazestart.xstart.y = 2; /入口点作上标记elem.x = start.x;elem.y = start.y;elem.d = -1; / 开始为 -1Push(S1, elem);again:while (!StackEmpty(S1) / 栈不为空 有路径可走

9、 Pop(S1, elem);i = elem.x;j = elem.y;d = elem.d + 1; / 下一个方向 while (d<4) / 试探东南西北各个方向 a = i + diraddd0;b = j + diraddd1;if (mazeab = 5)while (S1) / 逆置序列 并输出迷宫路径序列Pop(S1, e);Push(S3, e);mazeab = 1;for (i = 0; i < m; i+)for (j = 0; j < n; j+)if (mazeab = 2) mazeab = 0;cout << "n0=

10、东 1= 南 2= 西 3= 北 4= 走出迷宫 nn 通路为 ( 横坐标 , 列坐标 , 方向) ：n"while (S3)Pop(S3, e); Push(S1, e); cout << " -> " << e.x << "," << e.y << "," << e.d << ""cout << "n 你在 " << "" << a &l

11、t;< "," << b << "" << "点踩到地雷了 " <<endl;d = 0;goto again;if (a = end.x && b = end.y && mazeab = 0) /如果到了出口elem.x = i;elem.y = j;elem.d = d;Push(S1, elem);elem.x = a;elem.y = b;elem.d = 4; / 方向输出为 -1 判断是否到了出口Push(S1, elem);cout &

12、lt;< "n0= 东 1= 南 2= 西 3= 北 4= 走出迷宫 nn 通路为 ( 横坐标 , 列坐标 , 方向) ：n"while (S1) / 逆置序列 并输出迷宫路径序列Pop(S1, e); Push(S2, e);while (S2)Pop(S2, e);cout << " -> " << e.x << "," << e.y << "," << e.d << "" return; / 选

13、用 return 跳出两层循环找到可以前进的非出口的点标记走过此点if (mazeab = 0) /mazeab = 2; / elem.x = i;elem.y = j;elem.d = d;Push(S1, elem); /当前位置入栈i = a; /下一点转化为当前点j = b;d = -1; d+;cout << " 抱歉，小老鼠走投无路没有吃到奶酪！" << endl;二） 栈的生成出栈图 3：栈的实现功能图该模块的具体代码如下所示Maze:Maze() Maze:Maze()int Maze:InitStack(PLStack &

14、S) / 构造空栈S = NULL;return 1;int Maze:StackEmpty(PLStack S) / 判断栈是否为空if (S = NULL)return 1;elsereturn 0;int Maze:Push(PLStack &S, lianzhan e) / 在栈中放入一个新的数据元素(进栈) PLStack p;p = (PLStack)malloc(sizeof(LStack); / 申请新的栈顶结点空间p->elem = e; / 将元素值置入结点数据域p->next = S; / 原栈顶结点昨晚新结点后继S = p; /将新结点置为栈顶ret

15、urn 1;int Maze:Pop(PLStack &S, lianzhan &e) / 栈顶元素出栈PLStack p;if (!StackEmpty(S)e = S->elem;p = S;S = S->next;delete p; /释放结点return 1;elsereturn 0;三） 整个系统的生成流程图五、程序测试与步骤一） 测试迷宫与栈问题的可通程序设计测试该函数使用的测试方法，测试的具体步骤，测试用例的选取，测试的结果10图 4： 在测试中可以找到迷宫和踩雷路径（二） 测试迷宫与栈问题的不可通程序设计 测试该函数使用的测试方法，测试的具体步骤，测

16、试用例的选取，测 试的结果。11图 5 ： 在测试中并未找到迷宫路径六、总结迷宫求解首先实现了随机输入 m和 n 的值，自己设定一个矩阵的行与12 列，在给定空间内控制了迷宫的范围，再从电脑中输入“ 0”为通路，“1 为围墙显示出一个迷宫的雏形来， 最终通过 for 循环给写好的迷宫加一个围 墙，得到我们想要的结果，并且给定迷宫的入口和出口，从而寻找到迷宫 的可同路径或者说入口处进入后，并不能找到可通路径从而退出。而我定 义“ 5”为地雷，这样小老鼠就能愉快的踩雷回到起点了，重新进行下一步 的通路探测。也可以循环使用此程序。系统在设计过程中我只考虑到了迷宫中给定入口和出口，在选择路径 时仅有东

17、、西、南、北，这四个方向寻找出口，而不是更加全面的在东南、 东北、西南、西北，方向同时寻找迷宫的出路，因此这一点是我认为考虑 很不周到的，但是我已经对这个功能有了初步设想，利用移动两次下标进 行东南、东北、西南、西北的方向实现，希望能够在今后的学习中更好的 完善，让这个迷宫求解更加的充实。我的收获是这次的课程设计的内容是使用 C+和数据结构来实现栈的 应用，这对我来说是个很具有挑战性的任务，虽然只做了一个迷宫与栈的 问题，而且运行起来有很大的局限性，但通过两星期的设计也从中学到了 不少的东西，更多的了解到了课本中丰富的内容。 数据结构是一门实践 性较强的课程，为了学好这门课程，必须在掌握理论知

18、识的同时，加强上 机实践。同时再次深刻的了解了数据结构中数组与基本函数之间的调用， 并且使用顺序结构，选择结构，循环结构的嵌套，根据实际问题的需要实 现迷宫与栈问题。在本次课程设计中，我明白了理论与实际相结合的重要 性，并提高了自己组织数据及编写程序的能力，挺高了综合运用所学知识 的能力。13七、附件（代码、部分图表）#include<iostream>using namespace std;#define M 20 / 行#define N 20 / 列int m, n;int diradd42 = 0, 1 , 1, 0 , 0, -1 , -1, 0 ; / 向依次为东西南北

19、 struct Zuobiao /行增量和列增量 方定义迷宫内点的坐标类型int x;int y;struct lianzhan /int x, y; /xint d; /d;链栈元素行,y 列为下一步的方向typedef struct LStack / lianzhan elem;struct LStack *next; *PLStack; /*链栈栈函数 */进栈）class Mazepublic:Maze();Maze();int InitStack(PLStack &S); /int StackEmpty(PLStack S); /int Push(PLStack &S

20、, lianzhan e); / int Pop(PLStack &S, lianzhan &e); / /* 求迷宫路径函数构造空栈 判断栈是否为空 在栈中放入一个新的数据元素 栈顶元素出栈 */void lujing(); void initmaze();void input();private:int mazeMN;14入口和出口的坐标<<<< endl;<<struct Zuobiao start, end; /start,end ;int main()int s;Maze example; cout cout << &q

21、uot;* 小老鼠吃奶酪 *" << endl; cout<< endl;cout<<<< endl;cout<<<< endl;example.initmaze();/ 建立迷宫 example.input();/ 输入 example.lujing();/ 路径 cout << endl;cout << endl;cout << endl;<<cout<< endl;cout << "<<按 1 '则可以继续

22、玩游戏 ,按任意键 GAME OVE'R !>>"cin >> s;if (s = 1)main();elsecout << "# GAME OVE！R！'#n 谢谢进入迷宫游戏！ " << endl;return 0;Maze:Maze()构造空栈Maze:Maze() int Maze:InitStack(PLStack &S) / 15S = NULL;return 1;int Maze:StackEmpty(PLStack S) /判断栈是否为空if (S = NULL)return

23、1;elsereturn 0;在栈中放入一个新的数据元素（进栈）申请新的栈顶结点空间栈顶元素出栈int Maze:Push(PLStack &S, lianzhan e) /PLStack p;p = (PLStack)malloc(sizeof(LStack); / p->elem = e; /将元素值置入结点数据域p->next = S; /原栈顶结点昨晚新结点后继S = p; / 将新结点置为栈顶 return 1;int Maze:Pop(PLStack &S, lianzhan &e) /PLStack p;if (!StackEmpty(S)e

24、= S->elem;p = S;S = S->next;delete p; /释放结点return 1;elsereturn 0;求迷宫路径函数 *void Maze:lujing() int i, j, d;int a, b;lianzhan elem, e;PLStack S1, S2, S3;InitStack(S1);InitStack(S2);InitStack(S3);16入口点作上标记mazestart.xstart.y = 2; /elem.x = start.x;elem.y = start.y;elem.d = -1; / 开始为 -1Push(S1, elem

25、);again:while (!StackEmpty(S1) / 栈不为空 有路径可走Pop(S1, elem);i = elem.x;j = elem.y;d = elem.d + 1; / 下一个方向while (d<4) / 试探东南西北各个方向a = i + diraddd0;b = j + diraddd1;if (mazeab = 5)while (S1) / 逆置序列 并输出迷宫路径序列Pop(S1, e);Push(S3, e); mazeab = 1;for (i = 0; i < m; i+)for (j = 0; j < n; j+)if (mazeab

26、 = 2) mazeab = 0;cout << "n0= 东 1= 南 2= 西 3= 北 4= 走出迷宫 nn 通路为 ( 横坐标 , 列坐标 , 方向 ) ：n"while (S3)Pop(S3, e);Push(S1, e);cout << " -> " << e.x << "," << e.y << "," << e.d << ""cout << "n 你在 &q

27、uot; << "" << a << "," << b << "" << "点踩到地雷了 " <<endl;d = 0;17goto again;if (a = end.x && b = end.y && mazeab = 0) /如果到了出口elem.x = i;elem.y = j; elem.d = d;Push(S1, elem);elem.x = a;elem.y = b;elem.d =

28、4; / 方向输出为 -1 判断是否到了出口 Push(S1, elem);cout << "n0= 东 1= 南 2= 西 3= 北 4= 走出迷宫 nn 通路为 ( 横坐标 , 列坐标 , 方向 ) ：n"while (S1) / 逆置序列 并输出迷宫路径序列Pop(S1, e); Push(S2, e);while (S2)Pop(S2, e);cout << " -> " << e.x << "," << e.y << "," << e.d << ""return; / 选用 return 跳出两层循环找到可以前进的非出口的点标记走过此点if (mazeab = 0) /mazeab = 2; / elem.x = i; elem.y = j; elem.d = d;Push(S1, elem); /当前位置入