2004 Spring C++ 程式作業一：
　　　　　　　　集合 (Set) 類別設計

集合 (Set) 類別設計

1. 各種流程控制： for, while, if, switch, 函式等等,

2. 檔案輸入輸出

3. vector 物件的使用

4. 類別語法的基礎練習

5. 類別界面的設計

6. 自定類別物件的使用

7. 請使用多個 .h, .cpp 檔案來分隔你的程式模組

範例執行程式, 資料檔案: ass1_data1.dat, ass1_data0.dat

請注意 ass1_data0.dat 要和 testSet.exe 放在同一個資料匣裡面

如附件顯示

執行時先要輸入 ass1_data1.dat 或是 ass1_data2.dat 或是 ass1_data3.dat
然後給一個輸出檔案名稱, (程式會將交集, 聯集, 差集三個集合順序寫入檔案中)
程式自己會去開啟固定名稱的檔案 ass1_data0.dat

請注意: ass1_data1.dat (或是 ass1_data2.dat 或是 ass1_data3.dat) 檔案中先後存放了兩個集合

程式基本要求

在這個作業中我們希望製作一個 "集合" 的類別, 集合一般在數學的表示方法中是用 {1, 3, 5, 7}, {a, b, c} 來表示的, 每一個集合中相同的元素不可以出現多次, (元素可以出現多次的集合稱為 multiset, 我們在這個作業中實作的不是 multiset), 對於一個集合的物件來說, 有一些基本的運算, 例如: 交集, 聯集, 差集, 屬於, 包含於, 等等 請製作一個整數的集合類別, 能夠放進去的元素一定要是 -100000 ~ 100000 之間的整數

1. 由於集合裡可以放的元素個數沒有限制, 所以你必須要用彈性比較大的方法來存放資料, 如果用陣列的話, 你需要在元素個數超過陣列大小時自動地調整陣列的大小, 不可以在機器記憶體還沒用完前就拒絕服務。

2. 你需要撰寫一個設定集合物件內容的函式:
   void CSet::setMembers(int numData, int dataArray[]);
   這個函式會讀取 dataArray[] 陣列內共有 numData 筆的整數資料, 檢查資料是否合法, 並且記錄在自己這個物件內, 如果原先自己這個物件內有任何資料的話都要清除掉

3. 請再撰寫一個設定集合物件內容的函式:
   void CSet::setMembers(CSet *originalSet);
   這個函式會讀取 originalSet 指標所指向物件內所有整數資料, 並且拷貝在自己這個物件內, (可以假設 originalSet 所指到的物件內所有的資料都在正確範圍內), 如果原先自己這個物件內有任何資料的話都要清除掉

4. 你需要撰寫一個清除集合物件內容的函式:
   void CSet::cleanup();
   如果你自己配置記憶體來存放資料的話, 你必須自己清除所配置的記憶體, 否則記憶體會越用越少, 最後程式會當在那裡

5. 你也可以用 vector 類別的物件來存放集合的元素, 在這個作業裡當然希望你用 vector, 不過你如果不用 vector 而能夠達到相當的功能的話也是可以的

6. 你應該要替這個集合類別 CSet 寫下面的函式:

   • 交集: 這個函式傳入一個 CSet 物件的指標, (如果你會用參考 Reference 型態的話也可以使用), 請計算自己這個 CSet 物件與傳入的 CSet 物件的交集, 並且將物件內容更改為算出來的集合

     例如原來物件 A 的內容是 {1, 2, 3, 4, 8}, B 的內容是 {1, 3, 5, 6, 7, 8}

     A.intersect(B);
     

     執行完以後 A 集合的內容成為 {1, 3, 8}

   • 聯集: 這個函式傳入一個 CSet 物件的指標, 請計算自己這個 CSet 物件與傳入的 CSet 物件的聯集, 並且將物件內容更改為算出來的集合

   • 差集: 這個函式傳入一個 CSet 物件的指標, 請計算自己這個 CSet 物件與扣除傳入的 CSet 物件內所有的元素後剩下的集合, 並且將物件內容更改為算出來的集合

   • 屬於: 這個函式傳入一個整數參數, 請檢查這個元素是否在自己這個 CSet 物件內, 並且傳回一個 bool 型態的結果, 請注意這個函式和下面幾個函式一樣都沒有修改物件的狀態, 所以應該是 const function, 如果你沒有寫 const 的話, 這一部份的功能就當作你沒做

   • 包含或等於: 這個函式傳入一個 CSet 物件的指標, 請檢查這個傳入的物件中所有的元素是否都在自己這個 CSet 物件內, 並且傳回一個 bool 型態的結果

   • 集合大小: 不需要傳入任何參數, 傳回目前集合的大小

   • 相等: 這個函式傳入一個 CSet 物件的指標, 請檢查這個傳入的集合物件是否和自己這個集合一模一樣, 請運用前面的包含或等於函式來完成

   • 其它你自己想到的函式, 如果你有做的話, 記得在心得裡面提到, 才能夠酌量加分

7. 請替這個類別寫一個成員函式將集合內的元素在螢幕上列印出來, 這個函式不需要傳入資料, 也不會回傳任何數值

8. 請替這個類別寫一個成員函式, 傳入一個檔案串流 ofstream 物件的指標, 將集合內容以二進位格式寫入檔案串流中, 每一個集合在檔案串流中的格式如下:

       四個位元組的整數代表集合內的元素個數 n,
       四個位元組的整數代表第 1 個元素, 
       四個位元組的整數代表第 2 個元素, 
       ...
       四個位元組的整數代表第 n 個元素, 
   

   如果你會用參考變數, 這個地方是可以用參考變數的地方, 但是不會用參考用指標還是可以完成指定的工作

9. 請替這個類別寫一個成員函式, 傳入一個檔案串流 ifstream 物件的指標, 將檔案內容 (如上一步驟的格式) 讀進集合物件內, 請注意如果原來物件內有其它的元素, 需要先刪除掉

10. 主程式:

        請由鍵盤讀入一個二進位檔案名稱, (例如 ass1_data1.dat)
        打開此檔案,
        由此檔案中讀入兩個集合 A, B, 
        判斷集合是否相等, 
        是否有包含於的關係, 在螢幕上列印判斷結果,
        在螢幕上印出各個集合的元素個數, 以及集合的內容,
        算出交集, 聯集, 差集, 將這三個集合寫入一個輸出檔案中,
        並且分別列印在螢幕上 (參考範例程式的輸出),
        請由文字檔案 ass1_data0.dat 中讀取集合 C 的資料, 
        列印集合 C-A-B
        最後進入一個迴圈,
        由鍵盤讀入一個整數, 並且測試否該整數在 C - A - B 的集合中
        
        請注意資料檔案 ass1_data0.dat 中有重複的元素
    

11. 測試檔案: ass1_data1.dat, ass1_data2.dat, 或 ass1_data3.dat (請注意這三個檔案內的資料都是二進位格式, 所以你用編輯器打開來看都是看不懂的東西, 每一個檔案裡都依序存放兩個集合 set A 和 set B)

其他注意事項:

1. 撰寫程式的時候由於你還不是很熟悉 C++ 的語法, 最好是寫一點點就編譯一下, 才不會一直等到寫完了以後發現錯誤很多, 不知道怎樣開始修改。

2. 各個函式的功能盡量不要重複, 可以盡量用已經設計好的功能來組合成新的功能, 例如: setMembers() 就可以用聯集完成, 這樣子可以減少程式維護的困難

3. 如果你能夠用 assert() 替類別寫一個測試函式的話, 在持續不斷地修改程式, 新增程式功能的過程中這是非常有用的, 請參考 C++ 實習 1-2 以及 3-2

4. 還沒想到

進一步增加程式的功能

原則上你想要增加什麼功能都是可以的, 記得在心得中寫出來, 這樣我才會注意到, 也才能夠幫你加一些分數, 現在程式還簡單, 你應該有辦法增加功能或是基於這個類別做一些好玩的應用。

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

製作日期: 2/27/2004 by 丁培毅 (Pei-yih Ting)
E-mail: pyting@cs.ntou.edu.tw TEL: 02 24622192x6615
海洋大學 工學院 資訊工程系 Lagoon