數(shù)據(jù)結(jié)構(gòu)實驗報告棧和隊列(迷宮圖最短路徑)

1、目錄一、實驗要求（需求分析）3a. 實驗?zāi)康?b. 實驗內(nèi)容3c程序功能3二、程序分析42.1 存儲結(jié)構(gòu)42.2 關(guān)鍵算法分析4三、程序運行分析81.程序運行流程圖：82.程序運行結(jié)果截圖：9四總結(jié)11五、附錄12一、實驗要求（需求分析）a. 實驗?zāi)康耐ㄟ^實驗，掌握如下內(nèi)容： 進(jìn)一步掌握指針、模板類、異常處理的使用 掌握隊列的操作的實現(xiàn)方法 學(xué)習(xí)使用隊列解決實際問題的能力 學(xué)習(xí)使用圖的廣度優(yōu)先搜索解決實際問題的能力b. 實驗內(nèi)容利用隊的結(jié)構(gòu)實現(xiàn)迷宮求解問題。迷宮求解問題如下：心理學(xué)家把一只老鼠從一個無頂蓋的大盒子的入口趕進(jìn)迷宮，迷宮中設(shè)置很多隔壁，對前進(jìn)方向形成了多處障礙，心理學(xué)家在迷宮的唯一

2、出口放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達(dá)出口，測試算法的迷宮如下圖所示。c程序功能輸入起始點的坐標(biāo)，輸出走出迷宮最短路徑的長度。二、程序分析2.1 存儲結(jié)構(gòu) 存儲結(jié)構(gòu): 隊列順序存儲結(jié)構(gòu)示意圖如下: 2.2 關(guān)鍵算法分析核心算法思想：1. 如果采用直接遞歸的方式，用棧很容易實現(xiàn)路徑的輸出，但是這條路徑不一定是最短路徑。為了改進(jìn)算法，達(dá)到輸出最短路徑的目標(biāo)，采用隊列的實現(xiàn)方式。2. 為查找最短路徑，使用了“圖”中的算法：廣度優(yōu)先搜索。關(guān)鍵算法思想描述和實現(xiàn)：關(guān)鍵算法1：為尋求最短路徑，采用廣度優(yōu)先搜索算法，使用隊列實現(xiàn)路徑存儲，隊列中每個元素用結(jié)構(gòu)體存儲系，包含迷宮坐標(biāo)、隊列中的序號、

3、父節(jié)點的序號，實現(xiàn)了對路徑的記錄。c+實現(xiàn)：struct nodeintparent_id;/保存父節(jié)點的位置intnode_id;/當(dāng)前節(jié)點的序號，以便傳遞給孩子節(jié)點int x,y; /當(dāng)前結(jié)點對應(yīng)的坐標(biāo)q10*10; /每個節(jié)點包含迷宮坐標(biāo)、隊列中的序號、父節(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)+; r

4、eturn 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;/保存當(dāng)前節(jié)點對應(yīng)的坐標(biāo)位置qrear.parent_id = k;/保存父節(jié)點的序號qrear.node_id = rear; /保存當(dāng)前節(jié)點序號rear+;關(guān)鍵算法3：廣度優(yōu)先搜索算法的實現(xiàn)，找到最短路徑。廣度優(yōu)先算法在此相當(dāng)于樹的層序遍歷，如下圖：在迷宮地圖中，關(guān)鍵算法三通過不斷調(diào)用關(guān)鍵算法二就能將地圖中可以走的

5、位置入隊，形成類似上圖的樹形結(jié)構(gòu)，之后廣度搜索到最淺深度即為最短路徑。例如h節(jié)點的坐標(biāo)就是出口坐標(biāo)，當(dāng)層序搜索到h時就終止了，入隊工作結(jié)束，不再將i和j入隊。通過關(guān)鍵算法四逆序就能找到最短路徑a-b-c。其實最短路徑不一定只有一條，例如j點也可能是出口坐標(biāo)，但是當(dāng)搜索到h時就停止了，故此算法只是輸出了所有最短路徑中可能的一條。c+實現(xiàn)：void shortestpath_bfs(int i ,int j)int count,m,n,k;enqueue(i,j,-1);map11 = 1;/起點入隊,標(biāo)記起點已走過while(true)count = 1;dequeue(&i,&j,&k);n

6、= i,m = j; /保存當(dāng)前位置while(getnextpos(&i,&j,count)count+;if(!mapij) enqueue(i,j,k);mapij = 1;if(i = 8 & j = 9) return;/到達(dá)終點,(8,9)是默認(rèn)終點，可以任意修改i = n; j = m;/保證遍歷當(dāng)前坐標(biāo)的所有相鄰位置關(guān)鍵算法4：使用隊列指針查找父節(jié)點的方式，從隊尾回溯到隊首，標(biāo)記出最短路徑。隊列的元素示意圖如下：入隊之后的隊列如下圖：563774713 例如從13號節(jié)點可以讀出它在迷宮地圖中的坐標(biāo)（7，4），通過第三個元素7就能找到第七號節(jié)點，也即其父節(jié)點（5，6），從父節(jié)點又

7、可以同理找到它的父節(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;時間復(fù)雜度與空間復(fù)雜度：算法一和二時間復(fù)雜度與空間復(fù)雜度均為o(1)。算法三占用空間為迷宮邊長n的平方，故空間復(fù)雜度為o(n*n)。最多走n*n步,最少走1步，故時間復(fù)雜度為o(n*n/2)。三、程序運行分析1.程序運行流程圖：開始輸出迷宮圖輸入x,y否(x,y)是否合法是廣度優(yōu)先搜索標(biāo)記最短路徑輸出最短路徑結(jié) 束2.程序運行結(jié)果截圖：測試條件：以實驗題目中給出的迷宮圖進(jìn)行測試。測試時固

8、定終點位置，選擇不同的起點位置進(jìn)行測試，測試各個位置下的輸出是否正常。測試結(jié)論：本程序?qū)τ跍y試地圖在不同起始和終止位置輸出都完全正確。四總結(jié)1、在最初嘗試編寫代碼時，采用的是遞歸算法。雖然用棧實現(xiàn)代碼很簡單，只需要向四個方向不斷遞歸即可，但是使用棧并不能保證輸出的路徑是最佳路徑。所以在完成了遞歸算法之后，我開始思索如何能輸出最短路徑。查找大量資料，結(jié)論是用棧很難實現(xiàn)，即使要實現(xiàn)也需要不斷比較各種路徑的長短，然后不斷更新最短路徑。偶然發(fā)現(xiàn)迪杰斯特拉算法，后又學(xué)習(xí)廣度優(yōu)先搜索算法，才用隊列才最終使得問題得以解決。2、在將新算法應(yīng)用到迷宮問題過程中，遇到不少困難，反復(fù)琢磨和看書才將其解決。由于順序隊

9、列的出隊入隊操作加上了賦值和標(biāo)記位置、建立鏈表關(guān)系，實際將一個順序隊列以指針的作用，變成了一棵樹的結(jié)構(gòu)，而樹的深度恰好能反映最短路徑。3、從一個小小的迷宮問題，引出了許多知識，這種探索式的學(xué)習(xí)是很有意義的。從迷宮基本的遞歸和回溯到棧的運用和理解，再到隊列的運用，后又到樹與圖以及隊列的綜合運用，將很多知識點串聯(lián)起來了，加深了理解。同時探索式地學(xué)習(xí)迪杰斯特拉算法也收獲頗多。4、改進(jìn)：本題為了實現(xiàn)代碼的簡便，沒有采用鏈隊結(jié)構(gòu)，因而浪費了一定的空間，特別是當(dāng)迷宮的邊長很長的時候，空間復(fù)雜度以o（n*n）增長，程序效率將大大降低，因而如果是計算復(fù)雜的迷宮，可以考慮將本程序的順序隊列稍加修改變?yōu)殒滉?，實現(xiàn)

10、動態(tài)分配內(nèi)存，以節(jié)省空間消耗。5、進(jìn)一步的思考：此方法只能輸出一條最短路徑，如何能輸出所有最短路徑？初步算法是將同一深度的節(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); /獲取當(dāng)前節(jié)點的序號和對應(yīng)的迷宮坐標(biāo)，然后出列boolgetnextpos(int *i ,

11、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,

12、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;/當(dāng)前節(jié)點的序號，以便傳遞給孩子節(jié)點int x,y;/當(dāng)前結(jié)點對應(yīng)的坐標(biāo)q10*10;/每個節(jié)點包含迷宮坐標(biāo)、隊列中的序號、父節(jié)點的序號，多個節(jié)點形成隊列 int front = 0,rear = 0;/隊列頭指針和尾指針void main()cout程序說明：n1.輸出路徑為最短路徑；n2.默認(rèn)的出口在最右下角，如有需要可以調(diào)整。nn;cout初始地圖如下：endl; print();inti,j;reinput:cout

13、請輸入起點坐標(biāo)（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;/保存當(dāng)前節(jié)點對應(yīng)的坐標(biāo)位置qrear.parent_id = k;/保存父節(jié)點的序號qrear.node_id = rear; /保存當(dāng)前節(jié)點序號rear+;void dequeue(int *i,int *j,int *k)*i = qfront.

14、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);

15、map11 = 1;/起點入隊,標(biāo)記起點已走過while(true)count = 1;dequeue(&i,&j,&k);n = i,m = j; /保存當(dāng)前位置while(getnextpos(&i,&j,count)count+;if(!mapij) enqueue(i,j,k);mapij = 1;if(i = 8 & j = 9) return;/到達(dá)終點,(8,9)是默認(rèn)終點，可以任意修改i = n; j = m;/保證遍歷當(dāng)前坐標(biāo)的所有相鄰位置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