這還是個暖身的作業, 基本作法你在演算法的課程裡做過, 期末考也有考過, 這個作業開始有比較和物件相關的東西了, 主要要求你運用 C 的語法實作支援 Prim's Minimal Spanning Tree 演算法的 容器物件 - 抽象資料型態, 要求你運用課堂裡所解釋的函式指標 (page 15,16) 來作出這個抽象資料型態, 要求你同時也要求你這個容器物件需要使用上一次作業的 Heap 來提升效率。
你在演算法課程裡已經很熟悉這個演算法所以應該不會有太大的心理負擔, 但是那時候有可能你沒有把精神用在寫一個別人很容易看得懂的程式, 沒有盡量用函式來抽象化程式的各個部份, 沒有把變數和函式好好取名字, 可能你沒有真的使用 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 來實作
這個作業沒有提供範例執行程式, 針對程式執行的正確性, 需要你測試一些資料, 下面是兩組基本的測試資料
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, ...
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 } } }
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 的參數,
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++ 語法, 你自己應該可以很快地改出來)。
除非你有遇見特別的問題需要印出來問我, 否則不需要繳交紙本程式碼
回
C++ 物件導向程式設計課程
首頁
製作日期: 02/14/2014 by 丁培毅 (Pei-yih Ting) E-mail: pyting@mail.ntou.edu.tw TEL: 02 24622192x6615 海洋大學 電機資訊學院 資訊工程學系 Lagoon |