プログラミング言語 C

lang

関数 add_tree は 再帰型の関数である。
word は main関数で まず tree の top level (root) に 呈示される。
各 stage では、word は すでに ノードに 格納されている (他の) word と 比較され、関数 add_tree によって 呼び出された 再帰により 左または右の sub tree へと 振り分けられる。
結果、word は tree 内の word と 一致 - その場合には カウントが インクリメントされる - するか、null point に 出会って 新規に tree に 追加されることになる。
新しく ノードが つくられると、add_tree は (返り値として) そのノードの ポインタを返して、(上位にある) 親ノードに 連結される。

  1. struct Tnode *talloc(void);
  2. /* talloc : Tnode を作成する */
  3. char *str_dup(char *);
  4. /* str_dup : string の複製をつくる */
  5. /* add_tree : 親ノードの下に word のノードを加える */
  6. struct Tnode *add_tree(struct Tnode *p, char *w)
  7. {
  8. int cond;
  9. if (p == NULL) {
  10. p = talloc(); /* 新しくノードをつくる */
  11. p->word = str_dup(w);
  12. p->cnt = 1;
  13. p->left = p->right = NULL;
  14. /* str_cmp : 文字列の長さを比較する */
  15. } else if ((cond = str_cmp(w, p->word)) == 0)
  16. p->cnt++; /* repeated word */
  17. else if (cond < 0) /* 少ないときは left sub tree へ */
  18. p->left = add_tree(p->left, w);
  19. else /* 多いときは right sub tree に */
  20. p->right = add_tree(p->right, w);
  21. return p;
  22. }

新しいノードの 記憶領域 (storage) は talloc の ルーティンによって 確保され、tree のノードを 収容するのに 適切な free space に そのポインタを 返す。
そして 新しい word は 関数 str_dup により 退避スペースへと コピーされる (これに関しては 後述)。
(なお、上のプログラムには) カウントが 初期化され (左右の) 子ノードに null point が入る (部分がある)。 ここのコードは tree の末端 (leaves) で 新しく ノードが 追加されるときにのみ 実行される。
また - 不本意だが - str_dup と talloc の 返り値の エラーチェックについては (今回は) 省略した。(p171)