北郵數(shù)據(jù)結構實驗二題目3

北京郵電大學電信工程學院第1頁北京郵電大學電信工程學院第1頁2008級數(shù)據(jù)結構實驗報告實驗名稱：實驗二棧和隊列學生姓名：班級：2008211113班內序號：學號：日期：2009年11月8日實驗要求a.實驗目的通過選擇下面五個題目之一進行實現(xiàn)，掌握如下內容：進一步掌握指針、模板類、異常處理的使用掌握棧的操作的實現(xiàn)方法掌握隊列的操作的實現(xiàn)方法學習使用棧解決實際問題的能力學習使用隊列解決實際問題的能力b.實驗內容利用棧結構實現(xiàn)迷宮求解問題。迷宮求解問題如下：心理學家把一只老鼠從一個無頂蓋的大盒子的入口趕進迷宮，迷宮中設置很多隔壁，對前進方向形成了多處障礙，心理學家在迷宮的唯一出口放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達出口，測試算法的迷宮如下圖所示。2.程序分析2.1存儲結構存儲結構:隊列順序存儲結構示意圖如下:2.2關鍵算法分析核心算法思想：如果采用直接遞歸的方式，用棧很容易實現(xiàn)路徑的輸出，但是這條路徑不一定是最短路徑。為了改進算法，達到輸出最短路徑的目標，采用隊列的實現(xiàn)方式。為查找最短路徑，使用了“圖”中的算法：廣度優(yōu)先搜索。關鍵算法思想描述和實現(xiàn)：關鍵算法1：為尋求最短路徑，采用廣度優(yōu)先搜索算法，使用隊列實現(xiàn)路徑存儲，隊列中每個元素用結構體存儲系，包含迷宮坐標、隊列中的序號、父節(jié)點的序號，實現(xiàn)了對路徑的記錄。C++實現(xiàn)：structNode { int parent_id; //保存父節(jié)點的位置 int node_id; //當前節(jié)點的序號，以便傳遞給孩子節(jié)點 int x,y; //當前結點對應的坐標 }Q[10*10];//每個節(jié)點包含迷宮坐標、隊列中的序號、父節(jié)點的序號，多個節(jié)點形成隊列關鍵算法2：遍歷每個位置四周的位置，將沒有走過的位置入隊，形成樹形的隊列，通過出隊操作就能找到最短路徑。C++實現(xiàn)：boolGetNextPos(int*i,int*j,intcount){switch(count){case1:(*j)++;return1;//右case2:(*i)++;return1;//下case3:(*j)--;return1;//左case4:(*i)--;return1;//上default:return0;}}voidEnQueue(inti,intj,intk){ Q[rear].x=i; Q[rear].y=j; //保存當前節(jié)點對應的坐標位置 Q[rear].parent_id=k; //保存父節(jié)點的序號 Q[rear].node_id=rear; //保存當前節(jié)點序號 rear++;}關鍵算法3：廣度優(yōu)先搜索算法的實現(xiàn)，找到最短路徑。廣度優(yōu)先算法在此相當于樹的層序遍歷，如下圖：在迷宮地圖中，關鍵算法三通過不斷調用關鍵算法二就能將地圖中可以走的位置入隊，形成類似上圖的樹形結構，之后廣度搜索到最淺深度即為最短路徑。例如H節(jié)點的坐標就是出口坐標，當層序搜索到H時就終止了，入隊工作結束，不再將I和J入隊。通過關鍵算法四逆序就能找到最短路徑A->B->C。其實最短路徑不一定只有一條，例如J點也可能是出口坐標，但是當搜索到H時就停止了，故此算法只是輸出了所有最短路徑中可能的一條。C++實現(xiàn)：voidShortestPath_BFS(inti,intj){ intcount,m,n,k; EnQueue(i,j,-1); Map[1][1]=1; //起點入隊,標記起點已走過 while(true) { count=1; DeQueue(&i,&j,&k); n=i,m=j; //保存當前位置 while(GetNextPos(&i,&j,count)) { count++; if(!Map[i][j]) { EnQueue(i,j,k); Map[i][j]=1; if(i==8&&j==9)return; //到達終點,(8,9)是默認終點，可以任意修改 } i=n;j=m; //保證遍歷當前坐標的所有相鄰位置 } }}關鍵算法4：使用隊列指針查找父節(jié)點的方式，從隊尾回溯到隊首，標記出最短路徑。隊列的元素示意圖如下：入隊之后的隊列如下圖：563774713…………例如從13號節(jié)點可以讀出它在迷宮地圖中的坐標（7，4），通過第三個元素7就能找到第七號節(jié)點，也即其父節(jié)點（5，6），從父節(jié)點又可以同理找到它的父節(jié)點第三號節(jié)點。這樣就能實現(xiàn)逆序找到路徑。C++實現(xiàn)：k=rear-1; while(k!=-1) { i=Q[k].x; j=Q[k].y; Map[i][j]=2; k=Q[k].parent_id; } 時間復雜度與空間復雜度：算法一和二時間復雜度與空間復雜度均為O(1)。算法三占用空間為迷宮邊長n的平方，故空間復雜度為O(n*n)。最多走n*n步,最少走1步，故時間復雜度為O(n*n/2)。

開始3.程序運行結果開始輸出迷宮圖輸出迷宮圖輸入x,y輸入x,y否否(x,y)是否合法(x,y)是否合法是是廣度優(yōu)先搜索廣度優(yōu)先搜索標記最短路徑標記最短路徑輸出最短路徑輸出最短路徑結結束測試條件：以實驗題目中給出的迷宮圖進行測試。測試時固定終點位置，選擇不同的起點位置進行測試，測試各個位置下的輸出是否正常。測試結論：本程序對于測試地圖在不同起始和終止位置輸出都完全正確。

4.總結1、在最初嘗試編寫代碼時，采用的是遞歸算法。雖然用棧實現(xiàn)代碼很簡單，只需要向四個方向不斷遞歸即可，但是使用棧并不能保證輸出的路徑是最佳路徑。所以在完成了遞歸算法之后，我開始思索如何能輸出最短路徑。查找大量資料，結論是用棧很難實現(xiàn)，即使要實現(xiàn)也需要不斷比較各種路徑的長短，然后不斷更新最短路徑。偶然發(fā)現(xiàn)迪杰斯特拉算法，后又學習廣度優(yōu)先搜索算法，才用隊列才最終使得問題得以解決。2、在將新算法應用到迷宮問題過程中，遇到不少困難，反復琢磨和看書才將其解決。由于順序隊列的出隊入隊操作加上了賦值和標記位置、建立鏈表關系，實際將一個順序隊列以指針的作用，變成了一棵樹的結構，而樹的深度恰好能反映最短路徑。3、從一個小小的迷宮問題，引出了許多知識，這種探索式的學習是很有意義的。從迷宮基本的遞歸和回溯到棧的運用和理解，再到隊列的運用，后又到樹與圖以及隊列的綜合運用，將很多知識點串聯(lián)起來了，加深了理解。同時探索式地學習迪杰斯特拉算法也收獲頗多。4、改進：本題為了實現(xiàn)代碼的簡便，沒有采用鏈隊結構，因而浪費了一定的空間，特別是當迷宮的邊長很長的時候，空間復雜度