這是個暖身的作業, 希望你再延伸實習一, 將排序的演算法改為 Quicksort 排序法, Quicksort 的基本演算法你在演算法的課程裡學過, 但是請注意, 這個作業的要求不太一樣, 每位同學必須自己動手做, 不能拿以前練習的程式直接繳交, 如果你沒有達到下面要求的項目, 基本上是得不到太多分數的, 請不要小看這裡在程式的 "正確性" 之外所要求的事情, 趕快開始做, 不要最後因為時間不夠而胡亂繳交一份。

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

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

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

作業目標：

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

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

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

程式要求

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

       10
       Adas, Mohammad A
       e96570000
       140.5
       120
        .
        .
        .

   代表檔案中有 10 個僱員, 其中第一個僱員的資料包括 姓名, ID, 每月工作時數, 以及時薪
   
   每月工作時數應該是一個大於等於 0, 小於 180 的浮點數
   
   時薪基本上只有 80, 100, 120 三種
   
   
2. 請以 struct 定義能夠存放每一個僱員所有資料的型態, 由檔案中讀取資料至這種型態的陣列中
   
3. 請寫一個比較月薪的函式 int compareMonthPay(struct Employee person1, struct Employee person2)
   如果 person1 的月薪大於 person2 的月薪, 函式傳回 1, 如果相等則傳回 0, 如果小於則傳回 -1
   你的 QuickSort 裡應該要呼叫這個函式來比較大小
   
   
4. 你的程式需要做很多次的 swap 動作, 一定要獨立寫成函式
   
   
5. 讀取資料檔案以及和使用者互動的部份請用 iostream, fstream 函式庫完成
   
   
6. 請修改實習一中所有資料陣列的型態, 統計並且列印平均值, 中數, 以及眾數, 其中眾數的計算請以千元為單位來統計出現的次數 (0~1000, 1001~2000, ....)
   
   
7. 根據上課講義, 希望你的程式滿足下列要求:
   
   
   1. 去除不需要的指標運算 (能夠使用陣列語法的盡量使用)
      
      
   2. 使用有意義的變數名稱
      
      
   3. 不要使用沒有名稱的常數 (例如 int data[100];, 應該要用 int data[DATASIZE];)
      
      
   4. 程式請務必對齊 (同一層的敘述一定要對齊)
      
      
   5. 使用比較有限制的結構化語法 (for 迴圈比 while 迴圈好, if 比 goto 好, ...)
      
      
   6. 使用函式來組織你的程式, 同時讓程式中每一個區塊裡變數盡量減少, 邏輯上沒有關連的程式盡量分到不同的區塊或是不同的函式中, 函式不要太大 (以 30 列為平均值, 不要超過 50 列)
      
      
   7. 請運用 assert 敘述以及呼叫 stdlib.h 中的 qsort 建立自動測試正確性的程式碼 (至少排序完之後應該可以檢查一下正確性, 原始資料的正確性也可以檢查一下)
      
      
   8. 另外, 請不要使用全域變數 (global variable) 在函式之間傳遞資料, 這是程序化程式設計的大敵
      
      
      

作業繳交注意事項

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

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

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

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