1、實習(xí) 2棧的應(yīng)用本次實習(xí)的主要目的在于幫助學(xué)生深入了解棧的特性，以便在實際問題背景下靈活運(yùn)用他們；同時還將鞏固對棧這種結(jié)構(gòu)的構(gòu)造方法的理解。實驗課時6 課時程序 1：迷宮問題問題描述以一個 m×n 的長方陣表示迷宮， 0和 1分別表示迷宮中的通路和障礙。設(shè)計一個程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。基本要求首先實現(xiàn)一個以順序表或鏈表做存儲結(jié)構(gòu)的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i,j,d）的形式輸出，其中：（ i,j）指示迷宮中的一個坐標(biāo)，d表示走到下一坐標(biāo)的方向。如：對下列數(shù)據(jù)的迷宮，輸出的一條通路為： （ 1，1，1

2、），（1，2，2），（ 2， 2， 2），測試數(shù)據(jù)迷宮的測試數(shù)據(jù)如下：左上角（1， 1）為入口，右下角（3， 4）為出口。0123451111111001111001111000!1111111 實現(xiàn)提示 計算機(jī)解迷宮通常用的是 “窮舉求解” 方法，即從入口出發(fā)， 順著某一個方向進(jìn)行探索，若能走通， 則繼續(xù)往前進(jìn)；否則沿原路退回， 換一個方向再繼續(xù)探索， 直至所有可能的通路都探索到為止 ,如果所有可能的通路都試探過，還是不能走到終點(diǎn)，那就說明該迷宮不存在從起點(diǎn)到終點(diǎn)的通道，可以二維數(shù)組存儲迷宮數(shù)據(jù)。程序?qū)崿F(xiàn) #include <stdio.h>#include <stdlib

3、.h>/1.迷宮位置坐標(biāo)類型typedef structint x;/ 行int y;/ 列PosType;#define MAXENGTH 25 /迷宮最大行列數(shù)位25typedef int MazeTypeMAXENGTHMAXENGTH;/迷宮數(shù)列typedef struct/ 定義棧int ord;/ 通道塊在路徑上的序號PosType seat;/通道塊在迷宮中的位置int di;/走向下一塊的方向（03 表示東、南、西、北）SElemType;/2.全局變量MazeType m;/ 迷宮數(shù)組int curstep=1;/ 當(dāng)前位置，初值為1#define STACK_INIT

4、_SIZE 10/存儲空間初始分配量#define STACKINCREMENT 2/存儲空間分配增量/3.棧的順序存儲表示typedef struct SqStackSElemType *base;/ 尾指針SElemType *top;/ 頭指針int stacksize;/ 棧大小SqStack;/ 順序表/4.構(gòu)造空棧int InitStack(SqStack &S)S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!(S.base)exit(0);S.top=S.base;S.stacksize=

5、STACK_INIT_SIZE;return 1;/5.判斷棧是否為空（用來判斷迷宮是否不可達(dá)到出口）int StackEmpty(SqStack S)if(S.top=S.base)/ 棧底與棧頂相等為空棧return 1;elsereturn 0;/6.插入元素int Push(SqStack &S,SElemType e)if(S.top-S.base>=S.stacksize)/ 棧頂 -棧底 >=棧長，說明空間已滿S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemT

6、ype);if(!S.base)exit(0);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*(S.top)+=e;return 1;/7.棧不為空時，刪除棧頂元素，用 e 返回（用于當(dāng)棧頂元素各方向均不通時，將其從路徑中刪除）int Pop(SqStack &S,SElemType &e)if(S.top=S.base)return 0;e=*-S.top;/ 先將 S.top 的值賦給 e，再將 S.top 向下移一位 return 1;/8.判斷迷宮 m 中 b 點(diǎn)是否可通過（是 1，否 0），其中墻為 0，可

7、通過路徑為 1，不可通過路徑為 -1int Pass(PosType b)if(mb.xb.y=1)return 1;elsereturn 0;/9.是迷宮 m 中 a 的序號變?yōu)樽阚E（即該位置目前可通過）void FootPrint(PosType a)ma.xa.y=curstep;/10.根據(jù)當(dāng)前位置方向，返回下一位置PosType NextPos(PosType c,int di)PosType direc4=0,1,1,0,0,-1,-1,0;c.x+=direcdi.x;c.y+=direcdi.y;return c;/11.道路不能通過時（即為死路），將其標(biāo)記為-1void Ma

8、rkPrint(PosType b)mb.xb.y=-1;/12.求迷宮出口int MazePath(PosType start,PosType end)SqStack S;PosType curpos;/當(dāng)前位置SElemType e;InitStack(S);curpos=start;doif(Pass(curpos)FootPrint(curpos);e.ord=curstep;e.di=0;Push(S,e);curstep+;if(curpos.x=end.x&&curpos.y=end.y)return 1;curpos=NextPos(curpos,e.di);e

9、lseif(!StackEmpty(S)Pop(S,e);curstep-;while(e.di=3&&!StackEmpty(S)MarkPrint(e.seat);Pop(S,e);curstep-;if(e.di<3)e.di+;Push(S,e);curstep+;curpos=NextPos(e.seat,e.di);while(!StackEmpty(S);return 0;/13.輸出迷宮結(jié)構(gòu)void Print(int x,int y)int i,j;for(i=0;i<x;i+)for(j=0;j<y;j+)printf("%3d&

10、quot;,mij);printf("n");/14.主函數(shù)int main()PosType begin,end;int i,j,x,y,x1,y1;printf(" 請輸入迷宮行列數(shù)（包括外墻）:（空格隔開） n");scanf("%d %d",&x,&y);for(i=0;i<x;i+)/定義外墻m0i=0;mx-1i=0;for(j=0;j<y-1;j+)mj0=0;mjy-1=0;for(i=1;i<x-1;i+)for(j=1;j<y-1;j+)mij=1;/墻內(nèi)初始值均為1/輸入迷

11、宮中墻的個數(shù)printf(" 輸入墻的個數(shù)：");scanf("%d",&j);/安排墻的位置printf(" 請輸入墻的位置（坐標(biāo)），用空格隔開 :n");for(i=1;i<=j;i+)scanf("%d %d",&x1,&y1);mx1y1=0;printf(" 迷宮結(jié)構(gòu)如下n");Print(x,y);printf(" 請輸入起點(diǎn)坐標(biāo)：n");scanf("%d %d",&begin.x,&begin.y);printf(" 請輸入終點(diǎn)坐標(biāo)