這是個暖身的作業, 基本作法你在資料結構和演算法的課程裡都做過, 也都當作作業交過 (你在演算法課程裡甚至幾個人一組做過這個), 但是請注意, 這個作業的要求不一樣, 而且你必須自己動手做, 不能拿以前的程式直接繳交, 如果你沒有達到下面我們要求的, 基本上是得不到太多分數的 (如果幾個同學都拿演算法同組同學的作業直接繳交, 除了沒有達到我們這堂課程的要求之外, 你還會因為和別人的程式完全一樣而被判定抄襲, 如果有同學跟你要程式, 就說我規定是不行的, 抄襲基本上是大家 share 一個成績...)。同時也請你不要小看這裡在程式的 "正確性" 之外所要求的事情, 趕快開始做, 不要最後因為時間不夠而胡亂繳交一份。

這個作業主要是呼應我們在課堂裡討論的 "撰寫程式時無形的規範 (b&w)", 就請你拿簡單的 HeapSort 演算法當作範例, 按照我們課堂裡對於 Selection Sort 演算法的實作所作的逐步修改, 依樣畫葫蘆一番, 相信你更能夠了解設計程式時除了正確性以外一些比較形而上的要求。

其次, 這個作業裡也希望你練習 iostream 函式庫的用法, 多程式檔案的連結, 還有 assert 的使用。

雖然實際上這次作業比較像一個習題, 挑戰性稍微少了一點, 不過還是可以複習一下必備的 C 語法與程式設計, 如果你撰寫時遇見問題, 歡迎你隨時找我詢問, 上課後, 實習課, 電話, email, msn... 都可以運用 (當然這也是說服我 - 你的確付出努力去完成這個作業 - 最直接的辦法)。

作業目標：

1. 複習 C 中各種流程控制： for, while, if, switch, 函式等等
   
2. 複習 C 中的資料結構定義: struct 語法
   
3. 複習 Heap 資料結構和相關的演算法(JohnsonBaugh), Cormen's Chapter 7 Introduction to Algorithm
   
4. 練習 iostream 輸出入函式庫 (鍵盤,螢幕,檔案輸出入)
   
5. 練習撰寫以 "容易了解, 容易修改, 容易偵錯" 為目標的工程化程式
   
6. 練習運用 多檔案的方式 分工 (例如這個程式你可以分 main, io, 和 heapsort)
   
7. 練習運用 assert

這個作業不提供範例執行程式, 不過針對程式執行的正確性, 還是需要你測試一些資料, 下面是兩組基本的測試資料, 和一組內容有錯的資料 (data3.dat)

1. data1.dat
2. data2.dat
3. data3.dat

程式要求

1. 資料檔案內是某一個企業的臨時僱員的資料, 其中第一列為此檔案中資料的筆數, 第二列以後每四列代表一筆資料, 例如:

       10
       e96570000
       Adas, Mohammad A
       140
       100
        .
        .
        .

   代表檔案中有 10 個僱員, 其中第一個僱員的資料包括 ID, 姓名, 每月工作時數, 以及時薪
   
   每月工作時數應該是一個大於等於 0, 小於 180 的整數
   
   時薪基本上只有 80, 100, 120 三種
   
   
2. 請以 struct 定義能夠存放每一個僱員的型態, 由檔案中讀取資料至這種型態的陣列中, 以你自己撰寫的 HeapSort 程式將每一個僱員的月薪由小至大排序之後, 列印出月薪前五名的平均值, 後五名的平均值, 列印出薪水排名倒數第二名的僱員的姓名和 ID
   
   
3. 請寫一個比較月薪的函式 int compareMonthPay(struct Employee person1, struct Employee person2)
   如果 person1 的月薪大於 person2 的月薪, 函式傳回 1, 如果相等則傳回 0, 如果小於則傳回 -1
   你的 HeapSort 裡應該要呼叫這個函式來比較大小
   
   
4. 你的程式需要做很多次的 swap 動作, 一定要獨立寫成函式
   
   
5. 你的 HeapSort 裡應該至少要實作 siftdown(), heapify(), delete(), 以及 heapsort() 這些函式, 同時你的 heapify() 函式執行時間應該要是 O(n) 而不是 O(n log n)
   
   
6. 讀取資料檔案以及和使用者互動的部份請用 iostream, fstream 函式庫完成
   
   
7. 根據上課講義, 請你對你的程式進行下列的要求:

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

作業繳交注意事項

1. 請於時限內 (101/03/07 24:00) 上傳程式檔案 (逾時無法上傳, 請預先測試你的帳號與密碼), 上傳網頁
   
   
2. 請注意雖然作業的題目好像看過很多次, 可是由於你對於 iostream, fstream 不是很熟悉, 所以你還是應該早點開始做, 避免先看到同學的程式, 由於程式功能已經有很多的限制了, 所以如果你先看過別人的程式, 你很難寫出和別人不一樣的東西...

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

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

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