迷宫问题——栈实现（C语⾔）（数据结构与算法）
c语言二维数组表示方法前⾔
本⽂⽤栈解决迷宫问题，采⽤C语⾔实现，包括问题介绍、算法简介、求解过程、代码实现、结果展⽰。并附有完整代码。
⼀、迷宫问题
概括来说，迷宫问题就是在⼀个封闭空间⾥，事先不知道这个封闭空间的内部结构，经过个⽅向试探，从⽽到⼀个出⼝。假设有个机器⼈放置在这个封闭空间的⼊⼝处：
迷宫⽤⼀个⼆维数组表⽰，0表⽰可以通⾏，1表⽰不可以通⾏
构成迷宫为类似⼆维数组
（可以看到这个数组周围全是1，这⾥1表⽰不同，相当于迷宫的四周，这样可以保证机器⼈不会在搜寻过程中不会离开迷宫，当给定的迷宫没有边界时，建议⾃⼰添加上）
在任意给定时刻，机器⼈只能在上下左右四个⽅向上移动1步
机器⼈只能移动到没有障碍物的位置即0的位置，且不可以离开迷宫
机器⼈不可以重复⾛某点
机器⼈应该搜索从起始位置到⽬标位置的路径，直到到⼀个或者耗尽他所有可能性
⼆、问题分析
1.位置表⽰
由于迷宫构成是⼀个⼆维数组，我们可以采⽤坐标的形式
(x,y)
来表⽰机器⼈的位置，为了⽅便代码实现，我将⼊⼝出的位置规定为（1，1）标蓝的位置为（1，1）如下图所⽰：
2.⽅向探寻
规定机器⼈探寻的⽅向为四个
dierct incX incY
001
110
20-1
3-10
我们⽤incX、incY分别表⽰x、y⽅向上的增量表⽰如果机器⼈往这个⽅向上移动其位置坐标将会发⽣如上的变化。可以看到上⾯这个⽅向是遵循右下左上的原则，我们就可以定义⼀个结构体数组分别保存incX、incY这两个变量，对其实例化后即可实现⽅向的增量表⽰。
//定义⼀个结构体表⽰⽅向的增量
typedef struct{
//x,y⽅向的增量
int incX,incY;
}Direction;
实例化：
Direction direct[4]={{0,1},{1,0},{0,-1},{-1,0}};
3、算法实现过程
双层循环控制，内层循环控制机器⼈⽅向探寻过程，依次探寻四个⽅向，外层循环保证机器⼈进⾏回溯时退栈不为空。
1. 机器⼈从⼊⼝处（1，1）出发，开始按照右下左上的⽅向顺序进⾏搜索，判断四个⽅向上是否有路可⾛，这⾥实现过程可以利⽤⼀层
循环实现，依次遍历⽅向搜寻的四个⽅向，有路可⾛的含义就是机器⼈⽬前所处的位置上下左右四个⽅向是不是有为0的取值，有的话就证明机器⼈⽬前所处的位置不是死路，是能够前进的。
2. 因此把⽬前的位置和前进的⽅向这三个变量进⾏⼊栈操作。
3. ⼊栈完成后进⾏位置更新。要不这个已经⾛过的位置⽤-1替换，不再⽤0或者1表⽰。
if(maze[line][col]==0)
{
temp.x=x;
temp.y=y;
temp.di=di;
push(&S,temp.x ,temp.y ,temp.di);
x =line;
y =col;
maze[line][col]=-1;
5. 当然，如果四个⽅向都搜寻完，⼀位置这⼀层循环跳出了，那这样就是回溯算法的核⼼思想，这是机器⼈⽬前所处的位置是不会⼊栈
的，反⽽会执⾏退栈操作，返回到前⼀个位置，我们之前保存的其前进的位置就有⽤了，⽤di这个⽅向变量同时接受收当时保存的位置，位置更新后再次进⼊⽅向搜索的循环，这样不需要重复搜索原来已经搜索过的地⽅，因为原来搜索过的地⽅是⾛不通的，如果⼊栈时不保存原来的位置就会陷⼊死循环。
{
pop(&S,&(temp.x),&(temp.y),&(temp.di));
x = temp.x;
y = temp.y;
di = temp.di +1;
while(di <4)
{
line = x+ direct[di].incX;
col = y + direct[di].incY;
if(maze[line][col]==0)
{
temp.x=x;
temp.y=y;
temp.di=di;
push(&S,temp.x ,temp.y ,temp.di);
x =line;
y =col;
maze[line][col]=-1;
if(x ==M && y == N)
{
//由于栈先⼊后出的特性这⾥重新定义⼀个栈⽬的就是能够正序输出其坐标
while(!IsEmptyStack(&S))
{
pop(&S,&(temp.x),&(temp.y),&(temp.di));
push(&H,temp.x ,temp.y ,temp.di);
}
while(!IsEmptyStack(&H))
{
pop(&H,&(temp.x),&(temp.y),&(temp.di));
printf("(%d,%d),direct: %d\n",temp.x,temp.y,temp.di);
}
return1;
// int e1,e2,e3;
//GetTop(&S, &e1,&e2,&e3 );
// printf("%d",e1);
}
else di =0;
}
else
di ++;
}
}
6. 既然有退栈的操作，我们还要有⼀层循环，去判断栈是否为空，如果栈为空还没有到终点，表⽰这个迷宫⽆解，我们也要对这个结果
做出反馈。
7. 机器⼈搜索道路的终点应该是，机器⼈当前的位置坐标为最后的出⼝位置，即表⽰成功⾛出迷宫。
8. 成功⾛出迷宫后，要对其路程进⾏输出，由于栈先进后出的特点，栈顶保存的位置坐标是机器⼈最后的⾛的位置，这⾥我采⽤的⽅法
是重新定义⼀个栈，原有栈的结果依次出栈⼊新栈，打印的时候让新栈依次出栈
{
pop(&S,&(temp.x),&(temp.y),&(temp.di));
push(&H,temp.x ,temp.y ,temp.di);
}
while(!IsEmptyStack(&H))
{
pop(&H,&(temp.x),&(temp.y),&(temp.di));
printf("(%d,%d),direct: %d\n",temp.x,temp.y,temp.di);
}
⼆、遇到的问题与解决⽅案
1.结构体数组⼊栈的问题
1. 栈中需要保存位置坐标x、y以及从⽬前该位置移动⾄下⼀个位置的⽅向，保存这个⽅向的⽬的就在于⾛错路进⾏退栈。⽆需要四个⽅
向重新遍历，在原有基础上查为⾛过的⽅向即可。栈中保存的不再是⼀个数⽽应该是三个数，栈顶指针top更新时不可以简单的top++，理解也很简单这三个数分配的空间定义的⼀个结构体抽象数据类型⽤到的空间，具体是多少我们很难估计，基于此考虑利⽤双链表实现我们在定义保存当前位置坐标
与⽅向这个结构体时定义同样类型的指针，分别指向他的前⼀个节点与后⼀个节点，这样在更新栈顶指针所指位置时，直接将next指针传给top就能顺利完成出栈与⼊栈。⽽对于出栈⼀样的操作，数据出栈后，只需要把parent指针的内容传给top。由此我们可以看出，栈的实现本质上变成了双向链表的操作。分别对应其⼊栈出栈。简单的画了⼀下栈内各结点的连接过程：
2. 当我们考虑好结构体⼊栈出栈的具体实现⽅式，就要改变原来初始化的问题。进⾏栈的初始化，我采⽤的是提前动态申请部分空间，
除了空间的申请更要构建好节点之间的关系，即能够正确到next节点与parent节点。为了能够正确描述节点之间的关系选择采⽤循环申请的动态空间的⽅式。为了保证数据能够顺利⼊栈，栈顶指针需要指向下⼀个放⼊数据的空间，因此让栈顶指针等于栈底指针，初始化完成，得到⼀个空栈。
Status InitStack(SeqStack* stack)
{
//开辟空间
stack->base=stack->top =(EleType*)malloc(sizeof(Box));
int i =0;
for(i=0; i <50;i++)
{
stack->top->next =(EleType*)malloc(sizeof(Box));
stack->top->next->present = stack->top;
stack->top = stack->top->next;
}
stack ->top = stack ->base;
if(!stack->base)
{
exit(0);
}
stack->stackSize = STACK_INIT_SIZE;
return OK;
}
⼆、结果展⽰

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。