2008級資料結構實驗報告
實驗名稱： 實驗二棧和佇列
學生姓名：
班級： 2008211113
班內序號：
學號：日期： 2023年11月8日
1．實驗要求
通過選擇下面五個題目之一進行實現，掌握如下內容：
進一步掌握指標、模板類、異常處理的使用
掌握棧的操作的實現方法
掌握佇列的操作的實現方法
學習使用棧解決實際問題的能力
學習使用佇列解決實際問題的能力
b. 實驗內容
利用棧結構實現迷宮求解問題。迷宮求解問題如下：
心理學家把乙隻老鼠從乙個無頂蓋的大盒子的入口趕進迷宮，迷宮中設定很多隔壁，對前進方向形成了多處障礙，心理學家在迷宮的唯一出口放置了一塊乳酪，吸引老鼠在迷宮中尋找通路以到達出口，測試演算法的迷宮如下圖所示。
2. 程式分析
2.1 儲存結構
儲存結構:
佇列順序儲存結構
示意圖如下:
2.2 關鍵演算法分析
核心演算法思想：
1. 如果採用直接遞迴的方式，用棧很容易實現路徑的輸出，但是這條路徑不一定是最短路徑。為了改進演算法，達到輸出最短路徑的目標，採用佇列的實現方式。
2. 為查詢最短路徑，使用了「圖」中的演算法：廣度優先搜尋。
關鍵演算法思想描述和實現：
關鍵演算法1：
為尋求最短路徑，採用廣度優先搜尋演算法，使用佇列實現路徑儲存，佇列中每個元素用結構體儲存系，包含迷宮座標、佇列中的序號、父節點的序號，實現了對路徑的記錄。
c++實現：
struct node
q[10*10]; //每個節點包含迷宮座標、佇列中的序號、父節點的序號，多個節點形成佇列
關鍵演算法2：
遍歷每個位置四周的位置，將沒有走過的位置入隊，形成樹形的佇列，通過出隊操作就能找到最短路徑。
c++實現：
bool getnextpos(int *i ,int *j,int count) }
void enqueue(int i,int j,int k)
關鍵演算法3：
廣度優先搜尋演算法的實現，找到最短路徑。廣度優先演算法在此相當於樹的層序遍歷，如下圖：
在迷宮地圖中，關鍵演算法三通過不斷呼叫關鍵演算法二就能將地圖中可以走的位置入隊，形成類似上圖的樹形結構，之後廣度搜尋到最淺深度即為最短路徑。例如h節點的座標就是出口座標，當層序搜尋到h時就終止了，入隊工作結束，不再將i和j入隊。通過關鍵演算法四逆序就能找到最短路徑a->b->c。
其實最短路徑不一定只有一條，例如j點也可能是出口座標，但是當搜尋到h時就停止了，故此演算法只是輸出了所有最短路徑中可能的一條。
c++實現：
void shortestpath_bfs(int i ,int j)
}}關鍵演算法4：
使用佇列指標查詢父節點的方式，從隊尾回溯到隊首，標記出最短路徑。
佇列的元素示意圖如下：
入隊之後的佇列如下圖：
…………
例如從13號節點可以讀出它在迷宮地圖中的座標（7，4），通過第三個元素7就能找到第七號節點，也即其父節點（5，6），從父節點又可以同理找到它的父節點第三號節點。這樣就能實現逆序找到路徑。
c++實現：
k = rear-1;
while(k != -1)
時間複雜度與空間複雜度：
演算法一和二時間複雜度與空間複雜度均為o(1)。
演算法三占用空間為迷宮邊長n的平方，故空間複雜度為o(n*n)。最多走n*n步,最少走1步，故時間複雜度為o(n*n/2)。
3. 程式執行結果
測試條件：
以實驗題目中給出的迷宮圖進行測試。
測試時固定終點位置，選擇不同的起點位置進行測試，測試各個位置下的輸出是否正常。
測試結論：
本程式對於測試地圖在不同起始和終止位置輸出都完全正確。
4. 總結
1、在最初嘗試編寫**時，採用的是遞迴演算法。雖然用棧實現**很簡單，只需要向四個方向不斷遞迴即可，但是使用棧並不能保證輸出的路徑是最佳路徑。所以在完成了遞迴演算法之後，我開始思索如何能輸出最短路徑。
查詢大量資料，結論是用棧很難實現，即使要實現也需要不斷比較各種路徑的長短，然後不斷更新最短路徑。偶然發現迪傑斯特拉演算法，後又學習廣度優先搜尋演算法，才用佇列才最終使得問題得以解決。
2、在將新演算法應用到迷宮問題過程中，遇到不少困難，反覆琢磨和看書才將其解決。由於順序佇列的出隊入隊操作加上了賦值和標記位置、建立鍊錶關係，實際將乙個順序佇列以指標的作用，變成了一棵樹的結構，而樹的深度恰好能反映最短路徑。
3、從乙個小小的迷宮問題，引出了許多知識，這種探索式的學習是很有意義的。從迷宮基本的遞迴和回溯到棧的運用和理解，再到佇列的運用，後又到樹與圖以及佇列的綜合運用，將很多知識點串聯起來了，加深了理解。同時探索式地學習迪傑斯特拉演算法也收穫頗多。
4、改進：本題為了實現**的簡便，沒有採用鏈隊結構，因而浪費了一定的空間，特別是當迷宮的邊長很長的時候，空間複雜度以o（n*n）增長，程式效率將大大降低，因而如果是計算複雜的迷宮，可以考慮將本程式的順序佇列稍加修改變為鏈隊，實現動態分配記憶體，以節省空間消耗。
5、進一步的思考：此方法只能輸出一條最短路徑，如何能輸出所有最短路徑？初步演算法是將同一深度的節點全部遍歷，如果後續還有同樣長度的路徑則輸出該路徑，如果沒有則只有一條最短路徑。
北郵資料結構實驗報告
實驗名稱 實驗 2.1 學生姓名 班級 班內序號 學號 日期 1 實驗要求 1.實驗目的 熟悉c 語言的基本程式設計方法，掌握整合編譯環境的除錯方法 學習指標 模板類 異常處理的使用 掌握線性表的操作的實現方法 學習使用線性表解決實際問題的能力。2.實驗內容 完成單鏈表的基本功能，編寫測試main ...
北郵資料結構實驗報告排序
北京郵電大學 資料結構試驗報告 實驗名稱 實驗四排序 學生姓名 班級 班內序號 學號 日期 2014年1月4日 學習 實現 對比各種排序演算法，掌握各種排序演算法的優劣，以及各種演算法使用的情況。使用簡單陣列實現下面各種排序演算法，並進行比較。排序演算法 1 插入排序 2 希爾排序 3 氣泡排序 4...
資料結構實驗二題目
資料結構實驗報告 實驗名稱 實驗2 棧和佇列 學生姓名 班級 班內序號 學號 日期 2013年11月8日 1 實驗要求 實驗目的 進一步掌握指標 模板類 異常處理的使用 掌握棧的操作的實現方法 掌握佇列的操作的實現方法 學習使用棧解決實際問題的能力 學習使用佇列解決實際問題的能力 實驗內容 根據棧和...