數(shù)據(jù)結構課程設計迷宮問題課程設計報告

1、迷宮問題 迷宮問題——王欣歆 王欣歆 20080564 20080564一．需求設計： 一．需求設計：以一個 m*m 的方陣表示迷宮，0 和 1 分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口的通道，或得出沒有通路的結論。二．概要設計： 二．概要設計：存儲結構： 存儲結構：采用了數(shù)組以及結構體來存儲數(shù)據(jù)，在探索迷宮的過程中用到的棧，屬于順序存儲結構。/*八個方向的數(shù)組表示形式*/int move[8][2

2、]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1, 0},{-1, 1}};/*用結構體表示位置*/struct position{int x,y;};position stack[m*m+1];基本算法： 基本算法：走迷宮的過程可以模擬為一個搜索的過程：每到一處，總讓它按東、東南、南、西南、西、西北、北、東北 8 個方向順序試探下一個位置；如果某方向可以通過，并且不曾到達，則前進一步，在新位

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

4、 行、第 m+1 行、第 0 列、第 m+1 列元素全置成“1” ， 表示迷宮的邊界；第 1 行第 1 列元素和第 m 行第 m 列元素置成“0” ， 表示迷宮的入口和出口；其余元素值用隨機函數(shù)產(chǎn)生。假設當前所在位置是（x,y） 。沿某個方向前進一步，它可能到達的位置最多有 8 個。如果用二維數(shù)組 move 記錄 8 個方向上行下標增量和列下標增量，則沿第 i 個方向前進一步，可能到達的新位置坐標可利用 move 數(shù)組確定：x=x+mo

5、ve[i][0]y=y+move[i][1]從迷宮的入口位置開始，沿圖示方向順序依次進行搜索。在搜索過程中，每前進一步，在所到位置處做標記“?”（表示這個位置在通路上） ，并將該位置的坐標壓入棧中。每次后退的時候，先將當前所在位置處的通路標記“?”改6 7 85 14 3 2xy o/*用于記錄和輸出迷宮探路中相關符號，包括 1 .*/char maze[m+2][m+2];/*用棧來存儲探路過程中的數(shù)據(jù)*/position stack

6、[m*m+1];int top;/*棧頂*/int i,x,y,ok;position p;/*二維數(shù)組的第 0 行、第 m+1 行、第 0 列、第 m+1 列元素全置成“1“，表示迷宮的邊界；第 1 行第 1 列元素和第 m 行第 m 列元素置成“0“，表示迷宮的入口和出口；其余元素值用隨機函數(shù)產(chǎn)生。*/srand(time(0));for(x=1;x<=m;x++)for(y=1;y<=m;y++)maze[x][y]=

7、48+rand()%2;maze[1][1]='0';maze[m][m]='0';for(x=0;x<=m+1;x++){maze[x][0]='1';maze[x][m+1]='1';}for(y=0;y<=m+1;y++){maze[0][y]='1';maze[m+1][y]='1';}p.x=1;p.y=1;top=1;

8、stack[top]=p;maze[1][1]='.';/*開始探路走迷宮的過程可以模擬為一個搜索的過程：每到一處，總讓它按東、東南、南、西南、西、西北、北、東北個方向順序試探下一個位置；如果某方向可以通過，并且不曾到達，則前進一步，在新位置上繼續(xù)進行搜索；如果個方向都走不通或曾經(jīng)到達過，則退回一步，在原來的位置上繼續(xù)試探下一位置。每前進或后退一步，都要進行判斷：若前進到了出口處，則說明找到了一條通路；若退回到了入口處，