破“栈”式

栈的原理

如同图里的小汽车是排成一条直线，是线性排列，而且只能从一端进出，后进的汽车先出去，后进 先出（Last In First Out，LIFO），这就是"栈"。栈也是一种线性表，只不过它是操作受限的线性 表，只能在一端操作。 进出的一端称为栈顶（top），另一端称为栈底（base）。栈可以用顺序存储，也可以用链式存储。

其中，base 指向栈底，top 指向栈顶。

注意：栈只能在一端操作，后进先出，这是栈的关键特征，也就是说不允许在中间查找、取值、插入、删除等 操作，我们掌握好顺序栈的初始化、入栈，出栈，取栈顶元素等操作即可。

 

顺序栈的实现

//栈数据结构定义 #define MaxSize 128 //预先分配空间，这个数值根据实际需要预估确定 typedef int ElemType; typedef struct _SqStack{ ElemType *base; //栈底指针 ElemType *top; //栈顶指针 }SqStack;

bool InitStack(SqStack &S) //构造一个空栈 S { //为顺序栈分配一个最大容量为 Maxsize 的空 间 S.base = new int[MaxSize]; //空间分配失败 if (!S.base) return false; S.top=S.base; //top 初始为 base，空栈 return true; }

 

// 插入元素 e 为新的栈顶元素 bool PushStack(SqStack &S, int e) { //栈满 if (S.top-S.base == MaxSize) return false; *(S.top++) = e; /*元素 e 压入栈顶，然后栈顶指针加 1， 等价于*S.top=e; S.top++;*/ return true; }

  出栈

出栈操作: 和入栈相反，出栈前要判断是否栈空，如果栈是空的，则出栈失败，否则将栈顶元素暂存给一个变 量，栈顶指针向下移动一个空间（top- -）。

//删除 S 的栈顶元素，暂存在变量 e 中 bool PopStack(SqStack &S, ElemType &e) { //栈空 if (S.base == S.top){ return false; } e = *(--S.top); //栈顶指针减 1，将栈顶元素赋给 e return true; }

  获取栈顶元素 取栈顶元素和出栈不同，取栈顶元素只是把栈顶元素复制一份，栈的元素个数不变，而出栈是指栈顶元素取出， 栈内不再包含这个元素。

ElemType GetTop(SqStack &S) //返回 S 的栈顶元素，栈顶指针不变 { if (S.top != S.base){ //栈非空 return *(S.top - 1); //返回栈顶元素的值，栈顶指针不变 }else{ return -1; } }

  判断空栈

bool IsEmpty(SqStack &S){ //判断栈是否为空 if (S.top == S.base){ return true; }else{ return false; } }

  返回栈中元素个数

int GetSize(SqStack &S){//返回栈中元素个数 return (S.top-S.base); }

  销毁栈

void DestoryStack(SqStack &S) { if(S.base){ free(S.base); S.base = NULL; S.top = NULL; } }

 

栈在回溯法中的高级应用

这幅图熟不熟悉，是我们在推箱子实战中的练习。那么让我们通过回溯法来完成在这个小迷宫中的自动寻路。

maze.h

#pragma once #include<stdio.h> #include<stdlib.h> #define MAXSIZE 100 typedef struct _Position{//迷宫坐标 int _x; int _y; }Position; #define MaxSize 128 //预先分配空间，这个数值根据实际需要预估确定 typedef Position ElemType; typedef struct _SqStack{ ElemType *base; //栈底指针 ElemType *top; //栈顶指针 }SqStack; //构造一个空栈 S bool InitStack(SqStack &S) { S.base = new ElemType[MaxSize];//为顺序栈分配一个最大容量为 Maxsize 的空间 //空间分配失败 if (!S.base) return false; S.top=S.base; //top 初始为 base，空栈 return true; } // 插入元素 e 为新的栈顶元素 bool PushStack(SqStack &S, ElemType e) { //栈满 if (S.top-S.base == MaxSize) return false; *(S.top++) = e; //元素 e 压入栈顶，然后栈顶指针加 1，等价于*S.top=e; S.top++; return true; } //删除 S 的栈顶元素，暂存在变量 e 中 bool PopStack(SqStack &S, ElemType &e){ if (S.base == S.top){ //栈空 return false; } e = *(--S.top); //栈顶指针减 1，将栈顶元素赋给 e return true; } //返回 S 的栈顶元素，栈顶指针不变 ElemType* GetTop(SqStack &S) { if (S.top != S.base){ //栈非空 return S.top - 1; //返回栈顶元素的地址，栈顶指针不变 }else{ return NULL; } } //返回栈中元素个数 int GetSize(SqStack &S){ return (S.top-S.base); } //判断栈是否为空 bool IsEmpty(SqStack &S){ if (S.top == S.base){ return true; }else{ return false; } } //销毁栈 void DestoryStack(SqStack &S){ if(S.base){ free(S.base); S.base = NULL; S.top = NULL; } }

maze.cpp

#include <stdio.h> #include <stdlib.h> #include <string.h> #include "maze.h" #include <assert.h> #define ROW 6 #define COL 6 typedef struct _Maze{ int map[ROW][COL]; }Maze; //迷宫的初始化 void InitMaze(Maze* m, int map[ROW][COL]) { for (int i = 0;i< ROW ;++i) { for (int j = 0; j < COL; ++j) { m->map[i][j] = map[i][j]; } } } //打印迷宫 void PrintMaze(Maze* m) { for (int i = 0; i < ROW; ++i) { for (int j = 0; j < COL; ++j) { printf("%d ",m->map[i][j]); } printf("\n"); } printf("\n"); } //判断是否是有效的入口 int IsValidEnter(Maze* m, Position cur) { assert(m); if ((cur._x == 0 || cur._x == ROW - 1) || (cur._y == 0 || cur._y == COL - 1) && (m->map[cur._x][cur._y] == 1)) return 1; else return 0; } //判断当前节点的下一 个节点能否走通 int IsNextPass(Maze* m,Position cur, Position next) { assert(m); //判断 next 节点是否为 cur 的下一节点 if(((next._x == cur._x) && ((next._y == cur._y+1)|| (next._y == cur._y-1)))//在同一行上并且相邻 ||((next._y == cur._y) && ((next._x == cur._x+1)|| (next._x == cur._x-1)))){//或在同一列上并且相邻 //判断下一个节点是否在迷宫里面 if (((next._x >= 0 && next._x < ROW) && (next._y >= 0 && next._y < COL)) && (m->map[next._x][next._y] == 1)){ return 1; } } return 0; } //判断当前节点是 不是有效的迷宫出口 int IsValidExit(Maze* m, Position cur,Position enter) { assert(m); //这里首先得保证该节点不是入口点，其次只要它处在迷宫的边界即可 if ((cur._x != enter._x || cur._y != enter._y) && ((cur._x == 0 || cur._x == ROW - 1) || (cur._y == 0 || cur._y == COL - 1))) { return 1; }else return 0; } //找迷宫通路 int PassMaze(Maze* m,Position enter,SqStack* s) { assert(m && IsValidEnter(m,enter) == 1); //对给的迷宫的入口进行合法性判断 Position cur = enter; Position next; PushStack(*s, cur); //首先将迷宫的入口压入栈中 m->map[cur._x][cur._y] = 2; //将入口值改为 2 //PrintMaze(m); while (!IsEmpty(*s)) { cur = *GetTop(*s); //printf("cur: %d %d\n",cur._x, cur._y); //判断当前位置是否出口 if (IsValidExit(m,cur,enter) == 1) return 1; //尝试向左一步：看当前节点的左一个节点能不能走通 next = cur; next._y = cur._y - 1; if (IsNextPass(m, cur, next) == 1) { PushStack(*s, next); m->map[next._x][next._y] = m->map[cur._x][cur._y] + 1; //PrintMaze(m); continue; } //尝试向上一步:看当前节点的上一个节点能不能走通 next = cur; next._x = cur._x - 1; //next 节点能够走通时，将其压入 栈中 if (IsNextPass(m,cur,next) == 1) { PushStack(*s,next); //将 next 节点的值等于 cur 节点的值加 1 m->map[next._x][next._y] = m->map[cur._x][cur._y]+1; //PrintMaze(m); continue; } //右：看当前节点的向右的一个节点能不能走通 next = cur; next._y = cur._y + 1; if (IsNextPass(m, cur,next) == 1) { PushStack(*s, next); m->map[next._x][next._y] = m->map[cur._x][cur._y] + 1; //PrintMaze(m); continue; } //下：看当前节点的下一个节点能不能走通 next = cur; next._x = cur._x + 1; if (IsNextPass(m, cur,next) == 1) { PushStack(*s, next); m->map[next._x][next._y] = m->map[cur._x][cur._y] + 1; //PrintMaze(m); continue; } /*走到这里说明当前节点的四个方向都走不通，进行回溯， 看前一个节点 未被遍历的方向是否还能走通*/ Position tmp; PopStack(*s, tmp); } return 0; } int main() { //用二维数组描绘迷宫：1 代表通路，0 代表墙 int map[ROW][COL] = { 0,0,1,0,0,0, 0,0,1,1,1,0, 0,0,1,0,0,0, 0,1,1,1,1,0, 0,0,1,0,1,0, 0,0,0,0,1,0 }; Maze m; Position enter; //迷宫入口 enter._x = 0; enter._y = 2; InitMaze(&m, map); PrintMaze(&m); //system("pause"); //exit(0); SqStack s; //定义栈，保存已走过的坐标轨迹，便于回溯 InitStack(s); //栈的初始 int ret = PassMaze(&m,enter,&s); //使用栈和回溯法解开迷宫 if(ret){ printf("恭喜你！终于找到了出口~\n"); }else { printf("不是我笨！实在没有出口~\n"); } PrintMaze(&m); system("pause"); return 0; }