数据结构实验报告：迷宫问题
《数据结构》实验报告
题目：迷宫问题
专业：信息管理与信息系统班级：3班
组别：第一组组长：胡源完成日期：2018年12月8 日
评分依据及结果
代码分工情况
实验报告分工情况
一、需求分析
1、本演示程序中，有两种形成迷宫的方式，一是程序本身已经设定好的十行
十列的迷宫，二是系统自动随机生成十行十列的迷宫。迷宫由数字0和1构成，用0表示通路，1表示墙，
2、演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示
信息”之后，由用户在键盘上输入演示程序中规定的运算命令，相应的输入数据（只能输入数字）和运算结果显示在其后。
3、按照系统提示，先输入迷宫的入口坐标，（1到10之间的数字，两个数字
之间用空格隔开），输入后按任意键继续，系统提示输入迷宫出口坐标（同上），按任意键继续，进入第二个界面。
4、本次实验所解决的问题是：①寻找迷宫的出路；②寻找迷宫的所有路径；
③找出迷宫所有出路中最短路径。
5、程序执行的命令包括：
第一界面：
是否自动生成迷宫？
自动生成请按1
使用原始迷宫请按2
第二界面：
1----------求迷宫的一条路；
2----------求迷宫的全部路；
3-----------退出。
输入想实现的功能所对应的数字，按任意键继续即可。
二、概要设计
为了实现上述程序功能，应以栈来实现，因此需要栈的抽象数据类型。
1、迷宫的抽象数据类型为：
ADT Stack{
数据对象：D={ai|ai€ElemSet,i=1,2,…,n,n>=0}
数据关系：R={
基本橾作：
InitStack(&S)
操作结果：构造一个空栈S 。
GetTop(S, &e)
初始条件：栈S已存在且非空。
操作结果：用e返回S 的栈顶元素。
Push(&s，e)
初始条件：栈S已存在。
操作结果：插入元索e为新的栈顶元素。
Pop(&s, &e)
初始条件：栈S 已存在且非空。
操作结果：删除S 的栈顶元素，并用e返回其值。
StackEmpty(S)
初始条件：栈S已存在。
操作结果：若栈S为空栈，则返回TRUE, 否则FALSE。
操作结果：从栈底到栈顶依次对S 的每个数据元素调用函数visit()。一旦
visit()失败，则操作失效。
}ADT Stack
2、总共包含三个头文件，一个源文件
Stru.h 定义了两个结构体，point类和Selem类
Stack.h 定义了栈的结构体类型，以及和栈的相关操作
Maze.h 定义了与求解迷宫所有有关的函数和变量
Maze.cpp存储迷宫的二维数组，和相关的函数和变量
三、详细设计
(I)问题求解方法分析
最自然的求解方法是DFS算法，从入口出发，固定的按照东、东南、南、西南、西、西北、北、东北八个方向的顺序找到为通道的相邻格中第一个，若找到，则下一步走到该相邻格，否则返回上一步(回溯)，按照同样的规则找下一步，如此循环，直到走到出口或退出出口(无路径)为止，实现一条路径的求解。
(2)问题的表示----数据结构
a．为了保证每一个行走位置都有在东、东南、南、西南、西、西北、北、东北八个方向上的下一个位置，为迷宫加一圈边墙，分别是从一到十。b．迷宫可以用二维数组R[10][10]来表示，数组中的元素0表示通道，1表示墙，空格表示没有走过的路，“*”表示走过且走通的路，"灪"表示走过但不通的路，“国”表示障碍，迷宫入口为和出口为用户设置。
c. 任意时刻在迷宫中的行走位置可用坐标arra[a.seat.row][a.seat.col]
表示，在任意行走位置arra[a.seat.row][a.seat.col]时，下一位置的行走方
向为东、东南、南、西南、西、西北、北、东北八个方向。
d．固定按顺时针搜索当前位置的八个运动方向东、东南、南、西南、西、西北、北、东北的下一位置。用一个栈保存行走的路径(从栈底到栈顶)，其中每个单元存放2个行列下标。
(3)算法描述
do{
若当前位置可通
则{将当前位置插入栈顶
若当前位置是出口位置，则结束
否则切换当前位置的东邻方块为新的当前位置
}
否则{
若栈不空且栈顶位置尚有其他方向未经搜索
则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块
若栈不空但栈顶位置的四周都不通
则{ 删去栈顶位置
若栈不空，则重新测试新的栈顶位置
直到找到一个可通的相邻块或出栈至栈空
}
}
}while(栈不空)
四、调试分析
两个问题：
①如何判断所有路径搜索完毕
②怎样做到寻找全部路径
①判断所有路径搜索完毕解决
错误尝试：
把存储迷宫的二维数组进行一次便利，只要所有的方块或为墙或标记过了，判定是否找完所有路径
这种情况解决不了，只有说当栈中的所有元素都出了栈，此函数结束（可能找得到路径，可能找不到路径）
②怎样做到寻找全部路径
1.找到出口以后不能结束程序先退栈，直到栈顶元素8个方向都试完了。
2.不能再对死路进行标记。退栈的时候，把之前做的标记抹去，确保下一次从不同方向来的时候可以通过
Maze.h
DFS算法实现
SqStack S1;
SElemType e;
InitStack(S1);
PosType CurPos = start;
Status MazePath(int arra[][RANGE], PosType start, PosType end) {//输入迷宫（数组），起点和终点，求全部路径
初始化信息（略）
do{
if (Pass(arra, CurPos))//当前是零，为通路（函数提前定义）{
FootPrint(arra, CurPos);//标记为2，（函数提前定义）
e = SElem(CurPos,1);//够造函数的应用
Push(S1,e);//e元素压入栈
if (PosEquare(CurPos, end)) ;//判断是不是出口
{
PrintMaze(arra);
return OK;
}
CurPos = NextPos(CurPos, 1);//坐标按着标记方向移动
}
else//当前位置不是0，不通
while (!StackEmpty(S1));//S1非空，一直循环
return FALSE;
}
需要修改
Maze.h所有路径
算法实现
While（栈不空时循环）
{
If（找到了出口）
{
则输出查找路径，并退栈，用新的栈顶方向值取代当前的查找方向}
while（四个方向没有试玩）
{
换个方向继续检测
}
If（当前栈顶的4个方向都走完了，不通）
{
则退栈找新的栈顶元素
}else
{
把元素压入栈
}
Status MazeAllPath(int arra[][RANGE], PosType start, PosType end)
{ //输入迷宫（数组），起点和终点，求全部路径
int i, j,nextfound; SqStack S1; InitStack(S1);
SElemType a; int count = 0; int step = 1;
Push(S1, SElem( start, 0)); //该点的初始方向值0
arra[1][1] = 2; int minlen = RANGE; //最短路径长度
int minarr[100][100];//存储最短路径的数组
while (!StackEmpty(S1)) //栈不空时循环
{ a = GetTop(S1);
if (PosEquare((GetTop(S1).seat), end))//如果找到出口
{printf("\n"); printf("M%d: ", ++count); printf("\n");
PrintMaze(arra); //打印路径Pop(S1, a);//栈顶出栈
arra[a.seat.row][a.seat.col] = 0;//取消之前的足迹
if (LengthStack(S1) for (i = 0; i <= ROW + 1; i++) {for (j = 0; j <= COL + 1; j++){ minarr[i][j] = arra[i][j];}}//保存最短路径 minlen = LengthStack(S1); //保存最短路径的长度 } } nextfound = 0;//表示下一个结点不可走 a = GetTop(S1); while (a.di<8&& nextfound == 0) //找下一个可走结点 { while (a.di<8&& nextfound == 0) //八个方向没找完，找下一个可走结点 { Pop(S1, a); a.di++; //下一个查找方向 Push(S1, a); // 三条语句实现了修改栈顶元素的方向 a = GetTop(S1); if (Pass(arra, NextPos(a.seat, a.di))) { nextfound = 1; } } if (nextfound == 1) //从当前栈顶上找到了下一个可走结点{Push(S1, SElem(NextPos(a.seat, a.di), 0)); //下一个可走结点进栈arra[NextPos(a.seat, a.di).row][NextPos(a.seat, a.di).col] = 2; }else //如果当前栈顶的4个方向都已经查找完 { Pop(S1, a); arra[a.seat.row][a.seat.col] = 0; // 清除足迹} if (count==0) return FALSE; printf("\n"); printf("最短路径为：%d",minlen); printf("\n如下:"); printf("\n"); PrintMaze(minarr); printf("\n"); return OK; } Status InitMaze(int arra[][RANGE], int a[][COL], int row, int col) {//把迷宫路径进行初始化，对迷宫的边界加上墙 for (int i = 1; i <= row; i++) { for (int j = 1; j <= col; j++) arra[i][j] = a[i - 1][j - 1]; } for (int j = 0; j <= col + 1; j++) arra[0][j] = arra[row + 1][j] = 1;//把上下的边界初始化为1 for (int i = 0; i <= row + 1; i++) arra[i][0] = arra[i][col + 1] = 1;//把左右边界初始化为1 return OK; } 实验中的收获 错误1： error C4996: 'scanf': This function or variable may be unsafe. Consider using scanf_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details. 解决办法： 1.在VS里面不推荐用scanf可以替换成scanf_s 2. #define _CRT_SECURE_NO_DEPRECATE 加在头文件的开头 五、用户守则 （1）本程序的运行环境为DOS操作系统，执行文件为：SET.exe； （2）进入演示程序后显文本的用户界面； 自动生成迷宫： 用户输入命令1，进入下一个界面： ①输入迷宫入口坐标（输入两个1到10之间数字，中间空格隔开）； ②输入迷宫出口坐标（输入两个1到10之间数字，中间空格隔开），按随意键继 续。 输入各功能所对应的序号，按回车键继续。使用原始迷宫： 用户输入命令2，进入下一个界面 ①输入迷宫入口坐标（输入两个1到10之间数字，中间空格隔开）； ②输入迷宫出口坐标（输入两个1到10之间数字，中间空格隔开），按随意键继续。 输入各功能所对应的序号，按回车键继续。 1 六、测试结果（及截图） 附录（源代码） #include #include #include #define TRUE1 #define FALSE0 #define OK1 #define ERROR0 #define INFEASIBLE-1 #define OVERFLOW-2 #define RANGE100 typedef int DirectiveType; typedef int Status; typedef struct{ int row; int col; }PosType; typedef struct SElem{ //int step; PosType seat; DirectiveType di; SElem(PosType b, DirectiveType c){ seat = b; di = c; }; SElem(){}; }SElemType; #include"stack.h" #define ROW10 #define COL10 #define RANGE100 Status InitMaze(int arra[][RANGE], int a[][COL], int row, int col) {//把迷宫路径进行初始化 for (int i = 1; i <= row; i++) { for (int j = 1; j <= col; j++) arra[i][j] = a[i - 1][j - 1]; } for (int j = 0; j <= col + 1; j++) arra[0][j] = arra[row + 1][j] = 1;//把上下的边界初始化为1 for (int i = 0; i <= row + 1; i++) arra[i][0] = arra[i][col + 1] = 1;//把左右边界初始化为1 return OK; } Status Pass(int arra[][RANGE], PosType CurPos)//判断是是否为零 { if (arra[CurPos.row][CurPos.col] == 0)//是否能通，用0表示路，1表示墙return OK; else return ERROR; } Status FootPrint(int arra[][RANGE], PosType CurPos) { arra[CurPos.row][CurPos.col] = 2;//通的过，留下足迹，标记为2 return OK; } Status MarkPrint(int arra[][RANGE], PosType CurPos) { arra[CurPos.row][CurPos.col] = 3;//走过但是不能通过，标记为3 return OK; } PosType NextPos(PosType CurPos, DirectiveType di) {//返回值的类型是当前坐标按照给方向前进一个单位后的坐标 PosType Pos = CurPos; switch (di) { case1:Pos.col++; break;//East东，行不变，列加一 case2:{Pos.col++; Pos.row++;} break;//东南，列不变，行减一 case3:Pos.row++; break;//south南，列不变，行加一 case4:{Pos.col--; Pos.row++; } break;//西南，列不变，行减一 case5:Pos.col--; break;//west西，行不变，列减一 case6:{Pos.col--; Pos.row--;} break;//西北，列不变，行减一 case7:Pos.row--; break;//north北，列不变，行减一 case8:{Pos.col++; Pos.row--;} break;//东北，列不变，行减一 } return Pos; } Status PosEquare(PosType Pos1, PosType Pos2) {//判断连个点的坐标是否相等 if (Pos1.col == Pos2.col && Pos1.row == Pos2.row) return1; else return0; } void PrintMaze(int arra[][RANGE]) { int i, j; printf(" "); for (i = 0; i <= COL + 1; i++)//横坐标打印 printf("%2d", i);// % 2d是将数字按宽度为2，采用右对齐方式输出，如果数据位数不到2位，则左边补空格。 printf("\n"); for (i = 0; i <= ROW + 1; i++) { printf("%2d", i);//纵坐标打印 for (j = 0; j <= COL + 1; j++) { switch (arra[i][j]) { case0:printf(" ");break;//没有走过 case2:printf(" *"); break;//走过且走的通 case3:printf("灪"); break;//走过但不通 case1:printf("国"); break;//障碍 } } printf("\n"); } } Status MazePath(int arra[][RANGE], PosType start, PosType end) { SqStack S1;//栈 SElemType e;//序号，坐标，方向 InitStack(S1); PosType CurPos = start;//起始坐标 int Curstep = 1;//初始为路径的第一步 do { if (Pass(arra, CurPos))//当前是零，为通路 { FootPrint(arra, CurPos);//标记为2 e = SElem(CurPos,1);//够造函数给 Push(S1,e);//e元素压入栈 if (PosEquare(CurPos, end)) { PrintMaze(arra); return OK; } else CurPos = NextPos(CurPos, 1);//坐标按着标记方向移动/*return TRUE;*///判断是不是出口 /*CurPos = NextPos(CurPos, 1);*///坐标按着标记方向移动 Curstep++;//步数加一 } else {//当前位置不是0，不通 if (!(StackEmpty(S1))) {//栈不为空 Pop(S1, e);//把栈顶元素从栈中拿出来 while (e.di == 8 && !StackEmpty(S1)) {//e的四个方向都是试过了，并且栈不空，就是死路，通过这个循环，把死路中的元素全部从栈中拿出来 MarkPrint(arra, e.seat);//走过但是不通进行标记为3 Pop(S1, e);//把e元素从栈中拿出来 } if (e.di < 8) {//四个方向没有试完 e.di++; //改变方向 Push(S1, e);//把e元素押进栈 CurPos = NextPos(e.seat, e.di);//把坐标改变 } } } } while (!StackEmpty(S1));//S1非空，一直循环 return FALSE; } Status MazeAllPath(int arra[][RANGE], PosType start, PosType end) //路径为:(1,1)->(M,N) { int i, j, di, nextfound, k; //di是方向 SqStack S1;//栈 InitStack(S1); SElemType a; //初始结点进栈 //栈顶指针，初始值为-1 int count = 0; //路径数计数 int step = 1; Push(S1, SElem( start, 0)); //该点的初始方向值0，表示还没查找过从此出发的其他4个方向 arra[1][1] = 2; //2表示该节点位置进栈过(最好用其他数组来标示) int minlen = 100; //最短路径长度 int minarr[100][100]; while (!StackEmpty(S1)) //栈不空时循环 { a = GetTop(S1); if (PosEquare((GetTop(S1).seat), end)) { printf("\n"); printf("M%d: ", ++count); printf("\n"); PrintMaze(arra); Pop(S1, a); arra[a.seat.row][a.seat.col] = 0;