数据结构试验迷宫问题

数结构试验——迷宫问题

（）基问题
1问题描述
心理学中典问题心理学家老鼠顶盖盒子入口处放入老鼠行找出口出迷宫中设置障碍阻止老鼠前行迷宫唯出口处放块奶酪吸引老鼠找出口
简言迷宫问题解决布置许障碍通道中寻找出路问题题设置迷宫图1示

图1 迷宫示意图
迷宫四周设墙填充处通处设点四通方分东南西北(清晰称左右)左角入口右角出口迷宫入口出口设计程序求解迷宫条通路
2数结构设计
m×n数组mg表示迷宫元素表示方块状态数组元素01分表示迷宫中通路障碍迷宫四周墙应迷宫数组边界元素均1根题目中数设置数组mg
int mg[M+2][N+2]
{
{11111111}
{10010001}
{11000111}
{10010001}
{10000001}
{11111111}
}算法中栈采序存储结构栈定义
Struct
{ int i 前方块行号
int j 前方块列号
int di di相邻走方位号
}st[MaxSize] 定义栈
int top1 初始化栈
3设计运算算法
寻找条通迷宫路径必须进行试探性搜索路走前进步路进换方进行尝试方均走时原路退回步（称回溯）重新选择未走走路继续直达出口返回入口（没通路）探索前进路径时需搜索踪迹记录便走通时原路返回前点换方进行新探索退尝试路径前进路径正相反栈记录前进路径


方：通点4尝试方方前进时目坐标预先4方位移存数组中右左（时针方）次编号0123增量数组move[4]图3示
move[4]
x
y
0
1
0
1
0
1
2
1
0
3
0
1
图2数组move[4]
方位示意图：


通路：通路点3属性：横坐标属性i列坐标属性j方属性di表示点位置果约定尝试序右左（时针方）尝试方通时di值增1d增4时表示位置定通路点栈中找出口时栈中保存条迷宫通路
（1）面介绍求解迷宫（xiyj）终点（xeye）路径函数：先入口进栈（初始位置设置—1）栈空时循环——取栈顶方块（退栈）①该方块出口输出方块路径代码相应解释：
int mgpath(int xiint yiint xeint ye) 求解路径(xiyi)>(xeye)
{
struct
{
int i 前方块行号
int j 前方块列号
int di di走方位方位号
} st[MaxSize] 定义栈
int top1 初始化栈指针
int ijkdifind
top++ 初始方块进栈
st[top]ixist[top]jyi
st[top]di1mg[1][1]1
while (top>1) 栈空时循环
{
ist[top]ijst[top]jdist[top]di 取栈顶方块
if (ixe && jye) 找出口输出路径
{
printf(迷宫路径＼n)
for (k0k {
printf(＼t(dd)st[k]ist[k]j)
if ((k+1)50) 输出5方块换行
printf(＼n)
}
printf(＼n)
return(1) 找条路径返回1
}

②否找走相邻方块存样路径说明前路径走通恢复前方块0退栈存样方块方位保存栈顶元素中走相邻方块进栈（初始位置设置1）
求迷宫回溯程图4示

前方块找相邻走方块前方块找相邻走方块没样方快说明前方块入口路径出口路径方块前方块回溯前方块继续前方块找走方块
保证试探走相邻方块已走路径方块（ij）已进栈试探（i+1j）方块时试探道（ij）样会悲剧引起死循环方块进栈应mg数组元素值改1（变走相邻方块）退栈时（表示该方块没相邻走方块）值恢复0算法代码相应解释：
find0
while (di<4 && find0) 找走方块
{
di++
switch(di)
{
case 0ist[top]i1jst[top]jbreak
case 1ist[top]ijst[top]j+1break
case 2ist[top]i+1jst[top]jbreak
case 3ist[top]ijst[top]j1break
}
if (mg[i][j]0) find1找走相邻方块
}
if (find1) 找走方块
{
st[top]didi 修改原栈顶元素di值
top++ 走方块进栈
st[top]iist[top]jjst[top]di1
mg[i][j]1 避免重复走该方块
}
else 没路径走退栈
{
mg[st[top]i][st[top]j]0该位置变路径走方块
top 该方块退栈
}
}
return(0) 表示没走路径返回0
（2）求解程序
建立函数调面算法mgst栈指针定义全局变量
void main()
{
mgpath(11MN)
}

3界面设计
设计简单界面输出路径
4运行结果

图5基运行结果
（二）8方问题
1设计思想
(1)设置迷宫节点数结构
(2)建立迷宫图形
(3)迷宫进行处理找出条入口点出口点路径
(4)输出该路径
(5)印通路迷宫图
初始化迷宫
通机方法设置迷宫布局
建立输出迷宫原图
搜索迷宫通路
输出迷宫通路路线图
结束
图6功结构图

迷宫采二维数组表示时老鼠迷宫时刻位置数组行列序号ij表示 [i][j]位置出发进行方见图7果[i][j]周围位置均0值老鼠选择8位置中作位置8方分记作：E（东）SE（东南）S（南）SW（西南）W（西）NW（西北）N（北）NE（东北）非位置8相邻位置果[i][j]位边界i1imj1jn相邻位置35避免检查边界条件数组四周围值1边框包围起样二维数组maze应该声明maze[m+2][n+2]迷宫行进时行进方选规定方搜索次序东（E）时针方进行简化问题规定[i][j]步位置坐标[x][y]8方位伤xy坐标增量预先放结构数组move[8]中（见图8）该数组分量两域dxdy例 东走j值加dy步位置[x][y]值[i][j+dy]搜索方变化令方值dir0增7便move数组中[i][j]点出发搜索相邻点[x][y]
xi+move[dir]dx
yj+move[dir]dy
dx dy



图7 方位移图 图8量差图

防止重走原路规定已走位置原值0改1区该位置否已走边界值1相区整搜索程结束1改回0恢复迷宫原样
样计算机走迷宫方法：采取步步试探方法步（E）开始时针8方进行探测某方位maze[x][y]0表示通行走步maze[x][y]1表示方通行须换方试直8方试maze[x][y]均1说明步已路走需退回步步方重新开始探测需设置栈记录走位置方（ijdir）
退回步时栈中退出元素便位置方探测找行进方前位置新方重新进栈走新位置果探测xmyn已达迷宫出口停止检测输出存栈中路径某位置8方堵塞退回步继续探测果已退迷宫入口（栈中元素）表示迷宫路径通行
2系统算法（伪代码描述）：
(1)建立迷宫节点结构类型stack[]
(2)入迷宫图形 0表示通 1表示通 二维数组maze[m+2][n+2]进行存储
数组四周1表示墙壁中入口点（11）出口点（mn）固定
(3)函数path()迷宫进行处理入口开始：
While(((s>top1)&&(dir>7)||(xM)&&(yN)&&(maze[x][y]1)))
{
For(扫描八走方)
{
If(找走方)
{
进入栈
标志前点找走方
避免重复选择maze[x][y]1
前节点扫描
}
If(八方已全部扫描通路)
{
标志前节点没前路
退节点搜索
}
}
If(找目)
{
输出路径退出循环
}
}
未找路径
(4)输出入口点出口点条路径
(5)输出标通路迷宫图
3算法流程图：

开始
初始化迷宫显示迷宫
初始化方位移数组
寻找迷宫中条出路
If maze[x][y]0
设11出口
该点数入栈
T
F
While 栈空dir<7
do
elseIf dir<7
dir++
T
F
回退步
出口入口
dir>7 栈空
显示通路
结束
图9 算法流程图


4程序代码：
#define M2 12 *M2*N2实际迷宫数组*
#define N2 11
#define maxlen M2 栈长度
#include
#include
#include
int MM22NN22M*N迷宫
typedef struct 定义栈元素类型
{
int xydir
}elemtype
typedef struct 定义序栈
{
elemtype stack [maxlen]
int top
}sqstktp
struct moved
定义方位移数组元素类型存储坐标增量方位移数组move
{ int dxdy}

void inimaze(int maze[][N2])初始化迷宫
{
int ijnum
for(i0j0i maze[i][j]1
for(i0j0j maze[i][j]1
for(iM+1j0j maze[i][j]1
cout<<原始迷宫：< for(i1i {
for (j1j {
num(800*(i+j)+1500) 327根MN值产生迷宫
if ((num<150)&&(iM||jN))
maze[i][j]1
else
maze[i][j]0
cout< }
cout< }
cout< }inimaze

void inimove(struct moved move[])初始化方位移数组
{次EastSoutheastsouthsouthwestwestnorthwestnorthnortheast
move[0]dx0move[0]dy1
move[1]dx1move[1]dy1
move[2]dx1move[2]dy0
move[3]dx1move[3]dy1
move[4]dx0move[4]dy1
move[5]dx1move[5]dy1
move[6]dx1move[6]dy0
move[7]dx1move[7]dy1
}
void inistack(sqstktp *s) *初始化栈*
{
s>top1
} *inistack*
int push(sqstktp*selemtype x)
{
if(s>topmaxlen1)
return(false)
else
{
s>stack[++s>top]x*栈满执行入栈操作*
return(true)
}
}*push*
elemtype pop(sqstktp *s)*栈顶元素出栈*
{
elemtype elem
if(s>top<0) 果栈空返回空值
{
elemxNULL
elemyNULL
elemdirNULL
return(elem)
}
else
{
s>top
return(s>stack[s>top+1]) 栈空返回栈顶元素
}
} pop

void path(int maze[][N2]struct moved move[]sqstktp *s) 寻找迷宫中条通路
{
int ijdirxyf
elemtype elem
i1j1dir0
maze[1][1]1 设[1][1]入口处
do
{
xi+move[dir]dx球步行达点坐标
yj+move[dir]dy
if(maze[x][y]0)
{
elemxielemyjelemdirdir
fpush(selem)果行数入栈
if(ffalse)果返回假说明栈容量足
cout<<栈长足
ixjydir0maze[x][y]1
}
else
if (dir < 7)
dir++
else
{
elempop(s) 8方行回退
if(elemxNULL)
{
ielemx
jelemy
direlemdir+1
}
}
}while(((s>top1)&&(dir>7)||(xM)&&(yN)&&(maze[x][y]1))) 循环
if(s>top1)入口通路
cout<<迷宫通
else
{
elemxx elemyy elemdirdir出口坐标入栈
fpush(selem)
cout<<迷宫通路：< i0
while (i < s>top)
{
cout<<(<stack[i]x<<<stack[i]y<<)显示迷宫通路
if(is>top)
cout<<>
if((i+1)40)
cout< i++
}
}
}

void draw(int maze[][N2]sqstktp *s) 迷宫中绘制出通路
{
cout<<逃逸路线：< int ij
elemtype elem
for(i1i {
for(j1j {
if(maze[i][j]1)
maze[i][j]0
while(s>top>1) 根栈中元素坐标通路点值改8
{
elempop(s)
ielemxjelemy
maze[i][j]8
}
for(i1i {
for(j1j {
printf(3dmaze[i][j]) 显示已标记通路迷宫
}
cout< }
}
}
}
void main() 寻找迷宫通路程序
{
sqstktp *s
int maze[M2][N2]
struct moved move[8]
inimaze(maze) 初始化迷宫数组
s(sqstktp *)malloc(sizeof(sqstktp))
inistack(s) 初始化栈
inimove(move) 初始化方位移数组
path(mazemoves) 寻找迷宫通路
cout< draw(mazes) 绘制作出通路标记迷宫
}
5运行结果


（三）求通路短路径算法
1源代码（原题数）
#include
#define M 5 *行数*
#define N 7 *列数*
#define MaxSize 100 *栈元素数*
int mg[M+1][N+1]{ *迷宫四周加均1外框*
{11111111}
{10010001}
{11000111}
{10010001}
{10000001}
{11111111}
}
struct
{
int iint jint di
} Stack[MaxSize]Path[MaxSize] *定义栈存放短路径数组*
int top1 *栈指针*
int count1 *路径数计数*
int minlenMaxSize *短路径长度*
void mgpath() *路径(11)>(M2N2)*
{
int ijdifindk
top++ *进栈*
Stack[top]i1
Stack[top]j1
Stack[top]di1mg[1][1]1 *初始结点进栈*
while (top>1) *栈空时循环*
{
iStack[top]ijStack[top]jdiStack[top]di
if (iM2 && jN2) *找出口输出路径*
{
printf(4d count++)
for (k0k {
printf((dd) Stack[k]iStack[k]j)
if ((k+1)50) printf(＼n＼t) *输出时5结点换行*
}
printf(＼n)
if (top+1 {
for (k0k Path[k]Stack[k]
minlentop+1
}
mg[Stack[top]i][Stack[top]j]0 *该位置变路径走结点*
top
iStack[top]ijStack[top]jdiStack[top]di
}
find0
while (di<4 && find0) *找走结点*
{ di++
switch(di)
{
case 0iStack[top]i1jStack[top]jbreak
case 1iStack[top]ijStack[top]j+1break
case 2iStack[top]i+1jStack[top]jbreak
case 3iStack[top]ijStack[top]j1break
}
if (mg[i][j]0) find1
}
if (find1) *找走结点*
{ Stack[top]didi *修改原栈顶元素di值*
top++Stack[top]iiStack[top]jjStack[top]di1*走结点进栈*
mg[i][j]1 *避免重复走该结点*
}
else *没路径走退栈*
{
mg[Stack[top]i][Stack[top]j]0 *该位置变路径走结点*
top
}
}
printf(短路径＼n)
printf(长度 d＼nminlen)
printf(路径 )
for (k0k {
printf((dd) Path[k]iPath[k]j)
if ((k+1)50) printf(＼n＼t) *输出时5结点换行*
}
printf(＼n)
}
void main()
{
printf(迷宫路径＼n)
mgpath()
}
2求解结果

6实验收获思考
次试验总体说较简单思考问题基问题源代码进行改进补充第次数结构编程测试验次试验减少困难相说容易
附录
基问题换代码(思考问题源代码文中已全部出)

#define M 4
#define N 6
#define MaxSize 100
#include
int mg[M+2][N+2]
{
{11111111}
{10010001}
{11000111}
{10010001}
{10000001}
{11111111}
}
int mgpath(int xiint yiint xeint ye) 求解路径(xiyi)>(xeye)
{
struct
{
int i 前方块行号
int j 前方块列号
int di di走方位方位号
} st[MaxSize] 定义栈
int top1 初始化栈指针
int ijkdifind
top++ 初始方块进栈
st[top]ixist[top]jyi
st[top]di1mg[1][1]1
while (top>1) 栈空时循环
{
ist[top]ijst[top]jdist[top]di 取栈顶方块
if (ixe && jye) 找出口输出路径
{
printf(迷宫路径＼n)
for (k0k {
printf(＼t(dd)st[k]ist[k]j)
if ((k+1)50) 输出5方块换行
printf(＼n)
}
printf(＼n)
return(1) 找条路径返回1
}
find0
while (di<4 && find0) 找走方块
{
di++
switch(di)
{
case 0ist[top]i1jst[top]jbreak
case 1ist[top]ijst[top]j+1break
case 2ist[top]i+1jst[top]jbreak
case 3ist[top]ijst[top]j1break
}
if (mg[i][j]0) find1找走相邻方块
}
if (find1) 找走方块
{
st[top]didi 修改原栈顶元素di值
top++ 走方块进栈
st[top]iist[top]jjst[top]di1
mg[i][j]1 避免重复走该方块
}
else 没路径走退栈
{
mg[st[top]i][st[top]j]0该位置变路径走方块
top 该方块退栈
}
}
return(0) 表示没走路径返回0
}
void main()
{
mgpath(11MN)
}

文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档