數據結構課程設計

上學時沒學過數據結構和算法，於是現在有機會就自學。下面是我最近在等待進入項目組期間，花了1小時學習了一下迷宮問題。

一．需求設計：以一個m*m 的方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口的通道，或得出沒有通路的結論。

二．概要設計：

存儲結構：

採用了數組以及結構體來存儲數據，在探索迷宮的過程中用到的棧，屬於順序存儲結構。

/*八個方向的數組表示形式*/

int move[8][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個方向順序試探下一個位置；如果某方向可以通過，並且不曾到達，則前進一步，在新位置上繼續進行搜索；如果8個方向都走不通或曾經到達過，則退回一步，在原來的位置上繼續試探下一位置。

每前進或後退一步，都要進行判斷：若前進到了出口處，則說明找到了一條通路；若退回到了入口處，則說明不存在通路。

用一個字符類型的二維數組表示迷宮，數組中每個元素取值“0”（表示通路）或“1”（表示牆壁）。迷宮的入口點在位置（1，1）處，出口點在位置（m,m）處。設計一個模擬走迷宮的算法，爲其尋找一條從入口點到出口點的通路。

二維數組的第0行、第m+1行、第0列、第m+1列元素全置成“1”，表示迷宮的邊界；第1行第1列元素和第m行第m列元素置成“0”，表示迷宮的`入口和出口；其餘元素值用隨機函數產生。

假設當前所在位置是（x,y）。沿某個方向前進一步，它可能到達的位置最多有8個。

如果用二維數組move記錄8個方向上行下標增量和列下標增量，則沿第i個方向前進一步，可能到達的新位置座標可利用move數組確定：

x=x+move[i][0]

y=y+move[i][1]

從迷宮的入口位置開始，沿圖示方向順序依次進行搜索。在搜索過程中，每前進一步，在所到位置處做標記“”（表示這個位置在通路上），並將該位置的座標壓入棧中。每次後退的時候，先將當前所在位置處的通路標記“”改成死路標記“×”（表示這個位置曾到達過但走不通，以後不要重複進入），然後將該位置的座標從棧頂彈出。搜索到出口位置時，數組中那些值爲“”的元素形成一條通路。