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

概述C++自定义栈实现迷宫求解一：迷宫求解是一个锻炼我们的算法求解能力的问题，它的实现方法有很多；今天我们就介绍其中的用栈求解的方法。

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

一：迷宫求解

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

二：什么是栈：

      大家应该都有往袋子里装东西的经历，在往袋子里装满东西之后，当我们去取的时候，总是先从最后放进去的东西的地方去取。也就是后进先出(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 <stack> #include <iostream> using namespace std;  template<typename Elem> class PathStack: public stack<Elem> { 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<typename Elem> bool PathStack<typename Elem>::push(const Elem& item){   if(top == size) return false;   ListArray[top++] = item;   return true; }  template<typename Elem> Elem PathStack<typename Elem>::pop(){   Elem it;   if(top == 0) return it;   it = ListArray[--top];    return it; }  template<typename Elem> Elem PathStack<typename Elem>::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 <iostream> using namespace std;  class MazeSolveMethod { private:   static int maze[10][10];//存放迷宫数据   PathStack<int> pathStack;//定义栈 public:   MazeSolveMethod():pathStack(100){   }   ~MazeSolveMethod(){ }   voID findpath(int startX,int startY);   voID printPath() const; };  int MazeSolveMethod::maze[10][10] = {   {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<<"进入方法！"<<endl;   while(true){     if(maze[x-1][y] == 0){       pathStack.push(--x);       pathStack.push(y);       maze[x][y] = 2;     }else if(maze[x][y-1] == 0){       pathStack.push(x);       pathStack.push(--y);       maze[x][y] = 2;     }else if(maze[x][y+1] == 0){       pathStack.push(x);       pathStack.push(++y);       maze[x][y] = 2;     }else if(maze[x+1][y] == 0){       pathStack.push(++x);       pathStack.push(y);       maze[x][y] = 2;     }     if(maze[x-1][y] != 0 && maze[x][y+1] != 0 && maze[x+1][y] != 0 && maze[x][y-1] != 0){               if(x >= 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"<<endl;   for(int i=0; i<10; i++){     for(int j=0; j<10; j++){       if(maze[i][j] == 2)         cout<<'*'<<" ";       else if(maze[i][j] == 3)         cout<<0<<" ";       else         cout<<1<<" ";     }     cout<<endl;   } } 

   主函数类 

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

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

 其中* 为路径 

 

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

总结

以上是内存溢出为你收集整理的C++ 自定义栈实现迷宫求解全部内容，希望文章能够帮你解决C++ 自定义栈实现迷宫求解所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。