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

數(shù)據(jù)結(jié)構(gòu)實驗報告實驗名稱：實驗2——題目3學(xué)生姓名：班級：班內(nèi)序號：學(xué)號：日期：2012年11月17日實驗要求實驗?zāi)康耐ㄟ^選擇下面五個題目之一進行實現(xiàn)，掌握如下內(nèi)容：進一步掌握指針、模板類、異常處理的使用掌握棧的操作的實現(xiàn)方法掌握隊列的操作的實現(xiàn)方法學(xué)習(xí)使用棧解決實際問題的能力學(xué)習(xí)使用隊列解決實際問題的能力2.實驗內(nèi)容利用棧結(jié)構(gòu)實現(xiàn)迷宮求解問題。迷宮求解問題如下：心理學(xué)家把一只老鼠從一個無頂蓋的大盒子的入口趕進迷宮，迷宮中設(shè)置很多隔壁，對前進方向形成了多處障礙，心理學(xué)家在迷宮的唯一出口放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達出口，測試算法的迷宮如下圖所示。提示：1、可以使用遞歸或非遞歸兩種方法實現(xiàn)2、老鼠能夠記住已經(jīng)走過的路，不會反復(fù)走重復(fù)的路徑3、可以自己任意設(shè)置迷宮的大小和障礙4、使用“窮舉求解”的方法2.程序分析2.1存儲結(jié)構(gòu)存儲結(jié)構(gòu)：順序棧datadatadataA1A2A3A2A1A1A2A3A2A1toptoptop（1）空棧(2)A1A2入棧(3)A3出棧2.2關(guān)鍵算法分析1.試探方向：（1）基本思想每個點有4個方向去試探，如當(dāng)前點的坐標(x,y)，與其相鄰的4個點的坐標都可根據(jù)與該點的相鄰方位而得到，如圖所示。因為出口在（m，n），因此試探順序規(guī)定為：從當(dāng)前位置向前試探的方向為從正東沿順時針方向進行。為了簡化問題，方便的求出新點的坐標，將從正東開始沿順時針進行的這4個方向（用0，1，2，3表示東、南、西、北）的坐標增量放在一個結(jié)構(gòu)數(shù)組move[4]中，在move數(shù)組中，每個元素有兩個域組成，x：橫坐標增量，y：縱坐標增量。(x，(x，y)與點(x，y)相鄰的4個點及坐標(x，y+1)(x，y-1)(x+1，y)(x-1，y)xy00111020-13-10增量move數(shù)組（2）基本代碼structitem{intx;//行inty;//列};itemmove[4];2.尋找路徑基本思想：利用棧的結(jié)構(gòu)，走過的路入棧，如果不能走出棧，采用遍歷法，因此棧內(nèi)存儲的數(shù)據(jù)就是尋一條路徑。當(dāng)?shù)竭_了某點而無路可走時需返回前一點，再從前一點開始向下一個方向繼續(xù)試探。因此，壓入棧中的不僅是順序到達的各點的坐標，而且還要有從前一點到達本點的方向，即每走一步棧中記下的內(nèi)容為(行，列，來的方向)。代碼棧構(gòu)造函數(shù)：voidseqstack::Push(intx,inty,intd)//入棧{ if(top>=StackSize-1)throw"上溢"; top++; data[top].d=d; data[top].x=x; data[top].y=y;}尋找路徑：intseqstack::findpath(inta,intb){ itemmove[4]={{0,1},{1,0},{0,-1},{-1,0}};//定義移動結(jié)構(gòu) intx,y,d,i,j; Push(a,b,-1);//起點坐標入棧while(top!=-1) { d=data[top].d+1; x=data[top].x; y=data[top].y; Pop();//出棧while(d<4)//方向是否可以移動 {i=x+move[d].x;j=y+move[d].y;//移動后坐標if(Map[i][j]==0)//是否能移動 {Push(x,y,d);//移動前坐標入棧x=i; y=j; Map[x][y]=-1;if(x==m&&y==n)//判斷是否為終點坐標 { Push(x,y,-1); return1; }elsed=0; } elsed++; } } return0;}偽代碼棧初始化;將入口點坐標及到達該點的方向（設(shè)為-1）入棧while(棧不空){棧頂元素＝（x,y,d）出棧;求出下一個要試探的方向d++;while（還有剩余試探方向時）{if（d方向可走）則{（x,y,d）入棧;求新點坐標(i,j);將新點（i,j）切換為當(dāng)前點（x,y）;if((x,ｙ)==(ｍ,n))結(jié)束;else重置d=0;}elsed++;}}時間復(fù)雜程度時間復(fù)雜程度為O（1）2.3其他在運行時可選擇是否自己構(gòu)造地圖，實現(xiàn)函數(shù)如下：voidcreatmap()//自創(chuàng)地圖函數(shù){ for(inti=1;i<9;i++) { for(intj=1;j<9;j++) Map[i][j]=0; } Map[8][9]=1; printmap(); cout<<"請設(shè)置障礙物位置:（x,y）。(0,0)結(jié)束"<<endl; intp,q; while(1) {cin>>p>>q; if(p==0&&q==0) { cout<<"設(shè)置完成"<<endl; break; } if(p<=0||q<=0||p>=9||q>=9) {cout<<"輸入錯誤！"<<endl; } elseMap[p][q]=1; cout<<"繼續(xù)輸入："<<endl; } cout<<endl; cout<<"請設(shè)置終點位置:"<<endl; cin>>q>>p; m=p;n=q; Map[m][n]=0;}3.程序運行結(jié)果1.主函數(shù)流程開始開始是否自己設(shè)計迷宮是否自己設(shè)計迷宮設(shè)置障礙是設(shè)置障礙否打印地圖設(shè)置終點打印地圖設(shè)置終點設(shè)置起點設(shè)置起點是否有路徑否是否有路徑是打印路徑打印路徑結(jié)束結(jié)束測試條件當(dāng)構(gòu)造的迷宮符合要求，出入的起點正確則能輸出正確路徑3.測試結(jié)果4.總結(jié)最初程序編寫時不知道怎么實現(xiàn)適用于任何迷宮，后來采取了適當(dāng)?shù)姆绞剑梢宰远x迷宮；由于編程不熟練，開始不知道怎么用棧實現(xiàn)，經(jīng)過查資料并與同學(xué)探討，清楚了它的結(jié)構(gòu)原理；另外還有很多標識符使用的小問題，經(jīng)反復(fù)調(diào)試后終于得到了解決。編程不是一朝一夕的事，還是熟能生巧，所以一