數(shù)據(jù)結(jié)構(gòu)實驗2棧和隊列迷宮問題求解

1、數(shù)據(jù)結(jié)構(gòu)實驗報告實驗名稱： 實驗 2——題目 3學(xué)生姓名： 班 級：班內(nèi)序號： 學(xué) 號：日 期： 2012 年 11 月 17 日1． 實驗要求1. 實驗?zāi)康耐ㄟ^選擇下面五個題目之一進行實現(xiàn)，掌握如下內(nèi)容：? 進一步掌握指針、模板類、異常處理的使用? 掌握棧的操作的實現(xiàn)方法? 掌握隊列的操作的實現(xiàn)方法? 學(xué)習(xí)使用棧解決實際問題的能力? 學(xué)習(xí)使用隊列解決實際問題的能力2 .實驗內(nèi)容利用棧結(jié)構(gòu)實現(xiàn)迷宮求解問題。迷宮求

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

3、 x ; //行int y ; //列} ; item move[4] ;2.尋找路徑（1） 基本思想：利用棧的結(jié)構(gòu)，走過的路入棧，如果不能走出棧，采用遍歷法，因此棧內(nèi)存儲的數(shù)據(jù)就是尋一條路徑。當(dāng)?shù)竭_了某點而無路可走時需返回前一點，再從前一點開始向下一個方向繼續(xù)試探。因此，壓入棧中的不僅是順序到達的各點的坐標(biāo)，而且還要有從前一點到達本點的方向，即每走一步棧中記下的內(nèi)容為(行，列，來的方向)。（2） 代碼棧構(gòu)造函數(shù)：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}};//定義移動結(jié)構(gòu)int x, y,