數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告棧和隊(duì)列迷宮圖最短路徑

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

2、，對(duì)前進(jìn)方向形成了多處障礙，心理學(xué)家在迷宮的唯一出口放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達(dá)出口，測(cè)試算法的迷宮如下圖所示。c程序功能輸入起始點(diǎn)的坐標(biāo)，輸出走出迷宮最短路徑的長(zhǎng)度。二、程序分析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è)

3、元素用結(jié)構(gòu)體存儲(chǔ)系，包含迷宮坐標(biāo)、隊(duì)列中的序號(hào)、父節(jié)點(diǎn)的序號(hào)，實(shí)現(xiàn)了對(duì)路徑的記錄。c+實(shí)現(xiàn)：struct nodeintparent_id;/保存父節(jié)點(diǎn)的位置intnode_id;/當(dāng)前節(jié)點(diǎn)的序號(hào)，以便傳遞給孩子節(jié)點(diǎn)int x,y; /當(dāng)前結(jié)點(diǎn)對(duì)應(yīng)的坐標(biāo)q10*10; /每個(gè)節(jié)點(diǎn)包含迷宮坐標(biāo)、隊(duì)列中的序號(hào)、父節(jié)點(diǎn)的序號(hào)，多個(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)+; retu

4、rn 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)對(duì)應(yīng)的坐標(biāo)位置qrear.parent_id = k;/保存父節(jié)點(diǎn)的序號(hào)qrear.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)鍵

5、算法三通過不斷調(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(tru

6、e)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 例如

7、從13號(hào)節(jié)點(diǎn)可以讀出它在迷宮地圖中的坐標(biāo)（7，4），通過第三個(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 = qk.x;j = qk.y;mapij = 2;k = qk.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)。三、程序運(yùn)行分析1.程序運(yùn)行流程圖：開始輸出迷宮圖輸入x,y否(x,y)是否

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

9、法，才用隊(duì)列才最終使得問題得以解決。2、在將新算法應(yīng)用到迷宮問題過程中，遇到不少困難，反復(fù)琢磨和看書才將其解決。由于順序隊(duì)列的出隊(duì)入隊(duì)操作加上了賦值和標(biāo)記位置、建立鏈表關(guān)系，實(shí)際將一個(gè)順序隊(duì)列以指針的作用，變成了一棵樹的結(jié)構(gòu)，而樹的深度恰好能反映最短路徑。3、從一個(gè)小小的迷宮問題，引出了許多知識(shí)，這種探索式的學(xué)習(xí)是很有意義的。從迷宮基本的遞歸和回溯到棧的運(yùn)用和理解，再到隊(duì)列的運(yùn)用，后又到樹與圖以及隊(duì)列的綜合運(yùn)用，將很多知識(shí)點(diǎn)串聯(lián)起來了，加深了理解。同時(shí)探索式地學(xué)習(xí)迪杰斯特拉算法也收獲頗多。4、改進(jìn)：本題為了實(shí)現(xiàn)代碼的簡(jiǎn)便，沒有采用鏈隊(duì)結(jié)構(gòu)，因而浪費(fèi)了一定的空間，特別是當(dāng)迷宮的邊長(zhǎng)很長(zhǎng)的時(shí)候，空

10、間復(fù)雜度以o（n*n）增長(zhǎng)，程序效率將大大降低，因而如果是計(jì)算復(fù)雜的迷宮，可以考慮將本程序的順序隊(duì)列稍加修改變?yōu)殒滉?duì)，實(shí)現(xiàn)動(dòng)態(tài)分配內(nèi)存，以節(jié)省空間消耗。5、進(jìn)一步的思考：此方法只能輸出一條最短路徑，如何能輸出所有最短路徑？初步算法是將同一深度的節(jié)點(diǎn)全部遍歷，如果后續(xù)還有同樣長(zhǎng)度的路徑則輸出該路徑，如果沒有則只有一條最短路徑。五、附錄源代碼:/本程序在windows7 、visual studio2008 環(huán)境下調(diào)試運(yùn)行成功#include<iostream>using namespace std;voidenqueue(int i,int j,int k); /入隊(duì)一個(gè)節(jié)點(diǎn)void

11、dequeue(int *i,int *j,int *k); /獲取當(dāng)前節(jié)點(diǎn)的序號(hào)和對(duì)應(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

12、,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)的序號(hào)，以便傳遞給孩子節(jié)點(diǎn)int x,y;/當(dāng)前結(jié)點(diǎn)對(duì)應(yīng)的坐標(biāo)q10*10;/每個(gè)節(jié)點(diǎn)包含迷宮坐標(biāo)、隊(duì)列中的序號(hào)、父節(jié)點(diǎn)的序號(hào)，多個(gè)節(jié)點(diǎn)形成隊(duì)列 int front = 0,rear = 0;/隊(duì)列頭指針和尾指針void main()cout<<&qu

13、ot;程序說明："<<'n'<<"1.輸出路徑為最短路徑；"<<'n'<<"2.默認(rèn)的出口在最右下角，如有需要可以調(diào)整。"<<'n'<<'n'cout<<"初始地圖如下："<<endl; print();inti,j;reinput:cout<<"請(qǐng)輸入起點(diǎn)坐標(biāo)（x,y）： "<<endl;cin>>i>&

14、gt;j;if(mapij) cout<<"不能從該處出發(fā)，請(qǐng)重新輸入！"<<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)對(duì)應(yīng)的坐標(biāo)位置qrear.parent_id = k;/保存父節(jié)點(diǎn)的序號(hào)qrear.node_id = rear; /保存當(dāng)前節(jié)點(diǎn)序號(hào)rear+;vo

15、id 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(i

16、nt 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)的所有

17、相鄰位置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 8 9"<<endl;for(i = 0;i < 10;i+)cout<<i;for(j = 0;j < 10;j+)if(mapij=2)sum+; cout<<""elsecout<<""cout<<endl;cout