东莞外贸模板建站,网站优化电话,图片网站制作,100个万能网站栈的概念
对于栈#xff08;Stack#xff09;#xff0c;后进先出#xff08;Last In First Out#xff0c;LIFO#xff09;#xff0c;栈也是一种线性表#xff0c;只不过是一种操作受限的线性表#xff0c;只能在一端操作#xff0c;也就是不允许在中间进行查找、…栈的概念
对于栈Stack后进先出Last In First OutLIFO栈也是一种线性表只不过是一种操作受限的线性表只能在一端操作也就是不允许在中间进行查找、插入、删除等操作。
栈的图 进出的一端称为栈顶top另一端称为栈底base栈可以顺序存储也可以链式存储这里讲的是栈的顺序存储方式。
栈也可以比喻成一个乒乓球桶桶底是封口的桶顶是打开的桶的横截面积恰好为一个乒乓球投影的面积也就是说你只能从最后一个乒乓球后放入乒乓球后面放进去的乒乓球会压着前面的乒乓球只能拿走最后一个乒乓球不能拿走被压着的乒乓球。
栈的算法实现
栈的数据定义
#define MAX_SIZE 120 //栈的最大容量
typedef int DateElem;
typedef struct _Stack
{DateElem* top; //栈顶指针DateElem* base; //栈底指针指向栈的开始
}Stack;
初始化栈
bool initStack(Stack s)
{s.base new DateElem[MAX_SIZE];if (!s.base) return false; //空间分配失败s.top s.base; //为空栈栈中无任何元素return true;
}
销毁栈
销毁与初始化一一对应初始化时申请了内存销毁时就需要释放。
void destoryStack(Stack s)
{if (s.base ! NULL) //栈空间有效{delete s.base;s.base s.top NULL;}}
入栈
bool pushStack(Stack s, DateElem e)
{if (!s.base || (s.top - s.base) MAX_SIZE) return false; //栈没建立 或者 栈空间满了*(s.top) e; //因为最开始 s-top 0 return true;
}
出栈
bool popStack(Stack s, DateElem e) //用 e 返回被删除的元素的指
{if (!s.base || s.base s.top) return false;e *(--s.top); //先将栈顶元素赋值给e栈顶指针再移动因为栈顶指针都是指向栈顶元素的后一个位置除了栈为空时栈顶指针为 0return true;
}
获取栈顶元素
bool getTop(Stack s,DateElem e)
{if (s.top s.base) //栈不为空{e *(s.top - 1); //e 返回栈顶元素的值return true;}else{return false;}
}
判断栈是否为空
bool IsEmpty(Stack s)
{if (s.base s.top){ return true;}else{return false;}
}
获取栈中元素的个数
int getLength(Stack s)
{return (int)(s.top - s.base);
}
栈的应用
迷宫问题
在给定区域内二维数组告诉你起点找到一条到出口的移动路线。
迷宫求解问题
对于走出一个迷宫我们只需要将所有的路都走一遍就可以走出迷宫需要避免走重复的路对走过的路做好标记在这个过程中如果遇到岔路就选择其中一条路前进如果碰到死胡同就返回回退到上个岔路选择别的路,如果这个岔路也无路可走了继续回退到上个岔路选择一条路……直到找到出口或者是无路可走。我们把一个坐标的位置看作一个岔路可以向上、下左、右走
找迷宫的通路使用到的是回溯法穷举法的改进回溯的过程需要用到栈。我最开始想到的是栈的递归 回溯法:对一个包括有很多个结点每个结点有若千个搜索分支的问题把原问题分解为若千个子问题求解的算法;当搜索到某个结点发现无法再继续搜索下去时就让搜索过程回溯(回退)到该节点的前一一个结点继续搜索该节点外的其他尚未搜索的分支;如果发现该结点无法再搜索下去就让搜索过程回溯到这个结点的前一结点继续这样的搜索过程;这样的搜索过程--直进行到搜索到问题的解或者搜索完了全部可搜索分支没有解存在为止。 代码实现
其中栈存储的数据为而不是之前的 int 类型了
typedef struct _Position
{int x;int y;
}position;typedef position DateElem;
然后代码我就没有发关于顺序栈的实现了。 具体思想 一、在当前位置分别判断左、上、右、下四个方向的位置是否为路。 二、选择一条路然后这条路就是当前位置了。每当某个位置变为当前位置就要标记一下入口也要防止重复走判断当前位置是否为终点不为的话执行步骤一。 三、如果在当前位置左、上、右、下四个方向的位置都走过了或者是墙就回退到上一个位置存储在栈中执行步骤一、二。 四、重复步骤一、二、三直到找到出口或者回退到入口。 #include iostream
#include 顺序栈.husing namespace std;#define ROW 6
#define COL 6typedef struct _Maze //迷宫的结构体
{int map[ROW][COL];
}Maze;void initMaze(Maze* maze, int map[ROW][COL]) //将传入的地图数据来初始化迷宫
{for (int i 0; i ROW; i){for (int j 0; j COL; j){maze-map[i][j] map[i][j];}}
}
void printMaze(Maze* maze) //打印整个迷宫
{for (int i 0; i ROW; i){for (int j 0; j COL; j){cout maze-map[i][j] ;}cout endl;}
}int IsValidEnter(position* enter,Maze *maze) //判断入口是否有效
{if (!enter || !maze) return -1; //合法性检查if ((enter-x 0 || enter-x ROW-1 ) ||(enter-y 0 || enter-y COL-1) maze-map[enter-x][enter-y] 1) //在地图的边界上并且是通路{return 1;}else{return 0;}
}
int IsValidExit(position *cur, Maze* maze,position *enter) //判断出口是否有效
{if (!cur || !maze || !enter) return -1; //合法性检查if (((cur-x 0 || cur-x ROW - 1) ||(cur-y 0 || cur-y COL - 1)) (enter-x ! cur-x enter-y ! cur-y)) //在地图边界上并且不是入口那就是出口{return 1;}else{return 0;}}
int IsNextPass(position *next, Maze* maze) //判断下一步的位置是否有效
{if (!next || !maze) return -1; //合法性检查if ((next-x 0 next-x ROW) (next-y 0 next-y COL) maze-map[next-x][next-y] 1) //在地图里并且是路没走过等于2、3、4……就是走过的路{return 1;}else{return 0;}
}
int PassMaze(position *enter,Maze *maze,Stack *s)
{if (!maze || IsValidEnter(enter,maze) 0) return 0; //迷宫为空或者入口无效position cur { enter-x,enter-y }; //当前人所在的位置position next; // 保存下一步的位置pushStack(*s, cur); //入口入栈maze-map[enter-x][enter-y] 2; // 走过的地方要改变他的值防止重复走while (!IsEmpty(*s)){getTop(*s,cur); //得到当前所在的位置if (IsValidExit(cur, maze, enter)) //是出口就可以结束了{return 1;}next cur;next.y--; //尝试向左走一步看看能不能继续走if (IsNextPass(next, maze) 1) {pushStack(*s, next); //下一步入栈maze-map[next.x][next.y] maze-map[cur.x][cur.y] 1; //下一步的值为当前位置的值1continue;}next cur;next.x--; //尝试向上走一步看看能不能继续走if (IsNextPass(next, maze) 1){pushStack(*s, next);maze-map[next.x][next.y] maze-map[cur.x][cur.y] 1;continue;}next cur;next.y; //尝试向右走一步看看能不能继续走if (IsNextPass(next, maze) 1){pushStack(*s, next);maze-map[next.x][next.y] maze-map[cur.x][cur.y] 1;continue;}next cur;next.x; //尝试向下走一步看看能不能继续走if (IsNextPass(next, maze) 1){pushStack(*s, next); maze-map[next.x][next.y] maze-map[cur.x][cur.y] 1; continue;}//走到这里了说明当前位置的四个方向都走不通进行回溯到上个结点看看上个结点未被遍历的方向能否走通position temp;popStack(*s, temp);}return false;
}
int main(void)
{int map[ROW][COL] {0,0,1,0,0,0,0,0,1,1,0,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}; // 二维数组代表迷宫1代表路0代表墙Maze maze; //迷宫的拷贝initMaze(maze, map); //初始化maze迷宫//printMaze(maze); //打印迷宫测试position enter { 0,2 }; //创建了迷宫入口并初始化Stack s; //栈用来保存已走过的路便于回溯initStack(s); //初始化栈if (PassMaze(enter, maze, s)){cout 恭喜你找到了出口 endl;}else{cout 无路可走了 endl;}printMaze(maze); //打印迷宫return 0;
}
代码很多但是结构清楚。以下是代码的执行效果能清楚知道移动的轨迹。
