迷宮問題課程設(shè)計(jì)-數(shù)據(jù)結(jié)構(gòu)

1、迷宮問題一需求設(shè)計(jì)：可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出。二概要設(shè)計(jì)：存儲(chǔ)結(jié)構(gòu)：采用了數(shù)組以及結(jié)構(gòu)體來存儲(chǔ)數(shù)據(jù)，在探索迷宮的過程中用到的棧，屬于順序存儲(chǔ)結(jié)構(gòu)。/八個(gè)方向的數(shù)組表示形式int move82=0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1, 0,-1, 1;/用結(jié)構(gòu)體表示位置struct positionint x,y;position stackm*m+1;基本算法：走迷宮的過程可以模擬為一個(gè)搜索的過程：每到一處，總讓它按東、東南、南、西南、西、西北、北、東北8個(gè)方向順序試探下一個(gè)位置；如果某方向可以通過，并且不曾到達(dá)，

2、則前進(jìn)一步，在新位置上繼續(xù)進(jìn)行搜索；如果8個(gè)方向都走不通或曾經(jīng)到達(dá)過，則退回一步，在原來的位置上繼續(xù)試探下一位置。每前進(jìn)或后退一步，都要進(jìn)行判斷：若前進(jìn)到了出口處，則說明找到了一條通路；若退回到了入口處，則說明不存在通路。用一個(gè)字符類型的二維數(shù)組表示迷宮，數(shù)組中每個(gè)元素取值“0”（表示通路）或“1”（表示墻壁）。迷宮的入口點(diǎn)在位置（1，1）處，出口點(diǎn)在位置（m,m）處。設(shè)計(jì)一個(gè)模擬走迷宮的算法，為其尋找一條從入口點(diǎn)到出口點(diǎn)的通路。二維數(shù)組的第0行、第m+1行、第0列、第m+1列元素全置成“1”， 表示迷宮的邊界；第1行第1列元素和第m行第m列元素置成“0”， 表示迷宮的入口和出口；其余元素值用

3、隨機(jī)函數(shù)產(chǎn)生。假設(shè)當(dāng)前所在位置是（x,y）。沿某個(gè)方向前進(jìn)一步，它可能到達(dá)的位置最多有8個(gè)。如果用二維數(shù)組move記錄8個(gè)方向上行下標(biāo)增量和列下標(biāo)增量，則沿第i個(gè)方向前進(jìn)一步，可能到達(dá)的新位置坐標(biāo)可利用move數(shù)組確定： x=x+movei0 y=y+movei1從迷宮的入口位置開始，沿圖示方向順序依次進(jìn)行搜索。在搜索過程中，每前進(jìn)一步，在所到位置處做標(biāo)記“h”（表示這個(gè)位置在通路上），并將該位置的坐標(biāo)壓入棧中。每次后退的時(shí)候，先將當(dāng)前所在位置處的通路標(biāo)記“h”改成死路標(biāo)記“”（表示這個(gè)位置曾到達(dá)過但走不通，以后不要重復(fù)進(jìn)入），然后將該位置的坐標(biāo)從棧頂彈出。搜索到出口位置時(shí)，數(shù)組中那些值為“h

4、”的元素形成一條通路。三詳細(xì)設(shè)計(jì)：源程序：/*迷宮問題走迷宮的過程可以模擬為一個(gè)搜索的過程：每到一處，總讓它按東、東南、南、西南、西、西北、北、東北個(gè)方向順序試探下一個(gè)位置；如果某方向可以通過，并且不曾到達(dá)，則前進(jìn)一步，在新位置上繼續(xù)進(jìn)行搜索；如果個(gè)方向都走不通或曾經(jīng)到達(dá)過，則退回一步，在原來的位置上繼續(xù)試探下一位置。 每前進(jìn)或后退一步，都要進(jìn)行判斷：若前進(jìn)到了出口處，則說明找到了一條通路；若退回到了入口處，則說明不存在通路。 用一個(gè)字符類型的二維數(shù)組表示迷宮，數(shù)組中每個(gè)元素取值“”（表示通路）或“”（表示墻壁）。迷宮的入口點(diǎn)在位置（，）處，出口點(diǎn)在位置（m,m）處。這個(gè)算法，為其尋找一條從入

5、口點(diǎn)到出口點(diǎn)的通路。*/#include#include#includevoid main()/設(shè)定m=10const int m=10;/數(shù)組的形式表示八個(gè)方向int move82=0,1,1,1,1,0,1,-1,0,-1,-1,-1,-1, 0,-1, 1;/用結(jié)構(gòu)體表示位置struct positionint x,y;/用于記錄和輸出迷宮探路中相關(guān)符號(hào)，包括1 .char mazem+2m+2;/用棧來存儲(chǔ)探路過程中的數(shù)據(jù)position stackm*m+1;int top;/棧頂int i,x,y,ok;position p;/二維數(shù)組的第行、第m+1行、第列、第m+1列元素全/置

6、成“”，表示迷宮的邊界；第行第列元素和第m行第m列/元素置成“”，表示迷宮的入口和出口；其余元素值用隨機(jī)/函數(shù)產(chǎn)生。srand(time(0);for(x=1;x=m;x+)for(y=1;y=m;y+)mazexy=48+rand()%2;maze11=0;mazemm=0;for(x=0;x=m+1;x+)mazex0=1;mazexm+1=1;for(y=0;y=m+1;y+)maze0y=1;mazem+1y=1;p.x=1;p.y=1;top=1;stacktop=p;maze11=.;/開始探路/走迷宮的過程可以模擬為一個(gè)搜索的過程：每到一/處，總讓它按東、東南、南、西南、西、西北

7、、北、東北/個(gè)方向順序試探下一個(gè)位置；如果某方向可以通過，并且不/曾到達(dá)，則前進(jìn)一步，在新位置上繼續(xù)進(jìn)行搜索；如果個(gè)/方向都走不通或曾經(jīng)到達(dá)過，則退回一步，在原來的位置上/繼續(xù)試探下一位置。/ 每前進(jìn)或后退一步，都要進(jìn)行判斷：若前進(jìn)到了出/口處，則說明找到了一條通路；若退回到了入口處，則說明/不存在通路。dop=stacktop;ok=0;i=0;while(ok=0)&(i0)&(p.x!=m)|(p.y!=m);/輸出探路結(jié)果if(top=0) printf(沒有路徑n);else printf(有路徑n);/輸出探路迷宮留下的蹤跡for(x=1;x=m;x+)printf(n);for(y=1;y=m;y+) printf(%c ,mazexy);printf(n);四調(diào)試分析：測(cè)試數(shù)據(jù)和結(jié)果：當(dāng)設(shè)定迷宮為10*10：當(dāng)設(shè)定迷宮為5*5：算法時(shí)間復(fù)雜度