C语言数据结构之迷宫求解问题
现在网上各种对于迷宫的求解，版本多的数不胜数。本人小白一枚，贴上自己对迷宫的求解这个小项目，自己写的。望能帮助一些同样有困难的人，毕竟我当时费解了好一会儿时间呢。
首先，先标明对于迷宫求解这个项目，首先我提出自己的思路，利用“穷举求解”的方法（严蔚敏老师数据结构一书中提到，一开始不知方法其名。）其实简单来说就是一条路一条路去试，当然不能随便试，我的方法是按照从入口出发，顺一个方向向前探索，走得通就继续向前走；否则留下标记沿原路退回并换一个方向继续探索，直到所有的路都走完为止。还是用栈的先进后出的结构保存一路的路线。代码用到了栈的顺序实现数组格式的结构（对于栈并没有详细阐述）。
//调用头文件 #ifndefAFXSTD_H #defineAFXSTD_H #include#include #include #include usingnamespacestd; //cout;cin;C++的输入输出 #endif
//迷宫的结构体的创建
#ifndefMAZE_H
#defineMAZE_H
#defineROWSIZE10//迷宫大小
#defineCOLSIZE10
#defineReachable0//可以到达的结点
#defineBar1//障碍物
#defineFoot2//足迹
#defineMark3//不可通路标记
typedefintMapType[ROWSIZE][COLSIZE];//地图类型
typedefstruct
{
introw;//x
intcol;//y;
}PosType;//坐标结构体
typedefstruct
{
intord;//通道块在道路上的序号
PosTypeseat;//小人坐标
intdi;//方向//1234
}MElemType;//试迷宫小人的结构
typedefMElemTypeSElemType;//和stack关联
boolMazePass(MapTypemaze,PosTypecurpos);
voidFootPrint(MapTypemaze,PosTypecurpos);//足迹打印
PosTypeNextPos(PosTypecurpos,intdi);//下一个位置
voidMarkPrint(MapTypemaze,PosTypecurpos);//打印不可通标记
boolMazePath(MapTypemaze,PosTypestart,PosTypeend);//迷宫解谜核心
voidPrintMap(MapTypemaze);//打印地图
#endif
//栈的结构体
#include"Maze.h"
#ifndefSEQSTACK_H
#defineSEQSTACK_H
#defineSTACKSIZE100
//typedefintSElemType;
structSeqStack
{
SElemType*data;
intmaxsize;
inttop;
};
voidInit_Stack(SeqStack&st);
voidDestroy_Stack(SeqStack&st);
voidStack_Clear(SeqStack&st);
boolStack_Empty(SeqStack&st);
boolStack_Full(SeqStack&st);
intStack_Size(SeqStack&st);
boolStack_Push(SeqStack&st,constSElemType&x);
boolStack_Pop(SeqStack&st,SElemType&x);
SElemTypeGetTop(SeqStack&st);
voidPop(SeqStack&st);
#endif
以上是头文件的创建，和结构体的创建，现在真的深切感到结构体的重要性。结构体创建不好就是自己给自己挖坑，切记切记！！
现在贴出函数的代码，解释我会尽力都写清楚。（栈的问题我后续会重新再仔细阐述的，这次的重点在于迷宫的求解，所以直接贴出栈的详细代码，望谅解。）
//这里是栈的实现代码
#include"AfxStd.h"
#include"Stack.h"
boolStack_Resize(SeqStack&st)
{
SElemType*s=(SElemType*)malloc(sizeof(SElemType)*st.maxsize*2);
if(NULL==s)returnfalse;
for(inti=0;i<=st.top;++i)
{
s[i]=st.data[i];
}
free(st.data);
st.data=s;
st.maxsize=st.maxsize*2;
returntrue;
}
voidInit_Stack(SeqStack&st)
{
st.maxsize=STACKSIZE;
st.top=-1;
st.data=(SElemType*)malloc(sizeof(SElemType)*st.maxsize);
if(NULL==st.data)
{
exit(0);
}
}
voidDestroy_Stack(SeqStack&st)
{
free(st.data);
st.data=NULL;
st.maxsize=0;
st.top=-1;
}
voidStack_Clear(SeqStack&st)
{
st.top=-1;
}
boolStack_Empty(SeqStack&st)
{
returnStack_Size(st)==0;
}
boolStack_Full(SeqStack&st)
{
returnStack_Size(st)==st.maxsize;
}
intStack_Size(SeqStack&st)
{
returnst.top+1;
}
boolStack_Push(SeqStack&st,constSElemType&x)
{
if(Stack_Full(st)&&!Stack_Resize(st))
{
returnfalse;
}
st.data[++st.top]=x;
returntrue;
}
boolStack_Pop(SeqStack&st,SElemType&x)
{
if(Stack_Empty(st))
{
returnfalse;
}
x=st.data[st.top--];
returntrue;
}
//调用前面创建的头文件
#include"AfxStd.h"
#include"Maze.h"
#include"Stack.h"
/////////////////////////////////////////////////
boolMazePass(MapTypemaze,PosTypecurpos)//判断是否可以通过
{
returnmaze[curpos.row][curpos.col]==Reachable;//判断当前结点是否能通过
}
voidFootPrint(MapTypemaze,PosTypecurpos)//打印足迹
{
maze[curpos.row][curpos.col]=Foot;
}
PosTypeNextPos(PosTypecurpos,intdi)//对下一个结点方向的判断
{
switch(di)
{
case1:curpos.row+=1;break;//1
case2:curpos.col-=1;break;//2
case3:curpos.row-=1;break;//3
case4:curpos.col+=1;break;//4
}
returncurpos;
}
voidMarkPrint(MapTypemaze,PosTypecurpos)//不能通过的结点留下不能通过的标记
{
maze[curpos.row][curpos.col]=Mark;
}
boolMazePath(MapTypemaze,PosTypestart,PosTypeend)//（核心）迷宫解谜
{
boolres=false;//定义一个res参数为布尔型
PosTypecurpos=start;//初始当前位置为入口
intcurstep=1;//初始探索方向为1
SeqStackst;//路径存储栈
MElemTypee;//初始探索小人
Init_Stack(st);//初始化栈
do{
if(MazePass(maze,curpos))//当前位置可通过，即是未曾走到过的坐标
{
FootPrint(maze,curpos);//留下足迹
e.di=1,e.seat=curpos,e.ord=curstep++;
Stack_Push(st,e);//加入路径中
if(curpos.row==end.row&&curpos.col==end.col)
{
res=true;
break;
}//到达终点
curpos=NextPos(curpos,1);//探索下一位置
}
else
{
if(!Stack_Empty(st))//当前位置不能通过
{
Stack_Pop(st,e);
while(e.di==4&&!Stack_Empty(st))
{
MarkPrint(maze,e.seat);
Stack_Pop(st,e);//留下不能通过的标记，并退回一步
}
if(e.di<4)
{
e.di+=1;//换下一个方向探索
Stack_Push(st,e);//再次记录路径
curpos=NextPos(e.seat,e.di);//当前位置设为新方向的相邻块
}
}
}
}while(!Stack_Empty(st));//当栈空摧毁栈，返回失败参数
Destroy_Stack(st);
returnres;
}
voidPrintMap(MapTypemaze)//打印地图
{
for(inti=0;i
以上就是迷宫的详细解释，希望能帮助到大家。后面再添加我的测试文件。
#include"AfxStd.h"
#include"Maze.h"
intmain()
{
MapTypemaze={//一开始地图的创建
{1,1,1,1,1,1,1,1,1,1},
{1,0,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,0,0,1},
{1,0,0,0,1,1,1,1,0,1},
{1,0,0,0,1,1,1,1,0,1},
{1,0,1,1,1,1,0,0,0,1},
{1,0,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,1,1,1},
{1,0,1,1,1,1,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1},
};
PosTypestart={1,1},end={8,8};
PrintMap(maze);//打印初始地图
MazePath(maze,start,end);
PrintMap(maze);//打印迷宫解法
return0;
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。