今回のプログラムは、K&R2 の §6.5 に基づく。 最後の getword() は §6.3 にあるものに基づく。
英語の文章を読み込むと考える。 単語が次々と到着するわけだが、 それらを、アルファベット順にならべて、 出現回数を調べるプログラムを書こう。
前もって、出てくる単語を予測し、メモリを用意することはできない。 アルファベットは 26 文字あるので、 それが 8 つ並んだものは 268 = 208,827,064,576 あり、 これは 232 = 4,294,967,296 をはるかに超えるからである。 （実際には 8 文字を超える英単語がたくさんある。）
そこで、次のように考える。
欽定訳の創世記は IN THE BEGINNING GOD CREATED THE HEAVEN AND THE EARTH で始まる。 ここまでを二分木にしたのが以下である。 順を追って説明する。
IN
／ ＼
BEGINNING THE
／ ＼
AND GOD
／ ＼
CREATED HEAVEN
＼
EARTH
最初にきた IN は一番上に置く。これを root と呼ぶ。 次にきた THE はアルファベット順で IN よりも後である。よって右の子とする。 BEGINNING は IN よりも前である。よって左の子とする。 GOD は IN の前であり、IN の子の BEGINNING よりも後である。 よって BEGINNING の右の子とする。以下は説明を省略する。
上の図で CREATED には左の子がない。そこは NULL としておく。
struct Tnode を見よ。 単語へのポインタ、出現回数に加えて、左の子へのポインタ、右の子へのポインタがある。
main() について。 root へのポインタと、 出てきた単語を一時的に収める配列 word[ } がある。 最初は root は NULL である。 関数 getword() は word に次の単語をとってくる自作関数である。 関数 addtree() は root に word を追加する自作関数である。 自作関数 treeprint() は木を画面に出力する。
自作関数 addtree() について。 NULL（何もない）のところに加える場合は、 malloc() で struct Tnode の分のメモリを要求し、 四つの要素を設定する。 自作関数 strduplicate() は引数の文字列の複写を作るものである。 そうでない場合、w と tp->word とを比較し、 一致すれば既出の単語だから tp->count を 1 だけ増す。 一致しなければ、左または右の木に w を追加する。再帰である。
自作関数 treeprint() について。 これは木を出力する。 まず左の部分木を出力し、次にその node を出力し、最後に右の部分木を出力する。 これも再帰である。
文字列を複製する自作関数 strduplicate() は読めば理解できるであろう。 malloc() が失敗のときの処理は省略してある。
自作関数 getword() の説明はプログラムのあとにつける。 関数 isalpha() は元々ある関数で、アルファベットならば 0 以外、 そうでなければ 0 を返す。 元々ある関数 ungetc() は、一文字を（ここでは）stdin に押し戻す。 （押し戻された文字は、次の getchar() で読み出されるしくみである。） break は、それを囲む最小の for, while, do-while から脱出せよ、 の意味である。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAXWORD 100 /* 単語の長さの最大 */
struct Tnode *addtree(struct Tnode *, char *);
void treeprint(struct Tnode *, int depth);
char *strduplicate(char *s);
int getword(char *, int);
struct Tnode {
char *word; /* 単語へのポインタ */
int count; /* 出現回数 */
struct Tnode *left; /* 左の子へのポインタ */
struct Tnode *right; /* 右の子へのポインタ */
};
int main() {
struct Tnode *root; /* root */
char word[MAXWORD];
root = NULL;
while (getword(word, MAXWORD) != EOF) {
root = addtree(root, word); /* word を root の下に追加 */
}
treeprint(root, 0);
}
/* 木 tp に文字列 w を加える。tp が返る */
struct Tnode *addtree(struct Tnode *tp, char *w) {
int cond;
if (tp == NULL) {
tp = malloc(sizeof(struct Tnode));
tp->word = strduplicate(w);
tp->count = 1;
tp->left = tp->right = NULL;
} else {
cond = strcmp(w, tp->word);
if (cond == 0) {
tp->count++; /* 既出の単語 */
} else if (cond < 0) {
tp->left = addtree(tp->left, w); /* 左の subtree に追加 */
} else {
tp->right = addtree(tp->right, w); /* 右の subtree に追加 */
}
}
return tp;
}
/* 木を出力 */
void treeprint(struct Tnode *p, int depth) {
int i;
if (p != NULL) {
treeprint(p->left, depth + 1); /* 左の部分木を出力 */
// for (i = 0; i < depth; i++) { /* この 3 行をコメントで */
// printf(" "); /* なくすると、木の構造が */
// } /* 見やすくなる */
printf("%4d %s\n", p->count, p->word); /* その node を出力 */
treeprint(p->right, depth + 1); /* 右の部分木を出力 */
} /* p == NULL なら何もしない */
}
/* 文字列を複製 */
char *strduplicate(char *s) {
char *p;
p = malloc(strlen(s) + 1);
if (p != NULL) {
strcpy(p, s);
}
return p;
}
/* 次に入力される単語を返す。アルファベット以外は無視 */
int getword(char *word, int lim) {
int c, i;
i = 0;
while ((c = getchar()) != EOF && isalpha(c) == 0) {
; /* アルファベット以外を飛ばす */
}
if (c == EOF) {
return EOF;
}
word[i] = c; i++;
for ( ; i < lim; i++) {
word[i] = getchar();
if (isalpha(word[i]) == 0) {
ungetc(word[i], stdin); /* 読みすぎた分を戻す */
break;
}
}
word[i] = '\0';
return word[0];
}
自作関数 getword() について。 キーボードから入力される文字列を見て、次の単語を word に入れて返す。 単語の長さの上限は lim である。 まず、アルファベット以外の文字は飛ばす。 EOF なら EOF を返す。 そうでなければその文字を word[0] に収め、 引き続きキーボードから文字をとってきて word[1] 以下に収めてゆく。 もしもアルファベット以外が入力されたら、その手前で単語は終わっているから、 その文字は ungetc() で stdin に押し戻す。
このプログラムに、長めの英文テキストを読み込ませてみよ。
上のプログラムを元に、 入力されたアルファベットからなる単語をすべて大文字にしてからアルファベット順にならべ、 出現回数を調べるプログラムを書け。
レポートの本文冒頭に、氏名を、なるべく大学に届けるある通りの文字で書け。 次に、プログラムソースファイルを、添付ファイルではなく、本文に貼りつけよ。
件名は「??? kadai5」（←全て半角文字、小文字、 ??? は自分の履修者番号、その後ろに半角スペース一つ、 kadai と 5 の間にはスペースを入れない）とせよ。