重慶郵電大學計算機學院計算機專業(yè)實驗中心《數(shù)據(jù)結(jié)構(gòu)》第五次實驗報告學生姓名學生班級學生學號指導老師雷大江實驗內(nèi)容1)利用棧深度優(yōu)先進行迷宮求解。用數(shù)組表示迷宮建立棧，利用棧實現(xiàn)深度優(yōu)先搜索2)利用隊列寬度優(yōu)先進行迷宮求解。用數(shù)組表示迷宮建立隊列，利用隊列實現(xiàn)寬度優(yōu)先搜索需求分析利用棧的結(jié)構(gòu)，走過的路入棧，如果不能走出棧，采用遍歷法，因此棧內(nèi)存儲的數(shù)據(jù)就是尋一條路徑。當?shù)竭_了某點而無路可走時需返回前一點，再從前一點開始向下一個方向繼續(xù)試探。因此，壓入棧中的不僅是順序到達的各點的坐標，而且還要有從前一點到達本點的方向，即每走一步棧中記下的內(nèi)容為(行，列，來的方向)。三、詳細設(shè)計（1）基本代碼structitem{intx;//行inty;//列};itemmove[4];（2）代碼棧構(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;}（3）偽代碼a)棧初始化;b)將入口點坐標及到達該點的方向（設(shè)為-1）入棧c)while(棧不空){棧頂元素＝（x,y,d）出棧;求出下一個要試探的方向d++;while（還有剩余試探方向時）{if（d方向可走）則{（x,y,d）入棧;求新點坐標(i,j);將新點（i,j）切換為當前點（x,y）;if((x,ｙ)==(ｍ,n))結(jié)束;else重置d=0;}elsed++;}}（4）時間復雜程度時間復雜程度為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;}遇到的問題及解決辦法最初程序編寫時不知道怎么實現(xiàn)適用于任何迷宮，后來采取了適當?shù)姆绞?，可以自定義迷宮；由于編程不熟練，開始不知道怎么用棧實現(xiàn)，經(jīng)過查資料并與同學探討，清楚了它的結(jié)構(gòu)原理；另外還有很多標識符使用的小問題，經(jīng)反復調(diào)試后終于得到了解決。六、心得體會編程不是一朝一夕的事，還是熟能生巧，所以一定要多編多練，扎實