ViVi Home > 技術文書 > ポインタ入門 > リストクラス演習問題


 

 

C/C++ ポインタ入門 > リストクラス 演習問題
Nobuhide Tsuda
Jan-2014

演習問題

List は int 値を持つダミーノード付き環状双方向リンクリストクラスです。
ひとつの値はひとつのノードに格納されます。
front(), back(), at(ix) 等で値を参照でき、push_back(値), pop_back(), insert(ix, 値), erase(ix) 等で値を挿入・削除することが出来ます。
上記以外にも、isEmpty(), size() などオブジェクトの状態を返すメンバ関数や、 resize(sz, ch), clear() などでオブジェクトの状態を変えるメンバ関数を持ちます。
std::list と概ね同一ですが、データ型が int 型固定という点が大きく異なります。

List が保持するノードは前後のノードを指すポインタにより環状にリンクされ、m_dummy が先頭ノードを指します。
データが1個も無い場合でも、処理を共通にするために、ダミーのノードを保持し、m_dummy はそこを指します。
従って、データ数がsize個の場合、List が実際に保持するノードの数はsize+1個となります。
m_size にListが保持するデータ数が格納されます。

  1. void link(Node *prev, Node *next) prev が指すノードの次に next が指すノードを連結する関数を実装しなさい。 Node は以下のように定義されているものとする。
  2. struct Node
    {
        int   m_value;       //  ノードが保持する値
        Node*m_next;       // 次のノードへのポインタ
        Node*m_prev;       // 前のノードへのポインタ
    public:
        Node(int v = 0) : m_value(v) {}
    };
    
  3. List クラスにコンストラクタ List() を追加し、サイズを 0 に、 m_dummy がダミーノードを指し、ダミーノードは自分自身とリンクするよう初期化しなさい。
    List は以下のように宣言されるものとする。
  4. class List
    {
    public:
        List();
    private:
        Node*m_dummy;           //  ダミーノードへのポインタ
        int   m_size;             //  ダミーを除く要素数
    };
    
  5. ★★ List クラスにデストラクタ ~List() を追加し、オブジェクトが保持するノードを全て delete するようにしなさい。
  6. void appendTail(Node *dummy, Node *ptr) dummy がダミーノードを指すとき、環状リストの末尾に ptr ノードを追加する関数を実装しなさい。
  7. List クラスにコンストラクタ List(int sz, int v) を追加し、サイズを sz に設定し、 ダミーノードと値vを持つsz個のノードを環状につなぎ、m_dummy がダミーノードを指すように初期化しなさい。
  8. List クラスにコンストラクタ List(const int *first, const int *last) を追加し、 サイズをfirstからlastまでのデータ数に設定し、 ダミーノード付き環状リストを構築し、m_dummy がダミーノードを指すように初期化しなさい。 各ノードの値は first から last 直前までのデータを設定するものとする。
  9. List クラスにコピーコンストラクタ List(const List &x) を追加し、 同じサイズ・データを持ったリストを構築しなさい。
  10.  


    前: |上:C/C++ ポインタ入門 |次: