University: Students and departments

問題 -- University 1：在Acme大學，每個學生除有其姓名(name)之外，並在入學時取得一個學號(ID)，每個學生有一個主修系(major department)。每個學系有名稱(name)，並有一個代碼(code)。

Acme大學需要一個程式供行政人員使用。啟動時，程式將自三個檔案分別讀入學生、學系與學生主修學系資料，格式如下：

學生資料 
Jagger,Mick;U20130001
Carey,Mariah.;U20130002
Johnson,John;U20130003
Savitch,Sam;U20130004
Bass,Lenos;U20130005
Kazman,Rick;U20130006
Lippman,Stanley;U20130007

學系資料 
Computer Science;CS
Music;MU
Chemistry;CH

學生與主修學系資料 
U20130001;CS
U20130002;MU
U20130003;CH
U20130004;CS
U20130005;CH
U20130006;MU
U20130007;CS

程式啟動後，需顯示操作指引。在這個問題裡，行政人員將能依所選擇學系，並選擇名單按照學號或姓名增冪(increasing)或降冪(decreasing)，依據下列格式(以學號升冪排序)列出主修該學系的學生名單。

Computer Science (CS): 3 students
U20130001 Jagger, Mick
U20130004 Savitch, Sam
U20130007  Lippman, Stanley

U步驟：這是一個典型的資訊處理程式。這些資訊為現實世界(real world)中，個體(學生、學系)的模型(model)。除了讀檔與顯示之外，程式並涉及排序(sorting)的問題。

D步驟：列出工作如下。

1. Create a student given a name and ID.
2. Create a department given its name and code.
3. Add a student to a department.
4. Sort the list of students in a department.
5. Set up students from a file.
6. Set up departments from a file.
7. Set up relationships between students and departments according to relationships  specified in a file.
8. Produce a list of students by department in the specified format.  
C步驟：

相信你已經能處理工作1~2, 5~6,8了，工作7只要在知道工作3如何處理後，應當也無問題。所以，我們看看如何處理工作3與工作4。

工作3：回答兩個問題，(1)學生需不需要記得他的主修學系?(2)學系需不需要記得它的學生?在現實世界裡，一個學生一定記得他的主修學系；一般而言，學系也會記得學生(通常透過學系的職員查詢學生名冊，這裡先不考慮這個細節)。程式中為他們建立模型，而設計反映這個模型。由暫無其他特殊考量因素(例如可測試性)，故以符合現實世界的模型為依據進行設計，如下：

剩下的事就是「按圖施工」了--寫測試、建立Student 與 Department 類別相關的data與function。

Student以一個data member「記住」他的主修學系。有三種作法：

1. Department _major：將Department視為Student的一部分，在Student物件destructor執行時(例如going out of scope)，_major 所代表的Department物件將一併被解構。由於Department物件可能關係著其他學生，故此作法不適用。

2. Department & _major：將Department視為Student參考的一個物件，_major 所參考的Department物件在Student物件destructor執行時(例如going out of scope)，並不會被解構。這個做法的限制是 a. 學生物件 constructor執行時 department物件必須已存在且在 constructor initialization list中加以初值化：

   Student(... Department & dept): ... _major(dept) {}

b. Student物件不應變更 _major 所參考的Department物件，

   // semantics error
   void setMajor (Department & dept) {_major = dept;} 

因為如此一來，原先 _major所參考的 Department物件將被 dept覆蓋。解決之道是更改宣告為

   const Department & _major;

如此一來編譯時就會有錯：

   // syntax error
   void setMajor (Department & dept) {_major = dept;} 

這意味著學生將不得轉系！基於b.的限制，此作法亦不適用。

3. Department * _major：將Department視為Student以指標方式參考的一個物件，_major 在Student物件destructor執行時(例如going out of scope)，並不會被解構。這個做法最具彈性，Student constructor執行時可將 _major預設為 NULL：

   Student(... Department * dept=NULL): ... _major(dept) {}

稍後再加以設定：

 void setMajor (Department *dept) {_major = dept;} // OK

這個做法的缺點是在Student的函數中，你得視情況先確認 _major不為NULL再加以使用。

 _major->name(); // 有 NULL pointer exception的危險

接著，Department得記住它的學生。用上面同樣的作法，但Department物件通常有多個學生，且題目涉及sorting，所以記住的方法為

vector<Student *> _students;

學習課題：reference variable, vector (C++  standard template library STL)。

工作4：將學生按照學號或姓名作升冪或降冪排序。由於學號、姓名都適合以string表示，所以要了解如何對string排序。在Department中，我們已使用std::vector存放pointer to Student，
  
  vector<Student *> _students;

所以，工作4就是按照學號或姓名，以升冪或降冪排序 _students的內容。

對vector內容排序的函數，C++已有提供。下面我用測試的方式試試看：

#include <vector>
#include <algorithm>
...
TEST (intVector, vector){
int a[]={3,2,1,4};
vector<int> v(a,a+4);
std::sort (v.begin(), v.begin()+4);
LONGS_EQUAL(1,v[0]);
LONGS_EQUAL(2,v[1]);
LONGS_EQUAL(3,v[2]);
LONGS_EQUAL(4,v[3]);
}

std::sort內建為升冪。如要降冪排序則可傳入一個比較函數：


bool decrease(int i, int j) {return i>j;}

TEST (intVectorDecrease, vector){
int a[]={3,2,1,4};
vector<int> v(a,a+4);
sort (v.begin(), v.begin()+4, decrease);
LONGS_EQUAL(4,v[0]);
LONGS_EQUAL(3,v[1]);
LONGS_EQUAL(2,v[2]);
LONGS_EQUAL(1,v[3]);
}

請試試完成工作4。

學習課題： list, iterator, sort (C++ standard template library STL)。
 

© Y C Cheng, 2013. All rights reserved.