C++自定义栈实现迷宫求解

C++ 自定义栈实现迷宫求解

创新互联是专业的芜湖网站建设公司，芜湖接单;提供成都网站设计、做网站,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行芜湖网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!

一：迷宫求解

是一个锻炼我们的算法求解能力的问题，它的实现方法有很多；今天我们就介绍其中的用栈求解的方法。

二：什么是栈：

大家应该都有往袋子里装东西的经历，在往袋子里装满东西之后，当我们去取的时候，总是先从最后放进去的东西的地方去取。也就是后进先出(FILO)。虽然栈的单向性用起来会没有链表那样可以在任意位置对数据进行操作，但是正因为如此栈也带来了很大的方便。

三：迷宫求解

现在我们要在下面的迷宫寻找一条可行的路径

 1 1 1 1 1 1 1 1 1 1
 1 0 0 1 1 0 0 0 0 1
 1 0 0 0 1 0 1 0 0 1
 1 0 1 0 0 0 1 1 0 1
 1 0 1 0 0 0 1 1 1 1
 1 0 1 1 1 0 1 1 1 1
 1 0 1 1 1 0 1 1 1 1
 1 1 1 1 1 0 0 0 1 1
 1 1 1 1 1 1 1 0 0 1
 1 1 1 1 1 1 1 1 1 1

首先我们需要在程序中表示上面的迷宫，该问题可以用数组实现

1：栈的定义

/************************************************************************/ 
/*自定义栈                                     */ 
/*通过自定义的简单栈以满足迷宫求解        */ 
/*功能：push() 将元素加入栈中                 */ 
/*        pop() 退栈；topValue() 获得栈顶元素    */ 
/*        clear() 清除栈 length() 获得栈中元素个数*/ 
/************************************************************************/ 
#include  
#include  
using namespace std; 
 
template class PathStack: public stack 
{ 
private: 
  int size; 
  int top; 
  Elem* listArray; 
public: 
  PathStack(int sz = DefaultListSize){ 
    size = sz; 
    top = 0; 
    listArray = new Elem[sz]; 
  } 
  ~PathStack(){ delete []listArray; } 
  void clear(){ top = 0; } 
  /****向栈中加入元素****/ 
  bool push(const Elem& item); 
  /***********退栈**********/ 
  Elem pop(); 
  /********获得栈顶元素*******/ 
  Elem topValue() const; 
  int length() const { return top; } 
}; 
 
template 
bool PathStack::push(const Elem& item){ 
  if(top == size) return false; 
  listArray[top++] = item; 
  return true; 
} 
 
template 
Elem PathStack::pop(){ 
  Elem it; 
  if(top == 0) return it; 
  it = listArray[--top];  
  return it; 
} 
 
template 
Elem PathStack::topValue() const{ 
  Elem it; 
  if(top == 0) return it; 
  it = listArray[top - 1]; 
  return it; 
}

2：如何实现路径的寻找

1：设定寻找的方向，可以使用一个判断语句；判断起始位置周围哪个地方有路就将该位置的坐标加入到栈中，并将该位置标记(将改位置值改为2,既将走过的位置标记为2)

2：判断该位置周围是否还有路，若没有则退栈即退回到上一个位置；并将该位置做下另一个标记(将该位置值改为3,既将退栈位置值用3标记)

3：重复1,2步骤直到达到出口

路径寻找的类：

//迷宫求解的方法类 
//功能：通过findPath() 方法实现对路径的查找 
//       通过printPath()方法将路径打印出来 
#include "PathStack.h" 
#include  
using namespace std; 
 
class MazeSolveMethod 
{ 
private: 
  static int maze[10][10];//存放迷宫数据 
  PathStack pathStack;//定义栈 
public: 
  MazeSolveMethod():pathStack(100){ 
  } 
  ~MazeSolveMethod(){ } 
  void findPath(int startX,int startY); 
  void printPath() const; 
}; 
 
int MazeSolveMethod::maze[10][10] = { 
  {1,1,1,1,1,1,1,1,1,1}, 
  {1,0,0,1,1,0,0,0,0,1}, 
  {1,0,0,0,1,0,1,0,0,1}, 
  {1,0,1,0,0,0,1,1,0,1}, 
  {1,0,1,0,0,0,1,1,1,1}, 
  {1,0,1,1,1,0,1,1,1,1}, 
  {1,0,1,1,1,0,1,1,1,1}, 
  {1,1,1,1,1,0,0,0,1,1}, 
  {1,1,1,1,1,1,1,0,0,1}, 
  {1,1,1,1,1,1,1,1,1,1}, 
}; 
 
void MazeSolveMethod::findPath(int startX,int startY){ 
  int x = startX; 
  int y = startY; 
  pathStack.push(x); 
  pathStack.push(y); 
  maze[x][y] = 2; 
  cout<<"进入方法！"<= 8 && y >= 8){ 
        break; 
      }else{ 
        maze[x][y] = 3; 
        y = pathStack.pop(); 
        x = pathStack.pop(); 
      } 
      y = pathStack.topValue(); 
      int temp = pathStack.pop(); 
      x = pathStack.topValue(); 
      pathStack.push(temp); 
    } 
  } 
} 
 
void MazeSolveMethod::printPath() const{ 
  cout<<"printPath"<

主函数类

/************************************************************************/ 
/*迷宫求解----栈方法实现*/ 
//功能：通过对栈实现迷宫算法求解 
//Author：Andrew 
//Date  ：2012-10-20 
/************************************************************************/ 
#include "MazeSolveMethod.h" 
#include  
using std::cout; 
using std::endl; 
 
int main(){ 
 
  MazeSolveMethod solve; 
  solve.findPath(1,1); 
  solve.printPath(); 
  system("pause"); 
  return 0; 
}

将上面的代码运行后结果截图如下：

其中* 为路径

C++ 自定义栈实现迷宫求解

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

分享标题：C++自定义栈实现迷宫求解
标题URL：http://kswsj.cn/article/gosehs.html

关于创新互联

C++自定义栈实现迷宫求解

其他资讯