数据结构迷宫实验报告及代码Word格式文档下载.docx
《数据结构迷宫实验报告及代码Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《数据结构迷宫实验报告及代码Word格式文档下载.docx（16页珍藏版）》请在冰点文库上搜索。
R={r,c}
r={<
ai-1,ai>
|ai-1,ai∈D,i=1,2,…,n,}
c=<
结构体定义：
typedefstruct//迷宫中x行y列的位置
{intx;
inty;
}PosType;
typedefstruct//栈类型
{intord;
//通道块在路径上的“序号”
PosTypeseat;
//通道块在迷宫中的“坐标位置”
intdi;
//从此通道块走向下一通道块的“方向”
}MazeType;
typedefstruct
{MazeType*base;
MazeType*top;
intstacksize;
}MazeStack;
基本函数：
StatusInitStack（MazeStack&
S）//新建一个栈
StatusPush（MazeStack&
S,MazeType&
e）//入栈
StatusPop（MazeStack&
e）//出栈
StatusStackEmpty（MazeStack&
S）//判断是否为空
StatusMazePath（PosTypestart,PosTypeend）//迷宫路径求解
voidFootPrint（PosTypepos）
PosTypeNextPos（PosTypecurPos,int&
i）
voidMakePrint（PosTypepos）
三．程序设计
根据算法设计中给出的有关数据和算法，选定物理结构，详细设计需求分析中所要求的程序。
包括：
人机界面设计、主要功能的函数设计、函数之间调用关系描述等。
1界面设计
1）迷宫界面
2）迷宫路径显示
2主要功能
1）入栈操作
e）//入栈操作
{
if（S.top-S.base>
=S.stacksize）
{
S.base=（MazeType*）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;
2）出栈操作
if（S.top==S.base）
returnERROR;
e=*--S.top;
3）判断栈是否为空
if（S.base==S.top）
returnOK;
returnERROR;
4）迷宫路径求解
PosTypecurpos;
MazeStackS;
MazeTypee;
intcurstep;
InitStack（S）;
curpos=start;
//设定当前位置为入口位置
curstep=1;
//探索第一步
cout<
<
"
起点:
（"
<
start.y<
"
start.x<
）"
endl;
do
if（Pass（curpos））//当前位置可以通过，即是未曾走到的通道块
{
FootPrint（curpos）;
//留下足迹
e.ord=curstep;
e.seat=curpos;
e.di=1;
Push（S,e）;
//加入路径
if（curpos.x==end.x&
&
curpos.y==end.y）
{
cout<
\n终点（"
e.seat.y<
e.seat.x<
;
returnTRUE;
//到达终点（出口）
}
curpos=NextPos（curpos,e.di）;
//下一位置是当前位置的东邻
++curstep;
//探索下一步
}
else//当前位置不能通过
if（!
StackEmpty（S））
Pop（S,e）;
while（e.di==4&
!
{
MakePrint（e.seat）;
//留下不能通过的标记
Pop（S,e）;
cout<
倒退到（"
}
if（e.di<
4）
++e.di;
//换下一个方向探索
Push（S,e）;
curpos=NextPos（e.seat,e.di）;
//设定当前位置是该新方向上的相邻块
}while（!
StackEmpty（S））;
returnFALSE;
5）探索下一个位置
switch（i）//顺时针方向
case1:
++curPos.x;
//东
if（mazeMap[curPos.y][curPos.x]!
=2）
break;
--curPos.x;
case2:
i=2;
++curPos.y;
//南
--curPos.y;
case3:
i=3;
//西
case4:
i=4;
//北
if（mazeMap[curPos.y][curPos.x]==2）
++curPos.y;
mazeMap[curPos.y][curPos.x]=0;
break;
returncurPos;
6）标记走过的路径
mazeMap[pos.y][pos.x]=2;
//将走过的路径设为2
7）标记作废路径
\n（"
pos.y<
pos.x<
）走不通，作废"
mazeMap[pos.y][pos.x]=0;
//将走不通的块替换为墙壁
3函数调用
intmain（）
PosTypemazeStart,mazeEnd;
mazeStart.x=1;
//开始与结束点
mazeStart.y=1;
mazeEnd.x=8;
mazeEnd.y=8;
迷宫:
for（inti=0;
i<
10;
++i）
for（intj=0;
j<
++j）
cout<
mazeMap[i][j];
cout<
endl<
if（MazePath（mazeStart,mazeEnd））
\n走通迷宫"
else
\n走不通迷宫"
system（"
PAUSE"
）;
return0;
四．测试与分析
1、在编程序时迷宫的出入栈掌握的还好，可是编到迷宫方向的选择，与迷宫路径错误的情况时，不知道怎么处理，然后自己通过看书和网上查阅资料基本解决了问题。
2、在写代码的过程中，没有弄清使用指针与引用之后，结构体如何使用。
当使用指针的时候要使用‘.’，当使用引用或数的时候，要使用‘->
’。
源程序：
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
#defineOVERFLOW-2
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
typedefintStatus;
typedefstruct//迷宫中x行y列的位置
intx;
inty;
typedefstruct//栈类型
intord;
intdi;
//从此通道块走向下一通道块的“方向”,//1:
东2:
北3:
西（顺时针）
MazeType*base;
MazeType*top;
intstacksize;
#include<
iostream>
usingnamespacestd;
S）;
e）;
StatusMazePath（PosTypestart,PosTypeend）;
StatusPass（PosType&
pos）;
voidFootPrint（PosTypepos）;
i）;
voidMakePrint（PosTypepos）;
//迷宫地图，0表示墙壁，1表示通路,入口:
mazeMap[1][1],出口mazeMap[8][8]
intmazeMap[10][10]=
{//0,1,2,3,4,5,6,7,8,9
{0,0,0,0,0,0,0,0,0,0},//0
{0,1,1,0,1,1,1,0,1,0},//1
{0,1,1,0,1,1,1,0,1,0},//2
{0,1,1,1,1,0,0,1,1,0},//3
{0,1,0,0,0,1,1,1,1,0},//4
{0,1,1,1,0,1,1,1,1,0},//5
{0,1,0,1,1,1,0,1,1,0},//6
{0,1,0,0,0,1,0,0,1,0},//7
{0,0,1,1,1,1,1,1,1,0},//8
{0,0,0,0,0,0,0,0,0,0}//9
};
intmain（）
S.base=（MazeType*）malloc（STACK_INIT_SIZE*sizeof（MazeType））;
if（!
exit（OVERFLOW）;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
pos）
if（mazeMap[pos.y][pos.x]==0）
returnFALSE;
->
returnTRUE;
升级会员 