這還是個暖身的作業, 基本作法你在演算法的課程裡做過, 期末考也有考過, 這個作業開始有比較和物件相關的東西了, 主要要求你運用 C 的語法實作支援 Prim's Minimal Spanning Tree 演算法的 容器物件 - 抽象資料型態, 要求你運用課堂裡所解釋的函式指標 (page 15,16) 來作出這個抽象資料型態 (為什麼需要用到函式指標呢? 你在下面的演算法中會看到類似 h.init(key, n) 的用法, 這是什麼? 用 C 的基礎來想, init 是 h 這個結構變數的一個欄位, 但是它後面又有 (key, n) 這種函式呼叫時的參數, 所以 init 其實是一個 C 裡面的函式指標)。

你在資料結構和演算法課程裡已經很熟悉這個演算法所以應該不會有太大的心理負擔, 但是那時候有可能你沒有把精神用在寫一個別人很容易看得懂的程式, 沒有盡量用函式來抽象化程式的各個部份, 沒有替變數和函式好好取名字, 可能你沒有真的使用 MinHeap 來提昇容器的效率, 可能你沒有真的實作一個抽象資料型態, 只是用 C 的函式模擬需要有的功能, 你可能心態上把軟體當程式可以任意改變的, 覺得只要外在要求的功能達成就夠了, 裡面到底怎麼寫的都無所謂, 可能沒有運用 assert 來確保各部份界面資料的正確性, 可能你沒有實作 adjacency matrix 的初始化, 可能沒有檢查你的程式是否有把所有動態配置的記憶體都釋放掉。這個作業裡希望你要著重在這些部份, 當然如果你在前兩個學期沒有寫出這個程式, 再給自己一次機會囉。(如果你看了下面的描述還是沒有辦法下手的話, 還可以額外參考相關的 Kruskal MST 演算法的實作: JohnsonBaugh 課本: 3.6, 7.2, slides, splitted slides, bw)

雖然不強制要求, 這個作業裡面 adjacency matrix 你也可以把它變成一個 ADT, 你可以自己練習定義它的界面 (例如 getHead(vertex), next()), 如果你沒有時間完成這部份的話, 也可以自己有時間時再完成。

請注意: 雖然我們在課堂裡很快就會講到 C++ class 的語法, 這個作業請你運用 C 的 struct 和 函式指標 語法來實作 ADT, 請你不要用 C++ 的 class 或是 C++ 的 struct 來實作。

作業目標：

1. 複習 C 中各種流程控制: for, while, if, switch 函式等等
   
2. 複習 C 中的資料結構定義: struct 語法
   
3. 複習 Prim's MST 演算法: JohnsonBaugh 課本 7.3 (slides, splitted slides - 動畫請下載後在Adobe Acrobat Reader 中看, bw) 演算法說明
   
4. 練習 iostream 輸出入函式庫 (鍵盤,螢幕,檔案輸出入)
   
5. 練習撰寫以 "容易了解, 容易修改, 容易偵錯" 為目標的工程化程式
   
6. 練習運用 多檔案的方式 分工 (例如這個程式你可以分 main, io)
   
7. 練習運用 assert
   
8. 練習使用 C 語法 的函式指標來實作 容器ADT 的操作方法
   
9. 練習運用 memory_leak 檢查程式是否有將所有動態配置的記憶體釋放, 如果你在撰寫這個程式的時候並沒有動態配置記憶體, 你還是要測試 (也許你用到的函式庫或是模組有進行動態記憶體的配置)

這個作業沒有提供範例執行程式, 針對程式執行的正確性, 需要你測試一些資料, 下面是兩組基本的測試資料 (請小心上面的投影片裡節點編號由 1 開始, 但是下面的資料檔案裡節點是由 0 開始編號的)

1. data1.dat
2. data2.dat

程式要求

1. 資料檔案內描述一個 Graph, 其中第一列為此 Graph 中節點的個數, 第二列為此 Graph 中邊的數目, 第三列以後每一列代表一個邊, 例如:

       6               ; number of nodes 0..5
       9               ; number of edges
       0 1 4           ; edge (0,1), distance 4
       0 2 2           ; edge (0,2), distance 2
       0 4 3
       1 3 5
        .
        .
        .

   代表 Graph 中有 6 個節點 (編號為 0, 1, 2, 3, 4, 5), 9 個邊, 分別為 (節點0, 節點1) 邊長為 4, (節點0, 節點2) 邊長為 2, ...
   每一列後面都有可能有註解, 程式需要跳過這些註解 (請不要編輯資料檔案刪除)
   
   
2. Johnbaugh 課本裡 Prim's MST 演算法的 pseudocode 如下:

   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
           }
       }
   }

   
   
3. 其中 h 是一個 容器 ADT, 提供下列功能:

   • h.init(key, n): initializes h to the values in key

   • h.del(): deletes the item in h with the smallest weight and returns the vertex

   • h.isin(w): returns true if vertex w is in h

   • h.keyval(w): returns the weight corresponding to vertex w

   • h.decrease(w, new_weight): changes the weight of w to new_weight (smaller)
   
   
   請以 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, ...}; // 或是 h.init = initImplementation;

   上述函式定義中, 每一個函式的參數都需要多增加一個 struct Container *self 的參數,
   這樣子函式裡才知道要處理哪一個 Container 的資料, 例如:

   int del(struct Container *self);
   int isIn(int w, struct Container *self);
   ...

   在 prim 演算法裡呼叫 init() 時需要把 h.init(key, n); 改成 h.init(key, n, &h); 如果你這樣子實作這個 Container ADT 的話, 除了最後這個 self 參數之外, 你的 prim() 程式就和上面的演算法的 pseudocode 幾乎一樣了 (如果你希望寫出來程式和上面演算法完全一樣, 就需要使用 C++ 語法, 你自己應該可以很快地改出來)。
   
   
4. 讀取資料檔案以及和使用者互動的部份請用 iostream, fstream 函式庫完成
   
   
5. 由於你需要實作一個 adjacency matrix 來表示這個 Graph, 你可以嘗試(不強制要求這一部份)也把它實作為一個 ADT
   
   
6. 如果在 adjacency matrix 裡面你有用 list 來記錄, 你應該有使用動態記憶體配置, 請練習運用 memory_leak 檢查程式在結束時是否有將所有動態配置的記憶體釋放
   
   
7. 你的程式需要輸入資料檔案的名稱, 輸入 Prim 演算法指定的起始節點 (minimal spanning tree 的 root 節點)
   
   
8. 你的程式需要以 (父節點, 子節點) 形式輸出 minimal spanning tree 的每一條邊, 請由指定的起始節點 (MST 的樹根) 開始印, 以子樹為單位印出所有的邊, 每一個節點的所有子節點請以其編號的大小順序印出, 另外也請輸出所有邊的總長度
   
   
   例如上圖的輸出為 (4,0) (0,1) (0,2) (2,3) (4,5) 12
   
   (請注意3/14以前已經線上繳交的同學不需要理會這個列印順序)
   
   
9. 根據上課的說明, 也請你對你的程式進行下列的基本要求:

   1. 去除不需要的指標運算 (能夠使用陣列語法的盡量使用)
      
      
   2. 使用有意義的變數名稱
      
      
   3. 不要使用沒有名稱的常數 (例如 int data[100];, 應該要用 int data[DATASIZE];)
      
      
   4. 程式編寫時請務必對齊 (同一層的敘述一定要對齊)
      
      
   5. 使用比較有限制的結構化語法 (for 迴圈比 while 迴圈好, if 比 goto 好, ...)
      
      
   6. 使用函式來組織你的程式, 同時讓程式中每一個區塊裡變數盡量減少, 邏輯上沒有關連的程式盡量分到不同的區塊或是不同的函式中, 函式不要太大 (不要超過 50 列)
      
      
   7. 請運用 assert 敘述加上自動驗證正確性的程式碼
      
      
10. 如果有額外的時間, 你可以實作一個 MinHeap 來支援上面的 Container ADT, 如此 h.del() 可以得到最好的效率

作業繳交注意事項

1. 請於時限內 (105/03/10 星期四 21:00) 上傳程式檔案 (逾時無法上傳), 上傳網頁
   

2. 請編輯一個 report.doc (或是 .docx, .rtf, .pdf) 檔案, 說明你的演算法高階的模型, 概念上的作法, 資料結構, 你所完成的功能, 測試結果,... 以及對於此次作業各個部份的問題? (提出問題時請盡量整理你所知道的, 與你所懷疑的, 你所不認同的..., 如此會比空洞的 "我不懂 xxx?", "yyy 是什麼?" 要容易回答, 相對的你也比較容易得到你想要的答案, 要能夠清楚的描述問題, 當然最好是你把程式片段編列號以後一起合併到 Word 文件檔案裡面)
   
   
3. 請畫一些圖說明此演算法高階概念上的作法 (其實可以用 JohnsonBaugh 書中某幾張說明圖片) , 如果你是手寫或是手繪的, 就請掃描為電子檔, 或是繳交紙本 (3/15上課時繳交)
   
   
4. 報告檔案中請說明你的心得 (心得可以包括你覺得你獲得的觀念, 你 debug 時發現的問題, 你 debug 的心得, 作業的感想, 你自己覺得比較好或是比較特別的設計, 你覺得題目裡的演算法有什麼問題, ..., 連心得都和別人雷同...真的還蠻不容易的, 不過還是感謝你, 讓我可以花比較少的時間找到你是參考哪一位同學的)
   

除非你有遇見特別的問題需要印出來問我, 否則不需要繳交紙本程式碼