北郵數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)二題目3

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

開始3.程序運(yùn)行結(jié)果開始輸出迷宮圖輸出迷宮圖輸入x,y輸入x,y否否(x,y)是否合法(x,y)是否合法是是廣度優(yōu)先搜索廣度優(yōu)先搜索標(biāo)記最短路徑標(biāo)記最短路徑輸出最短路徑輸出最短路徑結(jié)結(jié)束測(cè)試條件：以實(shí)驗(yàn)題目中給出的迷宮圖進(jìn)行測(cè)試。測(cè)試時(shí)固定終點(diǎn)位置，選擇不同的起點(diǎn)位置進(jìn)行測(cè)試，測(cè)試各個(gè)位置下的輸出是否正常。測(cè)試結(jié)論：本程序?qū)τ跍y(cè)試地圖在不同起始和終止位置輸出都完全正確。

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