數據結構：線性表實驗報告內容實例

實驗報告內容：實驗題目：1、問題描述及分析2、設計（1）數據結構設計（2）算法設計3、實現（1）程序結構描述（2）完整程序（3）測試數據及預期結果4、調試與分析（1）實驗結果（2）與預期結果比較并分析5、總結：本次實驗完成的內容、體會實驗要求：1、為確保上機實驗的效果，在上機實驗之前要作好充分準備工作，寫好實驗報告1-32、實驗過程根據需要可以用紅筆修改實驗報告3、實驗結束填寫實驗報告4-54、實驗報告在上機結束后當場提交。附錄：實驗報告樣本

實驗題目：利用棧實現迷宮的求解1、問題描述及分析問題描述：心理學家把一只老鼠從一個無頂蓋的大盒子的入口處趕進迷宮。迷宮中設置很多墻壁，對前進方向形成了多處障礙，心理學家在迷宮的唯一出口放置了一塊奶酪，吸引老鼠在迷宮中尋找通路以到達出口。分析：迷宮可以用二維數組表示，該問題可以歸結為尋找一條從入口到出口的路徑。2、設計：

1）數據結構的設計（1）迷宮的表示設迷宮為m行n列，利用二維數組maze[m][n]來表示一個迷宮，其中(1，1)為入口，(m，n)為出口，

maze[m][n]=0或1，其中0表示通路，1表示不通。01110111101011110100000101110111100110000110011012345678123456入口出口011101111010111101000001011101111001100001100110迷宮定義#definem6#definen8intmaze[m+2][n+2]當從某點向試探時，之間點有8個方向可以試探，而四個角點有3個方向，其他邊緣點有5個方向，為使問題簡單化,在迷宮的四周加了一層，表示墻壁，這樣每個點的試探方向為8。11111111111111111111111111111111123456789012345670（2）試探方向的表示在上述表示迷宮的情況下，每個點有8個方向可以試探，設當前點的坐標為（x，y），與其相鄰的8個點的坐標可根據與該點的相鄰方位得到。為了方便求出新點的坐標，將從正東開始沿順時針進行的這8個方向的坐標增量放在一個結構數組move[8]中，其中x表示橫坐標增量，y表示縱坐標增量。（x，y+1）（x，y-1）（x-1，y）（x+1，y）（x+1，y+1）（x-1，y+1）（x-1，y-1）（x+1，y-1）（x，y）試探方向的表示typedefstruct{intx,y;}item;itemmove[8]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};（3）棧的表示當到達了某點無路可走，需從前一點的下一個方向試探。因此，壓入棧中的不僅是順序到達的各點的坐標，而且還有從前一點到達本點的方向序號。棧的表示#defineMAXSIZE20typedefstruct{intx,y,d;}datatype;typedefstruct{datatypedata[MAXSIZE];inttop;}SeqStack;2）算法的設計（2）防止重復到達某點的考慮為避免發(fā)生死循環(huán)，當到達某點（i，j）后，使maze[i][j]置-1，以便區(qū)分未到達過的頂點。算法結束前可恢復原迷宮。1，1，-1top（1）算法基本思想描述：利用回溯法，從入口處出發(fā)，按某一方向不斷試探，若能走通，則到達新點，否則試探另一未試探過的方向。若所有的方向均沒有通路，則沿原路返回前一點，換一個未試探過的通路繼續(xù)試探，直到找到出口，或所有的通路都試探過，未找到一條通路回到出口點。在試探過程中，為保證在到達某一點無路時，能正確返回前一點，需要用一個棧來保存到達的每一點的位置及試探方向。（3）算法描述intpath(intmaze[m+2][n+2],itemmove[8],sepstacks)/*maze為迷宮,move為試探方向,s是一個棧，保存試探中的各個頂點和試探方向，算法結束時，棧中保存的就是一條迷宮的通路。找到路徑返回1，否則為0*/{棧初始化；將入口點坐標及初始試探方向（設為-1）入棧；將入口點設置為已走過；設置found為0(未找到出口點);

while（未找到&&棧非空）

{將棧頂元素賦值給x;從x點出發(fā)尋找下一個可以走的方位；if(找到方位){修改棧頂元素的方位值;計算新點,并設置為已走過;將新點位置及初始試探方位值進棧;if(新點是結束點)found=1;}else//沒找到可走的方位,說明從該點出發(fā)已無路可走

出棧;}if(找到)return1;elsereturn0;}3、實現（1）程序結構該程序包含1個主程序main,和三個子程序：a、迷宮初始化:intinitmaze(intmaze[m+2][n+2])b、尋找路徑：intpath(intmaze[m+2][n+2],itemmove[8],sepstack*s)c、輸出路徑：voidprintpath(seqstacks)（2）完整程序(略)（3）測試數據及預期結果輸入迷宮數據如右圖：輸出路徑為(1,1,1)(2,2,1)(3,3,0)(3,4,0)(3,5,0)(3,6,3)(4,5,1)(5,6,0)(5,7,0)(5,8,2)011101111010111101000001011101111001100001100110111111111111