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

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告——棧和隊(duì)列棧和隊(duì)列數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告——棧和隊(duì)列北京郵電大學(xué)電信工程學(xué)院2008級(jí)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：實(shí)驗(yàn)二棧和隊(duì)列學(xué)生姓名：班級(jí)：班內(nèi)序號(hào)：學(xué)號(hào)：日期：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)容利用

2、棧結(jié)構(gòu)實(shí)現(xiàn)迷宮求解問題。迷宮求解問題如下：心理學(xué)家把一只老鼠從一個(gè)無頂蓋的大盒子的入口趕進(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)鍵算法分析核心算法思想：1.如果采用直接遞歸的方式，用棧很容易實(shí)現(xiàn)路徑的輸出，但是應(yīng)的坐標(biāo)位置Q[rear].parent_

3、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)鍵算法三通過不斷調(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)鍵算法四逆序就能找到最短路徑

4、ABC。其實(shí)最短路徑不一定只有一條，例如J點(diǎn)也可能是出口坐標(biāo)，但是當(dāng)搜索到H時(shí)就停止了，故此算法只是輸出了所有最短路徑中可能的一條。C實(shí)現(xiàn)：voidShtestPath_BFS(intiintj)intcountmnkEnQueue(ij1)Map[1][1]=1起點(diǎn)入隊(duì)標(biāo)記起點(diǎn)已走過while(true)count=1DeQueue(n=im=j保存當(dāng)前位置while(GetNextPos(if(!Map[i][j])EnQueue(