1002 C++ 程式作業二 (due 101/03/26 24:00) ：

The container ADT for Prim's MST algorithm

這還是個暖身的作業, 基本作法你在演算法的課程裡學過, 也會在實習時講一次, 不過這個作業開始有比較和物件相關的東西了, 主要要求你運用 C 的語法實作支援 Prim's Minimum Spanning Tree 演算法的 容器物件 - 抽象資料型態, 要求你運用課堂裡所解釋的函式指標來作出這個抽象資料型態, 同時也要求你這個容器物件需要使用上一次作業的 Heap 來提升效率。
因為在演算法課程裡學過這個程式, 所以應該不會有太大的心理負擔, 但是那時候有可能你沒有把精神用在寫一個別人很容易看得懂的程式, 沒有盡量用函式來抽象化程式的各個部份, 沒有把變數和函式好好取名字, 可能你沒有使用 MinHeap 來提昇容器的效率, 可能你沒有真的實作一個抽象資料型態, 只是用 C 的函式模擬需要有的功能, 沒有運用 assert 來確保各部份界面資料的正確性, 可能你沒有實作 adjacency matrix 的初始化, 可能沒有檢查你的程式是否有把所有動態配置的記憶體都釋放掉。這個作業裡希望你可以著重在這些部份, 當然如果你在上學期沒有寫出這個程式, 再給自己一次機會囉。

雖然不強制要求, 但是這個作業裡面的 adjacency matrix 你也可以把它變成一個 ADT, 你可以自己練習定義它的界面 (例如 getHead(vertex), next()), 如果你沒有時間完成這部份的話, 也可以留待下一個作業裡再完成。
請注意, 雖然我們在課堂裡已經開始講 C++ class 的語法, 但是這個作業你需要用 C 的函式指標語法以及你在資料結構和演算法裡頭熟悉的 struct 來實作 ADT, 請你不要用 C++ 裡的 class 或是 struct 來實作, 那個是下一次的作業... 一個邏輯上幾乎一樣的作業可以交兩次, 很划算喔!

作業目標：

複習 C 中各種流程控制： for, while, if, switch 函式等等
複習 C 中的資料結構定義: struct 語法
複習 Prim's MST (JohnsonBaugh, Cormen) (slide, slide_bw)
練習 iostream 輸出入函式庫 (鍵盤,螢幕,檔案輸出入)
進一步練習撰寫以 "容易了解, 容易修改, 容易偵錯" 為目標的工程化程式, 慢慢地養成習慣
練習運用多檔案的方式分工 (例如這個程式你可以分 main, io, 和 heapsort)
練習運用 assert
練習使用 C 語法的函式指標來實作 容器ADT (這個部份的目的是讓你了解 "物件化/物件導向的程式" 不一定需要使用 "物件導向的程式語言 (例如 C++, Java)" 來完成, C 就可以實作 ADT, 可以製作出很好的物件出來了)
運用上一次作業的 MinHeap 製作容器 ADT
練習運用 memory_leak 工具檢查程式是否有將所有動態配置的記憶體釋放, 如果你在撰寫這個程式的時候並沒有動態配置記憶體, 你還是要測試 (也許你用到的函式庫或是模組有進行動態記憶體的配置)

這個作業沒有提供範例執行程式, 針對程式執行的正確性, 需要你測試一些資料, 下面是三組基本的測試資料

參考執行結果(包含部份中間結果, 方便你檢查程式用的)

程式要求

資料檔案內描述一個 Graph, 其中第一列為此 Graph 中節點的個數, 第二列為此 Graph 中邊的數目, 第三列以後每一列代表一個邊, 例如:
```
    6               ; number of nodes 1..6
    9               ; number of edges
    1 2 4           ; edge (1,2), distance 4
    1 3 2           ; edge (1,3), distance 2
    1 5 3
    2 4 5
     .
     .
     .
```
代表 Graph 中有 6 個節點 (編號為 1, 2, 3, 4, 5, 6), 9 個邊, 分別為 (節點1, 節點2) 邊長為 4, (節點1, 節點3) 邊長為 2, ...
每一列後面都有可能有註解, 程式需要跳過這些註解 (請不要編輯資料檔案刪除)
Prim's MST 演算法的 pseudo code 如下 (JohnsonBaugh 版本):
```
prim(adj, start, parent) 
{
    n = adj.last
    for i = 1 to n
        key[i] = Infinite
    key[start] = 0
    parent[start] = 0
    h.init(key, n)
    for i = 1 to n 
    {
        v = h.del()
        ref = adj[v]
        while (ref != null) 
        {
            w = ref.ver
            if (h.isin(w) && ref.weight < h.keyval(w)) 
            {
                 parent[w] = v
                 h.decrease(w, ref.weight)
            }
            ref = ref.next
        }
    }
}
```
這個演算法中逐步建構一個 MST, 演算法中的 for 迴圈每執行一次就由 h 中把一個最接近 "目前 MST" 的節點刪除, 並且加入 "目前 MST" 中; 這個 "目前 MST" 最後會記錄在 parent[] 陣列中, MST 的起點就是 start, parent[start] 設為 0, 代表它是 tree 的 root, 沒有任何父節點, 迴圈每執行一次, 概念上就把節點 v 加入 "目前 MST", 由於 "目前 MST" 多增加了這個節點, 所以 h 中與 v 相鄰的所有節點 w 到 "目前 MST" 的距離可能會有所改變同時 parent[w] 也會改變, 這是內層 while 迴圈的作用: 修改那些 h 中與 v 相鄰節點 w 的 parent[w] 以及 weight
其中 h 是一個客製化的容器 ADT, 在 Prim 演算法中記錄 "所有還沒有加入 MST 的節點以及該節點到目前 MST 的最短距離" 並且可以很有效率地由 h 中取得距離目前 MST 最短距離的節點, 提供下列功能:
- h.init(key, n): initializes h to the values in key (程式開始時 h 裡面有 n-1 個節點, 也就是除掉 start 之外的所有節點)
- h.del(): deletes the item in h with the smallest weight and returns the vertex (由 h 中把距離目前 MST 距離最短的節點剔除)
- h.isin(w): returns true if vertex w is in h (這是一個簡單的測試函式, 可惜命名錯了, 想一下 isin 應該改成什麼?)
- h.keyval(w): returns the weight corresponding to the vertex w (由 h 中將指定的節點到目前 MST 的距離取出)
- h.decrease(w, new_weight): changes the weight of w to new_weight (smaller) (由於演算法一次增加一個新的節點到目前 MST 中, 每增加一個新的節點進入目前 MST, 所有還沒有加入目前 MST 的節點到目前 MST 的距離都需要修改, 此介面函式目的就是修改節點 w 距離目前 MST 的距離為 new_weight)
請以 C 的 struct 語法定義 Container 這個容器 ADT, 除了資料欄位之外, 請根據上述功能要求定義五個函式指標的欄位, 當你運用 struct Container h; 定義一個 h 結構時, 上述函式指標的內容把它設為你實際函式的位址, 例如:
```
struct Container
{
    ...
    void (*init)(int [], int, struct Container *self);
    ...
};
...
void initImplementation(int key[], int size, struct Container *self)
{
    ...
}
...
struct Container h = {..., initImplementation, ...};
```
上述函式定義中, 每一個函式的參數都需要多增加一個 struct Container *self 的參數,
這樣子函式裡才知道要處理哪一個 Container 的資料, 例如:
```
int del(struct Container *self);
int isIn(int w, struct Container *self);
...

函式指標相關的練習請參考 (實習 3-2) [這學期因為放假所以跳過這個實習了]

再看一個 堆疊 的例子
```
在 Prim 演算法裡呼叫 init() 時需要把 h.init(key, n); 改成 h.init(key, n, &h); 如果你這樣子實作這個 Container ADT 的話, 除了最後這個 self 參數之外, 你的 prim() 函式就和上面的演算法的 pseudocode 幾乎一樣了, 如果要完全一樣, 請使用 C++ 語法, 這是下一次的作業。
讀取資料檔案以及和使用者互動的部份請用 iostream, fstream 函式庫完成
請擴充上一次作業的 MinHeap 實作 Container ADT, 如此 h.del() 可以得到最好的效率
由於你需要實作一個 adjacency matrix 來表示這個 Graph, 你可以嘗試(不強迫你做這一部份, 可以是下一次作業的功能)也把它實作為一個 ADT
如果在 adjacency matrix 裡面你有用 list 來記錄 (adjacency matrix 常常是一個稀疏矩陣 sparse matrix), 你應該有動態配置記憶體, 請練習運用 memory_leak 檢查程式在結束時是否有將所有動態配置的記憶體釋放
你的程式需要以 (i, j) 形式輸出 minimum spanning tree 的每一個 edge, 同時輸出 edge 的總長度
根據上課的說明, 也請你對你的程式進行下列的基本要求:
1. 去除不需要的指標運算 (能夠使用陣列語法的盡量使用)
2. 使用有意義的變數名稱
3. 不要使用沒有名稱的常數 (例如 int data[100];, 應該要用 int data[DATASIZE];)
4. 程式請務必對齊 (同一層的敘述一定要對齊), 不要用 tab, 用空格來對齊
5. 使用比較有限制的結構化語法 (for 迴圈比 while 迴圈好, if 比 goto 好, ...)
6. 使用函式來組織你的程式, 同時讓程式中每一個區塊裡變數盡量減少, 邏輯上沒有關連的程式盡量分到不同的區塊或是不同的函式中, 函式不要太大 (不要超過 50 列)
7. 請運用 assert 敘述設計自動驗證正確性的程式碼

作業繳交注意事項

請於時限內 (101/03/26 24:00) 上傳程式檔案 (逾時無法上傳), 上傳網頁
請編輯一個 report.txt (或是 report.doc) 檔案, 說明你的演算法高階的模型, 概念上的作法, 資料結構, 你所完成的功能, 測試結果,... 以及對於此次作業各個部份的問題? (提出問題時請盡量整理你所知道的, 與你所懷疑的, 你所不認同的..., 如此會比空洞的 "我不懂 xxx?", "yyy 是什麼?" 要容易回答, 相對的你也比較容易得到你想要的答案)
程式設計或是測試過程中, 也許你會遇見一些很難找出來的錯誤, 請多利用作業繳交網頁, 上傳有問題的程式, 適當地描述你所觀察到或是懷疑的錯誤, 一方面如果我或是助教有看到的話, 可以協助你解決問題, 另外一方面也可以記錄你程式修正的過程, 也證明你的確是按步就般地完成你的作業 (上傳時麻煩把不需要的檔案刪除)
請畫一些圖代表此演算法高階概念上的作法 (其實可以用 JohnsonBaugh 書中某幾張說明圖片)
report.txt (或是 report.doc) 中請說明你的心得 (心得可以包括你覺得你獲得的觀念, 你 debug 時發現的問題, 你 debug 的心得, 作業的感想, 你自己覺得比較好或是比較特別的設計...)

回 C++ 程式設計課程首頁

製作日期: 03/13/2012 by 丁培毅 (Pei-yih Ting)
E-mail: [email protected] TEL: 02 24622192x6615
海洋大學電機資訊學院資訊工程系 Lagoon