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

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

2、解問題如下：心理學(xué)家把一只老鼠從一個(gè)無頂蓋的大盒子的入口趕進(jìn)迷宮，迷宮中設(shè)置很多隔壁，對(duì)前進(jìn)方向形成了多處障礙，心理學(xué)家在迷宮的唯一出口放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達(dá)出口，測(cè)試算法的迷宮如下圖所示。提示：1、可以使用遞歸或非遞歸兩種方法實(shí)現(xiàn)2、老鼠能夠記住已經(jīng)走過的路，不會(huì)反復(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)存儲(chǔ)的數(shù)據(jù)就是尋一條路徑。當(dāng)?shù)竭_(dá)了某點(diǎn)而無路可走時(shí)需返回前一點(diǎn)，再?gòu)那耙稽c(diǎn)開始向下一個(gè)方向繼續(xù)試探。因此，壓入棧中的不僅是順序到達(dá)的各點(diǎn)的坐標(biāo)，而且還要有從前一點(diǎn)到達(dá)本點(diǎn)的方向，即每走一步棧中記下的內(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}};//定義移動(dòng)結(jié)構(gòu)int x, y,