迷宫问题实验报告用栈解决迷宫问题.pdf

迷宫问题实验报告用栈解决

迷宫问题

本页仅作为文档页封面，使用时可以删除

Thisdocumentisforreferenceonly-rar21year.March

数据结构实验报告

题目：用栈解决迷宫问题

一．需求分析

1．以结构体Maze表示迷宫，其中pos表示该位置是否有障碍；freq

记录该位置被经过的次数；数组move表示下一步的方向。

2．本程序自动随机生成一个12×12大小的迷宫，字符“H”表示有

障碍，空符表示通路。

3．迷宫的入口为左上角，出口为右下角。

4．本程序只求出一条成功的通路。

二．概要设计

为了实现上述操作，以栈为存储结构。

本程序包含三个模块：

（1）主程序模块:实现人机交互。

（2）迷宫生产模块：随机产生一个12×12的迷宫。

（3）路径查找模块：实现通路的查找。

（4）求解迷宫中一条通路的伪代码：

do{

若当前位置可同，

则{

将当前位置插入栈顶；

若该位置是出口位置，则结束；

否则切换当前位置的东临方块为新的当前位置；

}

否则{

若栈不空且栈顶位置尚有其他方向未被探索，

2

则设定新的的当前位置为沿顺时针方向旋转找到的栈顶位置的下

一相邻块

若栈不空但栈顶位置的四周均不可通，

则{

删去栈顶位置；

若栈不空，则重新测试新的栈顶位置，直至找到一个可通的

相邻块或出栈至栈空。

}

}

}while(栈不空)

三．详细设计

栈的设计：

typedefstruct

{

Node*base,*top;

intlength;

}Stack;

Stack*initstack();主程序模块：

intmain()

{

随机产生一个12×12的迷宫，X字符表示障碍，空符表示通

路：路：

Mazea[N][N];

makemaze(a);

输入回车键显示路径,*字符表示路径。字符表示路径。

getchar();

findpath(a);

3

while(1);

return0;

}

2.迷宫生产模块；

voidmakemaze(Maze(*p)[N])

{

inti,j,conter;

for(i=0;iN;++i)

for(j=0;jN;++j)

{

(*(p+i)+j)-pos=0;

(*(p+i)+j)-freq=0;

(*(p+i)+j)-move[0]=0;

(*(p+i)+j)-move[1]=0;