數(shù)據(jù)結(jié)構(gòu)實驗報告-棧和隊列.doc

2008級數(shù)據(jù)結(jié)構(gòu)實驗報告實驗名稱： 實驗二 棧和隊列學生姓名： 班 級： 班內(nèi)序號： 學 號： 日 期： 2009年11月8日1 實驗要求a. 實驗目的通過選擇下面五個題目之一進行實現(xiàn)，掌握如下內(nèi)容： 進一步掌握指針、模板類、異常處理的使用 掌握棧的操作的實現(xiàn)方法 掌握隊列的操作的實現(xiàn)方法 學習使用棧解決實際問題的能力 學習使用隊列解決實際問題的能力b. 實驗內(nèi)容利用棧結(jié)構(gòu)實現(xiàn)迷宮求解問題。迷宮求解問題如下：心理學家把一只老鼠從一個無頂蓋的大盒子的入口趕進迷宮，迷宮中設(shè)置很多隔壁，對前進方向形成了多處障礙，心理學家在迷宮的唯一出口放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達出口，測試算法的迷宮如下圖所示。2. 程序分析2.1 存儲結(jié)構(gòu) 存儲結(jié)構(gòu):隊列順序存儲結(jié)構(gòu)示意圖如下: 2.2 關(guān)鍵算法分析核心算法思想：1. 如果采用直接遞歸的方式，用棧很容易實現(xiàn)路徑的輸出，但是這條路徑不一定是最短路徑。為了改進算法，達到輸出最短路徑的目標，采用隊列的實現(xiàn)方式。2. 為查找最短路徑，使用了“圖”中的算法：廣度優(yōu)先搜索。關(guān)鍵算法思想描述和實現(xiàn)：關(guān)鍵算法1：為尋求最短路徑，采用廣度優(yōu)先搜索算法，使用隊列實現(xiàn)路徑存儲，隊列中每個元素用結(jié)構(gòu)體存儲系，包含迷宮坐標、隊列中的序號、父節(jié)點的序號，實現(xiàn)了對路徑的記錄。C+實現(xiàn)：struct Nodeintparent_id;/保存父節(jié)點的位置intnode_id;/當前節(jié)點的序號，以便傳遞給孩子節(jié)點int x,y; /當前結(jié)點對應(yīng)的坐標Q10*10; /每個節(jié)點包含迷宮坐標、隊列中的序號、父節(jié)點的序號，多個節(jié)點形成隊列關(guān)鍵算法2：遍歷每個位置四周的位置，將沒有走過的位置入隊，形成樹形的隊列，通過出隊操作就能找到最短路徑。C+實現(xiàn)：bool GetNextPos(int *i ,int *j,int count) switch(count) case 1:(*j)+; return 1; /右 case 2:(*i)+; return 1; /下 case 3:(*j)-; return 1; /左 case 4:(*i)-; return 1; /上 default: return 0; void EnQueue(int i,int j,int k)Qrear.x = i;Qrear.y = j;/保存當前節(jié)點對應(yīng)的坐標位置Qrear.parent_id = k;/保存父節(jié)點的序號Qrear.node_id = rear; /保存當前節(jié)點序號rear+;關(guān)鍵算法3：廣度優(yōu)先搜索算法的實現(xiàn)，找到最短路徑。廣度優(yōu)先算法在此相當于樹的層序遍歷，如下圖：在迷宮地圖中，關(guān)鍵算法三通過不斷調(diào)用關(guān)鍵算法二就能將地圖中可以走的位置入隊，形成類似上圖的樹形結(jié)構(gòu)，之后廣度搜索到最淺深度即為最短路徑。例如H節(jié)點的坐標就是出口坐標，當層序搜索到H時就終止了，入隊工作結(jié)束，不再將I和J入隊。通過關(guān)鍵算法四逆序就能找到最短路徑A-B-C。其實最短路徑不一定只有一條，例如J點也可能是出口坐標，但是當搜索到H時就停止了，故此算法只是輸出了所有最短路徑中可能的一條。C+實現(xiàn)：void ShortestPath_BFS(int i ,int j)int count,m,n,k;EnQueue(i,j,-1);Map11 = 1;/起點入隊,標記起點已走過while(true)count = 1;DeQueue(&i,&j,&k);n = i,m = j; /保存當前位置while(GetNextPos(&i,&j,count)count+;if(!Mapij) EnQueue(i,j,k);Mapij = 1;if(i = 8 & j = 9) return;/到達終點,(8,9)是默認終點，可以任意修改i = n; j = m;/保證遍歷當前坐標的所有相鄰位置關(guān)鍵算法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 = Qk.x;j = Qk.y;Mapij = 2;k = Qk.parent_id;時間復雜度與空間復雜度：算法一和二時間復雜度與空間復雜度均為O(1)。算法三占用空間為迷宮邊長n的平方，故空間復雜度為O(n*n)。最多走n*n步,最少走1步，故時間復雜度為O(n*n/2)。開始3. 程序運行結(jié)果輸出迷宮圖輸入x,y否(x,y)是否合法是廣度優(yōu)先搜索標記最短路徑輸出最短路徑結(jié) 束測試條件：以實驗題目中給出的迷宮圖進行測試。測試時固定終點位置，選擇不同的起點位置進行測試，測試各個位置下的輸出是否正常。測試結(jié)論：本程序?qū)τ跍y試地圖在不同起始和終止位置輸出都完全正確。 4. 總結(jié)1、在最初嘗試編寫代碼時，采用的是遞歸算法。雖然用棧實現(xiàn)代碼很簡單，只需要向四個方向不斷遞歸即可，但是使用棧并不能保證輸出的路徑是最佳路徑。所以在完成了遞歸算法之后，我開始思索如何能輸出最短路徑。查找大量資料，結(jié)論是用棧很難實現(xiàn)，即使要實現(xiàn)也需要不斷比較各種路徑的長短，然后不斷更新最短路徑。偶然發(fā)現(xiàn)迪杰斯特拉算法，后又學習廣度優(yōu)先搜索算法，才用隊列才最終使得問題得以解決。2、在將新算法應(yīng)用到迷宮問題過程中，遇到不少困難，反復琢磨和看書才將其解決。由于順序隊列的出隊入隊操作加上了賦值和標記位置、建立鏈表關(guān)系，實際將一個順序隊列以指針的作用，變成了一棵樹的結(jié)構(gòu)，而樹的深度恰好能反映最短路徑。3、從一個小小的迷宮問題，引出了許多知識，這種探索式的學習是很有意義的。從迷宮基本的遞歸和回溯到棧的運用和理解，再到隊列的運用，后又到樹與圖以及隊列的綜合運用，將很多知識點串聯(lián)起來了，加深了理解。同時探索式地學習迪杰斯特拉算法也收獲頗多。4、改進：本題為了實現(xiàn)代碼的簡便，沒有采用鏈隊結(jié)構(gòu)，因而浪費了一定的空間，特別是當迷宮的邊長很長的時候，空間復雜度以O(shè)（n*n）增長，程序效率將大大降低，因而如果是計算復雜的迷宮，可以考慮將本程序的順序隊列稍加修改變?yōu)殒滉?，實現(xiàn)動態(tài)分配內(nèi)存，以節(jié)省空間消耗。5、進一步的思考：此方法只能輸出一條最短路徑，如何能輸出所有最短路徑？初步算法是將同一深度的節(jié)點全部遍歷，如果后續(xù)還有同樣長度的路徑則輸出該路徑，如果沒有則只有一條最短路徑。附錄源代碼:/本程序在windows7 、visual studio2008 環(huán)境下調(diào)試運行成功#includeusing namespace std;voidEnQueue(int i,int j,int k); /入隊一個節(jié)點voidDeQueue(int *i,int *j,int *k); /獲取當前節(jié)點的序號和對應(yīng)的迷宮坐標，然后出列boolGetNextPos(int *i ,int *j,int count); /得到下一個鄰接點的位置voidShortestPath_BFS(int i,int j); /廣度優(yōu)先遍歷尋找最短路徑voidShortestPath(); /輸出最短路徑 voidPrint(); /輸出迷宮形狀 int Map1010 = 1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1;struct Nodeintparent_id;/保存父節(jié)點的位置intnode_id;/當前節(jié)點的序號，以便傳遞給孩子節(jié)點int x,y;/當前結(jié)點對應(yīng)的坐標Q10*10;/每個節(jié)點包含迷宮坐標、隊列中的序號、父節(jié)點的序號，多個節(jié)點形成隊列 int front = 0,rear = 0;/隊列頭指針和尾指針void main()cout程序說明：n1.輸出路徑為最短路徑；n2.默認的出口在最右下角，如有需要可以調(diào)整。nn;cout初始地圖如下：endl; Print();inti,j;reinput:cout請輸入起點坐標（x,y）： ij;if(Mapij) cout不能從該處出發(fā)，請重新輸入！endl;goto reinput; ShortestPath_BFS(i,j);cout最短路徑之一如下：endl;ShortestPath();void EnQueue(int i,int j,int k)Qrear.x = i;Qrear.y = j;/保存當前節(jié)點對應(yīng)的坐標位置Qrear.parent_id = k;/保存父節(jié)點的序號Qrear.node_id = rear; /保存當前節(jié)點序號rear+;void DeQueue(int *i,int *j,int *k)*i = Qfront.x;*j = Qfront.y;*k = Qfront.node_id;front+;/出列一個節(jié)點bool GetNextPos(int *i ,int *j,int count) switch(count) case 1:(*j)+; return 1; /右 case 2:(*i)+; return 1; /下 case 3:(*j)-; return 1; /左 case 4:(*i)-; return 1; /上 default: return 0; void ShortestPath_BFS(int i ,int j)int count,m,n,k;EnQueue(i,j,-1);Map11 = 1;/起點入隊,標記起點已走過while(true)count = 1;DeQueue(&i,&j,&k);n = i,m = j; /保存當前位置while(GetNextPos(&i,&j,count)count+;if(!Mapij) EnQueue(i,j,k);Mapij = 1;if(i = 8 & j = 9) return;/到達終點,(8,9)是默認終點，可以任意修改i = n; j = m;/保證遍歷當前坐標的所有相鄰位置void ShortestPath()int i,j,k,sum(0) ;k = rear-1;while(k != -1)i = Qk.x;j = Qk.y;Mapij = 2;k = Qk.parent_id;cout 0 1 2 3 4 5 6 7