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