數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-棧和隊(duì)列.doc

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