本篇內(nèi)容主要講解“C++中棧的應(yīng)用”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“C++中棧的應(yīng)用”吧!
1、棧的應(yīng)用1 解決迷宮問題
問題：一個n*n的0、1矩陣，0 表示可以走通，1表示不可以走 ，假定矩陣的下邊是出口，給定矩陣的入口坐標(biāo)，求出走出迷宮的路徑
這里用 棧 主要是解決 如圖所示 走不出去 會退時上一步（出棧） 位置的記錄
以及 記錄已經(jīng)走過的路徑（壓棧）
擴(kuò)展 ：(1) 非遞歸法實(shí)現(xiàn)
（遞歸法 與 非遞歸 的 一點(diǎn)不同
遞歸法不會出現(xiàn) 嘗試下一步失敗后 退到上一步 再次嘗試下一步時 不會出現(xiàn) 重復(fù) 嘗試上一次走錯的那個“下一步” 而 下面使用 棧的方式的 退棧時 下一步嘗試還會判斷 已走過不成功的情況【重復(fù)判斷一次】）
(2) 多個出口 最短路問題 【在下面實(shí)現(xiàn)】
//-----------------Maze.h---------
#pragma once
#define N 10
#define MAZEPATH "MazeMap.txt"
#include
using namespace std;
#include
#include
struct Pos
{
int _row;
int _col;
};
void GetMaze(int* a, int n);
void PrintMaze(int* a, int n);
bool MazePath(int* a, int n, const Pos entry, stack
//-----------------Maze.cpp-----------
#define _CRT_SECURE_NO_WARNINGS 1
// 棧應(yīng)用：迷宮(n*n)問題
#include "Maze.h"
void GetMaze(int* a, int n)
{
FILE* f_out = fopen(MAZEPATH, "r");
assert(f_out != NULL);
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; )
{
char ch = fgetc(f_out);
if (ch == '0' || ch == '1') //通路為0 不通路2
{
a[i*n + j] = ch - '0';
++j;
}
else
{
continue;
}
}
}
fclose(f_out);
}
void PrintMaze(int* a, int n)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++ )
{
cout< } cout< } } bool CheckIsAccess(const int *a, int n, const Pos& next) //判斷路通不通 { assert(a); if (next._row >= 0 && next._row < n && next._col >= 0 && next._col < n && a[next._row * n + next._col] == 0)// 0 表示路通 { return true; } else { return false; } } // const Pos entry 入口 , stack bool MazePath(int* a, int n, const Pos entry, stack { Pos cur = entry; path.push(cur); while (!path.empty()) // 無路走時棧空 { a[cur._row * n + cur._col] = 2;// 走過的路標(biāo)記 2 // 定義數(shù)組 最下邊為 出口 if (cur._row == n - 1) // 判斷是否到出口 { return true; } Pos 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._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; } // 走不通 a[cur._row * n + cur._col] = 5;// 標(biāo)出錯誤路線 path.pop(); if (!path.empty()) { cur = path.top(); } } return false; } //---------------------test.cpp---------------------- #define _CRT_SECURE_NO_WARNINGS 1 #include "Maze.h" void TestMaze() { int a[N][N] = {}; GetMaze((int*)a, N); PrintMaze((int*)a, N); stack Pos entry = {2, 0}; MazePath((int*)a, N, entry, path); cout<<"------------------------------"< PrintMaze((int*)a, N); } int main() { TestMaze(); getchar(); return 0; } //--------------MazeMap.txt---------------- 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 ////////////////////////////////////////////////////////////////////// ///////////////////////////////////////////////////////////////////// 2、棧的應(yīng)用2 逆波蘭式計(jì)算 #define _CRT_SECURE_NO_WARNINGS 1 #include #include #include using namespace std; // 棧的應(yīng)用 2 算數(shù)表達(dá)式求解 enum Type { OP_NUM, OP_SYMBOL }; struct Cell { Type type; int value; }; enum SYMBOL { ADD, SUB, MUL, DIV }; int CountRNP(Cell* a,size_t size) { assert(a); stack for (size_t i = 0; i < size; i++) { if (a[i].type == OP_NUM) { s.push(a[i].value); } else { int right = s.top();// 注意 壓棧 與表達(dá)式 順序不同 s.pop(); int left = s.top(); s.pop(); switch (a[i].value) { case ADD: s.push(left + right); break; case SUB: s.push(left - right); break; case MUL: s.push(left * right); break; case DIV: s.push(left / right); break; } } } return s.top(); } void TestRnp() { Cell a[] = { {OP_NUM, 12}, {OP_NUM, 3}, {OP_NUM, 4}, {OP_SYMBOL, ADD}, {OP_SYMBOL, MUL}, {OP_NUM, 6}, {OP_SYMBOL, SUB}, {OP_NUM, 8}, {OP_NUM, 2}, {OP_SYMBOL, DIV}, {OP_SYMBOL, ADD} }; int ret = CountRNP(a, sizeof(a)/sizeof(a[0])); } int main() { TestRnp(); return 0; } //////////////////////////////////////////////////// //////////////////////////////////////////////////// //----------------迷宮 遞歸法（不用棧）--------- // 遞歸法 不需要棧 bool MazePath(int* a, int n, Pos cur) { // 定義數(shù)組 最下邊為 出口 if (cur._row == n - 1 && a[cur._row * n + cur._col] == 0) // 判斷是否到出口 { a[cur._row * n +cur._col] = 2; // 2 表示此路可走 return true; } if (CheckIsAccess(a, n, cur)) { a[cur._row * n +cur._col] = 2; // 2 表示此【點(diǎn)】可走 下一步還不知道 Pos next_left = cur; next_left._col--; Pos next_right = cur; next_right._col++; Pos next_up = cur; next_up._row--; Pos next_down = cur; next_down._row++; bool next = (MazePath((int*)a, n, next_up) || MazePath((int*)a, n, next_right) || MazePath((int*)a, n, next_down) || MazePath((int*)a, n, next_left)); if (!next) { a[cur._row * n +cur._col] = 5; //5表示 下一步走不出去 把當(dāng)前點(diǎn)從2變到五 表示這個點(diǎn)走不出去 return false; } else { return true; } } else //cur 不能走 { return false; } } 2 表示成功路線 5 表示 嘗試失敗的路線 ///////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////// //--------------------迷宮 （最短路） --------------- //-------------------Maze.h-------------------- #pragma once #define N 10 #define DEBUGE 0 // 1 調(diào)試 0 不調(diào)試 #define MAZEPATH "MazeMap.txt" #include using namespace std; #include #include struct Pos { int _row; int _col; }; //stack void GetMaze(int* a, int n); void PrintMaze(int* a, int n); bool MazePath(int* a, int n, const Pos entry, stack bool FindMinPath(int* a, int n, const Pos entry ,stack int GetCount(stack //---------------------------Maze.cpp----------------- #define _CRT_SECURE_NO_WARNINGS 1 // 棧應(yīng)用2：迷宮(n*n)問題 #include "Maze.h" void GetMaze(int* a, int n) { FILE* f_out = fopen(MAZEPATH, "r"); assert(f_out != NULL); for (int i = 0; i < n; i++) { for (int j = 0; j < n; ) { char ch = fgetc(f_out); if (ch == '0' || ch == '1') //通路為0 不通路2 { a[i*n + j] = ch - '0'; ++j; } else { continue; } } } fclose(f_out); } void PrintMaze(int* a, int n) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++ ) { cout< } cout< } } bool CheckIsAccess(const int *a, int n, const Pos& next) //判斷路通不通 { assert(a); if (next._row >= 0 && next._row < n && next._col >= 0 && next._col < n && a[next._row * n + next._col] == 0)// 0 表示路通 { return true; } else { return false; } } // const Pos entry 入口 , stack bool MazePath(int* a, int n, const Pos entry, stack { Pos cur = entry; path.push(cur); while (!path.empty()) // 無路走時?？?/p> { a[cur._row * n + cur._col] = 2;// 走過的路標(biāo)記 2 // 定義數(shù)組 最下邊為 出口 if (cur._row == n - 1) // 判斷是否到出口 { return true; } Pos 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._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; } // 走不通 a[cur._row * n + cur._col] = 5;// 標(biāo)出錯誤路線 path.pop(); if (!path.empty()) { cur = path.top(); } } return false; } int GetCount(stack { int count = 0; while(!path.empty()) { count += 1; path.pop(); } return count; } void huanyuan(int* a,int n, stack { while(!Path.empty()) { a[Path.top()._row * n + Path.top()._col] = 0; Path.pop(); } } bool FindMinPath(int* a, int n, const Pos entry,stack { bool next = false; bool ret = false; do { stack next = MazePath(a, n, entry, path); //----------------debuge---------- #if DEBUGE cout<<"-----------------------------"< PrintMaze(a,n); #endif if (next) { if (MinPath.empty()) { MinPath = path; } else { if (GetCount(MinPath) > GetCount(path)) { MinPath = path; // 更新MinPath } } huanyuan((int*)a, n, path);// 將已經(jīng)走過的路 2 標(biāo)記為 0 a[path.top()._row * n + path.top()._col] = 9; // 此出口已經(jīng)堵住 //--------------debuge--------- #if DEBUGE cout<<"-------------huanyuan----------------"< PrintMaze(a,n); #endif ret = true; } }while(next); if (ret) { huanyuan(a, n, MinPath); //a[MinPath.top()._row * n + MinPath.top()._col] = 2; //打開這個最短路出口 } return ret; } //--------------------------------test.cpp----------------- #define _CRT_SECURE_NO_WARNINGS 1 #include "Maze.h" void TestMaze() { int a[N][N] = {}; GetMaze((int*)a, N); PrintMaze((int*)a, N); stack stack Pos entry = {2, 0}; FindMinPath((int*)a, N, entry ,MinPath); cout<<"------------------------------"< PrintMaze((int*)a, N); } int main() { TestMaze(); getchar(); return 0; } //----------------------------MazeMap.txt--------------------- 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 1 運(yùn)行圖： 到此，相信大家對“C++中棧的應(yīng)用”有了更深的了解，不妨來實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！ 另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。
當(dāng)前題目：C++中棧的應(yīng)用-創(chuàng)新互聯(lián)
新聞來源：http://weahome.cn/article/djpejp.html
重慶分公司
重慶分公司
