實習目標 |
實作一個 List 類別
每一個節點請用 Inner Class 及 friend 來定義 |
---|---|
步驟一 | 如下圖, 串列 (List) 是一種很常用的資料結構, 這種資料結構最主要的優點是它可以允許彈性地更改資料的順序,
允許在任何地方新增及刪除資料節點, 可以用來很有效率地存放不適合用陣列存放的資料。
|
步驟二 |
我們要實作的串列中每一個節點的資料部份是一個指標,
指向 Student 類別的物件,
如下圖所示:
class Student { public: Student(const char *name, const char *ID, const char *phone, const char *department); ~Student(); void display(ostream &os) const; private: char *m_name; char *m_ID; char *m_phone; char *m_department; };請實作這個類別的建構元, 解構元, 以及一個簡單的 display() 列印資料函式 |
步驟三 |
接下來請定義 StudentList 類別,
其主要的資料與界面如下:
class StudentList { public: StudentList(); ~StudentList(); void appendEntry(Student *student); bool deleteEntry(char *id); Student *find(char *id); private: Node *m_head, *m_tail; };其中 Node 為一個 Inner Class, 請在 StudentList 類別內定義此類別, 如下: class StudentList { class Node { public: Node(Student *data); ~Node(); private: Student *m_data; Node *m_next; }; public: StudentList(); ~StudentList(); ... }; 請注意: 如此定義的 inner class 的全名是 StudentList::Node, 定義在 StudentList 的 private 區域之內, 是一個 private inner class, 因為是 private 區域, 所以在 StudentList 類別之外並沒有辦法直接用到這個類別, 例如在 main() 函式內如果你想要宣告一個 StudentList::Node mynode; 編譯器會告訴你無法直接使用 private class。 另外請注意 Node 類別雖然在 StudentList 類別內定義, 但是並沒有說它可以存取 StudentList 的私有資料, 同樣地 StudentList 也不能存取 Node 類別的私有資料,類別的邊界還是存在的。 |
步驟四 |
首先請實作 Node 類別建構元 Node(Student *data),
此函式傳入一個 Student 物件的指標,
請將此指標記錄在 m_data 欄位內
其次為 Node 類別的解構元 ~Node(), 此函式需要刪除所記錄的 Student 物件
然後實作 StudentList 建構元與 ~StudentList 解構元函式
請注意:一個指標容器物件裡面到底需不需要負責它所指向物件的刪除, 是一個設計者可以自己決定的選項, 上面這個 StudentList 在解構時基本上會把所有指到的 Student 物件刪除, 但是 C++ 標準函式庫裡面的 vector 容器就不會幫你刪除, 例如 int i; vector<Student *> sVector; for (i=0; i<10; i++) sVector.push_back(new Student("Carol Chen", "333331111", "0933333111", "Business")); 當 sVector 解構時並不會自動解構所有指到的 Student 物件, 你可以下載 testVector.zip, 編譯, 用 debugger 執行, 可以看到記憶體 沒有釋放的錯誤 其次請實作 void appendEntry(Student *student);
這個函式需要直接存取 Node::m_data 以及 Node::m_next, 請使用 friend 語法在 Node 類別內允許 StudentList 類別的成員函式直接存取, 特別注意一下, 因為 C/C++ 的編譯器只會由頭到尾檢查程式一次, 所以如果你定義 friend void StudentList::appendEntry(Student *); 則這個 friend 敘述之前一定要先定義 appendEntry 成員函式, 例如: class StudentList { public: void appendEntry(Student *student); ... private: class Node { friend void StudentList::appendEntry(Student *); ... }; ... }; |
步驟五 |
請實作
Student *StudentList::find(char *id);
傳入的參數是一個記錄 id 的字元陣列, 你的函式需要一個節點一個節點去比對每一筆資料, 看看是否那個學生的 m_ID 為所傳入的 id? 如果是的話, 將此 Student 物件的指標傳出 在實作之前, 我們應該先在 Student 類別內實作一個比較 id 字串的成員函式 bool Student::IDEquals(char *id) { ... }StudentList::find(char *id) 的主要內容如下: Node *ptr; for (ptr=m_head; ptr!=0; ptr=ptr->m_next) if (ptr->m_data->IDEquals(id)) return ptr->m_data; return 0; |
步驟六 |
請實作
bool StudentList::deleteEntry(char *id);
要實作刪除一個節點的功能, 至少需要兩個 Node 型態的指標變數, 主要的程式片段如下: (可以自己寫的話就自己先設計看看吧!) if (m_head->m_data->IDEquals(id)) { ptr1 = m_head; m_head = m_head->m_next; delete ptr1; return true; } for (ptr2=m_head, ptr1=m_head->m_next; ptr1!=0; ptr2=ptr1, ptr1=ptr1->m_next) if (ptr1->m_data->IDEquals(id)) { ptr2->m_next = ptr1->m_next; if (ptr1 == m_tail) m_tail = ptr2; // ptr1->next = 0; 如果 ~Node() 實作裡有刪除它的下一個節點的話 delete ptr1; return true; } return false;以上片段是 m_head != 0 且 m_tail != 0 的狀況, 你還需要考慮 m_head == m_tail 的狀況, 程式片段如下: if (m_head->m_data->IDEquals(id)) { delete m_head; m_head = m_tail = 0; return true; } return false;以及 m_head == 0 && m_tail == 0 的狀況 |
步驟七 | 請注意目前這個 StudentList 類別並不完備 (complete), 我們定義了增加/尋找/刪除資料節點的函式, 但是並沒有實作讀出資料的函式, 我們會在下一個實習中實作 |
步驟八 |
請測試下列程式
void main() { StudentList sList; sList.appendEntry(new Student("Mary Chen", "111111111", "0933111111", "Business")); sList.appendEntry(new Student("John Wang", "222222222", "0928222222", "Computer Science")); sList.appendEntry(new Student("Mel Lee", "333333333", "0968333333", "Mechanical Engineering")); sList.appendEntry(new Student("Bob Tsai", "444444444", "0930444444", "Electrical Engineering")); sList.appendEntry(new Student("Ron Yang", "555555555", "0918555555", "Computer Science")); sList.find("222222222")->display(cout); cout << endl; if (sList.deleteEntry("444444444")) cout << "Bob Tsai's entry deleted successfully!\n"; else cout << "Bob Tsai's entry deletion failed!\n"; if (sList.find("444444444") == 0) cout << "Can not fine Bob Tsai's entry!\n"; } |
步驟九 | 請助教檢查後, 將所完成的 專案 (只需保留 .cpp, .h, .sln 以及 .vcxproj 檔案即可; 刪除掉 .suo, .sdf, .filters, .users, debu\ 資料匣, 以及 ipch\ 資料匣下的所有內容) 壓縮起來, 選擇 Lab10-1 上傳, 後面的實習課程可能需要使用這裡所完成的程式 |
另外可以嘗試使用 C++ 標準函式庫裡面的 list (cplusplus) 來完成我們上面所作的 StudentList 的功能, 熟悉一下 C++ 的 list 工具類別 |
回
C++ 物件導向程式設計課程
首頁
製作日期: 05/03/2004 by 丁培毅 (Pei-yih Ting) E-mail: pyting@mail.ntou.edu.tw TEL: 02 24622192x6615 海洋大學 電機資訊學院 資訊工程學系 Lagoon |