C++ 實習測試: 基於相鄰矩陣的有向圖表示方法 - Graph 類別 |
時間: 160分鐘 (106/04/20 09:20 ~ 12:00 上傳時間截止) |
在這個測試裡, 我們把正課期中考時的 Graph 類別實際製作出來, 你需要在編譯器的協助下克服所有的語法問題。可以看書, 可以看講義, 可以 google, 可以線上查參考資料, 就是不要跟同學討論, 不要線上和別人討論, 不要繳交同學的 code, 對於下面的描述有疑問覺得有模稜兩可的請一定要提出問題, 不過請不要問這個為什麼 compile 不成功? 為什麼會當掉? 或是該怎麼寫? ... 在雲端運算/雲端儲存或是物聯網的環境中,我們可以運用上圖的有向圖 (Directed Graph) 作為端點以及連結架構的模型,以便運用一些演算法來計算流量或是動態地調配資源,資料檔案 data.txt 配合下面的Graph類別定義以及部份介面的實作, 可以在建構的時候由檔案串流中讀取資料,並且以下圖節點Vertex的單向串列建立相鄰矩陣 (Adjacency Matrix),代表一個一般化有權重的有向圖 struct Vertex { Vertex(): ID(0), weight(0), next(0) { } Vertex(int id, int weight) :ID(id), weight(weight), next(0) { } Vertex(const Vertex& src): ID(src.ID), weight(src.weight), next(0) { } ~Vertex() { delete next; } int ID; int weight; Vertex *next; }; class Graph { public: Graph(ifstream &); Graph(const Graph &src); ~Graph(); int getFirst(const int id, int *weight); int next(int *weight); void print(ostream &os); private: void clone(const Graph &src); Vertex *m_listHeads; int m_curVertex; Vertex *m_iter; int m_nNodes; int m_nEdges; }; Graph::Graph(ifstream &infile) : m_curVertex(0), m_iter(0) { int i; infile >> m_nNodes; infile.ignore(80, '\n'); infile >> m_nEdges; infile.ignore(80, '\n'); m_listHeads = new Vertex[m_nNodes]; for (i=0; i<m_nNodes; i++) m_listHeads[i].ID = i; int node1, node2, weight; Vertex *ptr; for (i=0; i<m_nEdges; i++) { infile >> node1 >> node2 >> weight; infile.ignore(80, '\n'); ptr = &m_listHeads[node1]; while (ptr->next!=0) ptr = ptr->next; ptr->next = new Vertex(node2, weight); m_listHeads[node1].weight++; } } Graph::~Graph() { delete[] m_listHeads; } Graph::Graph(const Graph &src) : m_listHeads(0), m_curVertex(src.m_curVertex), m_iter(src.m_iter), m_nNodes(src.m_nNodes), m_nEdges(src.m_nEdges) { clone(src); } void Graph::clone(const Graph &src) { int i, j; Vertex *ptr, *ptrSrc; if (m_nNodes≤<=0) return; m_listHeads = new Vertex[m_nNodes]; for (i=0; i<m_nNodes; i++) { m_listHeads[i].ID = i; m_listHeads[i].weight = src.m_listHeads[i].weight; ptrSrc = &src.m_listHeads[i]; ptr = &m_listHeads[i]; for (j=0; j<m_listHeads[i].weight; j++) { ptr->next = new Vertex(*(ptrSrc->next)); ptrSrc = ptrSrc->next; ptr = ptr->next; } } } |
請根據下列要求完成這個類別:
void Graph::unitTest() { cout << "Unit testing... " << endl; srand(time(0)); { cout << " [ctor, copy ctor, equal] started" << endl; // 請測試Graph由檔案串流輸入的建構元 // 請測試Graph的拷貝建構元, 並且以assert及equal驗證拷貝的結果是正確的 // 請再一次測試Graph的拷貝建構元, 但是請運用new來產生新的Graph物件 cout << " [ctor, copy ctor, equal] tested" << endl; cout << " [addEdge,deleteEdge] started" << endl; // data.txt 中的資料是 (0,1,5)->(0,3,3)->(0,4,3)->(0,5,2) // 下面請用 addEdge(), deleteEdge(), equal(), assert() 來驗證在 // 串列最前面, 串列中間, 以及串列最尾巴新增一個邊都不會出錯 // 你也可以運用 deleteEdge() 回傳的 bool 值驗證某一條邊, 例如 (0,1,1) // 並不存在 // 請考量 (0,1,1) // 請考量 (0,2,1) // 請考量 (0,6,7) // 因為邊在串列中的順序是依照節點大小以及權重大小來排列的 // 請藉由 addEdge() 的先後順序來測試程式新增邊的時候是否有按照順序 cout << " [addEdge,deleteEdge] tested" << endl; // 請測試輸出 Graph 物件到檔案串流, 再重新讀回來, // 與先前的 Graph 物件比對來驗證, 另外請直接驗證其中某些邊是否存在 cout << " [print(ostream&)] tested" << endl; // 請測試 Graph 的設定運算子, 除了能夠完整的拷貝一個物件, // 想辦法確定有沒有 dangling pointer cout << " [assignment] tested" << endl; // 為了配合 Vertex 結構以及 Graph 物件的記憶體配置與釋放測試, // 請新增一個全域的變數 gVertexCount 來紀錄配置了多少個 Vertex 結構, 請修改 // Vertex 所有的建構元函式來遞增 gVertexCount, 請額外實作拷貝建構元函式來遞增 // gVertexCount (因為下面的測試沒有用到 Vertex::operator==(), 所以沒有實作這個函式), // 請修改解構元函式來遞減 gVertexCount, 請運用 assert 來確保完整掌握記憶體的使用 // 你可以撰寫迴圈隨機配置/釋放大量的 Vertex 結構, 隨時掌握 Vertex 物件的數量 // 最後也應該要確保所有的 Vertex 結構(包含靜態配置和動態配置的)都釋放掉了 } ... cout << " [dtor] tested" << endl; cout << "Unit test completed" << endl; } |
考試時間: 160分鐘 (09:20 ~ 12:00 上傳時間截止) 將所完成的 project (只需保留 .cpp, .h, .sln 以及 .vcxproj 檔案即可; 刪除掉 .suo, .sdf, .filters, .users, debug\ 資料匣, 以及 ipch\ 資料匣下的所有內容) 以 zip/rar/7zip 程式將整個資料匣壓縮起來, 在「考試作業」繳交區選擇 Labtest2 上傳 |
後續: 前半學期最主要練習的是在 Bottom-up 程式設計中最基礎、也最重要的 類別封裝, 也許你心裡不斷地懷疑著: 不是說基礎嗎? 為什麼這麼複雜? 基礎和簡單不太一樣, 不要小看基礎, 萬丈高樓平地起, 就在這個基礎打下去的時候, 就已經預測得到它最後的高度了, 隨隨便便的基礎其實也就是常常需要打掉重練的原因, 沒有堅實的基礎, 真的不要去碰觸穩定的商用程式, 不要說製作, 連改都盡量不要去改它, 會出事的, 像是自己會走的機器人、自駕車、無人機、飛機上的自動駕駛、衛星上的控制系統、武器系統、...至於手機程式嘛...當掉重開就算了。也許你急著看到絢麗的界面, 想說都什麼時代了, 應該兩三行 code 就可以得到所有想要的功能, 應該都有現成的模組組合一下就好了, 如果真的是這樣, 你可以, 別人也可以, 大家都可以, 應該機器自己也可以吧, 咦!! 那你為什麼要來資訊系那麼辛苦做什麼? 接下去最直接的你可以運用這個類別寫一些圖的演算法, 例如 Prim 最小生成樹, Dijkstra 最短路徑等等, 此外需要練習的是越來越多物件之間的合作。 |
回
C++ 物件導向程式設計課程 首頁 製作日期: 04/20/2017 by 丁培毅 (Pei-yih Ting) E-mail: pyting@mail.ntou.edu.tw TEL: 02 24622192x6615 海洋大學 電機資訊學院 資訊工程學系 Lagoon |