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

数据结构实训报告设计题目：迷宫的求解（B）系别：XXXXXXXXXX专业(方向)：XXXXXXXX年级、班：XXXXXXXXXXXX学生姓名：XXX学生学号：XXXXXX指导教师：XXX日期：XXXX年XX月XX号目录一、系统开发的背景................................................................................................................1二、系统分析与设计................................................................................................................1（一）系统的分析....................................................................................................................1（二）系统的具体分析设计....................................................................................................2三、系统的功能要求..............................................................................................................................2、3（一）系统模块结构设计........................................................................................................3四、系统的设计与实现................................................................................................................................4（一）在栈中实现迷宫的具体操作.................................................................................4、7（二）栈的生成.................................................................................................................7、8（三）整个系统的生成流程图…………………………………………………………9、10五、程序测试与步骤.............................................................................................................10（一）测试迷宫与栈问题可通的程序设计…………..……………………………………10、11（二）测试迷宫与栈问题不可通的程序设计…………………………………………..…..12六、总结………………………………………………………………………………………….12、13七、附件（代码、部分图表）......................................................................................14、191迷宫的求解一、系统开发的背景迷宫求解其实就是迷宫与栈的问题，训练老鼠在迷宫中寻找食物。于是，老鼠过迷宫问题就此产生，这是一个很有趣的计算机问题，主要利用“栈”是老鼠通过尝试的办法从入口穿过迷宫走到出口。迷宫只有两个门，一个叫做入口，另一个叫做出口。把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。为了使迷宫更佳富有趣味性，按照设计要求，我还设置地雷，如果老鼠在前进的过程中踩到地雷，则要重新回到入口，继续寻找能吃到奶酪的通路。求解迷宫问题，即找出从入口到出口的路径。而数据结构则是数据的组织形式，可以用来表示特定的对象数据，在计算机中对数据的一种存储和组织形式，因此选用栈思想实现迷宫游戏的基本操作，也是我设计迷宫求解的基本背景。二、系统分析与设计(一)系统分析：迷宫问题通常是用“穷举求解”方法解决，即从入口出发，顺着某个方向进行搜索，若能走通，则继续往前走；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。另外附加的老鼠踩地雷则类似于是在通路上埋藏的隐形墙，如果踩到到雷则返回起点，寻找下一条2通路。栈是一个后进先出的结构，可以用来保存从入口到当前位置的路径。定义迷宫类型来存储迷宫数据，通常设定入口点的下标，出口点的下标，为处理方便起见，在迷宫的周围加一圈障碍，对于迷宫任何一个位置均约定为东、西、南、北四个方向，而东北、东南、西北、西南则是需要利用到两个下标进行移动。(二)系统具体设计在某个点上，按照一定的顺序（在本程序中顺序为上、右、下、左，而东北、东南、西北、西南利用的是两个下标移动）对周围的墙、路进行判断（在本程序中分别用1、0代替），若周围某个位置为0，则移动到该点上，再进行下一次判断；若周围的位置都为1（即没有通路），则一步步原路返回并判断有无其他通路，然后再次进行相同的判断，直到走到终点为止，或者确认没有任何通路后终止程序，附加踩雷（在本程序中用5代替）则返回到起点重新寻找下一条通路，并显示踩雷路线。要实现上述算法，需要用到栈的思想。栈里面压的是走过的路径，若遇到死路，则将该位置（在栈的顶层）弹出，再进行下一次判断；若遇到通路，则将该位置压栈并进行下一次判断。如此反复循环，直到程序结束。此时，若迷宫有通路，则栈中存储的是迷宫通路坐标的倒序排列，再把所有坐标顺序打印后，即可得到正确的迷宫通路，附加的踩雷则是相当于在通路上隐形了一道墙，踩雷，则从栈顶弹出，返回起点，再进行二次判断另一条通路。三、系统功能要求3（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：迷宫实现的主函数功能图通过上图的功能分析，把整个系统划分为2个模块：1、通过栈后进先出的结构，实现栈判断，首先判断栈是否为空，如果不为空，则实现栈中基本的入栈，出栈的实现。顺序栈是用一组地址连续主函数初始化栈入栈出栈判断栈是否为空判断方向留下足迹判断能否通过，是否踩雷初始化迷宫求解所有路径输出迷宫留下标记4的内存单元依次保存栈中的运算规则，在链式存储中链表首部head指针所指向元素为栈顶元素，栈表尾部指向地址为NULL为栈底。2、借助函数的嵌套与使用，由while语句对整体进行控制，return语句控制跳出函数，判断在迷宫中是否有出路，如果有出路，则通过东，西，南，北的方向进行路径的输出；如果无出路，则说明此迷宫不能走出。四、系统的设计与实现（一）在栈中实现迷宫的基本操作分析：首先输出表头，然后依次输入想要实现的步骤。功能图如图2所示。入口，出口位置传人方法里判断当前是否通过循环不结束，无解迷宫将元素入栈是否到达迷宫出口右边是否存在通路上边是否存在通路下边是否存在通路左边是否存在通路5图2：迷宫的实现功能图该模块的具体代码如下所示。voidMaze::lujing(){inti,j,d;inta,b;lianzhanelem,e;PLStackS1,S2,S3;InitStack(S1);InitStack(S2);InitStack(S3);maze[start.x][start.y]=2;//入口点作上标记elem.x=start.x;elem.y=start.y;elem.d=-1;//开始为-1Push(S1,elem);again:while(!StackEmpty(S1))//栈不为空有路径可走{Pop(S1,elem);i=elem.x;j=elem.y;d=elem.d+1;//下一个方向while(d4)//试探东南西北各个方向{a=i+diradd[d][0];b=j+diradd[d][1];if(maze[a][b]==5){while(S1)//逆置序列并输出迷宫路径序列存在结点入栈有解迷宫6{Pop(S1,e);Push(S3,e);}maze[a][b]=1;for(i=0;im;i++)for(j=0;jn;j++){if(maze[a][b]==2)maze[a][b]=0;}cout\n0=东1=南2=西3=北4=走出迷宫\n\n通路为(横坐标,列坐标,方向)：\n;while(S3){Pop(S3,e);Push(S1,e);cout--{e.x,e.y,e.d};}cout\n你在[a,b]点踩到地雷了endl;d=0;gotoagain;}if(a==end.x&&b==end.y&&maze[a][b]==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\n0=东1=南2=西3=北4=走出迷宫\n\n通路为(横坐标,列坐标,方向)：\n;while(S1)//逆置序列并输出迷宫路径序列{Pop(S1,e);Push(S2,e);}while(S2)7{Pop(S2,e);cout--{e.x,e.y,e.d};}return;//选用return跳出两层循环}if(maze[a][b]==0)//找到可以前进的非出口的点{maze[a][b]=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(){构建栈函数栈为空入栈出栈8}Maze::~Maze(){}intMaze::InitStack(PLStack&S)//构造空栈{S=NULL;return1;}intMaze::StackEmpty(PLStackS)//判断栈是否为空{if(S==NULL)return1;elsereturn0;}intMaze::Push(PLStack&S,lianzhane)//在栈中放入一个新的数据元素（进栈）{PLStackp;p=(PLStack)malloc(sizeof(LStack));//申请新的栈顶结点空间p-elem=e;//将元素值置入结点数据域p-next=S;//原栈顶结点昨晚新结点后继S=p;//将新结点置为栈顶return1;}intMaze::Pop(PLStack&S,lianzhan&e)//栈