數(shù)據(jù)結(jié)構(gòu)實驗報告——棧和隊列

1、數(shù)據(jù)結(jié)構(gòu)實驗報告數(shù)據(jù)結(jié)構(gòu)實驗報告——棧和隊列棧和隊列數(shù)據(jù)結(jié)構(gòu)實驗報告——棧和隊列北京郵電大學電信工程學院2008級數(shù)據(jù)結(jié)構(gòu)實驗報告實驗名稱：實驗二棧和隊列學生姓名：班級：班內(nèi)序號：學號：日期：2009年11月8日1實驗要求a.實驗目的通過選擇下面五個題目之一進行實現(xiàn)，掌握如下內(nèi)容：進一步掌握指針、模板類、異常處理的使用掌握棧的操作的實現(xiàn)方法掌握隊列的操作的實現(xiàn)方法學習使用棧解決實際問題的能力學習使用隊列解決實際問題的能力b.實驗內(nèi)容利用

2、棧結(jié)構(gòu)實現(xiàn)迷宮求解問題。迷宮求解問題如下：心理學家把一只老鼠從一個無頂蓋的大盒子的入口趕進迷宮，迷宮中設置很多隔壁，對前進方向形成了多處障礙，心理學家在迷宮的唯一出口放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達出口，測試算法的迷宮如下圖所示。2.程序分析2.1存儲結(jié)構(gòu)存儲結(jié)構(gòu):隊列順序存儲結(jié)構(gòu)示意圖如下:2.2關(guān)鍵算法分析核心算法思想：1.如果采用直接遞歸的方式，用棧很容易實現(xiàn)路徑的輸出，但是應的坐標位置Q[rear].parent_

3、id=k保存父節(jié)點的序號Q[rear].node_id=rear保存當前節(jié)點序號rear關(guān)鍵算法3：廣度優(yōu)先搜索算法的實現(xiàn)，找到最短路徑。廣度優(yōu)先算法在此相當于樹的層序遍歷，如下圖：在迷宮地圖中，關(guān)鍵算法三通過不斷調(diào)用關(guān)鍵算法二就能將地圖中可以走的位置入隊，形成類似上圖的樹形結(jié)構(gòu)，之后廣度搜索到最淺深度即為最短路徑。例如H節(jié)點的坐標就是出口坐標，當層序搜索到H時就終止了，入隊工作結(jié)束，不再將I和J入隊。通過關(guān)鍵算法四逆序就能找到最短路徑

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