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

 
實習目標 實作一個 List 類別
每一個節點請用 Inner Class 及 friend 來定義
 
步驟一 如下圖, 串列 (List) 是一種很常用的資料結構, 這種資料結構最主要的優點是它可以允許彈性地更改資料的順序, 允許在任何地方新增及刪除資料節點, 可以用來很有效率地存放不適合用陣列存放的資料。
在這個實習中我們要實作一個簡化的串列類別, 練習 Inner Class 以及 friend class 的使用方法
步驟二 我們要實作的串列中每一個節點的資料部份是一個指標, 指向 Student 類別的物件, 如下圖所示:
所以我們先定義 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 解構元函式
解構元函式需要把所有的 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 *);
        ...
    };
    ...
};
步驟五 請實作 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