C++中棧的應(yīng)用
本篇內(nèi)容主要講解“C++中棧的應(yīng)用”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“C++中棧的應(yīng)用”吧!
創(chuàng)新互聯(lián)公司專業(yè)為企業(yè)提供祿豐網(wǎng)站建設(shè)、祿豐做網(wǎng)站、祿豐網(wǎng)站設(shè)計(jì)、祿豐網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)與制作、祿豐企業(yè)網(wǎng)站模板建站服務(wù)，10年祿豐做網(wǎng)站經(jīng)驗(yàn)，不只是建網(wǎng)站，更提供有價(jià)值的思路和整體網(wǎng)絡(luò)服務(wù)。
1、棧的應(yīng)用1 解決迷宮問(wèn)題
問(wèn)題：一個(gè)n*n的0、1矩陣，0 表示可以走通，1表示不可以走 ，假定矩陣的下邊是出口，給定矩陣的入口坐標(biāo)，求出走出迷宮的路徑
這里用 棧 主要是解決 如圖所示 走不出去 會(huì)退時(shí)上一步（出棧） 位置的記錄
以及 記錄已經(jīng)走過(guò)的路徑（壓棧）
擴(kuò)展 ：(1) 非遞歸法實(shí)現(xiàn)
（遞歸法 與 非遞歸 的 一點(diǎn)不同
遞歸法不會(huì)出現(xiàn) 嘗試下一步失敗后 退到上一步 再次嘗試下一步時(shí) 不會(huì)出現(xiàn) 重復(fù)嘗試上一次走錯(cuò)的那個(gè)“下一步” 而 下面使用 棧的方式的 退棧時(shí) 下一步嘗試還會(huì)判斷 已走過(guò)不成功的情況【重復(fù)判斷一次】）
(2) 多個(gè)出口 最短路問(wèn)題 【在下面實(shí)現(xiàn)】
//-----------------Maze.h---------
#pragma once
#define N 10
#define MAZEPATH "MazeMap.txt"
#include<iostream>
using namespace std;
#include <assert.h>
#include <stack>
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<Pos>& path);
//-----------------Maze.cpp-----------
#define _CRT_SECURE_NO_WARNINGS 1
// 棧應(yīng)用：迷宮(n*n)問(wè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<<a[i * n + j]<<" ";
}
cout<<endl;
}
}
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<Pos>& path 用于壓路徑的 棧
bool MazePath(int* a, int n, const Pos entry, stack<Pos>& path)
{
Pos cur = entry;
path.push(cur);
while (!path.empty()) // 無(wú)路走時(shí)棧空
{
a[cur._row * n + cur._col] = 2;// 走過(guò)的路標(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)出錯(cuò)誤路線
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> path;
Pos entry = {2, 0};
MazePath((int*)a, N, entry, path);
cout<<"------------------------------"<<endl;
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<iostream>
#include<assert.h>
#include<stack>
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<int> s;
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變到五 表示這個(gè)點(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<iostream>
using namespace std;
#include <assert.h>
#include <stack>
struct Pos
{
int _row;
int _col;
};
//stack<Pos> MinPath;
void GetMaze(int* a, int n);
void PrintMaze(int* a, int n);
bool MazePath(int* a, int n, const Pos entry, stack<Pos>& path);
bool FindMinPath(int* a, int n, const Pos entry ,stack<Pos>& MinPath);
int GetCount(stack<Pos> path);
//---------------------------Maze.cpp-----------------
#define _CRT_SECURE_NO_WARNINGS 1
// 棧應(yīng)用2：迷宮(n*n)問(wè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<<a[i * n + j]<<" ";
}
cout<<endl;
}
}
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<Pos>& path 用于壓路徑的 棧
bool MazePath(int* a, int n, const Pos entry, stack<Pos>& path)
{
Pos cur = entry;
path.push(cur);
while (!path.empty()) // 無(wú)路走時(shí)?？?/p>
{
a[cur._row * n + cur._col] = 2;// 走過(guò)的路標(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)出錯(cuò)誤路線
path.pop();
if (!path.empty())
{
cur = path.top();
}
}
return false;
}
int GetCount(stack<Pos> path)
{
int count = 0;
while(!path.empty())
{
count += 1;
path.pop();
}
return count;
}
void huanyuan(int* a,int n, stack<Pos> Path) // Path不用引用
{
while(!Path.empty())
{
a[Path.top()._row * n + Path.top()._col] = 0;
Path.pop();
}
}
bool FindMinPath(int* a, int n, const Pos entry,stack<Pos>& MinPath)
{
bool next = false;
bool ret = false;
do
{
stack<Pos> path;
next = MazePath(a, n, entry, path);
//----------------debuge----------
#if DEBUGE
cout<<"-----------------------------"<<endl;
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)走過(guò)的路 2 標(biāo)記為 0
a[path.top()._row * n + path.top()._col] = 9; // 此出口已經(jīng)堵住
//--------------debuge---------
#if DEBUGE
cout<<"-------------huanyuan----------------"<<endl;
PrintMaze(a,n);
#endif
ret = true;
}
}while(next);
if (ret)
{
huanyuan(a, n, MinPath);
//a[MinPath.top()._row * n + MinPath.top()._col] = 2; //打開(kāi)這個(gè)最短路出口
}
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<Pos> path;
stack<Pos> MinPath;
Pos entry = {2, 0};
FindMinPath((int*)a, N, entry ,MinPath);
cout<<"------------------------------"<<endl;
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)行圖：
到此，相信大家對(duì)“C++中棧的應(yīng)用”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！
文章名稱：C++中棧的應(yīng)用
文章網(wǎng)址：http://bm7419.com/article6/igedog.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站策劃、虛擬主機(jī)、搜索引擎優(yōu)化、電子商務(wù)、網(wǎng)站導(dǎo)航、手機(jī)網(wǎng)站建設(shè)
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)
- 大眾組建車(chē)載軟件開(kāi)發(fā)部門(mén)，轉(zhuǎn)型之路任重而道遠(yuǎn) 2021-05-28
- 軟件開(kāi)發(fā)和網(wǎng)站開(kāi)發(fā)哪種好？?jī)烧哂惺裁磪^(qū)別？ 2022-05-29
- 自學(xué)編程面試技巧，軟件開(kāi)發(fā)？ 2022-03-30
- 軟件開(kāi)發(fā)的兩種開(kāi)發(fā)方式是完全不同的兩種東西，如果選擇軟件開(kāi)發(fā)方式。 2021-06-04
- APP開(kāi)發(fā)制作：醫(yī)療APP軟件開(kāi)發(fā)移動(dòng)端解決方案 2020-11-21
- app軟件開(kāi)發(fā)如何提升上帝視角和農(nóng)民視角能力 2020-11-28
- 手機(jī)app開(kāi)發(fā)工具，未來(lái)APP軟件開(kāi)發(fā)的趨勢(shì) 2023-03-01
- 河口區(qū)APP軟件開(kāi)發(fā)需要多少錢(qián)？ 2020-12-16
- 什么是軟件開(kāi)發(fā)中的過(guò)度設(shè)計(jì)？ 2016-09-06
- 手機(jī)app軟件開(kāi)發(fā)對(duì)企業(yè)和創(chuàng)業(yè)者有什么意義？ 2016-08-05
- 2019 年軟件開(kāi)發(fā)新趨勢(shì)必知！ 2019-08-07
- 影響APP軟件開(kāi)發(fā)周期長(zhǎng)短因素分析 2023-03-17