數據結構實驗2棧和隊列迷宮問題求解

1、數據結構實驗報告實驗名稱： 實驗 2——題目 3學生姓名： 班 級：班內序號： 學 號：日 期： 2012 年 11 月 17 日1． 實驗要求1. 實驗目的通過選擇下面五個題目之一進行實現，掌握如下內容：? 進一步掌握指針、模板類、異常處理的使用? 掌握棧的操作的實現方法? 掌握隊列的操作的實現方法? 學習使用棧解決實際問題的能力? 學習使用隊列解決實際問題的能力2 .實驗內容利用棧結構實現迷宮求解問題。迷宮求

2、解問題如下：心理學家把一只老鼠從一個無頂蓋的大盒子的入口趕進迷宮，迷宮中設置很多隔壁，對前進方向形成了多處障礙，心理學家在迷宮的唯一出口放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達出口，測試算法的迷宮如下圖所示。提示：1、可以使用遞歸或非遞歸兩種方法實現2、老鼠能夠記住已經走過的路，不會反復走重復的路徑3、可以自己任意設置迷宮的大小和障礙4、使用“窮舉求解”的方法增量 move 數組 （2）基本代碼struct item {int

3、 x ; //行int y ; //列} ; item move[4] ;2.尋找路徑（1） 基本思想：利用棧的結構，走過的路入棧，如果不能走出棧，采用遍歷法，因此棧內存儲的數據就是尋一條路徑。當到達了某點而無路可走時需返回前一點，再從前一點開始向下一個方向繼續(xù)試探。因此，壓入棧中的不僅是順序到達的各點的坐標，而且還要有從前一點到達本點的方向，即每走一步棧中記下的內容為(行，列，來的方向)。（2） 代碼棧構造函數：void se

4、qstack::Push(int x,int y,int d) //入棧{if(top>=StackSize-1)throw“上溢“;top++;data[top].d=d;data[top].x=x;data[top].y=y;}尋找路徑：int seqstack::findpath(int a,int b){item move[4]={{0,1},{1,0},{0,-1},{-1,0}};//定義移動結構int x, y,