演習問題

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 は以下のように定義されているものとする。

struct Node
{
    int   m_value;       //  ノードが保持する値
    Node*m_next;       // 次のノードへのポインタ
    Node*m_prev;       // 前のノードへのポインタ
public:
    Node(int v = 0) : m_value(v) {}
};

• Node prev, next; link(&prev, &next); を実行し、prev と next が正しく連結されていることを確認しなさい。
• テストコード、 解答例
2. ★ List クラスにコンストラクタ List() を追加し、サイズを 0 に、 m_dummy がダミーノードを指し、ダミーノードは自分自身とリンクするよう初期化しなさい。
   List は以下のように宣言されるものとする。

class List
{
public:
    List();
private:
    Node*m_dummy;           //  ダミーノードへのポインタ
    int   m_size;             //  ダミーを除く要素数
};

• List lst を生成し、オブジェクトが正しく構築されていることを確認しなさい。
• テストコード、 解答例
3. ★★ List クラスにデストラクタ ~List() を追加し、オブジェクトが保持するノードを全て delete するようにしなさい。
• List オブジェクトを生成・破棄し、ノードが全て解放されることをデバッガで確認しなさい。
• 解答例
4. ★void appendTail(Node *dummy, Node *ptr) dummy がダミーノードを指すとき、環状リストの末尾に ptr ノードを追加する関数を実装しなさい。
• 環状リストを生成し、そこに appendTail() を使ってノードを追加し、ノードが正しく追加されていることを確認しなさい。
• テストコード、 解答例
5. ★ List クラスにコンストラクタ List(int sz, int v) を追加し、サイズを sz に設定し、 ダミーノードと値vを持つsz個のノードを環状につなぎ、m_dummy がダミーノードを指すように初期化しなさい。
• List lst(3, 2); でオブジェクトを生成し、リストが正常に構築されていることを確認しなさい。
• テストコード、 解答例
6. ★ List クラスにコンストラクタ List(const int *first, const int *last) を追加し、 サイズをfirstからlastまでのデータ数に設定し、 ダミーノード付き環状リストを構築し、m_dummy がダミーノードを指すように初期化しなさい。 各ノードの値は first から last 直前までのデータを設定するものとする。
• int d[] = {3, 1, 4}; List lst(d, d+3); でオブジェクトを生成し、リストが正常に構築されていることを確認しなさい。
• テストコード、 解答例
7. ★ List クラスにコピーコンストラクタ List(const List &x) を追加し、 同じサイズ・データを持ったリストを構築しなさい。
• int d[] = {3, 1, 4}; List lst(d, d+3); List lst2(lst) でオブジェクトを生成し、lst2 が lst のコピーとして構築されていることを確認しなさい。
• テストコード、 解答例

　

---

前： ｜上：C/C++ ポインタ入門 ｜次：