棧的應用——迷宮求解

1、一、 棧的來源與定義：線性表：有序的有限集合，集合元素依據(jù)具體問題而定。例子：A=13,45,12 B=小明 87,小王 90等，這只是數(shù)學層次上的描述，如何在計算機層次上描述？有兩種：以上述為例數(shù)組：鏈表：當然，在實際運用中，一般很難估計到具體問題的規(guī)模，即不清楚集合中的元素個數(shù)上限是多少，所以都是用動態(tài)存儲分配進行實現(xiàn)的。相應的有些基本操作：插入元素，刪除元素，合并線性表，拆分線性表，查找元素，修改元素等，根據(jù)元素的性質(zhì)還可以得到一下額外操作。如：數(shù)值型元素可以有排序這個操作。在進行插入和刪除時，對任意位置元素都能進行。人們實踐中發(fā)現(xiàn)許多問題在進行上述兩項操作時都限制在末尾。由此提出棧的概

2、念，特定是“后進先出”；若將刪除限制在開頭，則稱為隊列，特定是“先進先出”。根據(jù)棧的特點，在數(shù)學層次上描述時，換一種更能符合其特點的表示，如下：134512headtail將其用“疊羅漢”的形式表示出來，每次進行插入或刪除時，都在最上面進行，最上面稱為棧頂，最下面稱為棧底，head指向第一個元素，tail指向棧頂?shù)南乱粋€元素。進行插入時，改變*tail的值，tail+；進行刪除時，tail-；可以看出當tail與head相等時，便是空集，或稱為空棧。當然也可以用一個變量來記錄棧的元素個數(shù)，簡稱棧長。二、 棧的應用方形迷宮求解起點終點如上圖，如何運用計算機對其進行求解呢？1. 算法思路：計算機求

3、解迷宮時，通常用的都是“窮舉法”，即每種走法都嘗試一遍，若走到終點，則輸出，否則，輸出迷宮無解。步驟如下：記錄begin所在的方塊坐標，當前方塊設為begin所在的方塊（一）尋找方向第一步：搜索當前方塊東南西北哪些方向可以走，為了方便描述，用數(shù)組direction4表示四個方向，分別代表東南西北，值為1，表示可以走，值為0，表示不能走。 第二步：在搜尋路徑時，不能走已經(jīng)記錄過的方塊坐標，免得在原地轉圈。因此，在能走的方向中，判斷是否有已經(jīng)記錄過的方塊坐標，有則置相應的方向為0（二）選擇方向 讓當前方塊從東邊開始順時針搜尋可以走的方向（可以從別的方向開始，還可以不用順時針，只要數(shù)組directi

4、on各個下標對應的方向不重復即可），即找到direction數(shù)組中，第一個為1的下標，0,1,2,3分別代表可以往東南西北走；若為其他值，表示當前方塊四處都無路可走。 if 有路可走 記錄此方向的方塊坐標，當前方塊設為剛剛記錄的方塊，若為end，則跳出循環(huán)，否則轉到（一）繼續(xù)循環(huán)else刪除最后一次記錄的方塊坐標if 記錄空了迷宮無解，跳出循環(huán)else當前方塊設為倒數(shù)第二次記錄的方塊，并將此方塊通往剛剛刪除的方塊的方向上設為0，轉到（二）2. 數(shù)據(jù)描述：i. 描述迷宮：可將迷宮看成矩陣，用二維數(shù)組進行描述即可，為0，表示墻壁；為1，表示通路，則上圖可用以下矩陣表示ii. 描述記錄：從算法的思路

5、中可以看出，記錄可用棧來描述，包含著求解結果，若記錄為空，則迷宮無解；否則，迷宮有解，輸出路徑。3. 舉例說明：beginend用上述迷宮，描述依次算法下，棧的變化：第一次循環(huán)：00東南西北1100有路可走，往東走。第二次循環(huán)：01東南西北000000東南西北1100不為終點，無路可走，退回去，封鎖東邊，往南走。第三次循環(huán)：10東南西北010000東南西北0100不為終點，有路可走，往南走。第四次循環(huán)：20東南西北110010東南西北010000東南西北0100不為終點，有路可走，往東走。第五次循環(huán)：21東南西北100020東南西北110010東南西北010000東南西北0100不為終點，有路

6、可走，往東走。第六次循環(huán)：22東南西北010121東南西北100020東南西北110010東南西北010000東南西北0100不為終點，有路可走，往南走。第七次循環(huán)：32東南西北100022東南西北010121東南西北100020東南西北110010東南西北010000東南西北0100不為終點，有路可走，往東走。第八次循環(huán)：33東南西北000032東南西北100022東南西北010121東南西北100020東南西北110010東南西北010000東南西北0100不為終點，無路可走，退回去，封鎖東邊。第九次循環(huán)：32東南西北000022東南西北010121東南西北100020東南西北110010

7、東南西北010000東南西北0100不為終點，無路可走，退回去，封鎖南邊，往北走。第十次循環(huán)：12東南西北100022東南西北000121東南西北100020東南西北110010東南西北010000東南西北0100不為終點，有路可走，往東走。第十一次循環(huán)：13東南西北000112東南西北100022東南西北000121東南西北100020東南西北110010東南西北010000東南西北0100不為終點，有路可走，往北走。第十二次循環(huán)：03東南西北000013東南西北000112東南西北100022東南西北000121東南西北100020東南西北110010東南西北010000東南西北0100走

8、到終點，算法結束，輸出路徑。4. 結構化設計：迷宮求解軟件選擇界面歡迎界面手動錄入迷宮隨機生成迷宮迷宮求解方向搜尋禁止重復判斷結束返回禁止打印結果5. 補充：（1）雖然此程序探討的是方形迷宮，但是對于形如下面非方形的迷宮，可以用一個方形進行覆蓋，原迷宮不變，其余地方都作為墻壁。（2）需要用到計算機求解的迷宮一般規(guī)模都比較大，如下圖，手動輸入時過于繁瑣，還不能保證沒錯，可以采取以下方法減少工作量。運用MATLAB將該圖片讀入，判斷出一個方塊所含的像素點，將其像素值全部相加求平均值作為該方塊的像素值，黑像素點的像素值和白像素點的像素值相差十分大，因此可以很明顯的判斷哪些方塊是墻壁或通路，生成矩陣。

9、三、 代碼示例：#include<stdio.h>#include<stdlib.h>#define Max_size 10000 /迷宮求解路徑的長度上限，越大越好 main() void welcome(); /歡迎界面 void choose(); /選擇界面 welcome();choose();void welcome()printf("*nn");printf("歡迎來到迷宮求解軟件!nn");printf("*nn");void choose()void rand_maze();/選擇隨機生成迷宮

10、 void hand_maze();/選擇手動生成迷宮 int number; printf("選擇以下選項：n");printf("輸入1：隨機生成迷宮n");printf("輸入2：手動輸入迷宮n");scanf("%d",&number);/考慮數(shù)據(jù)選項輸入違法 while(number!=1&&number!=2)printf("輸入錯誤，重新輸入：");scanf("%d",&number);switch(number)case 1:

11、rand_maze();break;case 2:hand_maze();break;void rand_maze()void solve(int *p,int n);int n,*p,i;/迷宮用動態(tài)生成的一維數(shù)組保存，用指針p指向其首地址 printf("輸入迷宮規(guī)模(大于等于3)：");scanf("%d",&n);while(n<=2)printf("輸入錯誤，重新輸入：");scanf("%d",&n);p=(int *)malloc(sizeof(int)*n*n);for(i=0

12、;i<n*n;i+)if(rand()<=17000)/rand（）所生成的范圍在-9032767，將其劃分成兩半，依此隨機生成通路和墻壁 *(p+i)=0;else*(p+i)=1;printf("代表通路，代表墻壁n"); /輸出迷宮形狀 printf("隨機生成的迷宮如下:n");for(i=0;i<n*n;i+)switch(*(p+i)case 1:printf("");break;case 0:printf("");break;if(i+1)%n=0)printf("n&qu

13、ot;);solve(p,n);/進行求解，傳送保存迷宮的一維數(shù)組的首地址和規(guī)模 void hand_maze()/和rand_maze大體相同，不過錄入迷宮時用二維數(shù)組表示 void solve(int *p,int n);int n,*p,i;printf("輸入迷宮規(guī)模：");scanf("%d",&n);while(n<=0)printf("輸入錯誤，重新輸入：");scanf("%d",&n);p=(int *)malloc(sizeof(int)*n*n);printf("

14、;下面開始錄入迷宮，用1表示（通路），用0表示（墻壁）:n");printf("例如:n1 1 0 n0 1 0 n0 1 1 等于 nnn");for(i=0;i<n*n;i+)scanf("%d",p+i);printf("手動生成的迷宮如下:n");for(i=0;i<n*n;i+)switch(*(p+i)case 1:printf("");break;case 0:printf("");break;if(i+1)%n=0)printf("n")

15、;solve(p,n);void solve(int *p,int n)int set(int begin_road2,int end_road2,int n,int *p);void exhaustion(int begin_road2,int end_road2,int n,int *p);int begin_road2,end_road2,judge;/設置起點和終點，在此函數(shù)中判斷起點終點是否重疊，重疊則返回0，求解完畢；否則返回1，調(diào)用函數(shù) exhaustion運用窮舉法求解 judge=set(begin_road,end_road,n,p);if(judge=1)exhausti

16、on(begin_road,end_road,n,p);int set(int begin_road2,int end_road2,int n,int *p)int judge,i;/說明規(guī)則，按照C語言二維數(shù)組的下標進行描述，方便下面編程printf("設置起點和終點，規(guī)則如下:n");printf("將迷宮方塊所在的位置看成一個矩陣，左上角的下標設為00n");printf("右移一格，第二個下標加1；下移一格，第一個下標加1n");/輸入起點和終點首先要判斷是否越界，再判斷是否為墻壁 /設置起點 do printf("

17、輸入起點的橫坐標："); scanf("%d",&begin_road0);while(begin_road0<0|begin_road0>=n)printf("越過范圍，重新輸入:");scanf("%d",&begin_road0);printf("輸入起點的縱坐標：");scanf("%d",&begin_road1);while(begin_road1<0|begin_road1>=n)printf("越過范圍，重新輸入

18、:");scanf("%d",&begin_road1);if(*(p+begin_road0*n+begin_road1)=0)printf("%d%d處是墻壁，設置錯誤，重新設置!n",begin_road0,begin_road1);judge=1;elsejudge=0;while(judge=1);/設置終點 doprintf("輸入終點的橫坐標："); scanf("%d",&end_road0);while(end_road0<0|end_road0>=n)pri

19、ntf("越過范圍，重新輸入:");scanf("%d",&end_road0);printf("輸入終點的縱坐標：");scanf("%d",&end_road1);while(end_road1<0|end_road1>=n)printf("越過范圍，重新輸入:");scanf("%d",&end_road1);if(*(p+end_road0*n+end_road1)=0)printf("%d%d處是墻壁，設置錯誤，重新設置

20、!n",end_road0,end_road1);judge=1;elsejudge=0;while(judge=1);/設置起點和終點，在此函數(shù)中判斷起點終點是否重疊，重疊則返回0，求解完畢；否則返回1，調(diào)用函數(shù) exhaustion運用窮舉法求解 if(begin_road0=end_road0&&begin_road1=end_road1)printf("迷宮的終點和起點重疊，迷宮求解完畢");return 0;elseprintf("在你的設置下，迷宮初始化如下圖：代表起點，代表終點:n"); for(i=0;i<

21、n*n;i+)if(i=(begin_road0*n+begin_road1)printf("");if(i+1)%n=0)printf("n");continue;if(i=(end_road0*n+end_road1)printf("");if(i+1)%n=0)printf("n");continue;switch(*(p+i)case 1:printf("");break;case 0:printf("");break;if(i+1)%n=0)printf("

22、;n");return 1;/設置求解時所需的變量結構，棧用結構體數(shù)組roadMax_size進行存儲，answer指向棧，有棧頂，棧尾和棧長三個量 struct road_step int coordinate2; /存儲路徑的坐標 int direction4; /存儲相應坐標的四個方向的可通行，0不可通，1可通 roadMax_size;struct searchstruct road_step *head;/棧尾 struct road_step *tail; /棧頂 int step_number;answer;/運用窮舉法進行求解的函數(shù)exhaustion，需要起點，終點

23、，規(guī)模，迷宮四個變量 void exhaustion(int begin_road2,int end_road2,int n,int *p)/返回棧頂四個方向中第一個可通的方向，0,1,2,3分別代表東，南，西，北，返回4時表示無路可走 int search_direction(struct road_step *a);/用來判斷棧頂四個方向的可通性 void set_direction(struct road_step *a,int n,int *p);/用來判斷棧頂是否與終點重合，判斷是否求解完畢，重合返回1，否則返回0，用judge接受 int arrive_aim(struct roa

24、d_step *a,int end_road2);/判斷完棧頂四個方向的可通性后，為了避免在一個地方轉圈圈，若某方向的可通方塊已經(jīng)在棧內(nèi)，則該方向設為不通 void ban_repeat(struct road_step *aim_end,struct road_step *aim_begin);/因為某方向探索完后發(fā)現(xiàn)不通，在退回來時要將該探索方向設置為0 void update_direction(struct road_step *a); /打印行走路線 void printf_road(struct search answer,int n,int *p);int choose_dire

25、ction,i,judge; /judge用來判斷是否到達終點 printf("迷宮的求解情況如下：n");/tail指向將要要存儲信息的單元，初始化后，head指向road0，tail指向road1，棧長為1，則tail-1表示棧頂 road0.coordinate0=begin_road0;road0.coordinate1=begin_road1;answer.head=&road0;answer.tail=&road1;answer.step_number=1;/設置起點四個方向的可通行 set_direction(answer.tail-1,n,p

26、);/選擇棧頂可通的方向進行探索，當探索后此方向不通時，將其置為0，若四個方向都不通則刪除棧頂do/按照東，南，西，北的順序選擇第一個可通的方向進行探索 choose_direction=search_direction(answer.tail-1);if(choose_direction!=4)/如果值不為4，表示還能探索，將第一個可通方向的方塊放入，并設置該方塊的可通行，而且不走重復路 switch(choose_direction) case 0: /東邊 answer.tail->coordinate1=(answer.tail-1)->coordinate1+1;answ

27、er.tail->coordinate0=(answer.tail-1)->coordinate0;answer.tail=answer.tail+1;answer.step_number+; /判斷是否為終點judge=arrive_aim(answer.tail-1,end_road);/設置棧頂方向，分兩步，初始化和不走重復路 set_direction(answer.tail-1,n,p); ban_repeat(answer.tail-1,answer.head);break;case 1: /南邊 answer.tail->coordinate1=(answer.

28、tail-1)->coordinate1;answer.tail->coordinate0=(answer.tail-1)->coordinate0+1;answer.tail=answer.tail+1;answer.step_number+; /判斷是否為終點judge=arrive_aim(answer.tail-1,end_road);/設置棧頂方向，分兩步，初始化和不走重復路 set_direction(answer.tail-1,n,p);ban_repeat(answer.tail-1,answer.head);break;case 2: /西邊answer.t

29、ail->coordinate1=(answer.tail-1)->coordinate1-1;answer.tail->coordinate0=(answer.tail-1)->coordinate0;answer.tail=answer.tail+1;answer.step_number+; /判斷是否為終點judge=arrive_aim(answer.tail-1,end_road);/設置棧頂方向，分兩步，初始化和不走重復路 set_direction(answer.tail-1,n,p); /初步可探索方向 ban_repeat(answer.tail-1,

30、answer.head); /禁止走重復的路 break;case 3: /北邊answer.tail->coordinate1=(answer.tail-1)->coordinate1;answer.tail->coordinate0=(answer.tail-1)->coordinate0-1;answer.tail=answer.tail+1;answer.step_number+; /判斷是否為終點judge=arrive_aim(answer.tail-1,end_road);/設置棧頂方向，分兩步，初始化和不走重復路 set_direction(answer

31、.tail-1,n,p); ban_repeat(answer.tail-1,answer.head);break;if(judge=1) /棧頂是出口了，退出循環(huán)，開始輸出 break; else /表示棧頂沒有方向探索了，刪除棧頂，并且新棧頂在通往舊棧頂?shù)姆较蛏显O置為不通 answer.tail-;if(answer.step_number!=1)update_direction(answer.tail); answer.step_number-; while(answer.step_number!=0);/若全都探索完畢還沒有找到出口，最后會連用來初始化的起點也刪除 ，導致answer.

32、step_number=0，此時迷宮無解if(answer.step_number=0)printf("此迷宮無解!");elseprintf_road(answer,n,p);void set_direction(struct road_step *a,int n,int *p) /初始化方向 /先判斷是否在邊緣/再判斷是否在四個角if(a->coordinate0=0&&a->coordinate1=0) /左上角 /西邊和北邊不通 a->direction2=0,a->direction3=0;/判斷東邊是否通 if(*(p+a

33、->coordinate0*n+a->coordinate1+1)=1)a->direction0=1;elsea->direction0=1;/判斷南邊是否通 if(*(p+(a->coordinate0+1)*n+a->coordinate1)=1)a->direction1=1;elsea->direction1=0;return; if(a->coordinate0=0&&a->coordinate1=n-1) /右上角 /東邊和北邊不通 a->direction0=0,a->direction3=

34、0;/判斷西邊是否通 if(*(p+a->coordinate0*n+a->coordinate1-1)=1)a->direction2=1;else a->direction2=0;/判斷南邊是否通 if(*(p+(a->coordinate0+1)*n+a->coordinate1)=1)a->direction1=1;elsea->direction1=0;return; if(a->coordinate0=n-1&&a->coordinate1=0) /左下角 /西邊和南邊不通 a->direction1

35、=0,a->direction2=0;/判斷東邊是否通 if(*(p+a->coordinate0*n+a->coordinate1+1)=1)a->direction0=1;elsea->direction0=0; /判斷北邊是否通 if(*(p+(a->coordinate0-1)*n+a->coordinate1)=1)a->direction3=1;elsea->direction3=0;return; if(a->coordinate0=n-1&&a->coordinate1=n-1) /右下角 /東邊

36、和南邊不通 a->direction0=0,a->direction1=0;/判斷西邊是否通 if(*(p+a->coordinate0*n+a->coordinate1-1)=1)a->direction2=1;elsea->direction2=0; /判斷北邊是否通 if(*(p+(a->coordinate0-1)*n+a->coordinate1)=1)a->direction3=1;elsea->direction3=0;return; /判斷是否在上邊，第一個坐標是否為0，則北面不通 if(a->coordinat

37、e0=0)a->direction3=0;/判斷西邊是否通 if(*(p+a->coordinate0*n+a->coordinate1-1)=1)a->direction2=1;elsea->direction2=0; /判斷東邊是否通 if(*(p+a->coordinate0*n+a->coordinate1+1)=1)a->direction0=1;elsea->direction0=0; /判斷南邊是否通 if(*(p+(a->coordinate0+1)*n+a->coordinate1)=1)a->direc

38、tion1=1;elsea->direction1=0;return; /判斷是否在左邊，第二個坐標是否為0，則西邊不通 if(a->coordinate1=0)a->direction2=0;/判斷東邊是否通 if(*(p+a->coordinate0*n+a->coordinate1+1)=1)a->direction0=1;elsea->direction0=0; /判斷南邊是否通 if(*(p+(a->coordinate0+1)*n+a->coordinate1)=1)a->direction1=1;elsea->di

39、rection1=0;/判斷北邊是否通 if(*(p+(a->coordinate0-1)*n+a->coordinate1)=1)a->direction3=1;elsea->direction3=0;return; /判斷是否在下邊，南邊不通 if(a->coordinate0=n-1)a->direction1=0;/判斷北邊是否通 if(*(p+(a->coordinate0-1)*n+a->coordinate1)=1)a->direction3=1;elsea->direction3=0;/判斷東邊是否通 if(*(p+a

40、->coordinate0*n+a->coordinate1+1)=1)a->direction0=1;elsea->direction0=0;/判斷西邊是否通 if(*(p+a->coordinate0*n+a->coordinate1-1)=1)a->direction1=1;elsea->direction1=0; return; /判斷是否在右邊,東邊不通 if(a->coordinate1=n-1)a->direction0=0; /判斷南邊是否通 if(*(p+(a->coordinate0+1)*n+a->c

41、oordinate1)=1)a->direction1=1;elsea->direction1=0; /判斷北邊是否通 if(*(p+(a->coordinate0-1)*n+a->coordinate1)=1)a->direction3=1;elsea->direction3=0;/判斷西邊是否通 if(*(p+a->coordinate0*n+a->coordinate1-1)=1)a->direction2=1;elsea->direction2=0; return; /不在邊緣/判斷南邊是否通 if(*(p+(a->co

42、ordinate0+1)*n+a->coordinate1)=1)a->direction1=1;elsea->direction1=0; /判斷北邊是否通 if(*(p+(a->coordinate0-1)*n+a->coordinate1)=1)a->direction3=1;elsea->direction3=0;/判斷西邊是否通 if(*(p+a->coordinate0*n+a->coordinate1-1)=1)a->direction2=1;elsea->direction2=0; /判斷東邊是否通 if(*(p+

43、a->coordinate0*n+a->coordinate1+1)=1)a->direction0=1;elsea->direction0=0;return;int search_direction(struct road_step *a)int i;for(i=0;i<4;i+)if(a->directioni=1)break;return i; /放回的i值代表第一個可通的方向，0,1,2,3分別代表東，南，西，北；為4時代表無路可走 int arrive_aim(struct road_step *a,int end_road2)if(a->c

44、oordinate0=end_road0&&a->coordinate1=end_road1)/是終點return 1;elsereturn 0; void ban_repeat(struct road_step *aim_end,struct road_step *aim_begin) /棧頂?shù)目赏ǚ较蛑胁荒苡幸鸭{入棧的方塊 while(aim_begin!=aim_end)/棧的方塊在棧頂方塊的上邊,北邊不通 if(aim_begin->coordinate0+1)=aim_end->coordinate0&&aim_begin->c

45、oordinate1=aim_end->coordinate1) aim_end->direction3=0;/棧的方塊在棧頂方塊的左邊,西邊不通 if(aim_begin->coordinate0=aim_end->coordinate0&&(aim_begin->coordinate1+1)=aim_end->coordinate1) aim_end->direction2=0;/棧的方塊在棧頂方塊的下邊，南邊不通 if(aim_begin->coordinate0-1)=aim_end->coordinate0&

46、;&aim_begin->coordinate1=aim_end->coordinate1) aim_end->direction1=0;/棧的方塊在棧頂方塊的右邊，東邊不通if(aim_begin->coordinate0=aim_end->coordinate0&&(aim_begin->coordinate1-1)=aim_end->coordinate1) aim_end->direction0=0;aim_begin+;void update_direction(struct road_step *a)/根據(jù)新舊棧頂