迷宮問題課程設計報告

1、<p>　　數(shù)據(jù)結(jié)構(gòu)課程設計報告</p><p>　　題 目： 迷宮問題</p><p><b>　　一. 設計目的</b></p><p>　?。?）熟練掌握鏈棧的基本操作及應用。</p><p>　　（2）利用鏈表作為棧的存儲結(jié)構(gòu)，設計實現(xiàn)一個求解迷宮的非遞歸程序。</p>&l

2、t;p><b>　　二. 設計內(nèi)容</b></p><p>　　計算機解迷宮通常用的是“窮舉求解”方法，即從入口出發(fā)，順著某一個方向進行探索，若能走通，則繼續(xù)往前進；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到則未能到達出口，則所設定的迷宮沒有通解。</p><p>　　可以二維數(shù)組存儲迷宮數(shù)據(jù)，通常設定入口點的

3、下標為（1，1），出口點的下標為（n,n）。為處理方便起見，可以迷宮的四周加一圈障礙。對于迷宮任一位置，均可約定有東、南、西、北四個方向可通。</p><p><b>　　三．概要設計</b></p><p>　　以一個m×n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序，對信任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論

4、。</p><p>　　首先實現(xiàn)一個鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以二元組（i,j）的形式輸出，其中：（i,j）指示迷宮中的一個坐標。如：對于下列數(shù)據(jù)的迷宮，輸出的一條通路為：（1，1），（1，2），（2，2），（3，2），（3，1），……</p><p><b>　　1．功能模塊圖；</b></p><p&g

5、t;<b>　　數(shù)據(jù)結(jié)構(gòu)</b></p><p>　　int mark[N][M] = {0};/*初始化標志位,0代表沒走過,1代表走過*/ </p><p><b>　　/*方向*/ </b></p><p>　　typedef struct{ </p><p>　　short int vert

6、; </p><p>　　short int horiz; </p><p>　　}offsets; </p><p>　　offsets move[4] = {{0,1},{1,0},{0,-1},{-1,0}};/*北,東,南,西*/ </p><p><b>　　/*迷宮類型*/ </b></p>&

7、lt;p>　　typedef struct { </p><p>　　short int row; </p><p>　　short int col; </p><p>　　short int dir; </p><p>　　}element; </p><p>　　element stack[MAX];<

8、/p><p><b>　　各個函數(shù)</b></p><p>　　element del(int* top)//出棧,top指向棧頂元素</p><p>　　void add(int* top,element item)/*入棧*/</p><p>　　void path(void)/*迷宮函數(shù)*/</p>&l

9、t;p>　　2．各個模塊詳細的功能描述。</p><p>　　出棧函數(shù)，top指向棧頂元素</p><p>　　入棧函數(shù)，將可走的路徑入棧</p><p><b>　　迷宮函數(shù)，進行尋路</b></p><p><b>　　模塊層次調(diào)用關(guān)系圖</b></p><p>&

10、lt;b>　　四．詳細設計</b></p><p>　　while(top > -1 && !found) </p><p><b>　　{ </b></p><p>　　position= del(&top); /*將棧頂元素取出,*/ </p><p>　　row =

11、 position.row; /*利用中間變量row,col,dir等候判斷*/ </p><p>　　col = position.col; </p><p>　　dir = position.dir; </p><p>　　while(dir < 4 && !found) </p><p>&l

12、t;b>　　{ </b></p><p>　　next_row = row + move[dir].vert; </p><p>　　next_col = col + move[dir].horiz; </p><p>　　if(row == 9&& col == 8) //判斷是否找到終點</p><p>

13、　　found = 1; </p><p>　　else if(!maze[next_row][next_col] && !mark[next_row][next_col])/*判斷下一步可走并且沒走過,則入棧*/ </p><p><b>　　{ </b></p><p>　　mark[next_row][next_col]

14、= 1; </p><p>　　position.row = row; </p><p>　　position.col = col; </p><p>　　position.dir = ++dir; </p><p>　　add(&top,position);/*合理則入棧*/ </p><p>　　row =

15、 next_row;/*繼續(xù)向下走*/ </p><p>　　col = next_col;</p><p><b>　　dir = 0; </b></p><p><b>　　} </b></p><p><b>　　else </b></p><p>

16、;　　dir++;/*dir<4時,改變方向*/</p><p>　　起點路徑入棧，判斷棧是否滿了，并且是否找到出口，將棧頂元素去除，利用中間變量row,col,dir等候判斷，首先判斷是否找到終點，選擇北,東,南,西四個方向，offsets move[4] = {{0,1},{1,0},{0,-1},{-1,0}};，運用這個轉(zhuǎn)換方向，判斷下一步可走并且沒走過,則入棧，可走的話，標志數(shù)組標志為1，合理可走

17、則入棧，繼續(xù)往下走，不合理則dir++，進行下次判斷。四個方向都走不通的話，棧頂元素出棧，繼續(xù)進行下面的判斷，直到找到終點或者走不通。</p><p>　　找到終點后，倒序打印棧里的元素，就是路徑，并保存。</p><p>　　五．測試數(shù)據(jù)及運行結(jié)果</p><p>　　1．正常測試數(shù)據(jù)和運行結(jié)果</p><p>　　int maze[N][

18、M] =</p><p>　　{ {1,1,1,1,1,1,1,1,1,1},</p><p>　　{1,0,0,1,0,0,0,1,0,1},</p><p>　　{1,0,0,1,0,0,0,1,0,1},</p><p>　　{1,0,0,0,0,1,1,0,1,1},</p><p>　　{1,0,1,1,1

19、,0,0,1,0,1},</p><p>　　{1,0,0,0,1,0,0,0,0,1},</p><p>　　{1,0,1,0,0,0,1,0,1,1},</p><p>　　{1,0,1,1,1,1,0,0,1,1},</p><p>　　{1,1,1,0,0,0,1,0,1,1},</p><p>　　{1,1,

20、1,0,0,0,0,0,0,1},</p><p>　　{1,1,1,1,1,1,1,1,1,1},</p><p>　　};/*初始化迷宮*/</p><p>　　2．異常測試數(shù)據(jù)及運行結(jié)果</p><p>　　int maze[N][M] =</p><p>　　{ {1,1,1,1,1,1,1,1,1,1},&

21、lt;/p><p>　　{1,0,0,1,0,0,0,1,0,1},</p><p>　　{1,0,0,1,0,0,0,1,0,1},</p><p>　　{1,0,0,0,0,1,1,0,1,1},</p><p>　　{1,0,1,1,1,0,0,1,0,1},</p><p>　　{1,0,0,0,1,0,0,0,0

22、,1},</p><p>　　{1,0,1,0,0,0,1,0,1,1},</p><p>　　{1,0,1,1,1,1,0,0,1,1},</p><p>　　{1,1,1,0,0,0,1,0,1,1},</p><p>　　{1,1,1,0,0,0,0,0,0,1},</p><p>　　{1,1,1,1,1,1,

23、1,1,1,1},</p><p>　　};/*初始化迷宮*/</p><p>　　六．調(diào)試情況，設計技巧及體會</p><p>　　調(diào)試比較順利，幾乎沒有出現(xiàn)什么重大問題，在和同學的討論之后，改進了算法。</p><p><b>　　1．改進方案</b></p><p>　　在對文件的存儲方面，

24、有一些不足，存儲出來的東西，也只是一些數(shù)字，不能很好地讀取。</p><p>　　在對迷宮的生成方面，也有一些不足，只是能簡單地初始化迷宮。</p><p><b>　　2．體會</b></p><p>　　剛開始主要是在尋找路徑那里遇到了很多問題，起初我用一個棧來比較符合通路的坐標，實現(xiàn)起來很費力。在返回值進出棧時又碰到麻煩，就是top=to

25、p->next和return top->data這兩個地方，有時沒出錯了但就是不能運行出結(jié)果。改了很久也糾正不過來，在同學給的建議下，position.dir = ++dir;，實現(xiàn)了。。</p><p>　　在輸出路徑時，怎么標記當前位置的四個方向也是一個難題。我就在考慮怎么指向才是正確的，通過不斷實踐，認為用路徑出棧時已出棧的坐標和棧頂值的差值可以正確的確定路徑的方向，把它倒退回去看就可以了。&l

26、t;/p><p>　　對棧的理解，也有了一定的加深，遺憾的是，沒有寫其他兩個程序，有空一定把它們完成要能很好的掌握編程僅僅通過幾個簡單的程序的編寫是無法達成的更需要大量積和深入有可能就從這個迷宮的問題來說在搜索的算法來解決兩點間最短路徑問題在程序的編寫中也不能一味得向已有的程序進行模仿而要自己去摸索去尋求最好的解決方式只有帶著問題去反復進行實踐才能更熟練的掌握和運用當對現(xiàn)有的程序也要多去接觸因為有些程序是我們無法在短