棧的定義
棧是一種只能在一端進行插入或刪除操作的線性表 表中允許進行插入、刪除操作的一端稱為棧頂(top)表的另一端稱為棧底(bottom)音榜。當棧中沒有數據元素時稱為空棧 棧的插入操作通常稱為進棧或入棧(push),棧的刪除操作通常稱為出棧或退棧(pop)。
棧的順序存儲結構及其基本運算的實現(xiàn)
采用順序結構存儲的棧稱為順序棧
typedef struct {
ElemType data[MaxSize];
int top;
}SqStack;
- 初始化棧
void InitStack(SqStack *&s)
{
s = (SqStack*)malloc(sizeof(SqStack));
s->top = -1;
}
- 銷毀棧
void DestroyStack(SqStack *&s)
{
free(s);
}
- 判斷棧是否為空
bool StackEmpty(SqStack *s)
{
return(s->top == -1);
}
- 進棧
bool Push(SqStack*&s, ElemType e)
{
if (s->top == MaxSize - 1)
return false;
s->top++;
s->data[s->top] = e;
return true;
}
- 出棧
bool Pop(SqStack*&s, ElemType &e)
{
if (s->top == -1)
return false;
e = s->data[s->top];
s->top--;
return true;
}
- 取棧頂元素
bool GetTop(SqStack *s, ElemType &e)
{
if (s->top == -1)
return false;
e = s->data[s->top];
return true;
}
棧的鏈式存儲結構及其基本運算的實現(xiàn)
采用鏈式存儲結構的棧稱為鏈棧
typedef struct linknode
{
ElemType data;
struct linknode *next;
}LinkStNode;
- 初始化棧
void InitStack(LinkStNode *&s)
{
s = (LinkStNode*)malloc(sizeof(LinkStNode));
s->next = NULL;
}
- 銷毀棧
void DestroyStack(LinkStNode *&s)
{
LinkStNode *pre = s,*p=s->next;
while (p != NULL)
{
free(pre);
pre = p;
p = pre->next;
}
free(pre);
}
- 判斷棧是否為空
bool StackEmpty(LinkStNode *s)
{
return(s->next = NULL);
}
- 進棧
void Push(LinkStNode *&s, ElemType e)
{
LinkStNode *p;
p = (LinkStNode*)malloc(sizeof(LinkStNode));
p->data = e;
p->next = s->next;
s->next = p;
}
- 出棧
bool Pop(LinkStNode *&s, ElemType &e)
{
LinkStNode *p;
if (s->next == NULL)
return false;
e = s->data;
p = s->next;
s->next = p->next;
free(p);
return true;
}
- 取棧頂元素
bool GetTop(LinkStNode *s, ElemType &e)
{
if (s->next == NULL)
return false;
e = s->data;
return true;
}
求解迷宮問題
問題描述
給定一個(M , N ) 的迷宮圖捧弃，求一條從指定入口到出口的迷宮路徑赠叼。假設一個迷宮圖如下圖所示，其中的每個方塊用空白表示通道塔橡，用陰影表示障礙物梅割。一般情況下，所求迷宮路徑是簡單路徑葛家，即在求得的迷宮路徑上不會重復出現(xiàn)同一方塊户辞。一個迷宮圖的迷宮路徑可能有多條，這里僅僅考慮用棧求一條從指定入口到出口的迷宮路徑癞谒。
數據組織
為了表示迷宮底燎，設置一個數組mg刃榨，其中每個元素表示一個方塊的狀態(tài)，為0時表示對應的方塊是通道双仍，為1時表示對應方塊時障礙物枢希。為了運算方便，一般在迷宮的外圍加一條圍墻朱沃。
#define M 8
#define N 8
int mg[M+2][N+2]=
{
{1,1,1,1,1,1,1,1,1,1},{1,0,0,1,0,0,0,1,0,1},
{1,0,0,1,0,0,0,1,0,1},{1,0,0,0,0,1,1,0,0,1},
{1,0,1,1,1,0,0,0,0,1},{1,0,0,0,1,0,0,0,0,1},
{1,0,1,0,0,0,1,0,0,1},{1,0,1,1,1,0,1,1,0,1},
{1,1,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,1}
};
在算法中用到的棧采用順序棧存儲結構
typedef struct{
int i;//當前方塊的行號
int j;//當前方塊的列號
int di;//di是下一相鄰可走方位的方位號
}Box;
typedef struct{
Box data[MaxSize];
int top;
}StType;
設計運算算法
- 對于迷宮中的每個方塊苞轿，有上、下逗物、左搬卒、右 4 個方塊相鄰，規(guī)定上方方塊為0翎卓，并按順時針方向遞增標號契邀。
- 求解迷宮問題采用的算法思想為“窮舉法”。即從入口出發(fā)失暴，按方位0到方位3的次序試探相鄰的方塊坯门，一旦找到一個可走的相鄰方塊就繼續(xù)走下去，并記下所走的方位逗扒。若沒有相鄰的可走方塊古戴，則沿原路退回到前一個方塊。
- 若一個非出口方塊是可走的矩肩，將它進棧允瞧，如果找到某個方位 的相鄰方塊是可走的，則將棧頂方塊的方位 di 置為d蛮拔。
- 在算法上應保證試探的相鄰可走方塊不是已走路徑上的方塊，因此在一個方塊進棧后將對應的 mg 數組元素值改為 -1 當退棧時將其恢復為 0
將入口(xi,yi)進棧(其初始方位設置為-1)
mg[xi][yi]=-1;
while(棧不為空)
{
取棧頂方塊(i,j,di);
if((i,j)是出口(xi,yi))
{
輸出棧中的全部方塊構成一條迷宮路徑
return true;
}
查找(i,j,di)的下一個相鄰可走方塊;
if(找到一個相鄰可走方塊)
{
該方塊為(i1,j1),對應方位d;
將棧頂方塊的di設置為d;
(i1,j1,-1)進棧;
mg[i1][j1]=-1;
}
if(沒有找到(i,j,di)的任何相鄰可走方塊)
{
將(i,j,di)出棧：
mg[i][j]=0;
}
}
return false; //沒有找到迷宮路徑
bool mgpath(int xi,int yi,int xe,int ye)
{
Box path[MaxSize],e;
int i,j,di,i1,j1,k;
bool find;
StType*st;
InitStack(st);
e.i=xi;e.j=yi;e.di=-1;
Push(st,e);
mg[xi][yi]=-1;
while(!StackEmpty(st))
{
GetTop(st,e);
i=e.i;j=e.j;di=e.di;
if(i==xe&&j==ye)
{
printf("一條迷宮路徑如下：\n");
k=0;
while(!StackEmpty(st))
{
Pop(st,e);
path[k++]=e;
}
while(k>=1)
{
k--;
printf("\t(%d,%d)",path[k].i,path[k].j);
if((k+2)%5==0)
printf("\n");
}
DestroyStack(st);
return true;
}
find=false;
while(di<4&&!find)
{
di++;
switch(di)
{
case 0: i1=i-1;j1=j;break;
case 1: i1=i;j1=j+1;break;
case 2: i1=i+1;j1=j;break;
case 3: i1=i;j1=j-1;break;
}
if(mg[i1][j1]==0) find=true;
}
if(find)
{
st->data[st->top].di=di;
e.i=i1;e.j=j1;e.di=-1;
Push(st,e);
mg[i1][j1]=-1;
}
else
{
Pop(st,e);
mg[e.i][e.j]=0;
}
}
DestroyStack(st);
return false;
}
設計求解程序
int main(){
if(!mppath(1,1,M,N))
printf("該迷宮問題沒有解");
return 0;
}
問題進階
在上述的過程中痹升，我們只能找到一條路徑建炫。可是疼蛾，往往我們需要找出最短路徑肛跌，對于棧而言，我們可以通過找出所有的路徑察郁，從而確定最短的路徑衍慎。由上述的分析可知，回溯的關鍵是 di 值要找出所有的路徑皮钠，直接退棧即可稳捆，并將該方塊對應的mg數組置為0，由于回溯過后的那個方塊保存了信息就可以實現(xiàn)窮舉出所有的路徑麦轰。
bool mgpath(int xi, int yi, int xe, int ye)
{
Box path[MaxSize], e;
int i, j, di, i1, j1, k;
int num=0;//用來判斷是否有路徑輸出
bool find;
StType*st;
InitStack(st);
e.i = xi; e.j = yi; e.di = -1;
Push(st, e);
mg[xi][yi] = -1;
while (!StackEmpty(st))
{
GetTop(st, e);
i = e.i; j = e.j; di = e.di;
if (i == xe && j == ye)
{
num++;
printf("\n一條迷宮路徑如下：\n");
k = 0;
int n = st->top;//由于要回溯需要棧的信息不能采用退棧的方式
while (n!=-1)
{
e = st->data[n--];
path[k++] = e;
}
while (k >= 1)
{
k--;
printf("\t(%d,%d)", path[k].i, path[k].j);
if ((k + 2) % 5 == 0)
printf("\n");
}
mg[i][j] = 0; //設置出口狀態(tài)為0
Pop(st, e); //回溯
mg[e.i][e.j] = 0; //設置其狀態(tài)為0
i = e.i; j = e.j; di = e.di; //將i和j置為當前方塊的值
}
find = false;
while (di < 4 && !find)
{
di++;
switch (di)
{
case 0: i1 = i - 1; j1 = j; break;
case 1: i1 = i; j1 = j + 1; break;
case 2: i1 = i + 1; j1 = j; break;
case 3: i1 = i; j1 = j - 1; break;
}
if (mg[i1][j1] == 0) find = true;
}
if (find)
{
st->data[st->top].di = di;
e.i = i1; e.j = j1; e.di = -1;
Push(st, e);
mg[i1][j1] = -1;
}
else
{
Pop(st, e);
mg[e.i][e.j] = 0;
}
}
DestroyStack(st);
if(num>0) return true;
return false;
}
