這還是個暖身的作業, 基本作法你在演算法的課程裡做過, 也當作作業交過, 不過這個作業開始有比較和物件相關的東西了, 主要要求你運用 C 的語法實作支援 Prim's Minimum Spanning Tree 演算法的 容器物件 - 抽象資料型態, 要求你運用課堂裡所解釋的函式指標來作出這個抽象資料型態, 要求你同時也要求你這個容器物件需要使用上一次作業的 Heap 來提升效率。

你在演算法課程裡幾個人一組做過這個程式, 所以應該不會有太大的心理負擔, 但是那時候有可能你沒有把精神用在寫一個別人很容易看得懂的程式, 沒有盡量用函式來抽象化程式的各個部份, 沒有把變數和函式好好取名字, 可能你沒有使用 MinHeap 來提昇容器的效率, 可能你沒有真的實作一個抽象資料型態, 只是用 C 的函式模擬需要有的功能, 沒有運用 assert 來確保各部份界面資料的正確性, 可能你沒有實作 adjacency matrix 的初始化, 可能沒有檢查你的程式是否有把所有動態配置的記憶體都釋放掉。這個作業裡希望你可以著重在這些部份, 當然如果你在上學期沒有寫出這個程式, 再給自己一次機會囉。

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

請注意, 由於我們在課堂裡已經開始講 C++ class 的語法, 這個作業你需要用 C 的函式指標語法來實作 ADT, 請你不要用 C++ 裡的 class 或是 struct 來實作, 那個是下一次的作業... 一個邏輯上幾乎一樣的作業可以交兩次, 很划算喔

作業目標：

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

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

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. Prim's MST 演算法如下:

   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, ...};

   上述函式定義中, 每一個函式的參數都需要多增加一個 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. 請使用上一次作業的 MinHeap 實作 Container ADT, 如此 h.del() 可以得到最好的效率
   
   
6. 由於你需要實作一個 adjacency matrix 來表示這個 Graph, 你可以嘗試(不強迫你做這一部份, 也是下一次的功能)也把它實作為一個 ADT
   
   
7. 如果在 adjacency matrix 裡面你應該有用 list 來記錄, 你應該有動態配置記憶體, 請練習運用 memory_leak 檢查程式在結束時是否有將所有動態配置的記憶體釋放
   
   
8. 你的程式需要以 (i, j) 形式輸出 minimum spanning tree 的每一個 edge, 同時輸出 edge 的總長度
   
   
9. 根據上課的說明, 也請你對你的程式進行下列的基本要求:

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

作業繳交注意事項

1. 請於時限內 (97/03/16 24:00) 上傳程式檔案 (逾時無法上傳), 上傳網頁
   

2. 請編輯一個 report.txt (或是 report.doc) 檔案, 說明你的演算法高階的模型, 概念上的作法, 資料結構, 你所完成的功能, 測試結果,... 以及對於此次作業各個部份的問題? (提出問題時請盡量整理你所知道的, 與你所懷疑的, 你所不認同的..., 如此會比空洞的 "我不懂 xxx?", "yyy 是什麼?" 要容易回答, 相對的你也比較容易得到你想要的答案)
   
   
3. 請畫一些圖代表此演算法高階概念上的作法 (其實可以用 JohnsonBaugh 書中某幾張說明圖片)
   
   
4. report.txt (或是 report.doc) 中請說明你的心得 (心得可以包括你覺得你獲得的觀念, 你 debug 時發現的問題, 你 debug 的心得, 作業的感想, 你自己覺得比較好或是比較特別的設計...)

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

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