這個課程排在一系列 程式設計/程式設計二/資料結構/演算法 課程之後, 課程目標是希望你能夠製作能夠不斷重複使用的程式碼、擴大你自己撰寫軟體的規模, 所以先要確定一下大家對於前面課程學到的程式設計方法有相當程度的掌握。
這是個暖身的作業, 基本作法你在資料結構和演算法的課程裡都學過, 我們上課時也簡要地複習過, 這個作業主要要求你運用 C 的語法實作支援 Prim's Minimal Spanning Tree 演算法的 容器物件, 這是一個抽象資料型態, 要求你運用課堂裡所解釋的 C 語言函式指標 (Abstract Datatype page 03-15,03-16) 來實作這個抽象資料型態 (雖然你在程式設計二課程裡就已經知道 C++ 的類別語法是可以實作上面所說的抽象資料型態, 但是你試著用函式指標來實作的話, 能夠更清楚知道 C++ 裡面是怎麼在 C 的基礎上實作這些成員函式的, 未來也會看到 C++ 的虛擬函式表格更是直接實作一整個函式指標的表格), 你在下面的演算法中會看到類似 h.init(key, n) 的用法, 這是什麼? 用 C 的基礎來想, init 是 h 這個結構變數的一個欄位, 但是它後面又有 (key, n) 這種函式呼叫時的參數, 所以 init 其實是一個 C 語法的函式指標。
在資料結構課程裡看過 array, list 和 heap 的實作,在演算法課程裡看過 Prim 這個 Minimal Spanning Tree 演算法, 所以應該不會有太大的心理負擔, 但是那時候有可能你沒有把精神用在寫一個別人很容易看得懂的程式, 沒有盡量用函式來抽象化程式的各個部份, 沒有替變數和函式好好取名字, 可能你沒有真的使用 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 開始, 但是下面的資料檔案裡節點是由 0 開始編號的)
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, ...}; // 或是 h.init = 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++ 語法, 你自己應該可以很快地改出來)。
除非你有遇見特別的問題需要印出來問我, 否則不需要繳交紙本程式碼
回 物件導向程式設計課程
首頁 製作日期: 02/21/2024 by 丁培毅 (Pei-yih Ting) E-mail: pyting@mail.ntou.edu.tw TEL: 02 24622192x6615 海洋大學 電機資訊學院 資訊工程學系 Lagoon |