今回は簡単な例題として「連結リスト (linked list)」という基本的なデータ構造を取り上げます。Ｃ++の標準ライブラリには <list> という「双方向リスト (doubly-linked list)」を実装したコンテナクラスや、「単方向リスト (singled-linked list)」を実装した <forward_list> というコンテナクラスが用意されています。私たちが連結リストを作る必要はありませんが、Ｃ++のお勉強ということで、あえてプログラムを作ってみることにしましょう。
今回作成する連結リストは双方向リストではなく単方向リストです。単方向リストはデータを一方向につなげたデータ構造です。データを前後につなげたものが双方向リストです。リストを操作するプログラミング言語では Lisp が有名ですが、Lisp で扱うリストが単方向リストです。関数型言語や論理型言語の Prolog で扱うリストもそうです。下図に連結リスト (単方向リスト) の構造を示します。
(1)変数
┌─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│・┼─→│10│・┼→│20│・┼→│30│／│ ／：終端(0)
└─┘ └─┴─┘ └─┴─┘ └─┴─┘
(2)ヘッダセル
┌─┬─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│ │・┼─→│10│・┼→│20│・┼→│30│／│ ／：終端(0)
└─┴─┘ └─┴─┘ └─┴─┘ └─┴─┘
図 : 連結リスト
連結リストはセル (cell) というデータを繋げて作ります。セルにはデータを格納する場所と、次のセルを指し示す場所から構成されます。上図でいうと、箱がひとつのセルを表していて、左側にデータを格納し、右側に次のセルへのポインタを格納します。リストの終わりを示すため、最後のセルの右側には特別な値（たとえば nullptr とか 0）を格納します。そして、上図 (1) のように先頭セルへのポインタを変数に格納しておけば、この変数を使って連結リストにアクセスすることができます。また、上図 (2) のようにヘッダセルを用意する方法もあります。
連結リストの長所は、データの挿入や削除が簡単にできることです。配列でデータの削除や挿入を行う場合、要素を移動しなければいけませんが、連結リストはセルを付け替えるだけで実現できます。逆に、配列はどの要素にも一定の時間でアクセスすることができますが、連結リストはセルを順番にたどっていくため、後ろのデータほどアクセスに時間がかかります。これが連結リストの短所です。
それではプログラムを作りましょう。今回はプログラムを簡単にするため、格納するデータ型は int に限定します。Ｃ++の場合、「テンプレート (template)」という機能を使うと、いろいろなデータ型に対応する連結リストを作成することができます。これはテンプレートを取り上げるときに試してみましょう。
最初に、連結リストを表すクラス LinkList とセルを表すクラス Cell を定義します。次のリストを見てください。
リスト : 連結リストの定義
// セル
class Cell {
int item;
Cell* next;
public:
Cell(int x, Cell* cp) : item(x), next(cp) {}
int& car() { return item; }
Cell* cdr() { return next; }
void set_car(int x) { item = x; }
void set_cdr(Cell* cp) { next = cp; }
};
// 連結リスト
class LinkList {
Cell* top;
static Cell* nth_cell(Cell*, int); // n 番目のセルを求める
static Cell* copy_cell(Cell*); // リストのコピー
public:
LinkList() : top(new Cell(0, 0)) { }
~LinkList() {
clear();
delete top;
}
LinkList(const LinkList&); // コピーコンストラクタ
LinkList& operator=(const LinkList&); // 代入演算子
// メンバ関数
int nth(int);
void set(int, int);
void insert(int, int);
int remove(int);
int length();
void clear();
bool empty();
// 演算子の多重定義
friend ostream& operator<<(ostream&, const LinkList&);
// イテレータとジェネレータの定義
//
// ・・・省略・・・
//
};
Cell のメンバ変数 item にデータを格納し、ポインタ変数 next に次のセルへのポインタを格納します。コンストラクタ Cell(x, cp) は引数 x を item に、引数 cp を next にセットします。これは Lisp / Scheme の関数 cons に相当します。メンバ関数 car は item への参照を返し、cdr は next の値を返します。これらのメンバ関数は Lisp / Scheme の関数 car, cdr に相当します。set_car と set_cdr はメンバ変数 item と next の値を書き換えます。名前は Scheme の関数 set-car!, set-cdr! から拝借しました。
| 関数名 | 機能 |
|---|---|
| int nth(int n) | n 番目の要素を求める |
| void set(int n, int x) | n 番目の要素を x に書き換える |
| void insert(int n, int x) | n 番目の位置にデータ x を挿入する |
| int remove(int n) | n 番目の要素を削除する |
| int length() | リストの長さ (要素数) を求める |
| bool clear() | 連結リストを空にする |
| bool empty() | 連結リストが空の場合は真を返す |
| Iterator begin() | 連結リストの先頭を示すイテレータを返す |
| Iterator end() | 連結リストの終端を示すイテレータを返す |
| Generator make_gen() | ジェネレータを生成する |
| void for_each(void (*func)(int)) | 連結リストの要素に関数 func を適用する |
次に、セルを使って連結リストクラス LinkList を作成します。LinkList はセルを保持するメンバ変数 top を用意します。デフォルトコンストラクタで、top にヘッダセルをセットします。ヘッダセルの item はダミーで、このプログラムでは 0 をセットします。また、セルの終端は 0 で表すことにします。
あとは、連結リストを操作するメンバ関数を定義します。要素の位置 (添字) は配列と同様に 0 から数えることにします。位置 n がリストの要素数 (長さ) よりも多い場合は例外 out_of_range を送出します。連結リストはランダムアクセスができないので、配列添字演算子 [] でのアクセスはサポートしません。n 番目の要素を操作する場合、0 番目の操作 (リストの先頭要素) はとても高速ですが、n が大きくなるほど時間がかかることに注意してください。
length はリストの長さを求めます。empty は連結リストが空の場合は true を返し、データがあれば false を返します。イテレータは内部クラス Iterator で定義し、ジェネレータも内部クラス Generator で定義します。
最初に、作業用の静的メンバ関数として n 番目のセルを求める処理を作ります。関数名は nth_cell としました。次のリストを見てください。
リスト : n 番目のセルを求める
Cell* LinkList::nth_cell(Cell* cp, int n)
{
int i = -1;
while (cp) {
if (n == i) break;
cp = cp->cdr();
i++;
}
return cp;
}
引数 cp にはヘッダセルを渡します。ヘッダセルから数えるので、変数 i は -1 に初期化します。次に、while ループでセルをたどり、i が n と等しくなったとき、そのセルを return で返します。
セルのたどり方は実に簡単です。下図を見てください。
cp1 cp2 cp3
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│10│・┼→│20│・┼→│30│・┼→
└─┴─┘ └─┴─┘ └─┴─┘
↑ ↑
(1) (2)
(1) cp = cp->cdr() => cp2
(2) cp = cp->cdr() => cp3
図 : セルのたどり方
セル cp1 の next にはセル cp2 へのポインタが格納されています。変数 cp が cp1 の場合、cp = cp->cdr() とすれば、cp の値はセル cp2 になります (図 (1))。さらに cp = cp->cdr() とすれば、cp の値は cp3 になります (図 (2))。
nth_cell の場合、while ループでセルをたどっていきますが、途中でセルがなくなった場合、cp の値は 0 になるので while ループを終了して 0 を返すことになります。
次に、連結リストをコピーする静的メンバ関数 copy_cell を作ります。
リスト : リストのコピー
Cell* LinkList::copy_cell(Cell* cp)
{
return !cp ? cp : new Cell(cp->car(), copy_cell(cp->cdr()));
}
リストのコピーは再帰定義を使うと簡単です。引数 cp が終端 (0) ならばそのまま返します。これは空リストのコピーは空リストであることに対応します。そうでなければ、new Cell() で新しいセルを作ります。item には cp->car() の値をコピーします。next には copy_cell を再帰呼び出しした返り値をセットします。このとき、copy_cell には cp->cdr() を渡します。
つまり、copy_cell を再帰呼び出しするたびに、引数のリスト cp の長さは一つずつ短くなるわけです。長さが 0 になったときが再帰呼び出しの停止条件です。再帰呼び出しから戻ってきたら新しいセルを作り、そこに cp->car() の値と copy_cell の返り値をセットして、新しいセルを返せばリストをコピーすることができます。
もちろん、繰り返しでもプログラムを作ることができます。興味のある方はプログラムを修正してみてください。
それでは、n 番目の要素を求めるメンバ関数 nth から作りましょう。次のリストを見てください。
リスト : n 番目の要素を求める
int LinkList::nth(int n)
{
Cell* cp = nth_cell(top, n);
if (cp) return cp->car();
throw out_of_range("LinkList::nth out of range");
}
nth_cell() を呼び出して n 番目のセルを求めます。cp が 0 でなければ、格納されているデータ cp->car() を返します。cp が 0 の場合は例外を送出します。
要素の値を書き換えるメンバ関数 set() も簡単です。
リスト : データの更新
void LinkList::set(int n, int x)
{
Cell* cp = nth_cell(top, n);
if (!cp) throw out_of_range("LinkList::set out of range");
cp->set_car(x);
}
セルを見つけたら set_car で item の値を x に書き換えるだけです。
次は、データの挿入を行うメンバ関数 insert を作りましょう。データの挿入はセルの next を書き換えることで実現できます。下図を見てください。セル (1) とセル (2) の間に、セル (3) を挿入します。
top (1) (2)
┌─┐ ┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│ ┼──→│10│・┼─ X ─→│20│・┼→│30│／│
└─┘ └─┴┼┘ └─┴─┘ └─┴─┘
│ (3) ↑
│ ┌─┬─┐│
└→│40│・┼┘
└─┴─┘
セル(1)とセル(2)の間にセル(3)を挿入する場合
図 : データの挿入
セル (1) の後ろにセル (3) を挿入する場合、セル (1) の next にはセル (2) へのポインタがセットされているので、この値をセル (3) の next にセットします。これで、セル (3) とセル (2) がリンクされます。次に、セル (1) の next にセル (3) へのポインタをセットします。これで、セル (1) とセル (2) の間に、セル (3) を挿入することができます。
プログラムは次のようになります。
リスト : データの挿入
void LinkList::insert(int n, int x)
{
Cell* cp = nth_cell(top, n - 1);
if (!cp) throw out_of_range("LinkList::insert out of range");
cp->set_cdr(new Cell(x, cp->cdr()));
}
連結リストにデータを挿入する場合、挿入する位置のひとつ手前のセルが必要になります。nth_cell で n - 1 番目のセルを求めます。セル cp が見つかれば、新しいセルを new で取得して、それを cp の後ろに挿入します。n が 0 の場合、nth_cell はヘッダセルを返すので、リストの先頭にデータが挿入されることになります。
new Cell(x, cp->cdr()) で x を格納する新しいセルを生成します。第 2 引数に cp->cdr() を指定することで、新しいセルの後ろに、cp の次のセルを接続することができます。そして、cp->set_cdr() で next の値を新しいセルに書き換えます。これで cp の後ろに新しいセルを挿入することができます。
次は、データを削除するメンバ関数 remove を作りましょう。
(1) (2) (3)
┌─┬─┐ ┌─┬─┐ ┌─┬─┐
│10│・┼×→│20│・┼→│30│・┼→
└─┴┼┘ └─┴─┘ └─┴─┘
│ ↑
└─────────┘
図 : データの削除:セル(2) を削除する場合
データを削除する場合も、セルを付け替えるだけで済ますことができます。上図を見てください。セル (1) の後ろにあるセル (2) を削除する場合、セル (1) の next をセル (3) へのポインタに書き換えればいいのです。セル (3) はセル (2) の next から求めることができます。つまり、セル (1) を保持する変数を cp とすると、セル (3) は cp->cdr()->cdr() で求めることができるのです。
プログラムは次のようになります。
リスト : データの削除
int LinkList::remove(int n)
{
Cell* cp = nth_cell(top, n - 1);
if (!cp || !cp->cdr())
throw out_of_range("LinkList::remove out of range");
Cell* cp1 = cp->cdr();
int x = cp1->car();
cp->set_cdr(cp1->cdr());
delete cp1;
return x;
}
データを削除する場合も、削除する位置のひとつ手前のセルが必要になります。nth_cell で n - 1 番目のセルを求めます。セル cp が見つかれば、cp の後ろのセルを削除します。
次に、削除するセルがあるか cp->cdr() の値をチェックします。値が 0 でなければ、そのセルを削除します。まず、削除するセルを変数 cp1 にセットし、格納されているデータを変数 x に取り出します。それから cp->cdr() の値を cp1->cdr() に書き換えます。そして、削除したセルを delete で解放してから、最後に x を返します。
次は連結リストを空にするメンバ関数 clear() を作ります。
リスト : 連結リストを空にする
void LinkList::clear()
{
Cell* cp = top->cdr();
while (cp) {
Cell *tmp = cp->cdr();
delete cp;
cp = tmp;
}
top->set_cdr(0);
}
連結リストを空にする場合、top の next を 0 に書き換えるだけではダメで、取得したセルのメモリを解放する必要があります。最初に、top->cdr() の値を変数 cp にセットします。あとは while ループでセルを順番にたどります。このとき、cp->cdr() の値を変数 tmp に退避してから、セル cp を delete で解放します。そして、cp の値を tmp に書き換えます。これで、セルを順番にたどりながらメモリを解放することができます。
LinkList のデストラクタは clear() を呼び出してから、top に格納されているヘッダセルを delete で解放するだけです。
LinkList はメンバ変数がポインタなので、コピーコンストラクタと代入演算子の多重定義が必要になります。プログラムは次のようになります。
リスト : コピーコンストラクタ
LinkList::LinkList(const LinkList& ls) : top(new Cell(0, 0))
{
top->set_cdr(copy_cell(ls.top->cdr()));
}
引数 ls のリスト (ls.top->cdr()) は copy_cell で簡単にコピーすることができます。あとは、返り値を set_cdr で top に連結するだけです。
リスト : 代入演算子の多重定義
LinkList& LinkList::operator=(const LinkList& ls)
{
if (this != &ls) {
clear();
top->set_cdr(copy_cell(ls.top->cdr()));
}
return *this;
}
代入演算子の場合、最初に自分自身の代入かチェックします。そうでなければ、clear() で連結リストを廃棄します。それから、copy_cell で引数 ls のリストをコピーして、それを set_cdr で top に連結するだけです。
次はイテレータを表すクラス Iterator を作りましょう。
リスト : イテレータ
class LinkList {
//
// ・・・省略・・・
//
class Iterator {
Cell* idx;
public:
Iterator(Cell* cp) : idx(cp) {}
// 前置きの ++ 演算子, -- 演算子は無い
Iterator& operator++() {
if (idx) idx = idx->cdr();
return *this;
}
// 間接演算子
int& operator*() { return idx->car(); }
// 比較演算子
bool operator==(const Iterator& iter) {
return idx == iter.idx;
}
bool operator!=(const Iterator& iter) {
return idx != iter.idx;
}
};
Iterator begin() { return Iterator(top->cdr()); }
Iterator end() { return Iterator(0); }
};
メンバ変数 idx はデータを格納するセルへのポインタです。idx はポインタ変数ですが、セルのメモリ領域は LinkList で取得しているので、Iterator のデストラクタで delete してはいけません。また、コピーコンストラクタと代入演算子もデフォルトのもので大丈夫です。
コンストラクタの第 1 引数 cp はセルへのポインタで、この値でメンバ変数 idx を初期化します。実際には、Iterator() を直接呼び出すのではなく、LinkList にイテレータを生成するメンバ関数 begin と end を用意して、そこでイテレータを生成します。 begin はヘッダセルの次のセルをコンストラクタに渡し、end は終端 (0) を渡します。
あとはイテレータの操作で必要となる演算子を多重定義します。++ 演算子は前置と後置がありますが、今回は前置だけを定義します。この場合、返り値の型は Iterator& になります。あとは、idx の値を idx->cdr() に書き換えるだけです。今回は単方向リストなので、一つ前に戻る -- 演算子は定義できません。間接演算子も簡単で、返り値の型を int& に指定します。これで連結リストの要素を読み書きすることができます。
比較演算子は等値演算子 ==, != だけを定義します。セルのメモリ領域は動的に取得されますが、割り当てられるセルのアドレスがどこになるのか、実際に実行してみないとわかりません。つまり、前のセルのアドレスが後ろのセルのアドレスよりも小さい (または大きい) とは限らないわけで、セルのアドレスだけで前後を判定することはできないのです。等値演算子は idx の値 (セルのアドレス) を比較するだけです。
次はジェネレータを表すクラス Generator を作りましょう。
リスト : ジェネレータ
class LinkList {
//
// ・・・省略・・・
//
class Generator {
Cell* idx;
public:
Generator(Cell* cp) : idx(cp) { }
bool operator()(int& x) {
if (!idx) return false;
x = idx->car();
idx = idx->cdr();
return true;
}
};
Generator make_gen() { return Generator(top->cdr()); }
};
基本的な考え方はイテレータと同じです。内部クラス Generator の中で演算子 () を多重定義します。連結リストの要素は有限なので、データの有無を返す必要があります。ここでは返り値のデータ型を bool とし、要素は引数の参照型変数 x にセットして返すことにします。メンバ変数 idx が終端 (0) の場合は false を返します。
最後に高階関数 for_each を作りましょう。
リスト : 高階関数 for_each
class LinkList {
//
// ・・・省略・・・
//
// 高階関数
void for_each(void (*func)(int x)) {
Cell *cp = top->cdr();
while (cp) {
func(cp->car());
cp = cp->cdr();
}
}
};
引数 func に関数ポインタを受け取り、while ループで順番に要素を取り出して func を呼び出すだけです。また、次のように通常の関数として定義することもできます。
リスト : 高階関数 for_each (2)
void for_each(LinkList& ls, void (*func)(int))
{
for (auto iter = ls.begin(); iter != ls.end(); ++iter)
func(*iter);
}
このように、イテレータを使うと引数のデータ型が異なるだけで、ベクタのプログラムと同じ処理になります。
あとのプログラムは簡単なので説明は割愛します。詳細はプログラムリストをお読みください。
それでは実行してみましょう。
リスト : 簡単なテスト
int main()
{
LinkList xs;
cout << xs << endl;
for (int i = 0; i < 8; i++) {
xs.insert(i, i);
cout << xs << endl;
}
cout << xs.length() << endl;
LinkList ys = xs; // コピーコンストラクタ
cout << ys << endl;
LinkList zs;
for (int i = 0; i < 10; i++) {
zs.insert(i, 0);
}
cout << zs << endl;
zs = ys; // 代入演算子
cout << zs << endl;
cout << xs.nth(0) << endl;
cout << xs.nth(4) << endl;
cout << xs.nth(7) << endl;
xs.set(0, 100);
xs.set(4, 200);
xs.set(7, 300);
cout << xs << endl;
cout << xs.remove(7) << endl;
cout << xs << endl;
cout << xs.remove(0) << endl;
cout << xs << endl;
cout << xs.remove(3) << endl;
cout << xs << endl;
cout << xs.empty() << endl;
xs.clear();
cout << xs << endl;
cout << xs.empty() << endl;
// イテレータ
for (auto iter = ys.begin(); iter != ys.end(); ++iter) {
cout << *iter << endl;
*iter = *iter * 2;
}
cout << ys << endl;
// ジェネレータ
auto gen = ys.make_gen();
int x;
while (gen(x)) cout << x << " ";
cout << endl;
//
ys.for_each(print);
cout << endl;
}
$ clang++ linklist.cpp $ ./a.out () (0) (0 1) (0 1 2) (0 1 2 3) (0 1 2 3 4) (0 1 2 3 4 5) (0 1 2 3 4 5 6) (0 1 2 3 4 5 6 7) 8 (0 1 2 3 4 5 6 7) (0 0 0 0 0 0 0 0 0 0) (0 1 2 3 4 5 6 7) 0 4 7 (100 1 2 3 200 5 6 300) 300 (100 1 2 3 200 5 6) 100 (1 2 3 200 5 6) 200 (1 2 3 5 6) 0 () 1 0 1 2 3 4 5 6 7 (0 2 4 6 8 10 12 14) 0 2 4 6 8 10 12 14 0 2 4 6 8 10 12 14
正常に動作していますね。
Ｃ/Ｃ++で大きいプログラムを作る場合、ソースファイルを機能単位 (または他の基準) で複数のファイルに分割して管理することがよく行われます。Ｃ/Ｃ++の場合、分割したファイルを個別にコンパイルすることが可能で、そのあとオブジェクトファイル (拡張子が .o のファイル) をリンクで結合すれば、実行ファイルを生成することができます。これを「分割コンパイル (separate compilation)」といいます。
プログラムのテスト段階になると、不具合を見つけては修正し、またテストを行うということを繰り返します。ソースファイルを修正したあと再コンパイルするのですが、ファイルが大きいとコンパイルに時間がかかります。ファイルを分割しておけば、修正したファイルだけコンパイルすればいいので、コンパイル時間を短縮することができるわけです。
簡単な例として、今回作成した連結リストを testlist.cpp と linklist.cpp に分割してみましょう。ファイルを分割する場合、linklist.cpp に定義されているデータ型や関数などの情報を testlist.cpp に知らせる必要があります。これにはヘッダファイルを使います。
Ｃ/Ｃ++ユーザならば、標準ライブラリを使用するときにヘッダファイルをインクルードしているはずです。ヘッダファイルには、そのライブラリで使用できる関数のプロトタイプ宣言、マクロ、構造体やクラスの定義などが格納されています。プロトタイプは、関数の引数と返り値の型を前もって宣言することです。そうすることで、コンパイル時において型チェックを行うことができます。
それでは、ヘッダファイルを書いてみましょう。クラス Cell と LinkList の定義を linklist.cpp から linklist.h に移すだけです。それから、linklist.h と linklist.cpp は using namespace std; を使わないように変更します。必要なところに std:: を追加してください。
リスト : linklist.h
#ifndef _LINKLIST_H_
#define _LINKLIST_H_
#include <iostream>
#include <stdexcept>
// セル
class Cell {
int item;
Cell* next;
public:
Cell(int x, Cell* cp) : item(x), next(cp) {}
int& car() { return item; }
Cell* cdr() { return next; }
void set_car(int x) { item = x; }
void set_cdr(Cell* cp) { next = cp; }
};
// 連結リスト
class LinkList {
Cell* top; // メンバ変数
static Cell* nth_cell(Cell*, int); // n 番目のセルを求める
static Cell* copy_cell(Cell*); // リストのコピー
public:
LinkList() : top(new Cell(0, 0)) { }
~LinkList() {
clear();
delete top;
}
LinkList(const LinkList&); // コピーコンストラクタ
LinkList& operator=(const LinkList&); // 代入演算子
int nth(int);
void set(int, int);
void insert(int, int);
int remove(int);
int length();
void clear();
bool empty();
// 演算子の多重定義
friend std::ostream& operator<<(std::ostream&, const LinkList&);
//
// イテレータとジェネレータは省略
//
};
#endif
#ifndef はプリプロセッサ指令です。
#ifndef マクロ 処理１ #else 処理２ #endif
マクロが定義されていなければ、処理 1 の展開を行い、定義されていれば処理 2 の展開を行います。linklist.h の場合、_LINKLIST_H_ が定義されていなければ _LINKLISH_H_ を定義します。それから、必要なヘッダファイルの読み込みとクラスの定義や関数宣言を行います。_LINKLIST_H_ が定義されている場合は何も行いません。
標準ライブラリ のヘッダファイルも同様な処理がなされています。これは、ヘッダファイルを何回読み込んでもコンパイルできるようにするためです。たとえば、linklist.h では iostream を読み込んでいますね。ほかのヘッダファイルでも iostream を読み込んでいるものがあるかもしれません。単純に読み込むだけでは、iostream での定義は二重に定義されたとしてコンパイルエラーになってしまいます。
それでは、linklist.h で iostream の読み込み (インクルード) をやめればいいはずです。しかし、今度は iostream をインクルードしないヘッダファイルといっしょに使用する場合に困ってしまいます。linklist.h を使う場合は、ほかのヘッダファイルを調べてから iostream をインクルードしてください、というのではとても使いにくいですね。ヘッダファイル側で二重定義にならないように工夫されているので、ほかのヘッダファイルの内容まで考えなくて済むのです。
ヘッダファイルは、ユーザにとってそのライブラリの顔を意味しています。ヘッダファイルを見れば、そのライブラリの機能概要や使い方がわかるように、きちんと書いておくといいでしょう。
最後に testlist.cpp を作ります。
リスト : testlist.cpp
#include "linklist.h"
using namespace std;
void print(int x)
{
cout << x << " ";
}
int main()
{
LinkList xs;
cout << xs << endl;
for (int i = 0; i < 8; i++) {
xs.insert(i, i);
cout << xs << endl;
}
cout << xs.length() << endl;
LinkList ys = xs; // コピーコンストラクタ
cout << ys << endl;
LinkList zs;
for (int i = 0; i < 10; i++) {
zs.insert(i, 0);
}
cout << zs << endl;
zs = ys; // 代入演算子
cout << zs << endl;
cout << xs.nth(0) << endl;
cout << xs.nth(4) << endl;
cout << xs.nth(7) << endl;
xs.set(0, 100);
xs.set(4, 200);
xs.set(7, 300);
cout << xs << endl;
cout << xs.remove(7) << endl;
cout << xs << endl;
cout << xs.remove(0) << endl;
cout << xs << endl;
cout << xs.remove(3) << endl;
cout << xs << endl;
cout << xs.empty() << endl;
xs.clear();
cout << xs << endl;
cout << xs.empty() << endl;
// イテレータ
for (auto iter = ys.begin(); iter != ys.end(); ++iter) {
cout << *iter << endl;
*iter = *iter * 2;
}
cout << ys << endl;
// ジェネレータ
auto gen = ys.make_gen();
int x;
while (gen(x)) cout << x << " ";
cout << endl;
//
ys.for_each(print);
cout << endl;
}
#include 命令で "..." を指定すると、カレントディレクトリからヘッダファイルを探します。見つからない場合は、標準ライブラリのヘッダファイルと同じディレクトリを探します。一般に、ユーザが定義したヘッダファイルはソースファイル (.cpp) と同じディレクトリに置き、#include "..." でインクルートします。
分割したファイルをコンパイルするのは簡単です。今回のように小さなプログラムでは、次のように複数のソースファイルを指定するだけで十分です。
$ clang++ testlist.c linklist.c
これで実行ファイル a.out を生成することができます。
//
// linklist.h : 連結リスト
//
// Copyright (C) 2015-2023 Makoto Hiroi
//
#ifndef _LINKLIST_H_
#define _LINKLIST_H_
#include <iostream>
#include <stdexcept>
// セル
class Cell {
int item;
Cell* next;
public:
Cell(int x, Cell* cp) : item(x), next(cp) {}
int& car() { return item; }
Cell* cdr() { return next; }
void set_car(int x) { item = x; }
void set_cdr(Cell* cp) { next = cp; }
};
// 連結リスト
class LinkList {
Cell* top; // メンバ変数
static Cell* nth_cell(Cell*, int); // n 番目のセルを求める
static Cell* copy_cell(Cell*); // リストのコピー
public:
LinkList() : top(new Cell(0, 0)) { }
~LinkList() {
clear();
delete top;
}
LinkList(const LinkList&); // コピーコンストラクタ
LinkList& operator=(const LinkList&); // 代入演算子
int nth(int);
void set(int, int);
void insert(int, int);
int remove(int);
int length();
void clear();
bool empty();
// 演算子の多重定義
friend std::ostream& operator<<(std::ostream&, const LinkList&);
// イテレータ
class Iterator {
Cell* idx;
public:
Iterator(Cell* cp) : idx(cp) {}
// 前置きの ++ 演算子, -- 演算子は無い
Iterator& operator++() {
if (idx) idx = idx->cdr();
return *this;
}
// 間接参照
int& operator*() { return idx->car(); }
// 比較演算子
bool operator==(const Iterator& iter) {
return idx == iter.idx;
}
bool operator!=(const Iterator& iter) {
return idx != iter.idx;
}
};
Iterator begin() { return Iterator(top->cdr()); }
Iterator end() { return Iterator(0); }
// ジェネレータ
class Generator {
Cell* idx;
public:
Generator(Cell* cp) : idx(cp) { }
bool operator()(int& x) {
if (!idx) return false;
x = idx->car();
idx = idx->cdr();
return true;
}
};
Generator make_gen() { return Generator(top->cdr()); }
// 高階関数
void for_each(void (*func)(int x)) {
Cell *cp = top->cdr();
while (cp) {
func(cp->car());
cp = cp->cdr();
}
}
};
#endif
//
// linklist.cpp : 連結リスト
//
// Copyright (C) 2015-2023 Makoto Hiroi
//
#include "linklist.h"
// 作業用の静的メンバ関数
Cell* LinkList::nth_cell(Cell* cp, int n)
{
int i = -1;
while (cp) {
if (n == i) break;
cp = cp->cdr();
i++;
}
return cp;
}
// リストのコピー
Cell* LinkList::copy_cell(Cell* cp)
{
return !cp ? cp : new Cell(cp->car(), copy_cell(cp->cdr()));
}
// コピーコンストラクタ
LinkList::LinkList(const LinkList& ls) : top(new Cell(0, 0))
{
top->set_cdr(copy_cell(ls.top->cdr()));
}
// 代入演算子
LinkList& LinkList::operator=(const LinkList& ls)
{
if (this != &ls) {
clear();
top->set_cdr(copy_cell(ls.top->cdr()));
}
return *this;
}
// 参照
int LinkList::nth(int n)
{
Cell* cp = nth_cell(top, n);
if (cp) return cp->car();
throw std::out_of_range("LinkList::nth out of range");
}
// 挿入
void LinkList::insert(int n, int x)
{
Cell* cp = nth_cell(top, n - 1);
if (!cp) throw std::out_of_range("LinkList::insert out of range");
cp->set_cdr(new Cell(x, cp->cdr()));
}
// 更新
void LinkList::set(int n, int x)
{
Cell* cp = nth_cell(top, n);
if (!cp) throw std::out_of_range("LinkList::set out of range");
cp->set_car(x);
}
// 削除
int LinkList::remove(int n)
{
Cell* cp = nth_cell(top, n - 1);
if (!cp || !cp->cdr())
throw std::out_of_range("LinkList::remove out of range");
Cell* cp1 = cp->cdr();
int x = cp1->car();
cp->set_cdr(cp1->cdr());
delete cp1;
return x;
}
// 長さ
int LinkList::length()
{
int n = 0;
Cell* cp = top->cdr();
while (cp) {
n++;
cp = cp->cdr();
}
return n;
}
// クリア
void LinkList::clear()
{
Cell* cp = top->cdr();
while (cp) {
Cell *tmp = cp->cdr();
delete cp;
cp = tmp;
}
top->set_cdr(0);
}
// 空か？
bool LinkList::empty()
{
return !top->cdr();
}
// 出力演算子
std::ostream& operator<<(std::ostream& output, const LinkList& xs)
{
Cell *cp = xs.top->cdr();
output << "(";
while (cp) {
output << cp->car();
if (cp->cdr()) output << " ";
cp = cp->cdr();
}
output << ")";
return output;
}
//
// main.cpp : 連結リストの簡単なテスト
//
// Copyright (C) 2015-2023 Makoto Hiroi
//
#include "linklist.h"
using namespace std;
void print(int x)
{
cout << x << " ";
}
int main()
{
LinkList xs;
cout << xs << endl;
for (int i = 0; i < 8; i++) {
xs.insert(i, i);
cout << xs << endl;
}
cout << xs.length() << endl;
LinkList ys = xs; // コピーコンストラクタ
cout << ys << endl;
LinkList zs;
for (int i = 0; i < 10; i++) {
zs.insert(i, 0);
}
cout << zs << endl;
zs = ys; // 代入演算子
cout << zs << endl;
cout << xs.nth(0) << endl;
cout << xs.nth(4) << endl;
cout << xs.nth(7) << endl;
xs.set(0, 100);
xs.set(4, 200);
xs.set(7, 300);
cout << xs << endl;
cout << xs.remove(7) << endl;
cout << xs << endl;
cout << xs.remove(0) << endl;
cout << xs << endl;
cout << xs.remove(3) << endl;
cout << xs << endl;
cout << xs.empty() << endl;
xs.clear();
cout << xs << endl;
cout << xs.empty() << endl;
// イテレータ
for (auto iter = ys.begin(); iter != ys.end(); ++iter) {
cout << *iter << endl;
*iter = *iter * 2;
}
cout << ys << endl;
// ジェネレータ
auto gen = ys.make_gen();
int x;
while (gen(x)) cout << x << " ";
cout << endl;
//
ys.for_each(print);
cout << endl;
}