《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》棧的應(yīng)用之迷宮求解
清華大學(xué)計(jì)算機(jī)系列教材? ?累計(jì)發(fā)行超400萬(wàn)冊(cè)
嚴(yán)蔚敏 吳偉明 編著
數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）?
以下是本人對(duì)紫皮書(shū)第三章3.2節(jié)棧的應(yīng)用舉例中3.2.4迷宮求解的代碼，3.2.1數(shù)制轉(zhuǎn)換、3.2.2括號(hào)匹配的檢驗(yàn)、3.2.3行編輯程序的代碼已在上一節(jié)寫(xiě)出，話不多說(shuō)上運(yùn)行結(jié)果：
可執(zhí)行代碼如下
（貌似專欄把我縮進(jìn)吃了，懶得加了，另外建議用visual studio編譯）?
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define STACK_INIT_SIZE 100//存儲(chǔ)空間初始分配量
#define STACKINCREMENT 10//存儲(chǔ)空間分配增量
#define LENGTH 10
#define WIDTH 10
typedef int Status;
typedef int MazeType[LENGTH][WIDTH];//迷宮大小
typedef struct
{
int row;//行
int col;//列
}PosType;
typedef struct
{
int ord;//通道塊在路徑上的“序號(hào)”
PosType seat;//通道快在迷宮中的“坐標(biāo)位置”
int di;//從此通道塊走向下一通道塊的“方向”
//1表示東，2表示南，3表示西，4表示北
}SElemType;//棧的元素類型
typedef struct
{
SElemType* base;
SElemType* top;
int stacksize;
}SqStack;
void FootPrint(PosType curpos, int curstep);//留下足跡
void ShowMaze(PosType start);//打印地圖
Status Pass(PosType pos);//判斷當(dāng)前位置是否可以通過(guò)
PosType NextPos(PosType CurPos, int i);//返回下一位置
void MarkPrint(PosType pos);//標(biāo)記走不通的位置
Status MazePath(MazeType maze, PosType start, PosType end);//若迷宮中存在從入口start到出口end的通道，則求得一條存放在棧中
Status InitStack(SqStack& S);//初始化一個(gè)空棧
Status Push(SqStack& S, SElemType e);//順序棧的入棧
Status Pop(SqStack& S, SElemType& e);//順序棧的出棧
Status StackEmpty(SqStack S);//判斷棧是否為空
//用全局變量表示迷宮地圖
MazeType maze =
{
/*用0表示墻，用1表示路*/
? ?//0,1,2,3,4,5,6,7,8,9
{0,0,0,0,0,0,0,0,0,0}, //0
{0,1,1,0,1,1,1,0,1,0}, //1
{0,1,1,0,1,1,1,0,1,0}, //2
{0,1,1,1,1,0,0,1,1,0}, //3
{0,1,0,0,0,1,1,1,1,0}, //4
{0,1,1,1,0,1,1,1,1,0}, //5
{0,1,0,1,1,1,0,1,1,0}, //6
{0,1,0,0,0,1,0,0,1,0}, //7
{0,0,1,1,1,1,1,1,1,0}, //8
{0,0,0,0,0,0,0,0,0,0}? //9
};
int main()
{
printf("迷宮地圖如下：\n");
PosType Start = { 1,1 };
PosType End = { 8,8 };
ShowMaze(Start);
if (MazePath(maze, Start, End))
{
printf("該迷宮的一條通路為：\n");
ShowMaze(Start);
}
return 0;
}
void FootPrint(PosType curpos, int curstep)//留下足跡
{
maze[curpos.row][curpos.col] = curstep;
}
void ShowMaze(PosType start)//打印地圖
{
for (int i = 0; i < LENGTH; i++)
{
for (int j = 0; j < 10; j++)
{
if (i == start.row && j == start.col)//打印起始位置
{
printf("1 ");
}
else if (maze[i][j] == 0)
{
printf("■");
}
else if (maze[i][j] == 1 || maze[i][j] == -1)
{
printf("? ");
}
else
{
printf("%-2d", maze[i][j]);
}
}
printf("\n");
}
}
Status Pass(PosType pos)//判斷當(dāng)前位置是否可以通過(guò)
{
if (maze[pos.row][pos.col] == 1)
{
return TRUE;
}
return FALSE;
}
PosType NextPos(PosType CurPos, int i)//返回下一位置
{
switch (i)
{
case 1:
++CurPos.col;//向東走一步
break;
case 2:
++CurPos.row;//向南走一步
break;
case 3:
--CurPos.col;//向西走一步
break;
case 4:
--CurPos.row;//向北走一步
break;
}
return CurPos;
}
void MarkPrint(PosType pos)//標(biāo)記走不通的位置
{
maze[pos.row][pos.col] = -1;//-1表示該位置走不通
}
Status MazePath(MazeType maze, PosType start, PosType end)//若迷宮中存在從入口start到出口end的通道，則求得一條存放在棧中
{
SqStack S;
PosType curpos;//cur為current的縮寫(xiě)，表示當(dāng)前位置(position)
SElemType e;
int curstep;//表示當(dāng)前走過(guò)的步數(shù)
InitStack(S);
curpos = start;//設(shè)定“當(dāng)前位置”為“入口位置”
curstep = 1;//記錄當(dāng)前走過(guò)的步數(shù)
do
{
if (Pass(curpos))//當(dāng)前位置可以通過(guò)，即是未曾走到過(guò)的通道塊
{
FootPrint(curpos, curstep);//留下足跡
printf("step%d:\t(%d,%d)\n", curstep, curpos.col, curpos.row);
e = { curstep,curpos,1 };//1表示當(dāng)前方位為東
Push(S, e);//加入路徑
if (curpos.col == end.col && curpos.row == end.row)//到達(dá)終點(diǎn)（出口）
{
printf("到達(dá)終點(diǎn)：(%d,%d)\n", e.seat.col, e.seat.row);
return TRUE;
}
curpos = NextPos(curpos, 1);//下一位置是當(dāng)前位置的東鄰
curstep++;
//ShowMaze(start);//可以打開(kāi)這一步注釋看看具體每一步代碼是怎么走的
}
else//當(dāng)前位置不能通過(guò)
{
if (!StackEmpty(S))
{
Pop(S, e);
while (e.di == 4 && !StackEmpty(S))//如果
{
MarkPrint(e.seat);
Pop(S, e);//留下不能通過(guò)的標(biāo)記，并退回一步
curstep--;
printf("倒退一步到step%d:(%d, %d)\n",curstep-1, e.seat.col, e.seat.row);
}
if (e.di < 4)
{
e.di++;//換下一個(gè)方向探索
Push(S, e);
curpos = NextPos(e.seat, e.di);//設(shè)定當(dāng)前位置是該新方向上的相鄰塊
}
}
}
} while (!StackEmpty(S));//如果棧空表示所有方向都不通
printf("對(duì)不起，找不到出口");
return FALSE;
}
/*以下代碼沿用上一節(jié)棧的基本功能*/
Status InitStack(SqStack& S)//初始化一個(gè)空棧
{
S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if (!S.base)
{
exit(OVERFLOW);
}
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
Status Push(SqStack& S, SElemType e)//順序棧的入棧
{
if (S.top - S.base >= S.stacksize)
{
SElemType* New_ptr = (SElemType*)realloc(S.base, ((S.stacksize) + STACKINCREMENT) * sizeof(SElemType));
if (!New_ptr)
{
exit(OVERFLOW);
}
S.base = New_ptr;
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return OK;
}
Status Pop(SqStack& S, SElemType& e)//順序棧的出棧
{
if (S.top == S.base)
{
return ERROR;
}
e = *--S.top;
return OK;
}
Status StackEmpty(SqStack S)//判斷棧是否為空
{
if (S.top == S.base)
{
return TRUE;
}
else
{
return FALSE;
}
}
