資料結構課程設計範例

下面給出乙個完整的課程設計示範。

問題：在有 n 個選手 p 1 ,p 2 ,p 3 ,… ,p n 參加的單迴圈賽中，每對選手之間非勝即負。現要求求出乙個選手序列 p 1 ' ,p 2 ' ,p 3 ' ,… ,p n ', 使其滿足 p i ' 勝 p i+ 1 ' (i=1,… ,n-1) 。

解：本題的求解如下：

（ 1 ）模型表示：由於僅涉及到 n 個選手，並且這些選手之間的關係僅是勝負關係，因此可用圖來表示：

用頂點表示選手。

用弧表示選手之間的勝負關係：當且僅當 p i 勝 p j 時，有從頂點 i 到 j 的一條弧。

在這種表示下，本題問題變成了如下的問題：

在有向圖中求解出一條包含所有頂點的簡單路徑的問題。

下圖所示為乙個有 8 個選手的問題的乙個示例。其中的乙個解為 1,2,3,4,8,6,5,7 。

（ 2 ）演算法設計：設計本題演算法的構思如下：

為搜尋出符合條件的簡單路徑，需按深度優先搜尋方式進行遍歷。因此求解演算法應是深度遍歷演算法的變形形式，也應是遞迴形式的演算法。

由於要求遍歷序列中的各結點按次序構成一條簡單路徑，因此演算法與深度遍歷演算法有明顯的不同：並非任意選擇的起點和訪問次序都能得到解。而這些又是事先難以確定的。

這就要求在求解過程中進行試探：試探起點以及訪問次序。

既然要在求解過程中進行試探，則需要記錄試探的中間狀態：某頂點是否在當前試探的路徑中，已經試探的各頂點的次序，當前正在試探的頂點等。將所用到的變數及有關引數設定如下：

設圖為 g ；設當前試探路徑中最後的頂點號為 v ； v 在試探路徑中的序號為 k ；

用布林型陣列 visited[n+1] 表示各頂點是否在當前試探的路徑中（初值為全 false ）；

用陣列 b[n+1] 儲存當前路徑中的各頂點（在前 k 個元素中，事實上應是棧）。

既然是試探型求解，則需對當前頂點 v 的每個鄰接點 ( 不妨用 w 表示 ) 進行試探，試探由 v 經 w 往下是否可以得到解。每個 w 都可能有成功（指現在可以將該頂點放在路徑上，這包括暫時的和最終的）與失敗（指此路不通）兩種情況，對此應分別作不同的處理：

a. 若試探成功，則應將 w 放入路徑中，並置相應的狀態值。然後再由 w 往下求解。

b. 若不成功，則應恢復 w 的有關資訊，以使 w 在試探其它路徑時成為可選頂點。

為了能求出解以及所有可能的解，需要作如下兩方面的工作：

a. 選擇起點：應以每個頂點為起點進行搜尋。

b. 搜尋路徑：在從 v 往下搜尋時，應依次選擇 v 的所有不在當前試探路徑中的鄰接點往下搜尋。

為此，需要有這方面的保證：應在試探某頂點 w 後並在換下乙個試探頂點前恢復 w 的有關狀態，以使其仍為可選擇的頂點。

由上述討論得本演算法的基本思想：

a. 若 k=n ，則說明已經求得一解，因此可輸出結果，並結束本次呼叫。

b. 若 k試探：將 w 放到 b[k+1] 中，並置 visited[w] 為 true ，然後以 w 為起點往下搜尋。

恢復：將 w 恢復為不在當前路徑中，以使其在試探其它路徑時可用。

有關演算法中的變數設定：可將上述討論中所提及的變數 k 、 v 作為引數（僅提供值而不返回值），將 g 作為位址傳送型引數（雖然不會改變其值，但這種形式更節省時間和空間），將陣列 b 和 visited 作為全程變數，以便各呼叫層能共享，並節省時間、空間，同時使程式更清晰。

演算法描述 ……。

（ 3 ）程式實現：為上機實現本題，還需要做一些工作：

新增功能：由演算法可知，需要新增一些功能，如輸入資料建圖、輸出路徑，顯示求解狀態等。

結構及型別說明：到目前為止，還沒有提及圖的儲存結構。若採用《資料結構實驗工具》，則可借助於實驗工具中的儲存結構，因此可省掉諸如型別說明、建圖、顯示圖等許多麻煩。

若要自己設計儲存結構，由教科書可知，圖的儲存結構可有多種，其中最常用的是鄰接矩陣和鄰接表兩種，兩者各有其特點。具體採用什麼結構取決於問題本身的要求。考慮到本題的特點，為簡單起見，採用鄰接矩陣儲存形式。

為此，需要做必要的說明。在採用具體的儲存結構後，演算法可能也要隨之發生變化。

輸入圖結構：為方便地除錯演算法，需要能方便地建圖。若採用逐個輸入元素的方式來建圖，則需要輸入 n 2 個元素，這對除錯演算法來說是不便的。

為此，可採用隨機產生的方式來建圖，即隨機地產生鄰接矩陣各元素的值。此處需要注意的是矩陣中元素的特點：對角線上全 0 ，其餘元素滿足 a[i][j]=1-a[j][i] 。

顯示結構：合理地顯示結構是除錯演算法所必需的。在此，採用工具系統中的圖結構、陣列等有關功能，以方便地顯示結構。

顯示輸出結果：輸出結果也必須要以可接受的形式顯示出來。此處每求解出乙個結果輸出一次。

完整程式 ……

（ 4 ）總結：本題主要部分是直接用 c 語言實現的乙個設計，由於採用鄰接矩陣作為圖的儲存結構，因此程式較為簡潔。若完全借助於實驗工具，程式將更為簡潔。

然而，鄰接矩陣作為圖的儲存結構的要求在程式執行之前必須要知道其頂點數。這是本設計的乙個缺陷。解決的辦法之一是將鄰接矩陣設定得「足夠大」，執行時輸入頂點數，將實際圖的鄰接關係儲存在矩陣的左上角部分，然後依此執行。

另一解決的辦法是採用鄰接表作為儲存結構，並將鄰接表的表頭指標也放到乙個鍊錶的各結點中，但隨之而來的是程式設計量的加大，因為鄰接表和「表頭表」的建立、插入、查詢、鄰接點的查詢等一系列功能的設計是較為麻煩的。