C++自定義棧實(shí)現(xiàn)迷宮求解

C++ 自定義棧實(shí)現(xiàn)迷宮求解

創(chuàng)新互聯(lián)是專業(yè)的蕪湖網(wǎng)站建設(shè)公司，蕪湖接單;提供成都網(wǎng)站設(shè)計(jì)、做網(wǎng)站,網(wǎng)頁(yè)設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行蕪湖網(wǎng)站開發(fā)網(wǎng)頁(yè)制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來(lái)合作!

一：迷宮求解

是一個(gè)鍛煉我們的算法求解能力的問(wèn)題，它的實(shí)現(xiàn)方法有很多；今天我們就介紹其中的用棧求解的方法。

二：什么是棧：

大家應(yīng)該都有往袋子里裝東西的經(jīng)歷，在往袋子里裝滿東西之后，當(dāng)我們?nèi)ト〉臅r(shí)候，總是先從最后放進(jìn)去的東西的地方去取。也就是后進(jìn)先出(FILO)。雖然棧的單向性用起來(lái)會(huì)沒(méi)有鏈表那樣可以在任意位置對(duì)數(shù)據(jù)進(jìn)行操作，但是正因?yàn)槿绱藯Ｒ矌?lái)了很大的方便。

三：迷宮求解

現(xiàn)在我們要在下面的迷宮尋找一條可行的路徑

 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

首先我們需要在程序中表示上面的迷宮，該問(wèn)題可以用數(shù)組實(shí)現(xiàn)

1：棧的定義

/************************************************************************/ 
/*自定義棧                                     */ 
/*通過(guò)自定義的簡(jiǎn)單棧以滿足迷宮求解        */ 
/*功能：push() 將元素加入棧中                 */ 
/*        pop() 退棧；topValue() 獲得棧頂元素    */ 
/*        clear() 清除棧 length() 獲得棧中元素個(gè)數(shù)*/ 
/************************************************************************/ 
#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：如何實(shí)現(xiàn)路徑的尋找

1：設(shè)定尋找的方向，可以使用一個(gè)判斷語(yǔ)句；判斷起始位置周圍哪個(gè)地方有路就將該位置的坐標(biāo)加入到棧中，并將該位置標(biāo)記(將改位置值改為2,既將走過(guò)的位置標(biāo)記為2)

2：判斷該位置周圍是否還有路，若沒(méi)有則退棧即退回到上一個(gè)位置；并將該位置做下另一個(gè)標(biāo)記(將該位置值改為3,既將退棧位置值用3標(biāo)記)

3：重復(fù)1,2步驟直到達(dá)到出口

路徑尋找的類：

//迷宮求解的方法類 
//功能：通過(guò)findPath() 方法實(shí)現(xiàn)對(duì)路徑的查找 
//       通過(guò)printPath()方法將路徑打印出來(lái) 
#include "PathStack.h" 
#include  
using namespace std; 
 
class MazeSolveMethod 
{ 
private: 
  static int maze[10][10];//存放迷宮數(shù)據(jù) 
  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<<"進(jìn)入方法！"<= 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"<

主函數(shù)類

/************************************************************************/ 
/*迷宮求解----棧方法實(shí)現(xiàn)*/ 
//功能：通過(guò)對(duì)棧實(shí)現(xiàn)迷宮算法求解 
//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; 
}

將上面的代碼運(yùn)行后結(jié)果截圖如下：

其中* 為路徑

C++ 自定義棧實(shí)現(xiàn)迷宮求解

感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！

文章標(biāo)題：C++自定義棧實(shí)現(xiàn)迷宮求解
鏈接地址：http://weahome.cn/article/gosehs.html

真实的国产乱ⅩXXX66竹夫人,五月香六月婷婷激情综合,亚洲日本VA一区二区三区,亚洲精品一区二区三区麻豆

C++自定義棧實(shí)現(xiàn)迷宮求解

其他資訊

網(wǎng)站制作

企業(yè)服務(wù)

網(wǎng)站建設(shè)

服務(wù)器托管