かなりの量の英文テキストがあったとしよう。 その中に出てくる異なる単語を全てあげ、アルファベット順に並べて、 出てくる回数を添えて出力せよ、という問題を考えよう。
この授業では文字や文字列の扱いに触れていないので無理であるが、 似た問題として、次が考えられる。
浮動小数点数が大量に入力される。 その中に出てくる異なる数値を全てあげ、小さい順に並べて、 出てくる回数を添えて出力せよ。 ただし、-1 が入力されたらその前で入力は終わり、と約束する。
なお、今回紹介する二分木を用いたプログラムは、 K&R2 の §6.5 にポインタを用いて書いてあるものを、 代わりに配列を用いて焼き直したものである。
二分木は、ヒープソートに出てきたヒープの一部が欠けたものである。 例を挙げる。（数値の意味については後述。）
5
／ ＼
／ ＼
3 8
／ ＼ ／ ＼
2 4 6 9
／ ＼
1 7
ただし、i 番の子が 2*i 番と 2*i+1 番、 というわけではない。
二分木は次の四つの配列と一つの int 型変数 top からなる。 添え字は 1 から N までである。
同じ添え字をもつ四つのデータが一つのノード (node) に対応する。 上の例で数が書かれている部分がノードである。 この数は value[ ] の値である。
（先週の構造体を学んだ人は、上の四つをまとめた構造体を定義し、 その配列を使ったらどうか、と思うかもしれない。 そういう書き方もできるが、配列を用いる場合、特にメリットはないようである。）
上の例は、実際には次のデータである。言い直すと、 次のデータを二分木と見ると上の例になる。 （左から順に、添え字 i, value[i], count[i], left[i], right[i} である。）
1 5.000000 1 3 2 2 8.000000 1 4 9 3 3.000000 1 6 7 4 6.000000 1 0 5 5 7.000000 1 0 0 6 2.000000 1 8 0 7 4.000000 1 0 0 8 1.000000 1 0 0 9 9.000000 1 0 0
この表にない要素、すなわち添え字が 10 以上のものは、まだ使われていない。 変数 top は添え字として使われているものの最大のもの、すなわちこの例では 9 である。
一番上にあるノードは root と呼ばれ、添え字は必ず 1 である。 left[1] が 3 なので第 1 のノードの左の子は添え字 3, right[1] が 2 なので第 1 のノードの右の子は添え字 2, というようになっている。 left[i], right[i] が 0 なのは子がないことを意味する。
二分木は、空、すなわちノード 0 個、から始まり、数値が到着するごとに成長してゆく。
i 番めのノードの左の子（resp. 右の子）およびその子孫を、 i 番めのノードの左の部分木（resp. 右の部分木）という。
規則： i 番めのノードの左の部分木（resp. 右の部分木）に属するノードの value[ ] は、 i 番めのノードの value[i] よりも真に小さく（resp. 真に大きく）なければならない。
このことから、同じ value をもつノードはただ一つしかないことがわかる。 実際、もしも二つのノードが同じ value を持っていたら、 それらの共通の先祖のうちもっとも世代を下ったノードを考えるとそこで矛盾が生じる。
空なる木もしくは空なる部分木に登録する場合、 まだ使っていない配列の番号のうち最も小さいものを選び、 データをそれの value[ ] に登録し、count を 1 とし、 left[ ] と right[ ] とは 0 とする。 そしてその番号を返す。top は 1 だけ増やす。
空でない木もしくは空でない部分木に登録する場合、 そのノードの value[ ] とデータが等しければ、 そのノードの count[ ] を 1 だけ増やす。 そのノードの value[ ] よりもデータが小さければ、左の部分木に登録する。 そのノードの value[ ] よりもデータが大きければ、右の部分木に登録する。 再帰である。
root から始めて、
という再帰的なアルゴリズムである。
次をコンパイルし、5, 8, 3, 6, 7, 2, 4. 1, 9 と入力すれば、 上の例の二分木となる。 （くわしく言えば、 5 を押して Enter, 8 を押して Enter, ..., 9 を押して Enter, -1 を押して Enter, である。）
DEBUG が 1 だと、一つのデータが着くごとに配列を全て出力し、 二分木としても出力する。また、その際、再帰の深さを行頭のスペースの数で表現する。 プログラムの開発が終わり、実際に大量のデータを処理させて実験するときは、 この DEBUG を 0 に変える。
main() の中の for ( ; (val = getnumber()) != -1; ) の継続条件について説明する。 val = getnumber() を実行し、代入された値が -1 でない限り、の意味である。
main() の終わりの return 0 について説明する。 これは、OS に 0 を返すものである。 「OS に 0 を返す」の意味は説明しないが、正常に終了したときは 0 を返すもの、と思っておくとよい。
addtree() の中の fprintf(stderr, "配列がいっぱいです.\n"); について説明する。 fprintf(stderr, "...") は printf("...") と同じく、画面に "..." を出力するが、 後述の出力リダイレクトをしてもこの出力はファイルには切り替わらず、 画面に出力される。 これを確かめるには、N を 3 などの小さな値とし、実験するとよい。
addtree() の中の exit(1); については、 プログラムが異常終了するときはこう書く、と覚えておくのがよかろう。 ここでプログラムは OS に 1 を返し、終了する。 「OS に 1 を返す」の意味は説明しないが、正常に終わらなかったときは 0 以外を返すもの、と思っておくとよい。 exit() を使うには stdlib.h の #include が必要である。
#include <stdio.h>
#include <stdlib.h> /* exit() */
#define N 100000
#define DEBUG 1 /* 開発時は 1, そうでなれけば 0 */
double value[N+1]; /* 数値 */
int count[N+1]; /* 出現回数 */
int left[N+1]; /* 左の子（の番号）*/
int right[N+1]; /* 右の子（の番号）*/
double getnumber(void);
void treeprint(int n, int depth);
int addtree(int n, double val);
void printall(void);
int top = 0; /* いま何番まで使われているか。0 だと木は空 */
int main() {
int root;
double val;
root = 0; /* 0 は、二分木が空、の意味 */
for ( ; (val = getnumber()) != -1; ) {
root = addtree(root, val); /* val を二分木に登録 */
if (DEBUG == 1) {
printf("---\n");
printall();
printf("---\n");
treeprint(root, 0);
}
}
treeprint(root, 0); /* 二分木全体を印字 */
return 0; /* 正常に終了した印 */
}
/* キーボードから double 型の数をとってきて返す */
double getnumber(void) {
double x;
scanf("%lf", &x);
return x;
}
/* 二分木を出力 */
void treeprint(int n, int depth) {
int i;
if (n == 0) { /* 空のとき、何もしない */
return;
}
treeprint(left[n], depth+1); /* 左の部分木を出力 */
if (DEBUG == 1) { /* 開発時は再帰の深さをスペースの数で表現 */
for (i = 0; i < depth; i++) {
printf(" ");
}
}
printf("%16f %d\n", value[n], count[n]); /* 自分自身を出力 */
treeprint(right[n], depth+1); /* 右の部分木を出力 */
}
/* 値 val を n 番めのノード以下の部分木に登録 */
int addtree(int n, double val) {
if (n == 0) { /* 空なる（部分）木に登録する場合 */
top++;
if (top > N) { /* 配列がいっぱいの場合 */
fprintf(stderr, "配列がいっぱいです.\n");
exit(1);
}
value[top] = val; count[top] = 1;
left[top] = right[top] = 0;
return top;
} else { /* 空でない（部分）木に登録する場合 */
if (val == value[n]) { /* 値が一致する場合 */
count[n]++;
} else if (val < value[n]) { /* 値が小さい場合 */
left[n] = addtree(left[n], val); /* 左の部分木に登録 */
} else { /* 値が大きい場合 */
right[n] = addtree(right[n], val); /* 右の部分木に登録 */
}
return n;
}
}
/* 配列をすべて出力。開発時用 */
void printall(void) {
int n;
for (n = 1; n <= top; n++) {
printf("%d %f %d %d %d\n", n, value[n], count[n], left[n], right[n]);
}
}
このプログラムを、 DEBUG を 0 に変えてコンパイルし、 できた a.exe を node.exe と改名しておこう。 こうすれば、コマンドプロンプトに node と打ち込んでこのプログラムが実行できる。
（gcc -o node.exe node.c としてコンパイルすると、 できる実行ファイルの名前は node.exe となる。この機能を使ってもよい。）
上のプログラムを試すために浮動小数点数を大量に手で入力するのは疲れる。 そこで、そのためのプログラムを書いた。
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define TIMES 500000
#define MODULO 65536
int main() {
int i, r1, r2;
{
/* この中カッコの中（乱数の種の設定）はわからなくてもよい */
unsigned seed = (unsigned)time(NULL); /* 現在時刻を取得して */
srand(seed); /* それを乱数の種に */
}
for (i = 0; i < TIMES; i++) {
r1 = rand() % 32768;
r2 = rand() % 32768;
printf("%f\n", (r2 * 32768 + r1) % MODULO * 1.0);
}
printf("%d\n", -1); /* -1 はデータの終わりの印 */
}
このプログラムをコンパイルしてできる a.exe を num.exe と改名しておこう。
注意：このプログラムの出力は 0 から 65535 までの整数である。 それらの出現回数を数えるなら、二分木を用いなくても、int a[65536]; と宣言し、 n がきたら a[n]++ とすれば済む。 単語を数える問題では、でてくる単語は予期できないので、そうはゆかない。 8 文字の単語の総数だけでも 268 = 208827064576 あり、 こんな大きな配列はとれない。
コマンドプロンプトに「num | node」と打ち込むと、 num.exe の出力が node.exe の入力となる。 これは C 言語の機能ではなく、コマンドプロンプトの仕様である。 この機能を「パイプ」と呼ぶ。
このように実行すると、node.exe に 500000 個の入力をしたことになる。 それでも、一瞬で node.exe の出力が始まる。
二分木を用いない、素朴なプログラムを二つ紹介する。 あとで述べるように実行してみると、二分木を利用したプログラムが速いことがわかるだろう。
やってきた数値を、出てきた順に、配列 value[ ] に入れてゆく。 value[i] に入れたら count[i] を 1 にする。 いま何番まで使っているかを格納しておく変数 top が必要である。 すでに出てきた数値と同じであるかどうかは、 この配列を端から順に調べてゆくしかない。 すでに value[i] として出てきていれば、新たに登録するのではなく、 count[i] を 1 だけ増す。
#include <stdio.h>
#include <stdlib.h> /* exit() */
#define N 100000
#define DEBUG 0 /* 開発時は 1, そうでなれけば 0 */
double getnumber(void);
void add(double val);
void print(void);
double value[N+1];
int count[N+1];
int top = 0; /* いま何番まで使われているか。0 だと表は空 */
int main() {
double value;
for ( ; (value = getnumber()) != -1; ) {
add(value);
if (DEBUG == 1) {
print();
}
}
/* 実際にはここでソートが必要（だが書き足す必要はない） */
print();
return 0;
}
/* キーボードから double 型の数をとってきて返す */
double getnumber(void) {
double x;
scanf("%lf", &x);
return x;
}
/* 値 val を表に登録 */
void add(double val) {
int i;
for (i = 1; i <= top; i++) {
if (value[i] == val) { /* すでにあったとき */
count[i]++;
return;
}
}
if (top < N) { /* 新しい数のとき */
top++;
value[top] = val;
count[top] = 1;
} else { /* 配列がいっぱいの場合 */
fprintf(stderr, "配列がいっぱいです.\n");
exit(1);
}
}
/* 配列をすべて出力 */
void print(void) {
int n;
for (n = 1; n <= top; n++) {
printf("%16f %d\n", value[n], count[n]);
}
}
このプログラムは、 コンパイルしてできた a.exe を array1.exe に改名しておこう。 「num | array1」と実行すると、 30 秒ほどかかってから出力が始まる。
上の「その１」のプログラムをコピーし、 void add(double val) の定義（＝本体）を次で置き換える。 また、「実際にはここでソートが必要」というコメントは不要なので削除する。 そしてコンパイルしてできた a.exe を array2.exe に改名しておこう。
void add(double val) {
int i, left, right, mid;
if (top == 0) { /* 空のとき */
value[1] = val;
count[1] = 1;
top = 1;
return;
}
left = 1; right = top; /* 二分探索が始まる */
for ( ; left <= right; ) {
mid = left + (right - left) / 2;
if (value[mid] > val) {
right = mid - 1;
} else if (value[mid] < val) {
left = mid + 1;
} else { /* 見つかったとき */
count[mid]++;
return;
}
}
if (value[mid] < val) { /* これで value[mid] が挿入位置になる */
mid++;
}
if (top == N) { /* 配列がいっぱいの場合 */
fprintf(stderr, "配列がいっぱいです.\n");
exit(1);
}
for (i = top; i >= mid; i--) { /* ずらし */
value[i+1] = value[i];
count[i+1] = count[i];
}
top++;
value[mid] = val; /* 挿入 */
count[mid] = 1;
return;
}
二分探索について。 いま、value[left] から value[right] までが小さい順に並んでいて、 その中から val を探したい。 mid を (left + right) / 2 とし、 value[mid] を val と比べる。 上のプログラムで mid = left + (right - left) / 2 となっているのは、 (left + right) / 2 だと桁あふれが生じる可能性があるからである。 value[mid] が val より大きければ right を mid - 1 として繰り返し。 value[mid] が val より小さければ left を mid + 1 として繰り返し。 一致すればそれでよい。これが二分探索である。
一致するものがなかった場合、 val を入れるべき位置以降を一つずつ後ろにずらし、 入れるべき位置に入れる。
「num | array2」と実行すると、 3 秒ほどで出力が始まる。
これは C 言語の機能ではなく、コマンドプロンプトの機能である。
num.exe は現在時刻を種として乱数を発生させる。 そのため、厳密にいえば「num | node」「num | array1」「num | array2」 を別々に実行すると入力データが異なることになる。
「num > data.txt」を実行すると、 プログラム num.exe の出力がファイル data.txt に収まる。 もしも data.txt がすでに存在すると上書きされるので注意。 これを「出力リダイレクト」と呼ぶ。
「node < data.txt」を実行すると、 プログラム node.exe の入力としてファイル data.txt の内容をキーボードから打ち込んだのと同じことになる。 これを「入力リダイレクト」と呼ぶ。
これらは組み合わせて使うことが可能である。 「node < data.txt > data0.txt」とすると、 プログラム node.exe を動かしてファイル data.txt の内容をキーボードから打ち込んだ結果をファイル data0.txt に収めることになる。
「array1 < data.txt」の出力はソートされていない。 これをソートさせるには、コマンド sort が便利である。 このコマンドは入力行をアルファベット順にソートして出力する。 「array1 < data.txt | sort > data1.txt」のようにパイプも組み合わせることができる。
「array2 < data.txt > data2.txt」も実行してみよ。
三つのファイル data0.txt, data1.txt, data2.txt ができた。 同一の内容かどうか確かめるにはコマンド fc が便利である。 fc data0.txt data1.txt のように使う。
提出されたプログラムにはすべて目を通しています。 一方、私の書いた解答例のプログラムにはある仕掛けがしてあり、 今回説明したパイプを使って動かすと、 みなさんの提出したプログラムの「乱数の種は ... です」を読み取り、 同じ乱数の種で動くようにしてあります。 そうして、みなさんのプログラムと私のプログラムとで、 比較回数・交換回数が一致するかどうかをチェックしています。