栈的定义
栈是一种只能在一端进行插入或删除操作的线性表 表中允许进行插入、删除操作的一端称为栈顶(top)表的另一端称为栈底(bottom)。当栈中没有数据元素时称为空栈 栈的插入操作通常称为进栈或入栈(push),栈的删除操作通常称为出栈或退栈(pop)。
栈的顺序存储结构及其基本运算的实现
采用顺序结构存储的栈称为顺序栈
typedef struct {
ElemType data[MaxSize];
int top;
}SqStack;
- 初始化栈
void InitStack(SqStack *&s)
{
s = (SqStack*)malloc(sizeof(SqStack));
s->top = -1;
}
- 销毁栈
void DestroyStack(SqStack *&s)
{
free(s);
}
- 判断栈是否为空
bool StackEmpty(SqStack *s)
{
return(s->top == -1);
}
- 进栈
bool Push(SqStack*&s, ElemType e)
{
if (s->top == MaxSize - 1)
return false;
s->top++;
s->data[s->top] = e;
return true;
}
- 出栈
bool Pop(SqStack*&s, ElemType &e)
{
if (s->top == -1)
return false;
e = s->data[s->top];
s->top--;
return true;
}
- 取栈顶元素
bool GetTop(SqStack *s, ElemType &e)
{
if (s->top == -1)
return false;
e = s->data[s->top];
return true;
}
栈的链式存储结构及其基本运算的实现
采用链式存储结构的栈称为链栈
typedef struct linknode
{
ElemType data;
struct linknode *next;
}LinkStNode;
- 初始化栈
void InitStack(LinkStNode *&s)
{
s = (LinkStNode*)malloc(sizeof(LinkStNode));
s->next = NULL;
}
- 销毁栈
void DestroyStack(LinkStNode *&s)
{
LinkStNode *pre = s,*p=s->next;
while (p != NULL)
{
free(pre);
pre = p;
p = pre->next;
}
free(pre);
}
- 判断栈是否为空
bool StackEmpty(LinkStNode *s)
{
return(s->next = NULL);
}
- 进栈
void Push(LinkStNode *&s, ElemType e)
{
LinkStNode *p;
p = (LinkStNode*)malloc(sizeof(LinkStNode));
p->data = e;
p->next = s->next;
s->next = p;
}
- 出栈
bool Pop(LinkStNode *&s, ElemType &e)
{
LinkStNode *p;
if (s->next == NULL)
return false;
e = s->data;
p = s->next;
s->next = p->next;
free(p);
return true;
}
- 取栈顶元素
bool GetTop(LinkStNode *s, ElemType &e)
{
if (s->next == NULL)
return false;
e = s->data;
return true;
}
求解迷宫问题
问题描述
给定一个(M , N ) 的迷宫图，求一条从指定入口到出口的迷宫路径。假设一个迷宫图如下图所示，其中的每个方块用空白表示通道，用阴影表示障碍物。一般情况下，所求迷宫路径是简单路径，即在求得的迷宫路径上不会重复出现同一方块。一个迷宫图的迷宫路径可能有多条，这里仅仅考虑用栈求一条从指定入口到出口的迷宫路径。
数据组织
为了表示迷宫，设置一个数组mg，其中每个元素表示一个方块的状态，为0时表示对应的方块是通道，为1时表示对应方块时障碍物。为了运算方便，一般在迷宫的外围加一条围墙。
#define M 8
#define N 8
int mg[M+2][N+2]=
{
{1,1,1,1,1,1,1,1,1,1},{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1}
};
在算法中用到的栈采用顺序栈存储结构
typedef struct{
int i;//当前方块的行号
int j;//当前方块的列号
int di;//di是下一相邻可走方位的方位号
}Box;
typedef struct{
Box data[MaxSize];
int top;
}StType;
设计运算算法
- 对于迷宫中的每个方块，有上、下、左、右 4 个方块相邻，规定上方方块为0，并按顺时针方向递增标号。
- 求解迷宫问题采用的算法思想为“穷举法”。即从入口出发，按方位0到方位3的次序试探相邻的方块，一旦找到一个可走的相邻方块就继续走下去，并记下所走的方位。若没有相邻的可走方块，则沿原路退回到前一个方块。
- 若一个非出口方块是可走的，将它进栈，如果找到某个方位 的相邻方块是可走的，则将栈顶方块的方位 di 置为d。
- 在算法上应保证试探的相邻可走方块不是已走路径上的方块，因此在一个方块进栈后将对应的 mg 数组元素值改为 -1 当退栈时将其恢复为 0
将入口(xi,yi)进栈(其初始方位设置为-1)
mg[xi][yi]=-1;
while(栈不为空)
{
取栈顶方块(i,j,di);
if((i,j)是出口(xi,yi))
{
输出栈中的全部方块构成一条迷宫路径
return true;
}
查找(i,j,di)的下一个相邻可走方块;
if(找到一个相邻可走方块)
{
该方块为(i1,j1),对应方位d;
将栈顶方块的di设置为d;
(i1,j1,-1)进栈;
mg[i1][j1]=-1;
}
if(没有找到(i,j,di)的任何相邻可走方块)
{
将(i,j,di)出栈：
mg[i][j]=0;
}
}
return false; //没有找到迷宫路径
bool mgpath(int xi,int yi,int xe,int ye)
{
Box path[MaxSize],e;
int i,j,di,i1,j1,k;
bool find;
StType*st;
InitStack(st);
e.i=xi;e.j=yi;e.di=-1;
Push(st,e);
mg[xi][yi]=-1;
while(!StackEmpty(st))
{
GetTop(st,e);
i=e.i;j=e.j;di=e.di;
if(i==xe&&j==ye)
{
printf("一条迷宫路径如下：\n");
k=0;
while(!StackEmpty(st))
{
Pop(st,e);
path[k++]=e;
}
while(k>=1)
{
k--;
printf("\t(%d,%d)",path[k].i,path[k].j);
if((k+2)%5==0)
printf("\n");
}
DestroyStack(st);
return true;
}
find=false;
while(di<4&&!find)
{
di++;
switch(di)
{
case 0: i1=i-1;j1=j;break;
case 1: i1=i;j1=j+1;break;
case 2: i1=i+1;j1=j;break;
case 3: i1=i;j1=j-1;break;
}
if(mg[i1][j1]==0) find=true;
}
if(find)
{
st->data[st->top].di=di;
e.i=i1;e.j=j1;e.di=-1;
Push(st,e);
mg[i1][j1]=-1;
}
else
{
Pop(st,e);
mg[e.i][e.j]=0;
}
}
DestroyStack(st);
return false;
}
设计求解程序
int main(){
if(!mppath(1,1,M,N))
printf("该迷宫问题没有解");
return 0;
}
问题进阶
在上述的过程中，我们只能找到一条路径。可是，往往我们需要找出最短路径，对于栈而言，我们可以通过找出所有的路径，从而确定最短的路径。由上述的分析可知，回溯的关键是 di 值要找出所有的路径，直接退栈即可，并将该方块对应的mg数组置为0，由于回溯过后的那个方块保存了信息就可以实现穷举出所有的路径。
bool mgpath(int xi, int yi, int xe, int ye)
{
Box path[MaxSize], e;
int i, j, di, i1, j1, k;
int num=0;//用来判断是否有路径输出
bool find;
StType*st;
InitStack(st);
e.i = xi; e.j = yi; e.di = -1;
Push(st, e);
mg[xi][yi] = -1;
while (!StackEmpty(st))
{
GetTop(st, e);
i = e.i; j = e.j; di = e.di;
if (i == xe && j == ye)
{
num++;
printf("\n一条迷宫路径如下：\n");
k = 0;
int n = st->top;//由于要回溯需要栈的信息不能采用退栈的方式
while (n!=-1)
{
e = st->data[n--];
path[k++] = e;
}
while (k >= 1)
{
k--;
printf("\t(%d,%d)", path[k].i, path[k].j);
if ((k + 2) % 5 == 0)
printf("\n");
}
mg[i][j] = 0; //设置出口状态为0
Pop(st, e); //回溯
mg[e.i][e.j] = 0; //设置其状态为0
i = e.i; j = e.j; di = e.di; //将i和j置为当前方块的值
}
find = false;
while (di < 4 && !find)
{
di++;
switch (di)
{
case 0: i1 = i - 1; j1 = j; break;
case 1: i1 = i; j1 = j + 1; break;
case 2: i1 = i + 1; j1 = j; break;
case 3: i1 = i; j1 = j - 1; break;
}
if (mg[i1][j1] == 0) find = true;
}
if (find)
{
st->data[st->top].di = di;
e.i = i1; e.j = j1; e.di = -1;
Push(st, e);
mg[i1][j1] = -1;
}
else
{
Pop(st, e);
mg[e.i][e.j] = 0;
}
}
DestroyStack(st);
if(num>0) return true;
return false;
}
