資料結構程式實習報告

一：約瑟夫環問題

（1）問題描述：

設有編號為1，2，3……n的n個人順時針方向圍坐一圈，每人有一密碼（正整數）。開始時給出一報數上限，從編號為1的人開始報數，報m的人出列；以後將出列者的密碼作為新的m，從順時針方向緊挨著他的下乙個人開始報數……直至所有人出列。試編一演算法，求出出列順序。

（2）程式設計思想：

首先人為地輸入要參與的人數m，和要求第一次出列的人的序號n。

然後根據輸入的m值構造乙個單向環鏈，每乙個節點包括序號域（每個人各自的序號），密碼域（記錄當他出環後下乙個出環的人是從他數後面的第幾個人，由隨機函式random()+1生成，加一的目的是防止生成數為零），鏈域（鏈結下各結點）。

然後再主程式總主要通過乙個while迴圈實現功能，流程圖如下：

二：迷宮問題

（1）問題描述：

由0和1構成的n維方陣m表示乙個迷宮，其中0表示通路，1表示牆壁。迷宮入口為(1,1),出口為(n,n)。試編一演算法求出從入口點到出口點可沿八個方向前進的一條通路。

（2）程式設計思想：

該程式主要由乙個遞迴函式和乙個棧來完成任務。首先隨機生成乙個迷宮，維數由人為給定，然後通過調遞迴函式和棧來尋找路徑，直到找到出口，找的過程中主要在當前節點的四周找，如果找不到任何通路，則返回到生成迷宮的那一步再次生成乙個迷宮，直到找到一條通路為止。流程圖如下：

三：二叉樹問題

（1）問題描述：

已知一棵二叉樹的前序、中序序列，試設計完成下列任務的乙個演算法：

構造此二叉樹

證明構造的正確性（即分別按先序和中序遍歷該樹，將所得的結果與給出的序列進行比較）

（2）程式設計思想:

根據二叉樹的先序序列和中序序列的關係，可以逐個確定各個節點的位置，

此程式主要通過遞迴函式來構造二叉樹的二叉鍊錶儲存結構，然後輸出結果以便校對。具體流程如下：

四：除錯技巧

在除錯中最大問題就是指標問題，尤其是有時候程式可以執行但是結果不對

在除錯過程中主要積累了以下幾條經驗：

（1）若遇到除錯不通過的情況，不要單看出錯的地方，還要仔細檢查可能的其他錯誤；

（2）當遇到結果不對時，最好用f7逐步執行，執行一步就看一下結果，以便查處問題所在；

（3）如果需要的話可以設一些斷點以便隨時觀察變數的變化情況。