C++中栈的应用-创新互联

本篇内容主要讲解“C++中栈的应用”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“C++中栈的应用”吧!

成都创新互联公司主要从事网页设计、PC网站建设（电脑版网站建设）、wap网站建设（手机版网站建设）、响应式网站设计、程序开发、网站优化、微网站、小程序设计等，凭借多年来在互联网的打拼，我们在互联网网站建设行业积累了丰富的成都做网站、网站设计、外贸营销网站建设、网站设计、网络营销经验，集策划、开发、设计、营销、管理等多方位专业化运作于一体。

1、栈的应用1 解决迷宫问题

问题：一个n*n的0、1矩阵，0 表示可以走通，1表示不可以走，假定矩阵的下边是出口，给定矩阵的入口坐标，求出走出迷宫的路径

C++中栈的应用

这里用栈主要是解决如图所示走不出去会退时上一步（出栈）位置的记录

以及记录已经走过的路径（压栈）

C++中栈的应用

扩展：(1) 非递归法实现

（递归法与非递归的一点不同

递归法不会出现尝试下一步失败后退到上一步再次尝试下一步时不会出现重复尝试上一次走错的那个“下一步” 而下面使用栈的方式的退栈时下一步尝试还会判断已走过不成功的情况【重复判断一次】）

(2) 多个出口最短路问题【在下面实现】

//-----------------Maze.h---------

#pragma once

#define N 10

#define MAZEPATH "MazeMap.txt"

#include

using namespace std;

#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& path);

//-----------------Maze.cpp-----------

#define _CRT_SECURE_NO_WARNINGS 1

// 栈应用：迷宫(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& path 用于压路径的栈

bool MazePath(int* a, int n, const Pos entry, stack& path)

{

Pos cur = entry;

path.push(cur);

while (!path.empty()) // 无路走时栈空

{

a[cur._row * n + cur._col] = 2;// 走过的路标记 2

// 定义数组最下边为出口

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;// 标出错误路线

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 path;

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

0 0 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 1 1 1

//////////////////////////////////////////////////////////////////////

/////////////////////////////////////////////////////////////////////

2、栈的应用2 逆波兰式计算

C++中栈的应用

#define _CRT_SECURE_NO_WARNINGS 1

#include

using namespace std;

// 栈的应用 2 算数表达式求解

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 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();// 注意压栈与表达式顺序不同

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)

{

// 定义数组最下边为出口

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 表示此【点】可走下一步还不知道

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表示下一步走不出去把当前点从2变到五表示这个点走不出去

return false;

}

else

{

return true;

}

else //cur 不能走

{

return false;

}

C++中栈的应用

2 表示成功路线

5 表示尝试失败的路线

/////////////////////////////////////////////////////////////

///////////////////////////////////////////////////////////

//--------------------迷宫（最短路） ---------------

//-------------------Maze.h--------------------

#pragma once

#define N 10

#define DEBUGE 0 // 1 调试 0 不调试

#define MAZEPATH "MazeMap.txt"

#include

using namespace std;

#include

struct Pos

{

int _row;

int _col;

};

//stack MinPath;

void GetMaze(int* a, int n);

void PrintMaze(int* a, int n);

bool MazePath(int* a, int n, const Pos entry, stack& path);

bool FindMinPath(int* a, int n, const Pos entry ,stack& MinPath);

int GetCount(stack path);

//---------------------------Maze.cpp-----------------

#define _CRT_SECURE_NO_WARNINGS 1

// 栈应用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& path 用于压路径的栈

bool MazePath(int* a, int n, const Pos entry, stack& path)

{

Pos cur = entry;

path.push(cur);

while (!path.empty()) // 无路走时栈空

{

a[cur._row * n + cur._col] = 2;// 走过的路标记 2

// 定义数组最下边为出口

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;// 标出错误路线

path.pop();

if (!path.empty())

{

cur = path.top();

}

return false;

}

int GetCount(stack path)

{

int count = 0;

while(!path.empty())

{

count += 1;

path.pop();

}

return count;

}

void huanyuan(int* a,int n, stack 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& MinPath)

{

bool next = false;

bool ret = false;

{

stack path;

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);// 将已经走过的路 2 标记为 0

a[path.top()._row * n + path.top()._col] = 9; // 此出口已经堵住

//--------------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 path;

stack MinPath;

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

0 0 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

运行图：

到此，相信大家对“C++中栈的应用”有了更深的了解，不妨来实际操作一番吧！这里是创新互联网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。

新闻标题：C++中栈的应用-创新互联
标题来源：http://pwwzsj.com/article/djpejp.html

其他资讯

为什么选择SpringBoot项目的内嵌容器
jQuery如何实现返回顶部按钮和scroll滚动功能
Java实现文件上传至服务器的方法
如何实现虚拟主机申请网站备案
git安装编译安装