棧的妙用-實(shí)現迷宮問(wèn)題

實(shí)質(zhì)上棧的運用并不是只能在函數調用中，棧作為一種數據結構，自然有其特殊的意義，棧的最大特點(diǎn)是"先入后出，后入先出"，這個(gè)特點(diǎn)可以用來(lái)結局很多的問(wèn)題。C語(yǔ)言中的函數調用算是其中的最主要的用法之一，也就不再分析和討論。同樣遞歸，嵌套調用等都屬于函數調用的子類(lèi)也不再描述。在其他方面經(jīng)典的運用是解決迷宮問(wèn)題，不同進(jìn)制數值之間的轉換，長(cháng)字符串的分解以及算術(shù)表達式的求值等。下面我主要采用棧實(shí)現經(jīng)典的迷宮問(wèn)題。
迷宮問(wèn)題
迷宮問(wèn)題是經(jīng)典的一類(lèi)問(wèn)題，如何從給出的入口找到對應的出口，實(shí)現的方法和馬踏棋盤(pán)問(wèn)題相似也是通過(guò)找到周?chē)?個(gè)方向坐標的關(guān)系，然后依據深度優(yōu)先搜索方法和一定的條件找到下一步對應的出路。由于迷宮問(wèn)題需要存儲具體的完成路勁，這與前面的問(wèn)題存在一定的差別。采用棧能夠很好的解決這個(gè)問(wèn)題，其中棧結構用來(lái)存儲具體的坐標和方向。這樣根據棧就能保證以后每一次都能快速的找到出路。
實(shí)現的基本步驟如下：
1、為了避免邊界檢測問(wèn)題，在迷宮的外圍添加一層圍墻，比如原來(lái)的迷宮為m*n,則添加圍墻以后的矩陣為(m+2)*(n+2)。其中為1表示不能走通，0時(shí)表示可以走通。這樣maze[1][1]表示迷宮的入口，而maze[m][n]表示迷宮的出口。
2、創(chuàng )建一個(gè)堆?？臻g，可以采用靜態(tài)數組的方式，但由于不能準確的估計數組空間大小，可以采用動(dòng)態(tài)創(chuàng )建的方式。并將入口坐標值壓入到棧中。定義一個(gè)與迷宮大小相同的矩陣mark，用來(lái)統計當前坐標是否已經(jīng)到達過(guò)，當沒(méi)有到達坐標（i,j）時(shí)，則有mark[i][j] = 0,如果之前到達過(guò)，則有mark[i][j] = 1.這樣主要是為了避免形成內部死循環(huán)，同時(shí)說(shuō)明此路不能走通。
3、檢測?？臻g是否為空，如果為空則停止，如果不為空，則彈出棧頂的元素.
4、采用循環(huán)的方式，依據元素的方向確定下一個(gè)坐標，具體的確定方法依據之前的移動(dòng)關(guān)系找到，判斷該位置是否為0（maze[nextrow][nextcol] == 0）以及之前是否到達該位置(mark[nextrow][nextcol] == 1)。如果滿(mǎn)足條件，則將mark[nextrow][newcol]設置為1，并將當前位置以及具體的方向值壓入棧中，將當前坐標設置為之前確定的下一個(gè)坐標，設置方向為0。然后重新進(jìn)行步驟4。如果8個(gè)方向全部不能找到合適的下一個(gè)坐標，說(shuō)明此路走不通。重新進(jìn)行步驟3，探索新的路勁。探索成功的條件是(nextrow == EXIT_ROW&&nextcol == EXIT_COL)。

基本的實(shí)現流程圖如下所示：

代碼實(shí)現如下：

/*maze_problem.h*/
#ifndef MAZE_PROBLEM_H_H_
#define MAZE_PROBLEM_H_H_

typedef struct
{
int vert;
int horiz;
}offsets;

typedef struct {
int row;
int col;
int dir;
}element;

typedef struct {
int row;
int col;
}coordinate;
#endif

/*maze_problem.c*/
#include "maze_problem.h"

#include
#include

offsets move[8];

/*the stack save the path, and used */
element * stack;
int top = -1;

void initial_move(void)
{
/*horiz means cols*/
move[0].horiz = 0;
/*vert means rows*/
move[0].vert = -1;

move[1].horiz = 1;
move[1].vert = -1;

move[2].horiz = 1;
move[2].vert = 0;

move[3].horiz = 1;
move[3].vert = 1;

move[4].horiz = 0;
move[4].vert = 1;

move[5].horiz = -1;
move[5].vert = 1;

move[6].horiz = -1;
move[6].vert = 0;

move[7].horiz = -1;
move[7].vert = -1;
}
#define MAZE_ROWS 12
#define MAZE_COLS 15

#define NEW_MAZE_ROWS (MAZE_ROWS + 2)
#define NEW_MAZE_COLS (MAZE_COLS + 2)
#define EXIT_COL 15
#define EXIT_ROW 12

int maze[NEW_MAZE_ROWS][NEW_MAZE_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,1,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,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,
};