Dokusyo-nissi Bessitu 2005-04-06 φ(-_-) ■ [lang]プログラミング言語 C 変数 p_message が char *p_message のように宣言されると、文 p_message = "now is the time"; では p_message へ実際の文字列の (先頭の) ポインタが代入される。これは文字列のコ ピーではなくて、ポインタのみの代入となる。 関数 strcpy をつくって文字列 t を文字列 s にコピーする場合、単に s = t とするだ けでは (ラクだけど) ポインタがコピーされるだけで、文字は代入できない。文字をコ ピーするにはループが必要となる。 (配列を用いた場合) 1. void strcpy(char *s, char *t) 2. { 3. int i; 4. i = 0; 5. while ((s[i] = t[i]) != '\0') 6. i++; 7. } (ポインタを用いた場合) 1. void strcpy(char *s, char *t) 2. { 3. while ((*s = *t) != '\0') { 4. s++; 5. t++; 6. } 7. } ここでは t と s とが都合よく初期化されたポインタとなり、t の終わりにある '\0' が s にコピーされるまで、一度に一文字ずつ配列を進んでいく。 あまり使われないが * と ++, -- との組合せも可能である。例えば、 *--p は p の指す文字を取り出す前に p をデクリメントすることを表している。 以前電卓プログラムでつくった関数 push, pop では実際に下のように使われていた。 *p++ = val; /* val をスタックに積む */ val = *--p; /* スタックの一番上を val に降ろす */ (p127-130) 2005-04-09 φ(-_-) ■ [lang]プログラミング言語 C ある入力中のすべての単語を計算処理する方法を考えてみよう。 単語リストは前もってわかっているわけではないので、それをつごうよく分類しておい て二分探索することはできない。 しかしだからといって単語が来るたびに、その存在の有無を線形探索するわけにはいか ない - 時間がかかりすぎるからである (正確にいうと実行時間の期待値は入力語数の二 乗で増加していく)。 任意の単語リストを効率よく処理するためにはデータをどのように構築すればよいのだ ろうか ? 一つの解は、単語が来たときそれを順番になるよう適当な位置に入れて、単語の集合が 常時分類されている状態にしておくやり方である。 しかし線形の配列で単語をシフトしながら、これを実行する方法は、時間がかかりすぎ ていい方法とはいえない。 そこで二本木 (binary tree) と呼ばれるデータ構造を使うことにしよう。 ノードの構造は、次の四つの成分をもつ構造体として表される。 1. struct Tnode { 2. char *word; 3. int cnt; 4. struct Tnode *left; 5. strucr Tnode *right; 6. }; ノード内の再帰的宣言は不思議に思うかもしれないがまちがいではない。なぜなら、 struct Tnode *left; での left は Tnode のポインタの宣言であって構造体自身ではないからである。 この tree は単語ごとに一つのノードをもっている。 各ノードには左の子ノードへのポインタと、右の子ノードへのポインタがある (もちろ ん、単語へのポインタとあとカウンタも)。 次に来た単語がすでに tree にあるかどうかを探すには root から出発してそのノード に格納されている単語と比較する。このとき二つが一致すれば (カウントされて) そこ で止まる。 その単語が tree に格納された単語より小さければ探索は左の子ノードに対して続けら れ、反対に大きければ右の子ノードが調べられる。 求める方向に子ノードがなければその単語は tree に含まれていないことになり、その 場所が新しい単語のおさまる位置となる。(P168-170) 2005-04-10 φ(-_-) ■ [lang]プログラミング言語 C (これからつくろうとする) 目的のプログラムの全体の量は、いくつかのサポートルーテ ィンを与えることで、非常にコンパクトにできる。 主ルーティンでは単に、関数 get_word により単語を読み込んで、add_tree のルーティ ンでそれを tree に埋め込めばよい。 1. #include 2. #define MAX 100 3. main() 4. { 5. struct Tnode *root; 6. char word[MAX]; 7. root = NULL; 8. while (get_word(word, MAX) != EOF) 9. if (isalpha(word[0]) /* word の先頭が英字であれば */ 10. root = add_tree(root, word); 11. tree_print(root); 12. return 0; 13. } 関数 get_word では入力から word を取り込む。 ここでの word は英字あるいは数字の文字列、または空白ではない 1文字のいずれかを 指す。 この関数の返り値は word の最初の文字 - 配列の 0 - あるいはファイルの最後であれ ば EOF、アルファベット以外 (の文字) であればその文字自体を返す。 get_word は関数 get_ch と unget_ch のルーティンを利用するので、英数字のトークン の読み込みが終了した時点では 1文字分余計に読んでいる。そのため unget_ch を呼び 出して、次の入力呼び出しに備えてその文字を push back しておく。 関数 isspace を使ってスペースをスキップして (次に) 英字の区別を isalpha で行い (最後に) isalnum によって英字と数字との区別を行っている。 1. #include 2. /* get_word : 入力から次の word または文字を求める */ 3. int get_word(char *word, int limit) 4. { 5. int c; 6. int get_ch(void); 7. void unget_ch(int); 8. char *pw = word; 9. while (isspace(c = get_ch())) 10. ; 11. if (c != EOF) 12. *pw++ = c; 13. if (!isalpha(c)) { 14. *pw = '\0'; /* 文字列の終わり */ 15. return c; 16. } 17. for ( ; --limit > 0; pw++) 18. if (!isalnum(*pw = get_ch())) { 19. unget_ch(*pw); 20. break; 21. } 22. *pw = '\0'; 23. return word[0]; 24. } (p165-171) (訂正) スペルミスとカッコを閉じるのをまた忘れてた ... 2005-04-11 φ(-_-) ■ [lang]プログラミング言語 C 関数 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) 2005-04-12 φ(-_-) ■ [lang]プログラミング言語 C 関数 str_cmp は文字列 s と t とを比較して、s が t より - 辞書での編集順のように - 小さいか等しいかまたは大きいかによって、それぞれ負、0、正の値を返す。 返り値 (value) は、s と t が最初に一致しなくなるポジションでの文字の引算によっ て得られる。 1. /* str_cmp : s < t ならば負の数、s == t なら 0、s > t なら正の整数を返す */ 2. int str_cmp(char *s, char *t) 3. { 4. int i; 5. for (i = 0; s[i] == t[i]; i++) 6. if (s[i] == '\0') 7. return 0; 8. return s[i] - t[i]; 9. } 関数 str_cmp のポインタ版は次の通り。 1. int str_cmp(char *s, char *t) 2. { 3. for ( ; *s == *t; s++, t++) 4. if (*s == '\0') 5. return 0; 6. return *s - *t; 7. } (p129-130) 2005-04-15 φ(-_-) ■ [lang]プログラミング言語 C (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. /* str_cpy : copy t to s */ 84. void str_cpy(char *s, char *t) 85. { 86. int i; 87. i = 0; 88. while ((*s = *t) != '\0') { 89. s++; 90. t++; 91. } 92. } 93. /* tree_print : in-order print of tree p */ 94. void tree_print(struct Tnode *p) 95. { 96. if (p != NULL) { 97. tree_print(p->left); 98. printf("%4d %s\n", p->cnt, p->word); 99. tree_print(p->right); 100. } 101. } 102. /* get_word : get next word or character from input */ 103. int get_word(char *word, int limit) 104. { 105. int c; 106. char *pw = word; 107. while (isspace(c = get_ch())) 108. ; 109. if (c != EOF) 110. *pw++ = c; 111. if (!isalpha(c)) { 112. *pw = '\0'; 113. return c; 114. } 115. for ( ; --limit > 0; pw++) 116. if (!isalnum(*pw = get_ch())) { 117. unget_ch(*pw); 118. break; 119. } 120. *pw = '\0'; 121. return word[0]; 122. } 123. /* get_ch : get a (possibly pushed-back) character */ 124. int get_ch(void) 125. { 126. return (buf_p > 0) ? buf[--buf_p] : getchar(); 127. } 128. /* unget_ch : push character back on input */ 129. void unget_ch(int c) 130. { 131. if (buf_p > BUFSIZE) 132. printf("unget_ch : too many characters\n"); 133. else 134. buf[buf_p++] = c; 135. } コンパイルしてみる。 $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 がそれぞ れ入ってるので、それらを使えば上のコードをもっと短くすることができます。