Lab 10-1: 串列 (List) 容器類別 (Container)

    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;
    };

    class StudentList
    {
    public:
        StudentList();
        ~StudentList();
        void appendEntry(Student *student);
        bool deleteEntry(char *id);
        Student *find(char *id);
    private:
        Node *m_head, *m_tail;
    };

    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 物件

然後實作 StudentList 建構元與 ~StudentList 解構元函式
解構元函式需要把所有的 Node 節點都釋放掉 (這裡有兩種實作的方法, 一種是寫一個迴圈, 把所有的 Node 節點一個一個釋放掉; 另外一種相當於是遞迴, 只刪除第一個 Node 節點, 第二個以後則是寫在 Node 類別的解構元裡, ~Node() 除了刪除 所紀錄的 Student 物件之外, 還去刪除 next 所指到的下一個 Node 節點)

請注意:一個指標容器物件裡面到底需不需要負責它所指向物件的刪除, 是一個設計者可以自己決定的選項, 上面這個 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);
這個函式應該要產生一個節點 new Node(student), 把這個節點接在目前的串列的最後面, 修改 m_tail 指標。 請特別小心處理 m_head == 0 且 m_tail == 0 的狀況

這個函式需要直接存取 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 *);
        ...
    };
    ...
};

傳入的參數是一個記錄 id 的字元陣列, 你的函式需要一個節點一個節點去比對每一筆資料, 看看是否那個學生的 m_ID 為所傳入的 id? 如果是的話, 將此 Student 物件的指標傳出

在實作之前, 我們應該先在 Student 類別內實作一個比較 id 字串的成員函式

    bool Student::IDEquals(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;

要實作刪除一個節點的功能, 至少需要兩個 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;

    if (m_head->m_data->IDEquals(id))
    {
        delete m_head;
        m_head = m_tail = 0;
        return true;
    }
    return false;

    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";
    }