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が保持するデータ数が格納されます。
- ★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 が正しく連結されていることを確認しなさい。
- テストコード、
解答例
- ★ List クラスにコンストラクタ List() を追加し、サイズを 0 に、
m_dummy がダミーノードを指し、ダミーノードは自分自身とリンクするよう初期化しなさい。
List は以下のように宣言されるものとする。
class List
{
public:
List();
private:
Node*m_dummy; // ダミーノードへのポインタ
int m_size; // ダミーを除く要素数
};
- List lst を生成し、オブジェクトが正しく構築されていることを確認しなさい。
- テストコード、
解答例
- ★★ List クラスにデストラクタ ~List() を追加し、オブジェクトが保持するノードを全て delete するようにしなさい。
- List オブジェクトを生成・破棄し、ノードが全て解放されることをデバッガで確認しなさい。
- 解答例
- ★void appendTail(Node *dummy, Node *ptr)
dummy がダミーノードを指すとき、環状リストの末尾に ptr ノードを追加する関数を実装しなさい。
- 環状リストを生成し、そこに appendTail() を使ってノードを追加し、ノードが正しく追加されていることを確認しなさい。
- テストコード、
解答例
- ★ List クラスにコンストラクタ List(int sz, int v) を追加し、サイズを sz に設定し、
ダミーノードと値vを持つsz個のノードを環状につなぎ、m_dummy がダミーノードを指すように初期化しなさい。
- List lst(3, 2); でオブジェクトを生成し、リストが正常に構築されていることを確認しなさい。
- テストコード、
解答例
- ★ List クラスにコンストラクタ List(const int *first, const int *last) を追加し、
サイズをfirstからlastまでのデータ数に設定し、
ダミーノード付き環状リストを構築し、m_dummy がダミーノードを指すように初期化しなさい。
各ノードの値は first から last 直前までのデータを設定するものとする。
- int d[] = {3, 1, 4}; List lst(d, d+3); でオブジェクトを生成し、リストが正常に構築されていることを確認しなさい。
- テストコード、
解答例
- ★ List クラスにコピーコンストラクタ List(const List &x) を追加し、
同じサイズ・データを持ったリストを構築しなさい。
- int d[] = {3, 1, 4}; List lst(d, d+3); List lst2(lst) でオブジェクトを生成し、lst2 が lst のコピーとして構築されていることを確認しなさい。
- テストコード、
解答例
前:
|上:C/C++ ポインタ入門
|次: