数据结构迷宫问题实验报告_数据结构迷宫实验报告
数据结构迷宫问题实验报告由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构迷宫实验报告”。
《数据结构与算法设计》
迷宫问题实验报告
——实验二
专业：物联网工程 班级：物联网1班 学号：15180118 姓名：刘沛航
一、实验目的
本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。
二、实验内容
用一个m*m长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序对于任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
三、程序设计
1、概要设计
（1）设定栈的抽象数据类型定义
ADT Stack{
数据对象：D={ai|ai属于CharSet，i=1、2…n，n>=0} 数据关系：R={|ai-1,ai属于D，i=2,3,…n} 基本操作： InitStack(&S)
操作结果：构造一个空栈 Push（&S，e）
初始条件：栈已经存在操作结果：将e所指向的数据加入到栈s中 Pop（&S,&e）
初始条件：栈已经存在操作结果：若栈不为空，用e返回栈顶元素，并删除栈顶元素 Getpop（&S，&e）
初始条件：栈已经存在操作结果：若栈不为空，用e返回栈顶元 StackEmpty(&S)
初始条件：栈已经存在操作结果：判断栈是否为空。若栈为空，返回1，否则返回0 Destroy(&S)
初始条件：栈已经存在操作结果：销毁栈s }ADT Stack
（2）设定迷宫的抽象数据类型定义
ADT yanshu{
数据对象：D={ai,j|ai,j属于{‘ ’、‘*’、‘@’、‘#’},0
ROW={|ai-1,j,ai,j属于D，i=1,2,…M,j=0,1,…N} COL={|ai,j-1,ai,j属于D,i=0,1,…M，j=1,2,…N} 基本操作：
InitMaze(MazeType &maze, int a[][COL], int row, int col){
初始条件：二维数组int a[][COL],已经存在，其中第1至第m-1行，每行自第1到第n-1列的元素已经值，并以值0表示障碍，值1表示通路。
操作结果：构造迷宫的整形数组，以空白表示通路，字符‘0’表示障碍
在迷宫四周加上一圈障碍
MazePath（&maze）{
初始条件：迷宫maze已被赋值
操作结果：若迷宫maze中存在一条通路，则按如下规定改变maze的状态；以字符‘*’表示路径上的位置。字符‘@’表示‘死胡同’；否则迷宫的状态不变 }
PrintMaze（M）{ 初始条件：迷宫M已存在 操作结果：以字符形式输出迷宫 }
}ADTmaze
（3）本程序包括三个模块
a、主程序模块 void main(){ 初始化； 构造迷宫； 迷宫求解； 迷宫输出； }
b、栈模块——实现栈的抽象数据类型 c、迷宫模块——实现迷宫的抽象数据类型
2、详细设计
（1）坐标位置类型：
typedef struct{ int row;//迷宫中的行 int col;//......的列
}PosType;//坐标
（2）迷宫类型：
typedef struct{ int m,n;int arr[RANGE][RANGE];}MazeType;//迷宫类型
void InitMaze(MazeType &maze, int a[][COL], int row, int col)//设置迷宫的初值，包括边缘一圈的值
Bool MazePath(MazeType &maze,PosType start, PosType end)//求解迷宫maze中，从入口start到出口end的一条路径 //若存在，则返回true，否则返回false Void PrintMaze（MazeType maze）//将迷宫打印出来
（3）栈类型：
typedef struct{ int step;//当前位置在路径上的“序号” PosType seat;//当前的坐标位置
DirectiveType di;//往下一个坐标位置的方向 }SElemType;//栈的元素类型
typedef struct{ SElemType *base;SElemType *top;int stacksize;}SqStack;栈的基本操作设置如下： Void InitStack（SqStack & S）
//初始化，设S为空栈（S.top=NUL）Void DestroyStack(Stack &S)//销毁栈S，并释放空间
Void ClearStack（SqStack & S）//将栈S清空
Int StackLength（SqStack &S）//返回栈S的长度
Status StackEmpty（SqStack &S）？、若S为空栈（S.top==NULL），则返回TRUE，否则返回FALSE Statue GetTop（SqStack &S，SElemType e）
//r若栈S不空，则以e待会栈顶元素并返回TRUE，否则返回FALSE Statue Pop(SqStack&S，SElemType e)//若分配空间成功，则在S的栈顶插入新的栈顶元素s并返回TRUE //否则栈不变，并返回FALSE Statue Push(SqStack&S，SElemType &e)//若分配空间程控，则删除栈顶并以e带回其值，则返回TRUE //否则返回FALSE Void StackTraverse（SqStack &S，Status）（*Visit）（SElemType e））//从栈顶依次对S中的每个节点调用函数Visit 4求迷宫路径的伪码算法：
Status MazePath(MazeType &maze,PosType start, PosType end){ //求解迷宫maze中,从入口start到出口end的一条路径 InitStack(s);PosType curpos = start;int curstep = 1;//探索第一部 do{ if(Pa(maze,curpos)){ //如果当前位置可以通过,即是未曾走到的通道块 FootPrint(maze,curpos);//留下足迹
e = CreateSElem(curstep,curpos,1);//创建元素 Push(s,e);if(PosEquare(curpos,end))return TRUE;curpos =NextPos(curpos,1);//获得下一节点:当前位置的东邻 curstep++;//探索下一步 }else{ //当前位置不能通过 if(!StackEmpty(s)){ Pop(s,e);while(e.di==4 &&!StackEmpty(s)){ MarkPrint(maze,e.seat);Pop(s,e);//留下不能通过的标记,并退回步 } if(e.di
curpos = NextPos(e.seat,e.di);//设定当前位置是该方向上的相块 }//if }//if }//else }while(!StackEmpty(s));return FALSE;} //MazePath
四、程序调试分析
1.首先呢，想自己读入数据的，回来发现那样，很麻烦，所以还是事先定义一个迷宫。
2.栈的元素类型 一开始有点迷惑，后来就解决了
3.本题中三个主要算法；InitMaze，MazePath和PrintMaze的时间复杂度均为O（m*n）本题的空间复杂度也是O（m*n）
五、用户使用说明
1．本程序运行在windows系列的操作系统下，执行文件为：Maze_Test.exe。
六、程序运行结果
1.建立迷宫： 2．通过1功能建立8*8的迷宫后，通过2功能继续建立迷宫内部：
通过建立自己设定单元数目建立迷宫内墙。3．通过3功能观察已建立的迷宫结构：
4．通过4功能确立迷宫起点和终点：
（此处像我们随机选择4,4和2,7分别为起点终点）
5．执行5功能，判断是否有路径走出迷宫：
这种情况无法走出迷宫。
我们再次观察图像设4,4和1,6分别为起点终点，再运行5功能。
观察到可以成功解开迷宫步数从1依次开始。
七、程序清单
#include #include #include #include // 迷宫坐标位置类型 typedef struct { int x;int y;}PosType;// 行值
// 列值
#define MAXLENGTH 25 // 设迷宫的最大行列为25
typedef int MazeType[MAXLENGTH][MAXLENGTH];// 迷宫数组[行][列]
typedef struct // 栈的元素类型
{ int ord;// 通道块在路径上的＂序号＂
PosType seat;// 通道块在迷宫中的＂坐标位置＂
int di;// 从此通道块走向下一通道块的＂方向＂(0～3表示东～北)}SElemType;
// 全局变量
MazeType m;// 迷宫数组
int curstep=1;// 当前足迹,初值为1
#define STACK_INIT_SIZE 10 // 存储空间初始分配量
#define STACKINCREMENT 2 // 存储空间分配增量
// 栈的顺序存储表示
typedef struct SqStack { SElemType *base;// 在栈构造之前和销毁之后，base的值为NULL
SElemType *top;
int stacksize;
// 构造一个空栈S int InitStack(SqStack *S){ // 为栈底分配一个指定大小的存储空间
(*S).base =(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!(*S).base)
(*S).top =(*S).base;
return 1;
// 栈底与栈顶相同表示一个空栈
(*S).stacksize = STACK_INIT_SIZE;exit(0);}SqStack;// 顺序栈
// 栈顶指针
// 当前已分配的存储空间，以元素为单位 }
// 若栈S为空栈（栈顶与栈底相同的），则返回1，否则返回0。int StackEmpty(SqStack S){ if(S.top == S.base)
else
}
// 插入元素e为新的栈顶元素。int Push(SqStack *S, SElemType e){ if((*S).top-(*S).base >=(*S).stacksize)// 栈满，追加存储空间
{
} *((*S).top)++=e;return 1;} // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；否则返回0。int Pop(SqStack *S,SElemType *e){ if((*S).top ==(*S).base)
左
return 1;} // 定义墙元素值为0,可通过路径为1,不能通过路径为-1,通过路径为足迹 // 当迷宫m的b点的序号为1(可通过路径)，return 1;否则，return 0。int Pa(PosType b){
if(m[b.x][b.y]==1)
else return 0;return 1;return 0;*e = *--(*S).top;
// 这个等式的++ * 优先级相同，但是它们的运算方式，是自右向
(*S).base =(SElemType *)realloc((*S).base ,(*S).top =(*S).base+(*S).stacksize;(*S).stacksize += STACKINCREMENT;((*S).stacksize + STACKINCREMENT)* sizeof(SElemType));exit(0);if(!(*S).base)return 0;return 1;}
void FootPrint(PosType a)
// 使迷宫m的a点的序号变为足迹(curstep)，表示经过 { m[a.x][a.y]=curstep;}
// 根据当前位置及移动方向，返回下一位置
PosType NextPos(PosType c,int di){ PosType direc[4]={{0,1},{1,0},{0,-1},{-1,0}};// {行增量,列增量}
// 移动方向,依次为东南西北
c.x+=direc[di].x;c.y+=direc[di].y;return c;}
// 使迷宫m的b点的序号变为-1(不能通过的路径)void MarkPrint(PosType b){
m[b.x][b.y]=-1;} // 若迷宫maze中存在从入口start到出口end的通道，则求得一条
// 存放在栈中(从栈底到栈顶)，并返回1；否则返回0 int MazePath(PosType start,PosType end){
SqStack S;PosType curpos;SElemType e;
InitStack(&S);curpos=start;do {
if(Pa(curpos)){// 当前位置可以通过，即是未曾走到过的通道块
FootPrint(curpos);// 留下足迹
e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=0;Push(&S,e);// 入栈当前位置及状态
curstep++;// 足迹加1
if(curpos.x==end.x&&curpos.y==end.y)// 到达终点(出口)
} else return 1;curpos=NextPos(curpos,e.di);{// 当前位置不能通过
} if(!StackEmpty(S)){
} Pop(&S,&e);// 退栈到前一位置
curstep--;while(e.di==3&&!StackEmpty(S))// 前一位置处于最后一个方向(北){
} if(e.di
}
e.di++;// 换下一个方向探索
Push(&S,e);curstep++;// 设定当前位置是该新方向上的相邻块 curpos=NextPos(e.seat,e.di);
MarkPrint(e.seat);// 留下不能通过的标记(-1)Pop(&S,&e);// 退回一步
curstep--;}while(!StackEmpty(S));return 0;}
// 输出迷宫的结构
void Print(int x,int y){
int i,j;
for(i=0;i
} }
void main(){ PosType begin,end;int i,j,x,y,x1,y1,n,k;for(j=0;j
//清屏函数
printf(“***************************************************nnn”);printf(“
1请输入迷宫的行数,列数n”);printf(“
2请输入迷宫内墙单元数n”);printf(“
3迷宫结构如下n”);printf(“
4输入迷宫的起点和终点n”);printf(“
5输出结果n”);printf(“
0退出n”);printf(“nn请选择
”);scanf(“%d”,&n);switch(n){ case 1:{
printf(“请输入迷宫的行数,列数(包括外墙)：(空格隔开)”);
scanf(“%d%d”, &x, &y);
for(j=1;j
{
for(i=1;i
for(j=1;j
// 迷宫左边列的周边即左边墙
m[j][y-1]=0;// 迷宫右边列的周边即右边墙
for(i=0;i
// 迷宫上面行的周边即上边墙
m[x-1][i]=0;// 迷宫下面行的周边即下边墙
物
联
网
班
-15180118-刘沛
航
}
}break;
case 2:
{printf(“请输入迷宫内墙单元数：”);
scanf(“%d”,&j);
printf(“请依次输入迷宫内墙每个单元的行数,列数：(空格隔开)n”);
for(i=1;i
{ scanf(“%d%d”,&x1,&y1);
} m[x1][y1]=0;
}break;
case 3:{ Print(x,y);printf(“刘沛航建立的迷宫，定义墙元素值为0,可通过路径为1，输入0退出”);scanf(“%d”,&k);}break;
case 4:{ printf(“请输入起点的行数,列数：（空格隔开）”);
scanf(“%d%d”,&begin.x,&begin.y);
printf(“请输入终点的行数,列数：（空格隔开）”);
scanf(“%d%d”,&end.x,&end.y);}break;
case 5:{
if(MazePath(begin,end))// 求得一条通路
{
} else printf(“此迷宫没有从入口到出口的路径，谢谢使用刘沛航的程序n”);printf(“输入0退出”);scanf(“%d”,&k);}break;} }while(n!=0);} printf(“此迷宫从入口到出口的一条路径如下，谢谢使用刘沛航的程序:n”);Print(x,y);// 输出此通路
