基于棧的C語言迷宮問題與實現(xiàn)

1、數(shù)據(jù)結(jié)構(gòu)與算法實驗報告基于棧的C語言迷宮問題與實現(xiàn)一 問題描述多年以來，迷宮問題一直是令人感興趣的題目。實驗心理學(xué)家訓(xùn)練老鼠在迷宮中尋找食物。許多神秘主義小說家也曾經(jīng)把英國鄉(xiāng)村花園迷宮作為謀殺現(xiàn)場。于是，老鼠過迷宮問題就此產(chǎn)生，這是一個很有趣的計算機(jī)問題，主要利用 “?！笔抢鲜笸ㄟ^嘗試的辦法從入口穿過迷宮走到出口。迷宮只有兩個門，一個叫做入口，另一個叫做出口。把一只老鼠從一個無頂蓋的大盒子的入口處趕進(jìn)迷宮。迷宮中設(shè)置很多隔壁，對前進(jìn)方向形成了多處障礙，在迷宮的唯一出口處放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達(dá)出口。求解迷宮問題，即找出從入口到出口的路徑。一個迷宮可用上圖所示方陣m,n表示

2、，0表示能通過，1 表示不能通過?，F(xiàn)假設(shè)耗子從左上角1,1進(jìn)入迷宮，編寫算法，尋求一條從右下角m,n 出去的路徑。下圖是一個迷宮的示意圖：迷宮示意圖二 算法基本思想迷宮求解問題是棧的一個典型應(yīng)用。基本算法思想是：在某個點(diǎn)上，按照一定的順序（在本程序中順序為上、右、下、左）對周圍的墻、路進(jìn)行判斷（在本程序中分別用1、0）代替，若周圍某個位置為0，則移動到該點(diǎn)上，再進(jìn)行下一次判斷；若周圍的位置都為1（即沒有通路），則一步步原路返回并判斷有無其他通路，然后再次進(jìn)行相同的判斷，直到走到終點(diǎn)為止，或者確認(rèn)沒有任何通路后終止程序。要實現(xiàn)上述算法，需要用到棧的思想。棧里面壓的是走過的路徑，若遇到死路，則將該

3、位置（在棧的頂層）彈出，再進(jìn)行下一次判斷；若遇到通路，則將該位置壓棧并進(jìn)行下一次判斷。如此反復(fù)循環(huán)，直到程序結(jié)束。此時，若迷宮有通路，則棧中存儲的是迷宮通路坐標(biāo)的倒序排列，再把所有坐標(biāo)順序打印后，即可得到正確的迷宮通路。三 程序具體部分的說明1. 迷宮的生成根據(jù)題目的要求，迷宮的大小是自定義輸入的。所以在程序中用malloc申請動態(tài)二維數(shù)組。數(shù)組中的元素為隨機(jī)生成的0、1。數(shù)組周圍一圈的元素全部定義為1，以表示邊界。2. 棧的C語言實現(xiàn)為了實現(xiàn)棧的功能，即清空、壓棧、彈出、返回棧頂元素，在程序中編寫了相應(yīng)的函數(shù)。MakeNULL 清空棧Push 將橫、縱坐標(biāo)壓棧Topx 返回棧頂存儲的橫坐標(biāo)T

4、opy 返回棧頂存儲的縱坐標(biāo)Pop 彈出棧頂元素3. 具體的判斷算法當(dāng)位置坐標(biāo)（程序中為X Y）移到某一位置時，將這個位置的值賦值為1并壓棧，以說明該點(diǎn)已經(jīng)走過。接著依次判斷該點(diǎn)的上、右、下、左是否為0，若有一方為0，則移動到該位置上，進(jìn)行下次判斷；若為周圍位置全部是1，則將該點(diǎn)壓棧后不斷彈出，每次彈出時判斷棧頂元素（即走過的路）周圍有無其他通路。如果有的話，則選擇該方向繼續(xù)走下去；如果棧已經(jīng)為空仍然沒有找到出路，則迷宮沒有出口程序結(jié)束。當(dāng)X Y走到出口坐標(biāo)時，程序判斷部分結(jié)束。棧里面存儲的是每個走過的點(diǎn)的坐標(biāo)，將這些橫縱坐標(biāo)分別存儲在兩個數(shù)組中，最后將數(shù)組中的坐標(biāo)元素倒序輸出，即得到了完整的

5、路徑。四 程序源代碼及注釋 / Maze.cpp : 定義控制臺應(yīng)用程序的入口點(diǎn)。/#include "stdafx.h"#include<stdio.h>#include<string.h>#include<malloc.h>#include <stdlib.h> #include<time.h>typedef int Elementtype;struct nodeElementtype val1;Elementtype val2; node *next;/定義結(jié)構(gòu)體typedef node *MAZE;void

6、 MakeNull(MAZE &S);void Push(Elementtype x,Elementtype y, MAZE S);void Pop(MAZE S);Elementtype Topx(MAZE S);Elementtype Topy(MAZE S);/申明函數(shù)int _tmain(int argc, _TCHAR* argv)int *p,*q,*x1,*y1,i,j,k,n1,n2,m1,m2,l,w,max;int x,y;int a,b,c,d; printf("輸入迷宮長度及寬度l和wn"); scanf("%d %d",

7、&l,&w);getchar();n1=w+2;n2=l+2;/為迷宮加上邊界max=n1*n2; p=(int*)malloc(n1*sizeof(int); for(i=0;i<n1;i+) pi=(int *)malloc(n2*sizeof(int);/生成二維動態(tài)數(shù)組 srand(time(NULL);x1=(int*)malloc(max*sizeof(int);/生成動態(tài)數(shù)組用于存儲路徑y(tǒng)1=(int *)malloc(max*sizeof(int);/生成動態(tài)數(shù)組用于存儲路徑 for(i=0;i<max;i+) x1i=0;for(i=0;i<

8、max;i+) y1i=0;/先將存儲路徑的數(shù)組元素全賦值為0 for(i=0;i<n1;i+) for(j=0;j<n2;j+) if(i=0 | j=0) pij=1; else if(i=n1-1 | j=n2-1) pij=1; else pij=rand()%2+0; /生成二維1 0隨機(jī)數(shù)組p11=0;pn1-2n2-2=0;/定義迷宮的入口及出口 printf("生成的迷宮如下（代表墻0代表路）：n"); for(i=0;i<n1;i+) for(j=0;j<n2;j+) printf("%2d",pij); pri

9、ntf("n");/打印迷宮 MAZE S; MakeNull(S);/清空棧 i=1;j=1;if(p12=1 && p21=1) printf("There is no way out");a getchar(); return 0;/判斷入口是否就是死路else do if(pi-1j=0) x=i; y=j; Push(x,y,S); pij=1; i=i-1; /判斷能否向上走 else if(pi-1j=1 && pij+1=0) x=i; y=j; Push(x,y,S); pij=1; j=j+1; /判斷

10、能否向右走 else if(pi-1j=1 && pij+1=1 && pi+1j=0) x=i; y=j; Push(x,y,S); k=Topx(S); pij=1; i=i+1; /判斷能否向下走 else if(pi-1j=1 && pij+1=1 && pi+1j=1 && pij-1=0) x=i; y=j; Push(x,y,S); pij=1; j=j-1; /判斷能否向左走 else if(pi-1j=1 && pij+1=1 && pi+1j=1 &&am

11、p; pij-1=1)/判斷如果為死路 pij=1; x=i; y=j; Push(x,y,S); for(;) Pop(S);/彈出棧頂元素 x=Topx(S); y=Topy(S);/返回棧頂元素橫縱坐標(biāo) if( px-1y=0) i=x-1; j=y; pij=1; x=i; y=j; Push(x,y,S); break; else if(px-1y=1 && pxy+1=0) i=x; j=y+1; pij=1; x=i; y=j; Push(x,y,S); break; else if(px-1y=1 && pxy+1=1 && px

12、+1y=0) i=x+1; j=y; pij=1; x=i; y=j; Push(x,y,S); break; else if(px-1y=1 && pxy+1=1 && px+1y=1 && pxy-1=0) i=x; j=y-1; pij=1; x=i; y=j; Push(x,y,S); break; /判斷彈出后棧頂元素周圍有無通路 else if(x=1 && y=1) printf("There is no way out"); getchar(); return 0; /如果棧頂元素為入口則迷宮無

13、出路 while(i!=n1-2 | j!=n2-2);/循環(huán)截止條件printf("Success!n The route is:n");for(i=0;i+) a=Topx(S); b=Topy(S); Pop(S); x1i=a; y1i=b;/將棧頂元素坐標(biāo)存儲在數(shù)組中 if(a=1 && b=1) getchar(); break; for(i=max-1;i>=0;) if(x1i!=0 && (x1i!=x1i-1 | y1i!=y1i-1) printf("<%d ,%d> ",x1i,y

14、1i); i-; else if(x1i!=0 && (x1i=x1i-1 && y1i=y1i-1) printf("<%d ,%d> ",x1i,y1i); i=i-2; else i-;/倒序打印數(shù)組得到順序出路坐標(biāo)printf("<%d ,%d>",n1-2,n2-2);/打印出口坐標(biāo) getchar();return 0;void MakeNull(MAZE &S) /清空棧的函數(shù)S = new node;S->next = NULL;void Push(Elementtyp

15、e x,Elementtype y, MAZE S)/壓棧函數(shù)MAZE stk;stk = new node;stk->val1 = x;stk->val2 = y;stk->next = S->next;S->next = stk;void Pop(MAZE S)/彈出函數(shù)MAZE stk;if(S->next)stk = S->next;S->next = stk->next;delete stk;Elementtype Topx(MAZE S)/返回橫坐標(biāo)函數(shù)if(S->next)return(S->next->va

16、l1);elsereturn NULL;Elementtype Topy(MAZE S)/返回縱坐標(biāo)函數(shù)if(S->next)return(S->next->val2);elsereturn NULL;五 程序運(yùn)行結(jié)果運(yùn)行程序后，首先輸入迷宮的長度和寬度假設(shè)迷宮是8*8的（也可以為其他大小）。輸入后若沒有出路，則顯示“There is no way out”,程序結(jié)束。輸入后若迷宮有出路，則顯示Success再次按下回車鍵，則打印出迷宮路徑程序結(jié)束六 程序運(yùn)行結(jié)果自評該程序運(yùn)用棧的思想，成功解決了迷宮問題。下面對上述運(yùn)行結(jié)果進(jìn)行簡要分析：當(dāng)迷宮沒有出路時，系統(tǒng)首先走到2,2點(diǎn)彈出，發(fā)現(xiàn)2,1點(diǎn)下方為出路，然后繼續(xù)向下走。但是走到5,1點(diǎn)時發(fā)現(xiàn)周圍再次為死路，只能不停彈出，同時檢測周圍有無出路。當(dāng)彈出到1,1，點(diǎn)時，發(fā)現(xiàn)迷宮沒有出路，程序結(jié)束。當(dāng)迷宮有出路時，系統(tǒng)按照既定規(guī)則移動，在3,5點(diǎn)時并未直接向下走向4,5點(diǎn)，而是按照判斷順序向右移動。當(dāng)走到1,8點(diǎn)時發(fā)現(xiàn)為死路，