迷宫问题.docx
《迷宫问题.docx》由会员分享，可在线阅读，更多相关《迷宫问题.docx（14页珍藏版）》请在冰点文库上搜索。
迷宫问题
《数据结构的课程设计》
报告
题目：
迷宫问题设计与实现
班级：
1612401
学号：
161240113
姓名：
张修鸣
指导老师：
孙涵
完成日期：
2014.1.3
目录
一.需求分析.
二.程序主要功能.
三.程序运行平台.
四.程序类说明.
五.程序运行分析
六.存在的不足与对策.
七．体验感悟
八.程序源代码.
需求分析
利用栈操作实现迷宫问题求解。
程序主要功能
（1）随机生成模拟迷宫地图，不少于10行10列，存在文件中。
（2）动态显示每一步的结果。
（3）可在此基础上有改进方法。
程序运行平台
该程序是用VC++6.0制做的，使用MicrosoftVisualC++6.0运行该程序，具体操作是：
打开MicrosoftVisualC++6.0，菜单栏里点文件→打开工作区→找到“图书管理系统.dsw”这个文件→打开，或者在资源管理器中双击该文件，此时，VC++6.0会自动打开，并载入该系统相关资源，点击Run命令菜单或者或用快捷键Ctrl+F5运行该程序。
trl计分析能_________________________________________________________________________________________________________________________
程序类说明
栈类
typedefstruct
{
introw;
intline;
}PosType;
typedefstruct
{
intord;
PosTypeseat;
intdi;
}SelemType;
typedefstruct
{
SelemType*base;
SelemType*top;
intstacksize;
}SqStack;
函数分析：
StatusInitStack（SqStack&S）栈的建立
StatusPush（SqStack&S,SelemTypee）入栈
StatusPop（SqStack&S,SelemTypee）出栈
voidInitMaze（intmaze[11][11]）随机建立迷宫
voidOutputmazeFirst（intmaze[11][11]）显示迷宫
StatusMazePath（intmaze[11][11],SqStack&S,PosTypestart,PosTypeend）寻找出口
voidMarkFoot（intmaze[11][11],PosTypeCurPos）标记路径
程序运行分析
存在的不足与对策
由于自身能力有限，所以没有动态显示每一步的结果。
在设计过程中由于设计者的编程功底欠缺，因此学习过程较为艰辛，需要解决的问题也比较多。
在以后的学习中，应该循序渐进，不可急于求成，先打好基础，这样才能更好地发展。
体验感悟
在编写程序的过程中，深切的体会到自身能力还有待提高，通过大规模的查询网上资料与相关书籍我学习到了很多以前不知道的编程方法与各种奇妙的函数语句时，提高了自己对程序设计本身的兴趣，更加乐意去学习这方面的新的东西，并在不断地自我挑战中收获着，或知识技能，或信心勇气。
希望自己在今后的学习中可以更好的完善自我。
程序源代码
#include
#include
#include
#include
typedefintStatus;
#defineOK1
#defineERROR0
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT5
typedefstruct
{
introw;
intline;
}PosType;
typedefstruct
{
intord;
PosTypeseat;
intdi;
}SelemType;
typedefstruct
{
SelemType*base;
SelemType*top;
intstacksize;
}SqStack;
StatusInitStack（SqStack&S）
{
S.base=（SelemType*）malloc（STACK_INIT_SIZE*sizeof（SelemType））;
if（!
S.base）
exit（-2）;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
returnOK;
}
StatusPush（SqStack&S,SelemTypee）
{
if（S.top-S.base>=S.stacksize）
{
S.base=（SelemType*）realloc（S.base,
（S.stacksize+STACKINCREMENT）*sizeof（SelemType））;
if（!
S.base）
exit（-2）;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
returnOK;
}
StatusPop（SqStack&S,SelemType&e）
{
if（S.top==S.base）
return0;
e=*--S.top;
returnOK;
}
StatusStackEmpty（SqStackS）
{
if（S.top==S.base）
returnOK;
else
returnERROR;
}
voidInitMaze（intmaze[11][11]）
{
srand（（int）time（NULL））;
for（inti=0;i<10;i++）
maze[0][i]=0;
for（i=1;i<9;i++）
{
maze[i][0]=1;
for（intj=1;j<9;j++）
{
maze[i][j]=rand（）%2;
}
maze[i][9]=1;
}
for（i=0;i<10;i++）
maze[9][i]=1;
}
voidOutputmazeFirst（intmaze[11][11]）
{
printf（"\n\n"）;
printf（"所建迷宫为（#为外墙）：
\n\n"）;
for（inti=0;i<10;i++）
printf（"#"）;
printf（"\n"）;
for（i=1;i<9;i++）
{
printf（"#"）;
for（intj=1;j<9;j++）
printf（"%d",maze[i][j]）;
printf（"#"）;
printf（"\n"）;
}
for（i=0;i<10;i++）
printf（"#"）;
printf（"\n"）;
}
voidOutputmazeEnd（intmaze[11][11],SqStackS）
{
printf（"\n迷宫通路路径为：
\n\n"）;
SelemType*p=S.base;
while（p!
=S.top）
{
maze[p->seat.row][p->seat.line]=2;
p++;
}
for（inti=0;i<10;i++）
printf（"#"）;
printf（"\n"）;
for（i=1;i<9;i++）
{
printf（"#"）;
for（intj=1;j<9;j++）
{
if（maze[i][j]==2）
printf（"*"）;
else
printf（""）;
}
printf（"#"）;
printf（"\n"）;
}
for（i=0;i<10;i++）
printf（"#"）;
printf（"\n"）;
}
StatusPass（intmaze[11][11],PosTypeCurPos）
{
if（maze[CurPos.row][CurPos.line]==0）
returnOK;
else
returnERROR;
}
voidMarkFoot（intmaze[11][11],PosTypeCurPos）
{
maze[CurPos.row][CurPos.line]=1;
}
PosTypeNextPos（PosTypeCurPos,intDir）
{
PosTypeReturnPos;
switch（Dir）
{
case1:
ReturnPos.row=CurPos.row;
ReturnPos.line=CurPos.line+1;
break;
case2:
ReturnPos.row=CurPos.row+1;
ReturnPos.line=CurPos.line;
break;
case3:
ReturnPos.row=CurPos.row;
ReturnPos.line=CurPos.line-1;
break;
case4:
ReturnPos.row=CurPos.row-1;
ReturnPos.line=CurPos.line;
break;
}
returnReturnPos;
}
StatusMazePath（intmaze[11][11],SqStack&S,PosTypestart,PosTypeend）
{
//若迷宫maze中从入口start到出口end的通道，则求得一条存放在栈中
//（从栈底到栈顶），并返回TRUE；否则返回FALSE
PosTypecurpos;
intcurstep;
SelemTypee;
InitStack（S）;
curpos=start;//设定"当前位置"为"入口位置"
curstep=1;//探索第一步
do
{
if（Pass（maze,curpos））
{//当前位置可通过，即是未曾走到过的通道块
MarkFoot（maze,curpos）;//留下足迹
e.di=1;
e.ord=curstep;
e.seat=curpos;
Push（S,e）;//加入路径
if（curpos.row==end.row&&curpos.line==end.line）
returnOK;//到达终点（出口）
curpos=NextPos（curpos,1）;//下一位置是当前位置的东邻
curstep++;//探索下一步
}
else
{//当前位置不能通过
if（!
StackEmpty（S））
{
Pop（S,e）;
while（e.di==4&&!
StackEmpty（S））
{
MarkFoot（maze,e.seat）;
Pop（S,e）;//留下不能通过的标记，并退回一步
}//while
if（e.di<4）
{
e.di++;
Push（S,e）;//换下一个方向探索
curpos=NextPos（e.seat,e.di）;//当前位置设为新方向的相邻块
}
}
}
}while（!
StackEmpty（S））;
return0;
}
intmain（）
{
SqStackS;
intmaze[11][11];
printf（"创建一个正方形迷宫，大小为10X10：
\n"）;
InitMaze（maze）;
OutputmazeFirst（maze）;
PosTypestart,end;
printf（"\n请输入入口坐标（行，列）：
"）;
scanf（"%d",&start.row）;
scanf（"%d",&start.line）;
printf（"\n请输入出口坐标（行，列）：
"）;
scanf（"%d",&end.row）;
scanf（"%d",&end.line）;
if（MazePath（maze,S,start,end））
{
OutputmazeEnd（maze,S）;
printf（"\n通路如上图所示！
\n"）;
}
else
printf（"\n无通路！
\n"）;
return0;
}
升级会员 