迷宫问题（堆栈及其应用）

矫情吗；* 2022-08-27 04:43 109阅读 0赞

首先我们来看看堆栈这个数据结构，像朱老师曾经说的那样堆栈是一个单腔生物，想想一个场景，有一个笔直的路，最远端是死胡同。我们现在让车一个一个的进去，那要出来的的时候必须是后进去的先出来（push和pop操作）。对于堆栈这样的数据结构有这些操作：  
            1.堆栈的初始化和销毁；  
            2.堆栈清空；  
            3.判断堆栈是否为空；  
            4.返回栈顶元素；  
            5.得到堆栈内元素的个数；  
            6.压栈与出栈；  
  
            堆栈的应用方面非常广泛，例如：数值转换，括号匹配，行编辑程序，迷宫问题和表达式等。  
            无论是那种应用，都要记住堆栈的最大的功能是：记忆！！！  
            下面是堆栈的代码，我这个里面没有判断堆栈是否为满，如果堆栈元素等于申请个数时，堆栈会追加10个元素，这个可以修改。让对内存的申请达到合适的数量。如果要用堆栈时，把头文件预处理就行了。  
              
        一.  STACK.H

\#ifndef \_STACK\_H\_

\#define \_STACK\_H\_

\#include<malloc.h>

\#include<stdlib.h>

\#define TRUE 1

\#define FALSE 0

\#define STACKINCREMENT  10

typedef struct STACK

USER\_TYPE \*top; //栈顶指针

USER\_TYPE \*base; //栈底指针

int maxRoom;

\}STACK;

typedef unsigned char Boolean;

STACK \*initStack(int maxRoom); //初始化堆栈

void destroyStack(STACK \*\*sta); //销毁堆栈

Boolean isStackEmpty(STACK sta); //判断堆栈是否为空

void clearStack(STACK \*sta); //清空堆栈信息

int stackLength(STACK sta); //返回堆栈内元素个数

Boolean getStackTop(STACK sta, USER\_TYPE \*element); //得到栈顶元素

Boolean push(STACK \*sta, USER\_TYPE element); //入栈

Boolean pop(STACK \*sta, USER\_TYPE \*element); //出栈

Boolean pop(STACK \*sta, USER\_TYPE \*element)

Boolean OK = TRUE;

if(isStackEmpty(\*sta) == FALSE)

\*element = \*(sta->top - 1);

sta->top--;

else

OK = FALSE;

return OK;

Boolean push(STACK \*sta, USER\_TYPE element)

Boolean OK = TRUE;

if( (sta->top - sta->base) >= sta->maxRoom)

sta->base = (USER\_TYPE \*)realloc(sta->base,

(sta->maxRoom + STACKINCREMENT) \* sizeof(USER\_TYPE));

if(sta->base == NULL)

exit(1); //存储分配失败

sta->top = sta->base + sta->maxRoom;

sta->maxRoom += STACKINCREMENT;

\*sta->top = element;

sta->top++;

return OK;

Boolean getStackTop(STACK sta, USER\_TYPE \*element)

Boolean OK = TRUE;

if(isStackEmpty(sta) == FALSE)

\*element = \*(sta.top - 1);

else

OK = FALSE;

return OK;

int stackLength(STACK sta)

return sta.top - sta.base;

void clearStack(STACK \*sta)

sta->top = sta->base;

Boolean isStackEmpty(STACK sta)

return sta.top == sta.base;

void destroyStack(STACK \*\*sta)

if((\*sta)->base)

free((\*sta)->base);

(\*sta)->top = NULL;

free(\*sta);

STACK \*initStack(int maxRoom)

STACK \*stack;

stack = (STACK \*)malloc(sizeof(STACK));

if(stack == NULL)

exit(1);

else

stack->maxRoom = maxRoom;

stack->base = (USER\_TYPE \*)malloc(sizeof(USER\_TYPE) \* maxRoom);

if(stack->base == NULL)

exit(0);

stack->top = stack->base;

return stack;

\#endif

二. 迷宫问题  
              
            迷宫问题跟那个电老鼠有很多相似之处，但只是在软件级别上的问题，简单了不少。迷宫问题要解决一下几个方面：  
            1.如何存储合理位置的信息（当然是用堆栈了）；  
            2.移动方向的判断（这个和醉酒螳螂有着极大的相似之处，还是把八个方向用一个结构体数组存储，看来这个方法经常用啊）；  
            3.不可以在迷宫上直接操作，需要用另外一个二维数组动态显示位置变化；  
  
            还需解决的问题：  
              
            如何动态的生成一个迷宫？以后再看；  
            迷宫搜索算法有没有比单方向查找更快的方法？大家一起看；  
              
            迷宫的代码就摆出来了。。。  
  
  
 /\*

迷宫问题：使用到了堆栈，原理是对的，但是在显示的时候太过狗血，而且路径没有正向输出，大家凑活着看吧。。。。

\*/

\#include<stdio.h>

\#include<conio.h>

\#include<windows.h>

typedef struct OFFSETS

short int vert; //横方向

short int horiz; //纵方向

\}OFFSETS;

//要保存的每个节点信息

typedef struct element

short int row;

short int col;

short int direct;

\}element;

typedef element USER\_TYPE;

\#include"STACK.H" //堆栈

\#define MAZE\_ROWS 11 //迷宫行数

\#define MAZE\_COLS 15 //迷宫列数

\#define BOUNDARY\_COLS  17 //边界列数

\#define BOUNDARY\_ROWS  13 //边界行数

\#define FALSE 0

\#define TRUE 1

//生成一个迷宫的图形(这尼玛是要累死人啊！！！)

static short int maze\[BOUNDARY\_ROWS\]\[BOUNDARY\_COLS\] =

\{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1\},

\{1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1\},

\{1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1\},

\{1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1\},

\{1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1\},

\{1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1\},

\{1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1\},

\{1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1\},

\{1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1\},

\{1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1\},

\{1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1\},

\{1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1\},

\{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1\},

\};

//该矩阵是为了记录已经检查过的迷宫位置，元素初始化都为0

static short int mark\[BOUNDARY\_ROWS\]\[BOUNDARY\_COLS\] = \{0\};

OFFSETS move\[8\]; /\*当前点对应的八个方向\*/

STACK \*nodeStack;

void initMove(void);  //初始化各方向

void showMaze(void);  //显示迷宫

void foundPath(); //寻找路径

void printOneNode(int row, int col, int direct); //打印一个节点

void showMark(void);  //显示路径

void showMark(void)

int i, j;

for(i = 0; i < BOUNDARY\_ROWS; i++)

for(j = 0; j < BOUNDARY\_COLS; j++)

if(mark\[i\]\[j\] == 1)

printf("%3c", 5);

else

printf("%3c", 3);

printf("\\n");

void printOneNode(int row, int col, int direct)

printf("%2d    %2d%5d", direct, row, col);

switch(direct - 1)

case 0:

printf("    北边");

break;

case 1:

printf("    东北");

break;

case 2:

printf("    东边");

break;

case 3:

printf("    东南");

break;

case 4:

printf("    南边");

break;

case 5:

printf("    西南");

break;

case 6:

printf("    西边");

break;

case 7:

printf("    西北");

break;

printf("\\n");

void foundPath()

int i, row, col, nextRow, nextCol, direct, count;

int found = FALSE; //初始化为没有找到出口

USER\_TYPE position;

mark\[1\]\[1\] = 1; //开始处于（1，1）迷宫入口

position.row = 1, position.col = 1, position.direct = 0;

push(nodeStack, position);

//节点栈不为空并且没有找到出口

while(isStackEmpty(\*nodeStack) == FALSE && found == FALSE)

pop(nodeStack, &position);

row = position.row;

col = position.col;

direct = position.direct;

while(direct < 8 && found == FALSE)

nextRow = row + move\[direct\].vert;

nextCol = col + move\[direct\].horiz;

//如果找到了出口

if(nextRow == MAZE\_ROWS + 1 && nextCol == MAZE\_COLS + 1)

found = TRUE;

//当前点没有被检查过

else if(!maze\[nextRow\]\[nextCol\]

&& !mark\[nextRow\]\[nextCol\])

mark\[nextRow\]\[nextCol\] = 1;

position.row = row;

position.col= col;

position.direct = ++direct;

push(nodeStack, position); //将这个节点保存

row = nextRow;

col = nextCol;

direct = 0;

system("cls");

showMaze();

printf("\\n");

printf("上一个图为迷宫图，下一个图是寻找路径的过程\\n");

showMark();

Sleep(200); //停顿一秒

else

direct++; //换个方向测试

if(found == FALSE)

printf("该迷宫没有路径可以出去！");

else

count = stackLength(\*nodeStack);

printf("该迷宫的出口路径是：\\n\\n");

printf("dir\#  rol  col  direct\\n\\n");

//打印出路径

for(i = 0; i < count; i++)

pop(nodeStack, &position);

printOneNode(position.row, position.col, position.direct);

void showMaze(void)

int i, j;

for(i = 0; i < BOUNDARY\_ROWS; i++)

for(j = 0; j < BOUNDARY\_COLS; j++)

if(maze\[i\]\[j\] == 1)

printf("%3c", 3);

else

printf("%3c", 5);

printf("\\n");

void initMove(void)

move\[0\].vert = -1, move\[0\].horiz = 0; /\* 北边 \*/

move\[1\].vert = -1, move\[1\].horiz = 1; /\* 东北 \*/

move\[2\].vert = 0, move\[2\].horiz = 1; /\* 东边 \*/

move\[3\].vert = 1, move\[3\].horiz = 1; /\* 东南 \*/

move\[4\].vert = 1, move\[4\].horiz = 0; /\* 南边 \*/

move\[5\].vert = 1, move\[5\].horiz = -1; /\* 西南 \*/

move\[6\].vert = 0, move\[6\].horiz = -1; /\* 西边 \*/

move\[7\].vert = -1, move\[7\].horiz = -1; /\* 西北 \*/

int main(int argc, char \*\*argv)

nodeStack = initStack(20); //初始化堆栈（起始数量为20个，如果堆栈内元素判满时，自动追加10个元素）

initMove(); //初始化各方向

showMaze(); //显示迷宫

foundPath(); //寻找路径

destroyStack(&nodeStack);

getch();

return 0;

\}  
  
  
  
关于堆栈的用法肯定会是多种多样的，咱们一起来探索。

迷宫问题（堆栈及其应用）

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关迷宫问题

相关迷宫问题

相关迷宫问题（堆栈及其应用）

相关迷宫问题

相关迷宫问题

相关算法——算术表达式计算问题（堆栈典型应用）

相关走迷宫问题

相关迷宫问题（上）之堆栈详解（C语言描述）

相关迷宫问题

相关二分及其典型应用问题