栈的迷宫求解数据结构试验.docx
- 文档编号:5961918
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:17
- 大小:90.92KB
栈的迷宫求解数据结构试验.docx
《栈的迷宫求解数据结构试验.docx》由会员分享,可在线阅读,更多相关《栈的迷宫求解数据结构试验.docx(17页珍藏版)》请在冰点文库上搜索。
栈的迷宫求解数据结构试验
实验二:
迷宫问题
班级:
姓名:
学号:
一、需求分析
(1)以二维数据Maze[m+2][n+2]表示迷宫,其中:
Maze[0][j]和Maze[m+1][j]
(0<=j<=n+1)及Maze[i][0]和Maze[i][n+1](0<=i<=m+1)为添加一圈障碍。
数组中以元素值
为0表示通路,1表示障碍,限定迷宫的大小m,n<=100。
(2)用户输入迷宫的规模m,n;并按照此规模输入迷宫的具体数据。
(3)迷宫的入口位置和出口位置可由用户随时设定。
(4)若设定的迷宫存在通路,则以长方阵形式将迷宫及其通路输出到标准输出文件(即
终端)上,其中,字符“#”表示障碍,字符“*”表示路径上的位置,字符“@”表示“死
胡同”,即曾途径然而不能到达出口的位置,余者用空格符印出。
若设定的迷宫不存在通路,
则报告相应信息。
(5)本程序只求出一条成功的通路。
然而,只需要对迷宫求解的函数作小量修改,便
可求得全部路径。
(6)测试数据见原题,当入口位置为(1,1),出口位置为(9,8)时,输出数据应为:
*
*
#
@
@
@
#
*
#
@
@
@
#
*
*
@
@
#
#
#
*
#
#
#
#
@
*
*
*
#
*
*
*
@
#
*
*
*
#
*
#
#
#
#
#
*
#
#
#
#
*
#
#
#
*
*
(7)程序执行的命令为:
1)创建迷宫;2)求解迷宫;3)输出迷宫的解。
二、概要设计
1.设定栈的抽象数据类型定义:
ADTStack{
数据对象:
D={ai|ai∈CharSet,i=1,2,…,n,n>=0}
数据关系:
R1={
基本操作:
InitStack(&S)
操作结果:
构造一个空栈S。
DestroyStack(&S)
初始条件:
栈S已存在。
操作结果:
销毁栈S。
ClearStack(&S)
初始条件:
栈S已存在。
操作结果:
将S清为空栈。
StackLength(&S)
初始条件:
栈S已存在。
操作结果:
返回栈S的长度。
StackEmpty(&S)
初始条件:
栈S已存在。
操作结果:
若S为空栈,则返回TRUE,否则返回FALSE。
GetTop(S,&e)
初始条件:
栈S已存在。
操作结果:
若栈S不空,则以e返回栈顶元素。
Push(&S,e)
初始条件:
栈S已存在。
操作结果:
在栈S的栈顶插入新的栈顶元素e。
Pop(&S,&e)
初始条件:
栈S已存在。
操作结果:
删除S的栈顶元素,并以e返回其值。
StackTraverse(S,visit())
初始条件:
栈S已存在。
操作结果:
从栈底到栈顶依次对S中的每个元素调用函数visit()。
}ADTStack
2.设定迷宫的抽象数据类型为:
ADTmaze{
数据对象:
D={ai,j|ai,j∈{‘’、‘#’、‘@’、‘*’},0≤i≤m+1,0≤j≤n+1,m,n≤10}
数据关系:
R={ROW,COL}
ROW={
COL={
基本操作:
InitMaze(&M,a,row,col)
初始条件:
二维数组a[row+2][col+2]已存在,其中自第1行至第row+1
行、每行中自第1列至第col+1列的元素已有值,并且以值0
表示通路,以值1表示障碍。
操作结果:
构成迷宫的字符型数组,以字符’6’表示通路,以字符‘4’
‘1’表示障碍,并在迷宫四周加上一圈障碍。
MazePath(&M)
初始条件:
迷宫M已被赋值,链栈S已经存在。
操作结果:
若迷宫M中存在一条通路,则按如下规定改变迷宫M的状态:
以字符“6”表示路径上的位置,字符“4”表示“死胡同”;
否则迷宫的状态不变。
PrintMaze(M)
初始条件:
迷宫M已存在。
操作结果:
以字符形式输出迷宫。
}ADTmaze;
3.本程序包含三个模块
1)主程序模块:
voidmain()
{
初始化;
do{
接受命令;
处理命令;
}while(命令!
=“退出”);
}
2)栈模块——实现栈抽象数据类型
3)迷宫模块——实现迷宫抽象数据类型
各模块之间的调用关系如下:
4.求解迷宫中一条通路的伪码算法:
设定当前位置的初值为入口位置;
do{
若当前位置可通,
则{将当前位置插入栈顶;//纳入路径
若该位置是出口位置,则结束;//求得路径存放在栈中
否则切换当前位置的东邻方块为新的当前位置;
}
否则{
若栈不空且栈位置尚有其他方向未被探索,
则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块;
若栈不空但栈顶位置的四周均不可通,
则{删去栈顶位置;//后退一步,从路径中删去该通道块,
主程序模块
迷宫模块
栈模块
若栈不空,则重新测试新的栈顶位置,
直到找到一个可通的相邻块或出栈至栈空;
}
}
}while(栈不空);
{栈空说明没有路径存在}
三、详细设计
1.坐标位置类型
typedefstruct{
intr,c;//迷宫中行、列的范围
}PosType;
2.迷宫类型
typedefstruct{
inta,b;
chararr[M][N];//各位置取值‘6’,‘4’,‘1’或‘0’
}MazeType;
voidinitmaze(MazeType&maze,intm,intn)
//按照用户输入的m行和n列的二维数组(元素值为0或1)
//设置迷宫的初值,包括加上边缘一圈的值
boolmazepath(MazeType&maze,PosTypestart,PosTypeend,SNode*&S)
//求解迷宫maze中,从入口start到出口end的一条路径
//若存在,则返回TRUE;否则返回FALSE
voidprintmaze(mazetypemaze)
//将迷宫以字符型方阵的形式输出到标准输出文件上
3.栈类型
typedefstruct{
intstep;//当前位置在路径上的“序号”
PosTypeposition;//当前的坐标位置
intdir;//往下一坐标位置的方向
}ElemType;//栈的元素类型
structSNode{
ElemTypedata;
SNode*next;
};//结点类型,指针类型
栈的基本操作设置如下:
voidInitStack(Stack&S)
//初始化,设S为空栈(S.top=NULL)
并返回TRUE,否则返回FALSE
StatusPush(Stack&S,ElemTypee)
//若分配空间成功,则在S的栈顶插入新的栈顶元素e,并返回TRUE;
//否则栈不变,并返回FALSE
StatusPop(Stack&S,ElemType&e)
//若栈不空,则删除S的栈顶元素并以e带回其值,且返回TRUE
//否则返回FALSE
voidprint(SNode*S)//输出栈的内容
其中该程序的C++全部代码如下:
#include
usingnamespacestd;
#definen10
#definem10
//迷宫各设置函数
voidprint(charmaze[n][m]){
for(inti=0;i for(intj=0;j cout< } cout< } } voidadd_maze(charmaze[n][m]){ inta,b,c; for(a=1;a<=(n-2)*(m-2);a++){ cout<<"障碍位置为(1<=i<="< "; cin>>b>>c; if(b==0&&c==0){ cout<<"设置完成"< break; } if(b<=0||c<=0||b>=n||c>=m){ cout<<"输入错误"< break; } maze[b][c]=1; } } voidcreate_maze(charmaze[n][m]){ inti=0,j=0; //为迷宫加围墙 for(j=0;j maze[0][j]=1; maze[n-1][j]=1; } for(i=0;i maze[i][0]=1; maze[i][m-1]=1; } //设围墙内所有点为通路 for(i=1;i for(j=1;j maze[i][j]=0; } } print(maze);//输出造好的迷宫 add_maze(maze);//增加迷宫障碍 cout< print(maze);//再次输出此时造好的迷宫 } //迷宫栈应用 structNode{ inti,j; }; structStack{ Nodepos; Stack*next; }; voidInitStack(Stack*&S){ Stack*p; cout<<"开辟一个新栈"< p=newStack; p->next=NULL; S->next=p; cout<<"hascreated...."< } voidpush(Stack*&S,charmaze[n][m],inta,intb){//入栈及相关操作 Stack*p; p=newStack; p->pos.i=a; p->pos.j=b; p->next=S->next; S->next=p; maze[a][b]='Y'; } voidpop(Stack*&S,charmaze[n][m]){//出栈及相关操作 if(! S->next){ cout<<"thestackisempty! "< return; } else{ maze[S->next->pos.i][S->next->pos.j]='N'; S->next=S->next->next; } } voidWalking(Stack*&S,charmaze[n][m],inti,intj){ if(i==n-2&&j==m-2){ return;//表示已经到达终点 } if(maze[i][j+1]! =1&&maze[i][j+1]! ='Y'&&maze[i][j+1]! ='N'){//向东走,if判断包括下一个位置是否是墙 (1),是否是已经走过的路(Y)(N) j++; push(S,maze,i,j); Walking(S,maze,i,j);return; } if(maze[i+1][j]! =1&&maze[i+1][j]! ='Y'&&maze[i+1][j]! ='N'){//向南走 i++; push(S,maze,i,j); Walking(S,maze,i,j);return; } if(maze[i][j-1]! =1&&maze[i][j-1]! ='Y'&&maze[i][j-1]! ='N'){//向西走 j--; push(S,maze,i,j); Walking(S,maze,i,j);return; } if(maze[i-1][j]! =1&&maze[i-1][j]! ='Y'&&maze[i-1][j]! ='N'){//向北走 i--; push(S,maze,i,j); Walking(S,maze,i,j);return; } pop(S,maze);//四个方向都不通,说明该点无法到达终点,实行出栈 i=S->next->pos.i; j=S->next->pos.j; Walking(S,maze,i,j); } voidgames(Stack*&S,charmaze[n][m]){ inti=1,j=1; push(S,maze,i,j);//先把第一个起始点入栈 Walking(S,maze,i,j);//递归算法 if(! S->next) cout<<"该迷宫是死胡同"< else cout<<"该迷宫可走通"< print(maze);//输出标记通路的迷宫 } intmain(){ charmaze[n][m]; create_maze(maze); Stack*S; S=newStack; S->next=NULL; InitStack(S); games(S,maze); //为方便DevC++可以看到最后运行的结果,故设此输入 cout<<"请随便输入一个数以结束程序"; intsui; cin>>sui; return0; } 四、调试分析 1.本次作业比较简单,只有一个核心算法,即求迷宫的路径,所以总的调试比较顺利, 只在调试MazePath算法时,遇到两个问题: 其一是,起初输出的迷宫中没有加上‘4’的 记号,后发现是因为在MarkPrint函数中的迷宫参数丢失“变参”的原因;其二是,由于回 退时没有将curpos随之减一,致使栈中路径上的序号有错。 2.栈的元素中的step域没有太多用处,可以省略。 3.StackTraverse在调试过程中很有用,它可以插入在MazePath算法中多处,以察看解 迷宫过程中走的路径是否正确,但对最后的执行版本没有用。 4.本题中三个主要算法: InitMaze,MazePath和PrintMaze的时间复杂度均为0(a*b), 本题的空间复杂度亦为0(a*b)(栈所占最大空间) 5.经验体会: 借助DEBUG调试器和数据观察窗口,可以加快找到程序中疵点。 五、用户手册 1.本程序的运行环境为xp,w7操作系统,执行文件为: 迷宫问题.exe. 2.进入演示程序后,即现实文本方式的用户界面: 主程序 InitializationReadCommandInterpret InitMazeMazePathPrintMaze InitStackPushPopStackEmptyStackTraverse FootPrintMarkPrintPassNextPos 3.进入“产生迷宫(mazeinit)”的命令后,即提示键入迷宫规模,结束符 为“回车符”,即提示键入入口位置(行号和列号,中间用空格分开,结束符为“回车符”)和出口位置(行号和列号,中间用空格分开,结束符为“回车符”),之后提示输入迷宫内容,该命令执行之后输出“迷宫图形”。 4.进入“求迷宫路径(MazePath)”的命令后,该命令执行之后根据情况输出更改之后的迷宫图形。 接着,若迷宫中存在,输出走迷宫的路径,否则输出“无路可走”。 六、测试结果 2组测试数据和输出结果分别如下: 1. 2. *
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 迷宫 求解 数据结构 试验