C言語で文字列を逆にする
最近 Joel on Software を紙で読んでいる。
その中に気になる一節があった。20章「採用面接ゲリラガイド」の中のこんな文章だ。
(※書籍版での更新日時は2004年6月4日となっており少し新しい。さらに更新された web 版の日記はこちら)
4.プログラミングの質問
面接のこの部分には一番時間をかけるべきだ。私は候補者にC言語で(あるいは彼らがなじんでいる言語なら何でもいい)小さな関数を書くように求める。
以下に、私がよく出す問題の例を挙げる。
- 文字列をその場で逆にする
- 連結リストを逆にする
- バイトデータの中で経っているビットの数を数える
- 二文探索
- 文字列の中で同じ文字が一番長く続くところを見つける
- atoi
- itoa(スタックやstrrevを使う必要があるため、良い問題だ)
「文字列を逆にするのか・・・strlen() で計って、 malloc() をして・・・」
と考えながら読み進めると、まさにそれを先読みしたかのようなこんな記述が。
(中略)
1.の「文字列をその場で逆順にする」については、私がこれまで面接した候補者はみんな1度目には間違ったやり方をした。例外なく、彼らはもう1つのバッファを用意して、そこに逆順の文字列を作ろうとする。問題は、そのバッファのメモリ領域を誰が割り当てるのか? 誰がそのバッファを開放するのか?
間違ったやり方らしい。
そしてこう続いた。
この質問を何ダースもの候補者に出して気づいた興味深い事実がある。C言語を知っていると思っている人たちの多くが、メモリやポインタを本当には理解していない。彼らは単にそれが分からないのだ。そういう人たちがプログラマとして働いているというのも驚きだが、実際そうなのだ。この質問で候補者を判定する方法はいくつかある。
・・・と、いうことは、ポインタを使えばもっと早くメモリ消費も短くなるのかな?
そんなわけで、書いてみた。
// 文字列を逆にする // どうせなら string.h なしで #include <stdio.h> // a.out の後に続く文字列を逆順にする int main(int argc, char* argv[]){ int len = 0; char temp = '\0'; char *s = argv[1]; char *head = NULL; char *tail = NULL; // 引数が足りないなら比較しない if(argc <= 1){ return 0; } // 操作前 printf("Input: %s\n", s); // 文字列の長さを取得する len = 0; head = s; while(*head != '\0'){ head++; len++; } // 逆にする head = s; tail = &s[len-1]; while(head != tail){ temp = *head; *head = *tail; *tail = temp; head++; if(head == tail){ break; } tail--; } // 操作後 printf("Output: %s\n", s); return 0; }
実行結果はこんな感じ。
imadedede$ ./a.out a Input: a Output: a imadedede$ ./a.out ab Input: ab Output: ba imadedede$ ./a.out abc Input: abc Output: cba imadedede$ ./a.out abcd Input: abcd Output: dcba
これだと、文字数が1文字でも奇数でも偶数でも入れ替えられる。
元の文字列が破壊されてしまうけど、特に制限はなかったからこれでも間違いではないはず。
・・・実のところ、書き始めでは文字列の長さをとった後で head ポインタの初期化を忘れており、そのデバッグに30分ほどかかってしまった。
まだまだ精進が足りませんなあ。
まあでも、たまにはこういうことを考えてみるのも一興ということで。
追記:最新版はこちら