栈是数据结构中一种重要的线性结构,限定仅在表尾进行插入和删除操作的线性表,因此我们也可以认为它是一种特殊的线性表。由于栈的这个特点,我们又可以称其为后进先出的结构。如图所示:
创新互联专注于企业营销型网站、网站重做改版、茶陵网站定制设计、自适应品牌网站建设、成都h5网站建设、购物商城网站建设、集团公司官网建设、外贸网站建设、高端网站制作、响应式网页设计等建站业务,价格优惠性价比高,为茶陵等各大城市提供网站开发制作服务。
由于栈具有后进先出的性质我们可以利用,是程序设计中一个有用的工具。利用栈我们可以来实现数制转换、后缀表达式求值、迷宫求解等等。在书本上我们可以看到用C语言实现的简单思路,但是程序仍旧存在许多bug。今天,我想尝试用强大的C++来实现。
迷宫问题的求解思路大致则是从入口出发,顺着某一方向向前探索,若能走通,则继续向前探索;若不能走通,则换一方向进行探索,直至所有可能的通路都探索完为止。利用栈的特性,我们可以将探索过可通的路依次进栈,如果遇到不通的路则进行出栈操作,进行回退,重复探索。
ps:为了方便起见我利用了一个记事本来存放迷宫,用1表示不通,0表示通路。将走过的路程标注为2.
代码实现:
struct Pos //可通过下标访问位置 { int _ROW; int _COL; }; void GetMaze(int *a,int n) //从文件中读出迷宫地图 { FILE* fout=fopen("Maze.txt","r"); assert(fout); for(int i=0; i=0) && (next._ROW =0) && (next._COL & path) //探索过程 { Pos cur=entry; path.push(cur); while(!path.empty()) { Pos next=cur; a[cur._ROW*n+cur._COL]=2; if(next._ROW==n-1) /*|| next._ROW==0 || next._COL==n-1 || next._COL==0*/ { return true; } //判断上下左右是否为通路 next=cur; next._ROW--;// 上 if(CheckIsAccess(a,n,next)) { cur=next; path.push(cur); continue; } next=cur; next._ROW++;//下 if(CheckIsAccess(a,n,next)) { cur=next; path.push(cur); continue; } next=cur; next._COL--;//左 if(CheckIsAccess(a,n,next)) { cur=next; path.push(cur); continue; } next=cur; next._COL++;//右 if(CheckIsAccess(a,n,next)) { cur=next; path.push(cur); continue; } //回退 cur=path.top(); path.pop(); } } void PrintMaze(int *a,int n) //输出迷宫 { for(int i=0; i
网页名称:应用栈求解迷宫问题(C++实现)
分享链接:http://cdkjz.cn/article/jghjgj.html