プログラミング言語 C

lang

(tree node の 領域を 確保する) 関数 talloc は 次のように 書くことができる。

  1. #include /* 関数 malloc に 必要 */
  2. struct Tnode *talloc(void)
  3. {
  4. return (struct Tnode *)malloc(sizeof(struct Tnode));
  5. }

malloc は void型の ポインタを 返すので、そのポインタを キャストによって 望む形へと 明示的に 変換しておくようにする。
関数 str_dup は 引数によって 与えられた 文字列を、malloc を 呼び出すことによって 確保した 安全な場所に copy する。

  1. char *str_dup(char *s)
  2. {
  3. char *p;
  4. p = (char *)malloc(str_len(s) + 1); /* '\0' 分を 1文字 加えておく */
  5. if (p != NULL)
  6. str_cpy(p, s);
  7. return p;
  8. }

関数 tree_print は tree を 辞書順に print していく。
それぞれのノードでは、まず 左の subtree (より小さい側) が print され、次に (そのノードの) word が、最後に 右の subtree (より大きい側) が print される。
もし 再帰 (recusion works) の 理解が 不十分だと 思うなら、上の例で 示された tree を 関数 tree_print を 使って シュミレートしてみるとよい。

  1. /* tree_print : tree 辞書順に print する */
  2. void tree_print(struct Tnode *p)
  3. {
  4. if (p != NULL) {
  5. tree_print(p->left);
  6. printf("%4d %s\n", p->cnt, p->word);
  7. tree_print(p->right);
  8. }
  9. }

(p171-173)


(完成したプログラム)

  1. /* cnt_wd.c */
  2. #include
  3. #include
  4. #include
  5. #define MAX 100
  6. #define BUFSIZE 100
  7. struct Tnode { /* the tree node */
  8. char *word; /* points to the text */
  9. int cnt; /* member of occurrence */
  10. struct Tnode *left; /* left child */
  11. struct Tnode *right; /* right child */
  12. };
  13. struct Tnode *add_tree(struct Tnode *, char *);
  14. struct Tnode *talloc(void);
  15. char *str_dup(char *);
  16. int str_cmp(char *, char *);
  17. int str_len(char *);
  18. void str_cpy(char *, char *);
  19. void tree_print(struct Tnode *);
  20. int get_word(char *, int);
  21. int get_ch(void);
  22. void unget_ch(int);
  23. char buf[BUFSIZE]; /* buffer for unget_ch */
  24. int buf_p = 0; /* next free position in buf */
  25. /* word frequency count */
  26. main()
  27. {
  28. struct Tnode *root;
  29. char word[MAX];
  30. root = NULL;
  31. while (get_word(word, MAX) != EOF)
  32. if (isalpha(word[0]))
  33. root = add_tree(root, word);
  34. tree_print(root);
  35. return 0;
  36. }
  37. /*add_tree : add a node with w, at or below p */
  38. struct Tnode *add_tree(struct Tnode *p, char *w)
  39. {
  40. int cond;
  41. if (p == NULL) { /* a new word has arrived */
  42. p = talloc(); /* make a new node */
  43. p->word = str_dup(w);
  44. p->cnt = 1;
  45. p->left = p->right = NULL;
  46. } else if ((cond = str_cmp(w, p->word)) == 0)
  47. p->cnt++; /* repeated word */
  48. else if (cond < 0) /* less than into left subtree */
  49. p->left = add_tree(p->left, w);
  50. else /* greater than into right subtree */
  51. p->right = add_tree(p->right, w);
  52. return p;
  53. }
  54. /* talloc : make a tree node */
  55. struct Tnode *talloc(void)
  56. {
  57. return (struct Tnode *)malloc(sizeof(struct Tnode));
  58. }
  59. /*str_dup : make a duplicate of s */
  60. char *str_dup(char *s)
  61. {
  62. char *p;
  63. p = (char *)malloc(str_len(s) + 1); /* +1 for '\0' */
  64. if (p != NULL)
  65. str_cpy(p, s);
  66. return p;
  67. }
  68. /* str_cmp : return '< 0' if s < t, '0' if s == t, '> 0' if s > t */
  69. int str_cmp(char *s, char *t)
  70. {
  71. for ( ; *s == *t; s++, t++)
  72. if (*s == '\0')
  73. return 0;
  74. return *s - *t;
  75. }
  76. /* str_len : return length of string s */
  77. int str_len(char *s)
  78. {
  79. char *p = s;
  80. while (*p != '\0')
  81. p++;
  82. return p - s;
  83. }
  84. /* str_cpy : copy t to s */
  85. void str_cpy(char *s, char *t)
  86. {
  87. int i;
  88. i = 0;
  89. while ((*s = *t) != '\0') {
  90. s++;
  91. t++;
  92. }
  93. }
  94. /* tree_print : in-order print of tree p */
  95. void tree_print(struct Tnode *p)
  96. {
  97. if (p != NULL) {
  98. tree_print(p->left);
  99. printf("%4d %s\n", p->cnt, p->word);
  100. tree_print(p->right);
  101. }
  102. }
  103. /* get_word : get next word or character from input */
  104. int get_word(char *word, int limit)
  105. {
  106. int c;
  107. char *pw = word;
  108. while (isspace(c = get_ch()))
  109. ;
  110. if (c != EOF)
  111. *pw++ = c;
  112. if (!isalpha(c)) {
  113. *pw = '\0';
  114. return c;
  115. }
  116. for ( ; --limit > 0; pw++)
  117. if (!isalnum(*pw = get_ch())) {
  118. unget_ch(*pw);
  119. break;
  120. }
  121. *pw = '\0';
  122. return word[0];
  123. }
  124. /* get_ch : get a (possibly pushed-back) character */
  125. int get_ch(void)
  126. {
  127. return (buf_p > 0) ? buf[--buf_p] : getchar();
  128. }
  129. /* unget_ch : push character back on input */
  130. void unget_ch(int c)
  131. {
  132. if (buf_p > BUFSIZE)
  133. printf("unget_ch : too many characters\n");
  134. else
  135. buf[buf_p++] = c;
  136. }

コンパイルしてみる。
$cc -o cnt_wd cnt_wd.c
次に 文字列テキストを 用意。(例えば こんなの -> song.txt)

Where have all the flowers gone?
Long time passing
Where have all the flowers gone?
Long time ago
Where have all the flowers gone?
Girls have pick them every one
When will they ever learn?
When will they ever learn?

$./cnt_wd < song.txt として 確認。


(注) ヘッダファイル string.h には 標準関数として strcmp, strlen, strcpy が それぞれ 入ってるので、それらを 使えば 上のコードを もっと 短くすることが できます。
(追記) カッコと セミコロンが 一部 抜けていたので 訂正。
(さらに追記)ヘッダファイル名が まちがっていたので 訂正 (<- 以前のままでも なぜか 正常に 実行できますが ... )