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

1、第第 頁五、附錄源代碼:/本程序在windows7、visualstudio2008環(huán)境下調(diào)試運(yùn)行成功#includeusingnamespacestd;voidEnQueue(inti,intj,intk);/入隊(duì)一個(gè)節(jié)點(diǎn)voidDeQueue(int*i,int*j,int*k);/獲取當(dāng)前節(jié)點(diǎn)的序號(hào)和對(duì)應(yīng)的迷宮坐標(biāo)，然后出列boolGetNextPos(int*i,int*j,intcount);/得到下一個(gè)鄰接點(diǎn)的位置voidShortestPath_BFS(inti,intj);/廣度優(yōu)先遍歷尋找最短路徑voidShortestPath();/輸出最短路徑voidPrint();/輸

2、出迷宮形狀intMap1010=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;structNodeintparent_id;/保存父節(jié)點(diǎn)的位置intnode_id;/當(dāng)前節(jié)點(diǎn)的序號(hào)，以便傳遞給孩子節(jié)點(diǎn)intx,y;/當(dāng)前結(jié)點(diǎn)對(duì)應(yīng)的坐標(biāo)Q10*10

3、;的序號(hào)，多個(gè)節(jié)點(diǎn)形成隊(duì)列/每個(gè)節(jié)點(diǎn)包含迷宮坐標(biāo)、隊(duì)列中的序號(hào)、父節(jié)點(diǎn)intfront=0,rear=0;/隊(duì)列頭指針和尾指針voidmain()coutvv程序說明：vvnvvl.輸出路徑為最短路徑；vvnvv2.默認(rèn)的出口在最右下角，如有需要可以調(diào)整?！眝vnvvn;coutvv初始地圖如下：vvendl;Print();inti,j;reinput:coutvv請(qǐng)輸入起點(diǎn)坐標(biāo)(x,y)：vvendl;if(Mapij)coutvv不能從該處出發(fā)，請(qǐng)重新輸入！vvendl;gotoreinput;ShortestPath_BFS(i,j);coutvv最短路徑之一如下：vvendl;Sho

4、rtestPath();voidEnQueue(inti,intj,intk)/保存當(dāng)前節(jié)點(diǎn)對(duì)應(yīng)的坐標(biāo)位置/保存當(dāng)前節(jié)點(diǎn)對(duì)應(yīng)的坐標(biāo)位置/保存父節(jié)點(diǎn)的序號(hào)/保存當(dāng)前節(jié)點(diǎn)序號(hào)Qrear.y=j;Qrear.parent_id=k;Qrear.node_id=rear;rear+;voidDeQueue(int*i,int*j,int*k)*i=Qfront.x;*j=Qfront.y;*k=Qfront.node_id;front+;/出列一個(gè)節(jié)點(diǎn)boolGetNextPos(int*i,int*j,intcount)switch(count)TOC o 1-5 h zcase1:(*j)+;re

5、turn1;/右case2:(*i)+;return1;/下case3:(*j)-;return1;/左case4:(*i)-;return1;/上default:return0;voidShortestPath_BFS(inti,intj)intcount,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)的所有相鄰位置voidShortestPath()inti,j,k,sum(0);k=rear-1;while(k!=-1)i=Qk.x;j=Qk.y;Mapij=2;k=Qk.parent_id;cout0123456789endl;for(i=0;i10;i+)couti;for(j=0;j10;j+)if(Mapij=2)sum+;coutvv訃elsecoutvv”；coutendl;coutvv最短路徑長(zhǎng)度：vvsumvvendl;voidPrint()cout01