数据结构-迷宫实验报告Word下载.doc
《数据结构-迷宫实验报告Word下载.doc》由会员分享，可在线阅读，更多相关《数据结构-迷宫实验报告Word下载.doc（19页珍藏版）》请在冰点文库上搜索。
m的迷宫，将迷宫的左上角作入口，右下角作出口，设“0”为通路，“1”为墙，即无法穿越。
假设从起点出发，目的为右下角终点，可向“上、下、左、右、左上、左下、右上、右下”8个方向行走。
如果迷宫可以走通，则用“■”代表“1”，用“□”代表“0”，用“→”代表行走迷宫的路径。
输出迷宫原型图、迷宫路线图以及迷宫行走路径。
如果迷宫为死迷宫，输出信息。
可以二维数组存储迷宫数据，用户指定入口下标和出口下标。
为处理方便起见，可在迷宫的四周加一圈障碍。
对于迷宫中任一位置，均可约定有东、南、西、北四个方向可通。
二、【实验设计（Design）】
（20%）
抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系）
1.设定迷宫的抽象数据类型定义：
ADTMaze{
数据对象：
D={ai,j|ai,j∈{‘■’、‘□’、‘※’、‘→’、‘←’、‘↑’、‘↓’},0≤i≤row+1,0≤j≤col+1,row,col≤18}
数据关系：
R={ROW,COL}
ROW={<
ai-1,j,ai,j>
|ai-1,j,ai,j∈D,i=1,…,row+1,j=0,…,col+1}
COL={<
ai,j-1,ai,j>
|ai,j-1,ai,j∈D,i=0,…,row+1,j=1,…,col+1}
基本操作：
Init_hand_Maze（Maze,row,col）
初始条件：
二维数组Maze[][]已存在。
操作结果：
手动初始化迷宫，0表示通路，1表示障碍。
Init_automatic_Maze（Maze,row,col）
初始条件：
自动初始化迷宫，0表示通路，1表示障碍。
PrintMaze（Maze）
迷宫Maze已存在。
将迷宫输出到屏幕，“□”表示通路，“■”表示障碍。
MazePath（Maze）
初始条件：
计算路径。
PrintPath（Maze）
若迷宫存在一条通路，将路径输出至屏幕，以“→”“←”“↑”“↓”表示可行路径，“※”表示途径过却无法到达出口的位置；
若不存在通路，报告相应信息。
}ADTMaze；
2.设定栈的抽象数据类型定义：
ADTStack{
数据对象：
D={ai|ai∈CharSet,i=1,2,…,n,n≥0}
R1={<
ai-1,ai>
|ai-1,ai∈D,i=2,…,n}
基本操作：
InitStack（&
S）
操作结果：
构造一个空栈。
Push（&
S,e）
初始条件：
栈S已存在。
在栈S的栈顶插入新的栈顶元素e。
Pop（&
S,&
e）
栈S已存在.
删除S的栈顶元素，并以e返回其值。
}ADTStack；
3.本程序包含三个模块
1）主程序模块：
voidmain（）
{
初始化;
do{
接受命令;
处理命令;
}while（命令!
=退出）;
}
2）栈模块——实现栈抽象数据类型；
3）迷宫模块——实现迷宫抽象数据类型。
4各模块之间的调用关系如下：
主程序模块
迷宫模块
栈模块
三、【实现描述（Implement）】
（30%）
抽象数据类型具体实现的函数原型说明、关键操作实现的伪码算法、函数设计、函数间的调用关系，关键的程序流程图等，给出关键算法的时间复杂度分析。
）
1.迷宫与栈类型
intmaze[M][N],row,col;
typedefstruct//存放迷宫访问到点的行，列，方向
intm,n,direc;
}MazeType,*LMazeType;
typedefstruct
LMazeTypetop;
//路径第一个元素的位置
LMazeTypebase;
//路径最后一个元素的位置
intstacksize;
//栈大小
intover;
//溢出
}Stack;
2.栈操作函数
voidInit_hand_Maze（intmaze[M][N],intm,intn）
inti,j;
for（i=1;
i<
=m+1;
i++）
for（j=1;
j<
=n+1;
j++）
{
maze[i][j]=1;
}
cout<
<
"
请按行输入迷宫，0表示通路，1表示障碍:
endl;
m+1;
n+1;
cin>
>
maze[i][j];
{
for（j=1;
j++）
{
if（maze[i][j]!
=0&
&
maze[i][j]!
=1）{
cout<
您输入有误，请重新输入"
;
Init_hand_Maze（maze,m,n）;
}
}
}
}
时间复杂度为O（m*n）
voidInit_automatic_Maze（intmaze[M][N],intm,intn）//自动生成迷宫
inti,j;
cout<
\n迷宫生成中……\n\n"
system（"
pause"
）;
for（i=1;
maze[i][j]=rand（）%2;
//随机生成0、1
StatusPush（Stack&
S,MazeTypee）//将路径上的点依次压栈
if（S.top-S.base>
=S.stacksize）
{
S.base=（LMazeType）realloc（S.base,（S.stacksize+STACKINCREMENT）*sizeof（MazeType））;
if（!
S.base）exit（OVERFLOW）;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
returnOK;
StatusPop（Stack&
S,MazeType&
e）//将能走通的路径的点依次出栈
if（S.top==S.base）returnERROR;
e=*--S.top;
3.求解迷宫
StatusMazePath（Stack&
e,intmaze[M][N],intm,intn）
do
if（maze[e.m][e.n]==0）//0可通，1不可通，2为已走过
{
Push（S,e）;
maze[e.m][e.n]=2;
if（e.m==m&
e.n==n）
{
S.over=1;
//表示存满一条路径
returnOK;
}
else{
e.n++;
e.direc=0;
//来这一点时的方向，0右1下2左3上
MazePath（S,e,maze,m,n）;
}
}
else
if（S.top!
=S.base&
S.over!
=1）
switch（e.direc）//回到上一位置并同时改变方向走下一步
{
case0:
//退回后，列坐标减一，行坐标加一，下一方向向下
e.n--;
e.m++;
e.direc=1;
break;
case1:
//退回后，行坐标减一，列坐标减一，下一方向向左
e.m--;
e.direc=2;
case2:
//退回后，列坐标加一，行坐标减一，下一方向向上
e.n++;
e.direc=3;
case3:
//无需退回，路径，出栈
Pop（S,e）;
}
}while（S.top!
=1）;
}
4.打印路径
intPrintPath（StackS,intmaze[M][N],introw,intcol）
if（S.top==S.base）
cout<
\n===============================================\n"
此迷宫无解\n\n"
returnERROR;
}
MazeTypee;
while（S.top!
=S.base）
Pop（S,e）;
maze[e.m][e.n]=（e.direc+10）;
路径为:
row+1;
for（j=1;
col+1;
switch（maze[i][j]）
case0:
cout<
□"
break;
case1:
■"
case2:
※"
case10:
→"
case11:
↓"
case12:
←"
case13:
↑"
cout<
完成!
5.主函数
intmain（）
switch（i）
case1:
Init_hand_Maze（maze,m,n）;
PrintMaze（maze,m,n）;
InitStack（S）;
MazePath（S,start,maze,end.m,end.n）;
PrintPath（S,maze,m,n）;
break;
case2:
Init_automatic_Maze（maze,m,n）;
InitStack（S）;
case3:
cycle=（-1）;
break;
default:
cout<
\n"
cout<
你的输入有误!
}
}
四、【测试结果（Testing）】
对实验的测试结果，应具体列出每次测试所输入的数据以及输出的数据，并对测试结果进行分析总结）
手动生成迷宫寻找路径结果正确。
自动声称迷宫寻找路径结果正确。
四、【实验总结】
自己在实验中完成的任务，注意组内的任意一位同学都必须独立完成至少一项接口的实现；
对所完成实验的经验总结、心得）
1.本次实验核心算法明晰，思路明确，易于实现。
遇到的问题是，迷宫的外围若未设置障碍，用此程序采用的求解迷宫路径的算法无法获得正确结果。
2.本程序的MazePath算法代码不够简洁，但不影响算法实现。
3.本次实验由于时间问题和知识水平有限，还存在一些问题，比如：
界面比较单调，整个程序的功能还不完善，还有界面做的有些简单，菜单没有做好，可进行的操作太少，这些都有待进一步改善。
4．本次实验使我对迷宫游戏的原理有了一定的了解，但做出的结果离真正的迷宫还有很大差距，还需要进一步完善，需要自己课下学习更多的知识。
五、【项目运作描述（Operate）】
项目的成本效益分析，应用效果等的分析。
本程序可基本实现题目的要求，但仍不够完善。
比如对于有多种路径的迷宫只能显示一条路径，当输入的路径超过范围时只能取前几个范围内的数据，而无法将这一消息告诉用户，这些问题还有待解决。
六、【代码】
完整的代码及充分的注释。
注意纸质的实验报告无需包括此部分。
格式统一为，字体:
Georgia,行距:
固定行距12，字号:
小五）
#include<
stdlib.h>
//库中包含system（"
）和rand（）函数
stdio.h>
//c语言里的库
iostream>
#include<
malloc.h>
#defineOK1
#defineERROR0
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
#defineOVERFLOW-1
#defineM49
#defineN49
usingnamespacestd;
intmaze[M][N];
typedefintStatus;
intm,n,direc;
voidPrintMaze（intmaze[M][N],introw,intcol）
迷宫如图所示."
if（maze[i][j]==1）
cout<
else
StatusInitStack（Stack&
S.base=（LMazeType）malloc（STACK_INIT_SIZE*sizeof（MazeType））;
if（!
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
升级会员 