2023 年度「数学特論」 2024-01-24

これは、自習のための草稿である。次回、正式なものを配布する。

今回のプログラムは、K&R2 の §6.5 に基づく。最後の getword() は §6.3 にある。

§12.1 二分木による単語の出現度のカウント

英語の文章を読み込むと考える。単語が次々と到着するわけだが、それらを、アルファベット順にならべて、出現回数を調べるプログラムを書こう。

前もって、出てくる単語を予測し、メモリを用意することはできない。アルファベットは 26 文字あるので、それが 8 つ並んだものは 26⁸ = 208,827,064,576 あり、これは 2³² = 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 を返す。

#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);      /* 左に追加 */
    } else {
      tp->right = addtree(tp->right, w);    /* 右に追加 */
    }
	  }
  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;
  char *w;

  w = word;

  while (isspace((c = getchar())) != 0 || c != EOF && isalpha(c) == 0) {
    ;
  }
  if (c == EOF) {
    return EOF;
  }
  *w = c; w++;
  for (i = 0; i < lim; i++) {
    *w = getchar();
    if (isalpha(*w) == 0) {
      ungetc(*w, stdin);       /* 読みすぎた分を戻す */
      break;
    }
    w++;
  }
  *w = '\0';
  return word[0];
}

岩瀬順一