Dokusyo-nissi Bessitu 2005-12-28 φ(-_-) ■[lang]はじめての C C programming note*1 たとえば、「入力テキストの中で "the" という文字列が含まれている行だけを選ん で出力する (そうでない行は出力しない) という処理は、いろんな場面でありそう な処理だ。 入力がテキストであるときに、それを 1文字ずつ処理して言ったほうが都合のよい 場面ももちろん多い。だが ... このテーマに関するようなプログラムでは「行単位 」での入出力をするほうがずっと効率がよい。(p158) UNIX のコマンド grep ですね。たしか grep は "global regular expression and print" の略だったと思うけど ...。 プログラム全体の骨組みは cat3r.c を使うことにして、 また、ここでは問題を簡単にするために、「1行は 80 Byte 以下でなければならな い」という制限をつけてある。 まず、各行中にキーワード (この例だと "the") が含まれていれば標準出力する関数を つくっていきます、 #include #define KEYWORD "the" #define MAX_SIZE (80 + 1 + 1) /* plus '\n' + '\0') */ void find(FILE *fp) { char buf[MAX_SIZE]; while (fgets(buf, MAX_SIZE, fp) != NULL) { if (strstr(buf, KEYWORD)) fputs(buf, stdout); } } fgets() で 1行ごとに標準入力から読み、(if の条件文でキーワードを探してから) fputs() で行単位で標準出力に書いている。 この関数ではじめて使われた標準ライブラリ関数の strstr() ですが、 この関数を使うときには、string.h をインクルードしなければならない。string.h の中には、 char *strstr(const char *cs, const char *ct); というようなプロトタイプ宣言が含まれているはずだ。この const という C のキ ーワードについてはここでは説明しないので、 char *strstr(char *cs, char *ct); とでも書いてあると考えてよい。 strstr() 関数は、文字列 cs の中から文字列 ct を探し、見つかれば最初に現れる 位置へのポインタを、見つからないときには NULL を返す。 ということは、1つめの引数に 1行分のデータを、2つめの引数に探そうとしている 単語を指定して strstr() 関数を呼び出せば、その単語が含まれている行かどうか を検査できる。(p160-161) このままでもプログラムは組み立てられますが、少し改良を加えていきます。まずキー ワードは #define で変更可能ですが、このままだと、 変更のたびにいちいちプログラムを修正してコンパイルしなおさないと、新しい検 索対象に対応した実行用ファイルを作れないのだ。 つまり、 このようなときには、1つのプログラムで「実行時に指定した任意の文字列を探せる 」ようにするべきなのだ。(p162) そのためには、以前つくったように、main() 関数の中にパラメータを指定するためのコ ードを追加する必要があります。 始めは、オプションを使わずキーワードが 1つだけの場合、 検索語 (探すべき文字列) の指定は (コマンドラインの) 第1パラメータで行なうこ とにする。 つまり、実行時にそこに指定した文字列を探せるようにするのだ。 第2パラメータ以降が入力ファイル名で、その順に処理する。 またパラメータが 1つしかないとき (ファイル名の指定が 1つもないとき) には、 標準入力を処理する。 パラメータが 1つもないときには使用法のヒントを標準エラー出力に表示して終了 することにしよう。(p163) こんなふうな指定のやりかたです、 $ ./find1 keyword file または、 $ ./find1 keyword < file 続けてファイルを読み込むには、 $ ./find1 keyword file1 file2 file3 *1：「作ってわかる Cプログラミング」 2005-12-31 φ(-_-) ■[lang]はじめての C C programming note*1 keyword をコマンドライン上で指定するため、 main() 関数は次のようになります。 main(int argc, char **argv) { char *keyword; FILE *fp; --argc; ++argv; if (argc < 1) usage(); /* no return */ --argc; keyword = *argv++; if (argc == 0) find(stdin, keyword); else { while (argc--) { if ((fp = fopen(*argv, "r")) == NULL) cant(*argv); /* no return */ find(fp, keyword); fclose(fp); argv++; } } return 0; } ここで 1つ、新しいテクニックがでてきます。 main() 関数の以下の部分で、コマンドラインの第1パラメータを変数 keyword (探 すべき文字列) に入れている。 ところです。下のコードの最後の行、 if (argc < 1) usage(); /* no return */ --argc; keyword = *argv++; argv の前ではなく、後ろに "++" がついていることに注意しよう。そのときに argv が指しているパラメータ (1つめ) へのポインタを変数 keyword に代入し終わ ってから、argv がインクリメントされるようになっている。(p165) 全体のプログラムは次のとおり、 /* find1.c */ #include #include #include #define MAX_SIZE (80 + 1 + 1) /* plus '\n' + '\0' */ void find(); void usage(); void cant(); main(int argc, char **argv) { char *keyword; FILE *fp; --argc; ++argv; if (argc < 1) usage(); /* no return */ --argc; keyword = *argv++; if (argc == 0) find(stdin, keyword); else { while (argc--) { if ((fp = fopen(*argv, "r")) == NULL) cant(*argv); /* no return */ fprintf(stdout, "[ %s ]\n", argv[0]); find(fp, keyword); fclose(fp); argv++; } } return 0; } void find(FILE *fp, char *word) { char buf[MAX_SIZE]; while (fgets(buf, MAX_SIZE, fp) != NULL) { if (strstr(buf, word)) fputs(buf, stdout); } } void usage(void) { fprintf(stderr, "Usage: ./file1 keyword [file ... ]\n"); exit(1); } void cant(char *name) { fprintf(stderr, "can't open %s\n", name); exit(1); } このプログラムでは grep と同様、keyword は 1つしか指定できません。そこで次は、 オプションを導入して多くの keyword を同時に指定できるよう、変更を加えていきます 。 ■[diary]useless tips 上の find1 プログラムは実際に役にたつのか、UNIX の time コマンドを使って調べて みた。 検索用のファイルを用意、全部で 5100行ほどある。 http://www4.kcn.ne.jp/~yoitiro/unix_study/book_stk.txt 測定してみると、 $ time ./find1 三浦アンナ book_stk.txt [ book_stk.txt ] 190 イエスの幼年時代 三浦アンナ 新教出版社(427p) 58 real 0m0.009s user 0m0.000s sys 0m0.010s 比較するため、grep でも測定、 $ time grep 三浦アンナ book_stk.txt 190 イエスの幼年時代 三浦アンナ 新教出版社(427p) 58 real 0m0.045s user 0m0.040s sys 0m0.000s これは速い ! 試しに match する行数が多い文字列を検索すると、その差は 10倍以上に もなる (機能の少ない分だけ find1 のほうが速い)。 正規表現や grep のオプションを使わない簡単な検索なら、十分使えますネ。 (ぼくのパソコンの性能は cpu が 1.20GHz, メモリは 256MB です - 参考までに) *1：「作ってわかる Cプログラミング」 2006-01-02 φ(-_-) ■[lang]はじめての C C programming note*1 プログラムの扱う内容が少し複雑になってきたときは、 内部のしかけを考える前に、まず外部の仕様を考えよう。プログラムとその外側と のやりとりのことだ。 この場合の外部 (外側) とは「人間がそのプログラムをどう操作しどんな形式で入 力を与え、そしてどんな出力を得るか」ということだ。 そこで以下のような外部仕様 (インターフェイス仕様) を考える。 1. find1.c を改良し、複数の文字列を探せるようにする。 2. 検索文字列リストは、別のテキストファイル (をつくり、そこ) に 1行あたり 1 つの文字列として格納されているものとする。 3. 検索文字列リストのファイル名は -f filename のオプションでコマンドライン で指定できるようにする。 4. その場合の入力元の指定は find1.c と同様とする。 5. -f オプションの指定がなかった場合は、find1.c と同様の処理をするものとす る (入力元の指定についても)。 6. 検索文字列リストのファイルに指定できる検索語は最大 256個以内とする (それ と、検索語のサイズもきめておく)。 7. ある 1つの行が複数文字列にマッチしても、1度しか出力しない (ようにする)。 (p168-169) 1 は当初の目的、3 から 7 までがいわゆるユーザインターフェイスとよばれるものです 。 つまり find1 と同じく $ ./find2 keyword file1 file2 と実行しても、あるいは $ ./find2 -f search_list file1 file2 のようにリストで指定しても、どちらも検索が可能だということです。 まず最初に、関数 find() を「複数の文字列との照合」ができるよう変更を加えます。 void find(FILE *fp, char *word[], int n) { char buf[MAX_SIZE]; int i; while (fgets(buf, MAX_SIZE, fp) != NULL) { for (i = 0; i < n; i++) { if (strstr(buf, word[i])) { fputs(buf, stdout); break; } } } } 仮引数のところで、変数 word が文字列へのポインタから配列へのポインタに変更され 、また検索文字列の数 n が追加されています。 n は比較すべき文字列の個数だ。 文字列を 1つだけ指定するやりかた (find1 と同じ形) で起動したときには、この n の値は 1 になっている。 検索文字列用のファイルの中に 3つの文字列が格納されていたのならば、n は 3 だ 。 for文によるくり返しを使って文字列の個数分だけ比較を行なっている。 検索文字列はこの word という名前の配列に入っていて、word[0] には 1つめの検 索文字列、word[1] には 2つめの検索文字列 ... のように文字列が格納されている ので、この if文で比較ができるわけだ。(p174) find() 関数に渡される各引数がどのように準備されるのかはちょっと置いといて、次は ユーザインターフェイスの 7つめにあったしくみについて、 fputs() したあとの break に着目してほしい。 この break はループからの脱出のためのものだ。 break文を実行すると、for や while などのくり返しループを脱出し、ループの後ろの部分へ分岐する。 (関数 find() の) この部分では、while ループの中に for ループが入っていると いう二重のループが構成されている。 break文は 1つのループしか脱出しないので、この場合は内側の for ループから脱 出して for の終わったところに分岐するわけだ。 この break にて、配列 word に入っている文字列のうちいずれか 1つにマッチした ならば、すぐにその行を出力して、次の行の照合に制御を移動させている。 すなわち、「同じ行に探している文字列が 2つ以上存在しても、出力は 1回だけ」 を実現している (ことになる)。(p174-175) *1：「作ってわかる Cプログラミング」 2006-01-03 φ(-_-) ■[lang]はじめての C C programming note*1 検索文字列用のファイルをつくって、そこに keyword を収めるまではわかったけど、そ こから keyword を取り出すのはどうするのかというと、 まず外部変数として下の 2つを宣言しておきます。 #define MAX_KEY_COUNT 256 /* 検索語の最大数 */ char *keyword[MAX_KEY_COUNT]; key_n; key_n が検索文字列の個数だというのはわかるだろう。これは簡単だ。 問題は keyword という配列が「char型を指すポインタ」としてしか宣言されていな いことだ。ポインタだというは、実はこの配列はアドレスが入っているだけの配列 だということになる。 文字列の実体はそのアドレスが指し示す別の場所に存在しているのだ。さて、その 場所というのはどこにあるのだろう ? (p177) それは、次の readkey() 関数の中で (こっそりと) 格納されています。 #define MAX_KEY_SIZE (40 + 1 + 1) /* 検索文字列の Byte数 */ int readkey(char **key, FILE *fp) { char buf[MAX_KEY_SIZE]; int n; n = 0; while (fgets(buf, MAX_KEY_SIZE, fp) != NULL) { buf[strlen(buf) - 1] = '\0'; key[n++] = strdup(buf); } return n; } readkey() 関数の仮引数は、後ろから「検索文字列の格納されたファイル」、それに問 題のまだ中身のない宣言されただけのポインタ配列 keyword です (**key はだから * key[] のことです)。 つまり、文字列の格納されたファイルを開いて、この空の配列 keyword に n個分の文字 列を (コピーし) 格納していくわけです。詳しくいうと、 (ファイルを読み込んだ後) ナル文字 '\0' を代入しているところは、たいしたこと はしていない。 fgets() が行末の改行文字も読んでしまうことを知っていれば、何 のためにそうしているかわかるだろう。 各文字列から改行文字 '\n' を取り除いてるのですね。 重要なのはその次の行だ。 key という配列の要素に strdup() という関数からの戻 り値が次々に代入されている。 この関数が文字列の実体が入っているアドレスを返してくれるので、それを配列の 要素に代入するだけで、最終的には (char型のデータが) 配列 keyword にセットさ れることになる。(p177) ここのところです、 key[n++] = strdup(buf); 空の箱 (ポインタ配列) だけ用意しておいて、後で中身 (正確にはそのアドレス) を詰 めていくのです。 strdup() 関数の働きを詳しく述べる前に、重要なことがある。実は strdup() 関数 は標準ライブラリ関数にはない。多くの処理系で採用されているが、どの場合もあ るとは限らない。(p177) でも、たいていの場合 string.h にインクルードされています。 $ man strdup として調べてみると、次のように書いてあります、 名前 strdup - 文字列を複製する 書式 #include char *strdup(const char *s); 説明 strdup() 関数は、文字列 s の複製である 新しい文字列への ポインタを返す。 新しい文字列のためのメモリは malloc で 得ている。そして free() で開放すること ができる。 返り値 strdup() 関数は 複製された文字列への ポインタ、または 十分なメモリが確保でき なかった場合には NULL を返す。 つまり、関数内部で malloc() を使うことで、動的なメモリ割当が実行されているので す。 変数や配列で静的 static にメモリ領域を確保するのに対して、malloc() で実行時 に領域を確保することを動的なメモリ割当 Dynamic Memory Allocation と呼ぶ。 あらかじめどれだけのメモリを確保しておいたらよいかわからない場合などにべん りなしくみだ。 少なめに準備しておいて足りなくなるのも困るが、めったにないような「極端に多 く使う」状況を想定してムダに多くのメモリを使うのも避けたい ... などという場 合に使う。(p178) また、普通は「malloc() で動的に確保したメモリ領域は、使い終わったら free() 関数 を用いることで、そのメモリ領域を開放」しますから、そのための関数も用意しておき ます。 void freekey(int n, char **key) { int i; for (i = 0; i < n; i++) free(key[i]); } 最後に、find1 と同じ使い方もできるようにするために、もう少しだけコードを改良し ていきます。それには、もう一度 strdup() 関数を使うことになりますが。 *1：「作ってわかる Cプログラミング」 2006-01-06 φ(-_-) ■[lang]はじめての C C programming note*1 はじめに、オプションが指定されたときの解析用コードをつくっていきます。 ここでは、-f オプションに続くコマンドライン上のファイルを開き、keyword を読み込 んでいます。 char *s; key_n = -1; while (--argc > 0 && **++argv == '-') { for (s = *argv + 1; *s != '\0'; s++) { switch (*s) { case 'f': if (--argc > 0) { if ((fp = fopen(*++argv, "r")) == NULL) cant(*argv); /* no return */ else { key_n = readkey(keyword, fp); fclose(fp); } } break; default: freekey(key_n, keyword); usage(); /* no return */ } } } 以前つくったものより行数が増えていますが、そのほとんどはファイルの開閉に関した 部分です。 readkey() はファイルに含まれる keyword の数を返すので、その戻り値を key_n に代 入しておきます。 また、default で関数 freekey() が使われているのは、usage() を実行するとプログラ ムは終了してしまうので、その前に readkey() で取得したメモリを解放するためです。 次は、オプションがついていないとき、 if (key_n == -1) { if (argc < 0) usage(); /* no return */ --argc; keyword[0] = strdup(*argv++); key_n = 1; } 関数 strdup() を使ってコマンドライン上の文字列 (キーワード) をポインタ配列 keyword の 1つめに記憶させ、key_n に '1' を代入しています。 ここまでくれば、コマンドライン上に残っているのは (普通は) 検索対象となるファイ ル名だけですから、それほどむずかしくはありません。 関数が find() に変わることと、あとは、strdup() に malloc が使われているので、 freekey() を使用してメモリを解放しておくことだけです。 if (argc == 0) find(stdin, keyword, key_n); else { while (argc--) { if ((fp = fopen(*argv, "r")) == NULL) cant(*argv); /* no return */ find(fp, keyword, key_n); fclose(fp); argv++; } } freekey(key_n, keyword); これで後は、プログラムを組み立てるだけです。 その前に、課題にある機能をつけ加えるにはどうすればよいか ? もう少しだけ考えてみ ることにしましょう。 まず、追加する機能 1個に対し 1つの flag をプログラムの始めにおきます。 #define YES 1 #define NO 0 int x_flag = NO; switch文に追加するオプション名を足し、その機能を使うときには flag の値を真に変 えるようにします。 switch (*s) { case 'x': x_flag = YES; break; } そして、関数 find() に、if文を使って、flag が真ならその機能を実行するコードを追 加します。 if (x_flag == YES) do_something(); 追加するオプションは、次の 2つです。 1. 指定された文字列が「見つからなかった」行だけを出力する。 2. 指定された文字列が「見つかった」行の番号 (そのファイルの中の何行めか) を 、行そのものの前に出力できる (ようにする)。(p179) < *1：作ってわかる Cプログラミング」 2006-01-08 φ(-_-) ■[lang]はじめての C C programming note*1 1つめの課題が思っていたよりむずかしいので、行の始めに番号をつけるオプションだけ を追加して、プログラムをつくってみました*2。 その前に keyword.txt を作成、 $ vi keyword.txt として、予約語をいくつか記入、 while if for こんなかんじで、コマンドライン上に指定します、 $ ./find2r -n -f keyword.txt find2r.c できあがったプログラムはこちら、 /* find2r.c */ #include #include #include #define MAX_SIZE (80 + 1 + 1) /* plus '\n' + '\0' */ #define MAX_KEY_SIZE (40 + 1 + 1) /* plus '\n + '\0' */ #define MAX_KEY_COUNT 256 #define YES 1 #define NO 0 void find(); int readkey(); void freekey(); void usage(); void cant(); char *keyword[MAX_KEY_COUNT]; int key_n; int n_flag = NO; main(int argc, char **argv) { FILE *fp; char *s; key_n = -1; while (--argc > 0 && **++argv == '-') { for (s = *argv + 1; *s != '\0'; s++) { switch (*s) { case 'n': n_flag = YES; break; case 'f': if (--argc > 0) { if ((fp = fopen(*++argv, "r")) == NULL) cant(*argv); /* no return */ else { key_n = readkey(keyword, fp); fclose(fp); } } break; default: freekey(key_n, keyword); usage(); /* no return */ } } } if (key_n == -1) { if (argc <= 0) usage(); /* no return */ --argc; keyword[0] = strdup(*argv++); key_n = 1; } if (argc == 0) find(stdin, keyword, key_n); else { while (argc--) { if ((fp = fopen(*argv, "r")) == NULL) cant(*argv); /* no return */ find(fp, keyword, key_n); fclose(fp); argv++; } } freekey(key_n, keyword); return 0; } void find(FILE *fp, char *word[], int n) { char buf[MAX_SIZE]; int i; int cnt; cnt = 1; while (fgets(buf, MAX_SIZE, fp) != NULL) { cnt++; for (i = 0; i < n; i++) { if (strstr(buf, word[i])) { if (n_flag == YES) fprintf(stdout, "%04d: ", cnt); fputs(buf, stdout); break; } } } } int readkey(char **key, FILE *fp) { char buf[MAX_KEY_SIZE]; int n; n = 0; while (fgets(buf, MAX_KEY_SIZE, fp) != NULL) { buf[strlen(buf) - 1] = '\0'; key[n++] = strdup(buf); } return n; } void freekey(int n, char **key) { int i; for (i = 0; i < n; i++) free(key[i]); } void usage(void) { fprintf(stderr, "Usage: ./find2r keyword [file ... ]\n"); fprintf(stderr, " ./find2r -f keyfile [file ... ]\n"); fprintf(stderr, " ./find2r -n (display line number)\n"); exit(1); } void cant(char *name) { fprintf(stderr, "can't open %s\n", name); exit(1); } ■[diary]useless tips find1 は (あたりまえだが) 記号類も検索できる。バックスラッシュ + 記号名で指定す れば O.K. $ ./find1 \# find1.c *1：「作ってわかる Cプログラミング」 *2：あとは宿題ということで ... 2006-01-09 φ(-_-) ■[lang]はじめての C C programming note*1 プログラムは、必ず何らかのデータを扱う。重要なのは、処理の流れだけではない 。 その処理で扱うデータがどういう形式で保持されるかということ、つまり処理のし かたに合った内部のデータ構造 data structure を考えることも重要なのだ。 (p184) という理由で、「基本的なデータ構造」のうち、マトリックス、スタック、キューとそ れにヒープについて取り上げていきます。 はじめの 3つはむずかしくありません。 まずマトリックスから、 マトリックス matrix とは 2次元以上の配列のことである。 C では、「2次元以上の配列」を表わす手段は直接は準備されていない。そのため、 2次元の配列はいわば「配列を要素とした配列」で表現する。 例えば int型の 2次元配列だと、 int a[4][5]; これは「a[5] という 1次元の配列」という要素を 4つもつ配列として表現している わけだ。(p167) 説明は以上ですべてです。 実際にどのように使われるかは、K&R 2nd の p136 - p137 に載っています。 http://d.hatena.ne.jp/sekiyo/20051105 次はスタック、 スタック stack は、最後に追加したデータが最初に取り出されるデータ構造だ (Last-In-First-Out)。 (すなわち) スタックは、先に入れたデータを後回しにし、最も最近に入れたデータ から新しい順に取り出す場合に使う。(p188) スタックの説明もわずかこれだけです。 スタックには push と pop という 2つの基本的な操作があり、そこでは配列が用いられ ています。 int x[MAX]; int sp = 0; /* stack pointer*2 */ void push(int n) { if (sp < MAX) x[sp++] = n; else fputs("stack full\n", stdout); /* overflow */ } int pop(void) { if (sp > 0) return x[--sp]; else { fputs("stack empty\n", stdout); /* underflow */ return 0; } } データを引数にして push 関数を呼び出すことにより、データがスタック (←配列) に格納される。また、pop 関数を呼び出すことにより、戻り値としてスタックから データを取り出すことができる。(p189) スタックを使った特殊な例として、 たとえば、プログラム言語の内部などでも、関数の呼び出し時の引数などは一時的 にスタックに置かれる場合が多い。 (また) 関数の中でさらに関数を呼び出しても 、その新しい呼び出しの引数が一時スタックに保存される。 呼び出した関数から戻るときには一時的に保存された引数がスタックから取り出さ れるので、効率よく参照できるわけだ。(p188) *1：「作ってわかる Cプログラミング」 *2：←配列の添字 2006-01-12 φ(-_-) ■[lang]はじめての C C programming note*1 キュー queue は、先に入れたデータが先に取り出されるデータ構造 (First-In-First-Out) だ。 後から入ったデータはいちばん後ろに追加される。 データが入れられた順に処理されるのを待つため「待ち行列」ともいう。(p189) キューの実現は、モジュロ演算子を使って、見かけ上のリングバッファをつくることで 可能になります。 % は剰余演算子 modulus operator、つまり割算の「余り」を求める演算子である。 たとえば "10 % 7" は 3 だ。 (ただし) 割られる数も割る数も整数型でなければな らない。(p191) キューでモジュロ演算子を使ってデータを入力する関数は、次のようなものです。 int r_buf[MAX]; int sp = 0; int cnt = 0; void buf_in(int c) { if (cnt == MAX) return; r_buf[(sp + cnt) % MAX] = c; ++cnt; } モジュロ演算子を使った割られるほうの数は配列の添字に count数を加えたもの、割る ほうの数は添字の最大値です。ここのところ、 r_buf[(sp + cnt) % MAX] = c; sp はこのプログラムでは変化しませんから、その値は (一応) 0 です。プログラムを使 って配列に値を入れていくと、cnt の数は増えていきますが、最大でもその値は "MAX -1" になります。 値を入力するだけなら、モジュロ演算子の左辺はつねに右辺の値より小さくなります。 このとき、モジュロ演算子がどんなふるまいをするのか、実際に試してみましょう。 /* modulus_1.c */ #include main() { int a; int b; a = 7; b = 10; printf("%d\n", a % b); b = 20; printf("%d\n", a % b); return 0; } 結果は、 7 7 となるはずです。つまり、"a < b" の場合には剰余計算の結果は 'b' の値に関係なく、 つねに 'a' という値になるわけです。 (sp + cnt) % MAX == sp + cnt ということですね。 では、今度はデータを次々取り出していくと、どうなるのか ? 1つデータが取り出されると配列は 1つずれていくので、sp の値は最大 "MAX - 1" まで 増えるはずです。 途中で "sp + cnt" の値は MAX の値を越えてしまいます。 ただし、最大でも "(sp + cnt) < (MAX * 2)" の範囲に収まります。 つまりこの場合、剰余計算の結果は、 (sp + cnt) % MAX == (sp + cnt) - MAX となるはずです。試してみましょう、 /* modulus_2.c */ #include main() { int a; int b; int a = 25; int b = 13; printf("%d\n", a % b); int b = 17; printf("%d\n", a % b); return 0; } コンパイルして実行させるまでもなく、結果は、 12 8 となります。 つまり 'b' が MAX の値だとすると、配列はそれぞれ 13 と 17 で終わっているにもか かわらず、見かけ上では 'a' の値が 12 (→ 25 - 13) 及び 8 (→ 25 - 17) と、一巡 しているように見えます。 概念的には、配列の最後に最初がつながったようなリング状のデータ構造となる。 これをリングバッファ ring buffer と呼ぶ。 このようにデータ構造をリング状にすることにより、データを入れる位置と取り出 す位置を無限にずらし続けることができる (ようになる)。(p191) この仕組みを取り入れることで、配列の添字 sp と count 数とがどのように変化しても 、つねに最初に入れた順からデータを取り出すことができるのです。 キューを C で実現するときには、1つの配列と 2つの指標用の変数 (sp と cnt) を 用いて、次のようにコーディングする。 int r_buf[MAX]; int sp = 0; int cnt = 0; void buf_in(int c) { if (cnt == MAX) return; r_buf[(sp + cnt) % MAX] = c; ++cnt; } int buf_out(void) { if (cnt == 0) return 0; r = r_buf[sp]; sp = ++sp % MAX; return r; } データを引数にして buf_in() 関数を呼び出すことにより、データがキューに格納 される。 また、buf_out() 関数を呼び出すことにより、戻り値としてキューからデータを取 り出すことができる。(p190-191) では、どのようなところで使われているか、というと、 キューは、キーボードやマウスの入力イベントを処理する場合など、ある程度の先 行入力を蓄えておく必要のあるときなどによく使われる。(p190) *1：「作ってわかる Cプログラミング」 2006-01-16 φ(-_-) ■[lang]はじめての C C programming note*1 座標上の対角線の長さを計算するプログラムを考え、その中に「構造体をメンバとして 含む構造体」を組み込んでいきます。 ここでは、その長さを求める対角線は、座標上の左上と右下の 2点をむすぶ直線だと仮 定しておきます。 はじめに基本となる「座標の 1つの点を表わす」構造体をつくります。 struct { int x; int y; }; タグ名がついていないのは、この構造体は別の構造体のメンバにするつもりであり、ま た「後のコードで使う」予定がないからです。 typedef をつかって、構造体に POINT という名前をつけておきます。 typedef struct { int x; int y; } POINT; 次に、この「2つの点のデータを一組に管理する構造体」を定義することで、見通しのよ いプログラムをつくっていきます。 つまり、構造体のメンバとして先の構造体を含むようにするわけです。 typedef struct { POINT p1; POINT p2; } RECT; POINT と同じく、typedef をつかって RECT という名をつけておきます。 それぞれのメンバを定義するのは、ふつうの構造体でのそれと同じです。 RECT r; r.p1.x = 2; r.p1.y = 4; r.p2.x = 6; r.p2.y = 1; 対角線の長さを求めるため、「与えられた 2点間の距離を (計算して) 返す」関数をつ くっていきます。 #include double distance(RECT r) { int dx; int dy; double dis; dx = r.p1.x - r.p2.x: dy = r.p1.y - r.p2.y; dis = sqrt(dx * dx + dy * dy); return dis; } 関数 sqrt() は、与えられた引数の値の平方根を返し、引数がマイナスだとエラーにな ります。 dx と dy は座標では直角三角形の直角をはさんだ 2辺の長さと同じですから、それぞれ の値を 2乗したものの和の平方根が、三角形の他の 1辺つまり対角線の長さになるわけ です。 K&R 2nd では、 sqrt は double の引数を仮定しているから、不注意に他の型が渡されると無意味な 結果を出す (p56) ので、キャストを使って double型に変更するよう警告しています。 しかし、sqrt() はマイナスの値でなければ、引数が int型であっても正常に計算してく れるようです。 また、引数にとる値 - dx と dy - がマイナスになっていても、簡単に対角線の長さが 求められる関数 hypot() もあるので、そちらを使うこともできます。 hypot() はユークリッド距離関数と呼ばれ、引数には直角三角形の直角をはさんだ 2辺 の長さをとります。 double hypot(double x, double y); この関数を使えば、対角線の長さは次のように求められます。 dis = hypot(dx, dy); 構造体のメンバ p1 と p2 - 座標上の 2点 - はその位置をそれぞれ左上と右下に仮定し ていますが、実際のデータではそうでない逆の組み合わせも考えられます。 そこで、この仮定の条件につねに合うように、正規化 normalize する関数も用意してお きます。 void normalize_rect(RECT *r) { int tmp; if (r->p1.x > r->p2.x) { tmp = r->p1.x; r->p1.x = r->p2.x; r->p2.x = tmp; } if (r->p1.y < r->p2.y) { tmp = r->p1.y; r->p1.y = r->p2.y; r->p2.y = tmp; } } ここでは、各メンバを表わすのにアロー演算子 (->) が使われていますが、それは データを直接変更するために、(関数の) 引数には RECT型のポインタを渡すように なっている (p206) からです。 テスト用のプログラムは次のとおり、 /* calc_dist.c */ #include #include void normalize_rect(); double distance(); typedef struct { int x; int y; } POINT; typedef struct { POINT p1; POINT p2; } RECT; main() { double dis; RECT r; r.p1.x = 6; r.p1.y = 1; r.p2.x = 2; r.p2.y = 4; puts("original:"); printf("a == (%d, %d)\n", r.p1.x, r.p1.y); printf("b == (%d, %d)\n", r.p2.x, r.p2.y); puts("normalize:"); normalize_rect(&r); printf("a == (%d, %d)\n", r.p1.x, r.p1.y); printf("b == (%d, %d)\n", r.p2.x, r.p2.y); dis = distance(r); printf("distance a to b: %0.2f\n", dis); return 0; } void normalize_rect(RECT *r) { int tmp; if (r->p1.x > r->p2.x) { tmp = r->p1.x; r->p1.x = r->p2.x; r->p2.x = tmp; } if (r->p1.y < r->p2.y) { tmp = r->p1.y; r->p1.y = r->p2.y; r->p2.y = tmp; } } double distance (RECT r) { int dx; int dy; double dis; dx = r.p1.x - r.p2.x; dy = r.p1.y - r.p2.y; dis = hypot(dx, dy); return dis; } なお、ヘッダファイルの math.h をインクルードして、数学関連の関数を使うときには 、コンパイルする際に 1つ注意することがあります。 それは、コマンドラインの末尾に必ず -lm オプションをつけておく、ということです。 $ cc -o calc_dist calc_dist.c -lm http://www.linux.or.jp/JF/JFdocs/archive/GCC-FAQ/index.html#AEN220 (gcc 以外のコンパイラでも、これは適用されるはずです) *1：「作ってわかる Cプログラミング」 2006-01-23 φ(-_-) ■[lang]はじめての C C programming note*1 ヒープは二分木の一種で、上の方ほど値がより大きく (または小さく) なるように 積み重ねた二分木だ。整列二分木ともよばれる。 2つの子の間の大小関係には順序はなく、親がその子より大きいという関係だけが成 り立つ (上の方ほど小さくなる場合はその逆になる)。 データの追加や削除に関しては、この大小関係をくずさないよう行なうわけだ。 最初にヒープをつくるときには、1つの要素ごとに追加の処理を行なえばよい。 ヒープというデータ構造は、「要素の追加や削除は任意のタイミングで起きるが、 参照したいのはいつも一番大きな (または小さな) 値だけ」という用途に向いてい る。 ヒープの実現方法としては、以下のように配列に入れる方法が最も一般的だ。 子の数は最大 2つで、上から、また左からぎっしり詰める。 a[1] はルート (root: 木の根っこほどの意味) を入れる。 a[2], a[3] に lebel 1 の要素を ... のよう に順に格納していく。このようにすれば、 a[i] の子は a[i * 2] と a[i * 2 + 1] である。 という関係が (すべての要素について) 成り立つ。 C の配列の添字は 1 からではなく 0 からだが、この場合はあえて 0 を使わないで 1 から使うのがコツだ。その方が添字の計算式がすっきりする (からだ)。 (p210-211) heap の説明はこれですべてです。 サンプルコードを見ていくと、いろいろ気がつく点があります。 ・他の二分木と異なって配列が使われている。 ・そのため malloc を使ったメモリ確保の必要がない。 ・データの追加は tree の末尾から行ない、逆にデータを取り出す (参照する) ときは root からである。 ・他の二分木と同じく再帰が効果的に使われている。 ・多次元配列が内部的に用いられている←これは後まわしにして ... と。 まず元になる関数 heap() から、 heap() の仮引数 i は入力データの配列の添字、n はそれと比較する配列の添字です。 /* heap.c */ static void heap(int i, int n) { int child; if (i <= n / 2) { if (2 * i + 1 > n) child = 2 * i; else { if (i_comp(2 * i, 2 * i + 1) > 0) child = 2 * i; else child = 2 * i + 1; } if (i_comp(i, child) < 0) { i_swap(i, child); heap(child, n); } } } /* sub.c*/ #include #define MAX_S 8 #define MAX_ITEMS 1024 static char array[MAX_ITEMS][MAX_S]; int i_comp(int a, int b) { return (strcmp(array[a], array[b])); } void i_swap(int a, int b) { char tmp_str[MAX_S]; strcpy(tmp_str, array[a]); strcpy(array[a], array[b]); strcpy(array[b], tmp_str); } sub.c ではじめに外部宣言してある多次元配列 array には static がついています。こ れは sub.c というコード内でしか使われない変数だからです。 同じく、heap.c で関数 heap() に static がついているのも、heap.c 以外のプログラ ムからは参照できないようにするためです。 i_comp() では関数 strcmp() を使って、配列の中身 (要素) を比べています。 array [a] が array[b] より大きければ正の値を、小さいときは負の値を返します。 i_swap() では添字はそのままで、その配列の中身 (要素) を strcpy() と変数 tmp_str を使って交換します。 まず関数 heap() は、i 番目の配列は必ず n 番目の配列の親である、という仮定で始ま っています。 if (i <= n / 2) 実際は、i の要素はずっと上の line にある可能性が多いのですが、まず n の親である として、それが 2つの子のどちらにあるかを決めていきます。 そして、親に子がないか、あるいは子があってもその子の中身 (要素) が左側の要素よ り小さいときはその子に代わって 1つめの要素になり、それ以外なら 2つめの子になり ます。 さらに、 i と child の要素を比較して、もし child よりデータが小さいときには、そ れぞれの中身 (要素) を交換して、もう一度再帰的に heap() を実行させていきます。 これをくり返すわけです。結果的に、(入力した) データの中身 = 要素ではなく、配列 の添字を変えていくことで tree に組み込んでいってるのです。 以上の説明は単純化したイメージにすぎないので、当然正確とはいえませんね。 *1：「作ってわかる Cプログラミング」 2006-01-27 φ(-_-) ■[lang]はじめての C C programming note*1 次は、heap にデータを追加する関数、 /* heap.c */ static int n_item = 0; void add_item(char *s) { int i; i = ++n_item; i_add(i, s); while (i_comp(i, i / 2) > 0) { i_swap(i, i / 2); i = i / 2; if ( i == 1) break; } } /* sub.c */ void i_add(int n, char *s) { strcpy(array[n], s); } はじめに、変数 n_item が static 宣言され、0 に初期化しています。 n_item は配列の添字を表わし、実際に使われるときは、tree 末尾の配列の添字になり ます。 i_add() は配列の添字を指定してそこにデータを入れる関数です。 つまり、関数 add_item() において、 i = ++n_item; i_add(i, s); とすることで、tree の末尾にデータを追加するわけです。 その下の while ループでは、末尾の配列とその親のそれぞれの要素を比較して、親より 大きければ要素を交換し、次に 1つ上の lebel でさらに比較をくり返します。 root ま でたどり着くと、このループを抜け出します。 あと 2つ、root を削除する remove_root() と、要素を tree に整列させる make_heap () 関数、 /* heap.c */ void remove_root(void) { i_swap(1, n_item); i_remove(n_item); heap(1, --n_item); /* tree の 再構成 */ } void make_heap(int n) { int i; n_item = n; for (i = n_item / 2; i >= 1; i--) heap(i. n_item); } /* sub.c */ void i_remove(int n) { ; } 関数 remove_root に含まれる 3つの関数のうち、i_remove() は dummy ですからなにも 実行しません。 変数 n_item は末尾の配列の添字ですので、 i_swap(1, n_item); i_remove(n_item); とすることで「一番下位の要素を root へ移動」させ、同時に「root の要素を削除」し ています。 関数 make_heap() のなかで、heap() は 1組の要素を比較しているだけですが、for ル ープを使うことで、tree の末尾から順に要素を整列させることができるようになります 。 あとは、文字列関数を使用する関数と、その他の関数とを 2つのコードに分け、別にテ スト用の main() 関数をつくっていきます。 /* sub2.c */ #include #include #define MAX_S 8 #define MAX_ITEMS 1024 static char array[MAX_ITEMS][MAX_S]; int i_comp(int a, int b) { return (strcmp(array[a], array[b])); } void i_swap(int a, int b) { char tmp_str[MAX_S]; strcpy(tmp_str, array[a]); strcpy(array[a], array[b]); strcpy(array[b], tmp_str); } void i_add(int n, char *s) { strcpy(array[n], s); } void i_remove(int n) { ; } void i_print(int n) { printf("%3d: %s", n, array[n]); } /* heap2.c */ static void heap(); int i_comp(); void i_swap(); void i_add(); void i_remove(); static int n_item = 0; static void heap(int i, int n) { int child; if (i <= n / 2) { if ( 2 * i + 1 > 2) child = 2 * i; else { if (i_comp(2 * i, 2 * i + 1) > 0) child = 2 * i; else child = 2 * i + 1; } if (i_comp(i, child) < 0) { i_swap(i, child); heap(child, n); } } } /* 今回は 使用しない */ void add_item(char *s) { int i; i * ++n_item; i_add(i, s); while (i_comp(i, i / 2) > 0) { i_swap(i, i / 2); i = i / 2; if (i == 1) break; } } void remove_root(void) { i_swap(1, n_item); i_remove(n_item); heap(1, --n_item); } void make_heap(int n) { int i; n_item = n; for (i = n_item / 2; i >= 1; i--) heap(i, n_item); } /* test_heap.c */ #include extern void i_add(int, char *); extern void i_print(int); extern void make_heap(int); extern void remove_root(void); char *data[] = { "cab", "dab", "gab", "jab", "lab", "nab", "tab", "lac", "sac", "bad", "dad", "fad", "gad", "had", "lad", "mad", "pad", "sad", "tad", "wad", "oaf", "bag", "fag", "gag", "jag", "lag", "nag", "rag", "sag", "tag", "wag", "zag", "bah", "wah", "yah", "raj", "oak", "yak", "gal", "pal", "bam", "cam", "dam", "gam", "ham", "jam", "lam", "ram", "tam", "yam", "ban", "can", "fan", "man", "pan", "ran", "tan", "van", "wan", "tao", "cap", "gap", "hap", "lap", "map", "nap", "pap", "rap", "sap", "tap" }; main() { int i, n; n = sizeof(data) / sizeof(char *); for (i = 1; i <= n; i++) i_add(i, data[i - 1]); for (i = 1; i <= n; i++) i_print(i); printf("\n\n"); make_heap(n); for (i = 1; i <= n; i++) i_print(i); printf("\n\n"); for (i = 1; i <= n; i++) { i_print(1); remove_root(); } putchar('\n'); } main() 関数で注意するのは、data をポインタ配列として宣言しているところです。 char *data[]; sub.c では array を 2次元配列として宣言していましたが、多次元配列では例えば、 char a[i][j]; と宣言したとき、これは char 型の j 個の配列が i 列 (または i 組) あることを意味 します。 関数 i_add() では第2引数として文字列のポインタをとっています。ところが、data は ポインタ配列ですので、このコードでは文字列の入った配列のポインタを渡しています 。 i_add(i, data[i - 1]); このとき関数内の strcpy() は、渡されたポインタ配列を 2次元配列と解釈して、その データをコピーしていきます。 はじめは char 型の配列のポインタとして、次にデータが格納されている配列として、 という具合に 2つに分けて取り入れているわけです。 試しに、array を 2次元配列ではなく通常の配列として宣言しておくと、sub.c をコン パイルすると、文字列関数が使われているところでキャストをつけるよう警告がでるは ずです。 あとは、コンパイルして実行させてみます。 $ cc -c test_heap.c heap2.c sub2.c $ cc -o test_heap test_heap.o heap2.o sub2.o $ ./test_heap 実行の結果を見てみると、はじめに i_add() を使ってデータを入れています。このとき はコピーした順に配列に格納されていきます。 次に、make_heap() を使って tree に組み込んでいきます。「2つの子の間の大小関係に は順序は」ないので、root だけが確定していて、あとは組み込まれた順で print され ます。 最後に、remove_root() で順次、root を削除していきます。ここでようやく、文字列の 大きさ順に print されていきます。 data の入力は tree の末尾から、参照は逆に root から、ということですね。 *1：「作ってわかる Cプログラミング」 2006-02-04 φ(-_-) ■[lang]はじめての C C programming note*2 ハッシュはデータ構造そのものというよりも、アルゴリズムと深く結びついている ので、いままで説明してきた他のデータ構造とはちょっと毛色が変わっているとい える。 ハッシュを使うと、データ構造の中からあるデータを検索するのに、データの比較 などをせずに基本的には計算するだけで検索することができる。 データを格納するためのメモリ領域が比較的多めに必要なかわりに、データの検索 が速いという特徴がある。 ハッシュ法の検索において「キーからデータの格納場所を計算する」関数をハッシ ュ関数という。 この関数を使ってデータの内容ごとに「格納すべき場所」を決定してその位置にデ ータを格納してあるので、アクセスするときも計算で位置が求められるわけだ。 (p216) K&R 2nd では、次の 2つの章で取り上げられています。 http://d.hatena.ne.jp/sekiyo/20051029 http://d.hatena.ne.jp/sekiyo/20051103 まず、キーとデータとを格納するためのポインタ配列をつくり、配列に格納する最大値 を決定していきます。こんな感じで、 # define HASHSIZE 101 static *hashtab[HASHSIZE]; この hashtable と、あとハッシュ関数が準備できれば、hash search の半分以上はでき たも同然です。 hashtable にはふつう構造体を用い、1つの key に 1つの data が割り当てられるよう にします。 typedef struct { char *key; char *data; } ENTRY; static ENTRY *hashtab[HASHSIZE]; 例題のハッシュ関数は、 K&R 2nd に載っているものとは少しだけ違っています。 int hash(char *s){ unsigned u; for (u = 0; *s != '\0'; s++) u = ((u << 8) + *s) % HASHSIZE; return u; } s は「文字列中の各文字」ですから、1文字ずつ「文字の value (とシフト計算の結果) を混ぜ合わせながら」それを HASHSIZE で割った modulo (余り) を次々加算していき、 その計算結果をハッシュ値として返しています。 また、ここではビット演算子の "<<" も使われています。 a = a << b; の場合、a は必ず正の値であり、b はビット数を表わします。"<<" は左シフトですから 、このとき a の値は 2 の b乗倍になります。 上のハッシュ関数だと、2 の 8乗つまり 256倍になるわけです。 また、前にも見たように、モジュロ演算子の左側の数値がどれだけ大きくなっても割る 数の値を越えることはありません。 u = ((u << 8) + *s) % HASHSIZE; u の値は HASHSIZE より大きくはならないわけです。 ハッシュ値は hashtable の添値として使われるのですが、モジュロ演算子を用いること で、格納される key と data はつねに最大値が HASHSIZE の配列内に収まるようになり ます。 *2：「作ってわかる Cプログラミング」 2006-02-09 φ(-_-) ■[lang]はじめての C C programming note*1 ハッシュ関数を使えば、1回の照合で探索 search が可能のように思われますが、実はデ ータがたびたび更新されると、照合の回数が増えてしまいます。 その場合でも、ハッシュを使うことで、平均すれば 2, 3回の照合で検索は可能になりま す。 ただし経験則で、データを入れる配列の数が、総データ数の 2倍以上であれば、探索は ほぼ 2回以下で収まることがわかっています。(注) (注) ブルーバックス版「パソコンなんでも小事典」(isbn:4062572427) p126-127) ハッシュはアルゴリズムですから、目的によってそのデータ構造が少しずつ違ってきま す。 例えば K&R 2nd の例では、構造体を使って、リンクリストをつくっています。 struct nlist { struct nlist *next; char *name; char *defn; }; このリンクリストをたどっていくために、lookup 関数で for文が用いられているわけで す。 また、データを格納してそのハッシュ値を決定する install 間数では、そのためのリン クリストつくっていきます。 install 関数の中を見ていくと、 1. lookup 関数で、データに name が含まれているかをチェック。 2. なければ、malloc で nlist 分のメモリを確保。 3. strdup 関数を使って name のコピーを作成し、nlist に格納。 4. name からハッシュ値を求めて、配列ポインタ hashtab の添字とし、nlist をつない でいく。 5. 1 へ戻って、name が含まれているときは、一応前の defn 定義分を free で消去。 6. (新しい) defn のコピーをつくって nlist に格納。 7. リスト作成に成功した場合には、name と defn の格納された nlist のポインタを返 す。 (なお、ここで使われている strdup は標準ライブラリ関数ではなく、K&R 2nd p173 に あるものです) hashtable から name を削除する undef 関数については、次の page に載っています。 http://users.powernet.co.uk/eton/kandr2/krx605.html 最初の回答例のほうがやさしいので、参考のため写してみましょう。 int undef(char *name) { struct nlist *np1; struct nlist *np2; if ((np1 = lookup(name)) == NULL) /* name not found */ return 1; for (np1 = np2 = hashtab[hash(name)]; np1 != NULL; np2 = np1, np1 = np1->next) { if (strcmp(name, np1->name) == 0) { /* name found */ /* remove name from list */ if (np1 == np2) hashtab[hash(name)] = np1->next; else np2->next = np1->next; /* free memory */ free(np1->name); free(np1->defn); free(np1); return 0; } } return 1; } 以上のコードを組み立てて、実際に使えるプログラムをつくれるようになるのは、次の 課題の - ず〜っと - 後になりそうですが ... (;_;) *1：「作ってわかる Cプログラミング」