2005-05-14 φ(-_-) ■ [lang]はじめての C しばらく C++ World の tutorial を少しずつ訳してみる。 http://www.cppworld.com/tutorials/ 「構造体について」 構造体は、互いに関連している異なった型の値をまとめて扱うことのできる、都合 のよいやり方 - convenient way - です。 struct Person { char *name; int age; float height; }; まず初めに - ちょうどぼくらがおしゃべりを始めるときのように - 構造体を宣言 します。ただしここでは構造体の値の宣言は含まれていません。 なぜかというと、構造体は名前を書き込む荷札 - tag - を 1つもっていて、後から その構造体の値を宣言することができるからです。 "struct" というキーワードで、"Person" が構造体だということを、コンパイラに 知らせるよう命じているのです。 構造体の値は (そこでコピーを作ってやることで) 実際の構造体を割り当てること により、初期化することができます。 struct Person { char *name; int age; float height; } Prelude = { "Prelude", 25, 5.9f }; struct Person Prelude = { "Prelude", 25, 5.9f }; 同様に、同じ型の構造体を返す関数を呼び出すことでも、初期化できます。 ポインタで構造体にアクセスするときには、はじめに、ドット演算子を使うことで 、ポインタの示す先を参照 - dereference - しないといけません。 (*structure-name).member このやり方は使いにくくてみっともないし、すでにこき使われてる language に、 さらにムダな語句を加えることにもなります。 そこで、ポインタのメンバにアクセスするのに、構造体を一般的で使いやすいもの にするため、arrow operator という操作が language に追加されました。 structure-name->member 2005-05-15 φ(-_-) ■ [lang]はじめての C 「構造体について 2」 ポインタを構造体に渡す、という参照方法は多くの場面で採り入れられています。 それは、大きすぎる構造体の占めるスペースを節約してくれますし、ときには、そ の実行速度を上げることにもなります。 実際、多くのデータ構造ライブラリでは、ノード作成型 - make_node type - の関 数をもつことになるでしょうし、そこではポインタをメモリに割り当てて - allocate - 返すか、またはポインタのポインタを使って同様にメモリに割り当てる ことになります。 struct Node *make_node(void) { struct Node new_node = malloc(sizeof*new_node); /* Error check and set a default state */ return *new_node; } このようなデータ構造アルゴリズムのロジックを用いると、リンクリストや 2分木 - binary trees - を容易に実現できますし、またそれ以上に、スパース行列 - sparse matrices - と skip list に対してはるかに役立たせることができるのです 。 そのほかにも、構造体の配列をつくることができます。その用法はふつうの配列と 同じことになります。 struct Person { char *name; int age; float height; }; struct Person people[] = { { "prelude", 25, 5.9f }, { "Generic person", 20, 6.0f } }; それぞれのメンバにアクセスするには、ドット演算子を使う前に、配列に添字を用 いてください。 printf("Name : %s\n", people[0].name); 2005-05-16 φ(-_-) ■ [lang]はじめての C 「構造体について 3」 構造体は、そのなかに同じ型の構造体のポインタを含むことができ、自己参照構造 体と呼ばれています。 struct Node { void *data; struct Node *next; }; これが、連結リストに含まれた単体の項目 - simple item - に使われて、よく見か けるノード構造体です。 その機能は、まあわかりにくいでしょうが、ノードの値が宣言されたとき、メンバ に対して作成されるのは、実際のノードではなくて、ノードへのポインタである、 ということに留意してください。 もし実際にノードが作成されるとすると、それは再帰的宣言 - recursive declaration - ということになって、メモリが喰いつぶされるまでノードがつくら れることになります。 しかしこの場合は、ポインタだと再帰としては機能しませんので、安全なのです。 構造体の他の機能としては、ビットフィールドの呼び出しに使われることがありま す。 2005-05-17 φ(-_-) ■ [lang]はじめての C 「対話型入力」 対話式入力、つまりデータを直接ユーザが入力することで知られている方法は、落 ちかけてる橋を歩いて渡るようなものです。 というのも、ユーザというのはけっこういきあたりばったりなので、連中がしでか すであろう考えられる限りの誤操作 - mistake - に対処できるコードを簡単明解に 実装するのが困難だからです。 C で、一般的な入力方法の手順を使って、それをやりとげるのは、まったく楽では ありません。 実際、C ではもっとも標準的な、scanf を使用して入力するやり方では、堅牢なコ ードを書くのはむずかしく、信頼できないのです。 なぜなら、それは自在 - flexible - で複雑にすぎるからです。 書式付入力 - formatted input - でのみの使用が奨励されているにもかかわらず、 プログラマというのは、ユーザからの入力に、書式付以外のどれかで scanf を使う 必要性を感じています。 このことは、一直線に、問題のあるプログラムへと通じ、さらに悪い方向に陥るこ とになります。 scanf は、エラーが発生すると、それを正常に戻すのが困難な、評 判のよくない関数だからです。 scanf の通常の使用方法は、数 - numbers - を直接、値に読み込むことです。 int var; scanf("%d ", &var); 2005-05-18 φ(-_-) ■ [lang]はじめての C 「対話型入力 2」 これは動いてくれます。ただし、ユーザがおかしな整数値を入力しなければ、です が。 scanf の呼び出し - call - を改良する 1つの手段として、返り値のチェックがあ ります。 scanf は値によって数値を返します。呼び出しが成功すれば 1 を返すので、その値 を組み込むようにするのです。 int var; if (scanf("%d", &var) != 1) { fputs("Error, invalid integer"); exit ( EXIT_FAILURE ); } これは簡単だし処理も十分ですが、ただその症状を改善しただけで、実際の問題が 解決されたわけではありません。 というのも、ユーザからの入力で scanf が不適当な使われ方をする、という事実は 残っているのですから。 さらに悪いことに、プログラマというのは scanf で文字列データも読み込もうとす るのです。 char buf[20]; scanf("%s", buf); or scanf("%[^\n] ", buf); scanf は、最初の例では空白が見つかるまで文字数を読み込み、二つ目の例だと、 新しい行の文字が来るまで文字数を読み込みます。 ここでの問題は、その文字数がどのくらいの範囲に収まるのか、ということです。 入力数が 20 を越えてしまうと、いったいなにが起きるのでしょう ? 結果ははっきりしません。ただ通常では、あなた自身のものでもないメモリが踏み にじられて、プログラムが動かなくなり burn するか、あるいはそのまま稼働して も大変な損傷を受けるか、でしょう。 これには、どれだけの文字数を読み込むかを指定するという手続きをすれば、その 場しのぎですけど、解決が可能になります。 (コードは省略) (注) %[^\n] - 改行文字以外のすべての文字(列)とマッチする。結果的に 1行分の文字 列を表すことになる。 2005-05-19 φ(-_-) ■ [lang]はじめての C 「対話型入力 3」 ここで、わずかですが scanf のたぐいを回避できる選択肢があります。その中には かなり複雑なものもあり、使う前には、ユーザ入力が正確であることを十分確かめ ないといけません。でないと、あなたにとってなにかよくないことが、すぐに起き ることになります。 はじめのオプションは fgets と sscanf です。 int var; char buf[20]; while (fgets(buf, 20, stdin) != NULL) { if (sscanf(buf, "%d", &var) == 1) break; fputs("Error, invalid input, try again", stderr); } このオプションは安全です。ユーザからの入力をストリングとして読み込み、必要 とする値が取り込まれると停止 - break - します。 この実装は単純ですが、sscanf が使われるそれ以前に、そのストリングすべてが正 確であることを確認できるのです。 留意することは、scanf は安全ではありませんが、その scanf の仲間を含む他の関 数群は、多くの parsing situation において、とても役にたつ、という点です。 つぎは、1つの数のように、単一の値を入力するときのオプションです。 2005-05-20 φ(-_-) ■ [lang]はじめての C 「対話型入力 4」 #define INVAL -1 int var; char buf[20]; if (fgets(buf, 20, stdin) != NULL) var = (int)strtol(buf, NULL, 10); else { fputs("Error, no input read\n", stderr); var = INVAL; } /* ここでは (var は) strtol の返り値を * (int に変換してから) 用いるので * エラーの場合でもその値を安全に扱えます。 */ (注) strtol - K&R 2nd p317 (stdlib.h) long strtol(const char *s, char **endp, int base) strtol は、先頭部分の空白文字を無視し、s (string) の接頭子 - prefix - を long に変換する。 このとき endp が NULL でなければ、変換されなかった接尾子 - suffix - へのポイン タを *endp に格納する。 base が 2 と 36 の間にあれば、入力はその基数で書かれたものとして、変換が行なわ れる (10 なら 10進法として)。 base がゼロなら、基数は 8, 10 または 16 となる。 (s の) 先頭に 0 があれば 8進法、0x が前につくと 16進法と解釈される。 答がオーバーフローしたときには、その結果の符号によって、LONG_MAX か LONG_MIN が 返され、errno が ERANGE にセットされる (<- この関数は安全に扱える、ということら しい)。 複数の値がいるのなら、strtok を使うことができます (strchr を工夫して使って もいいでしょう)。 char buf[BUFSIZE], *sep; /* sep <- separate */ int val_array[5], index = 0; fgets(buf, sizeof buf, stdin); sep = strtok(buf, " "); while (sep != NULL) { val_array[index++] = (int)strtol(sep, NULL, 10); sep = strtok(NULL, " "); } (注2) strtok - K&R 2nd p314 (string.h) strtok(s, ct) ct (character) によって区切られるトークンを、 s (string) から探索する。 strtok を連続して呼び出すと、s は ct で指定された文字により区切られたトークンに 分割される。 最初のトークンでは、s の次の文字に '\0' を上書きしてトークンの終端とし、ポイン タを返す。 s の値を NULL とすることで再度、呼び出しが行なわれる。 その後の呼び出しでは、前の文字列の終わった次から探索が始まり、同様に次のトーク ンのポインタが返される。 それ以上トークンが見つからなければ、NULL を返す。 (注3) strchr - K&R 2nd p202 (string.h) strchr(s, c) s (string) 中の最初の c (character) へのポインタが返される。なければ NULL を返 す。 もちろん、sscanf や strtok など、strto* の仲間である文字列関数 - string conversion functions - を、fgets のような関数といろいろ組み合わせて使えるの で、ユーザからの入力を完全に確保しておき、必要とされる分析を行なう - parse - こともできます。 2005-05-21 φ(-_-) ■ [lang]はじめての C 「対話型入力 5」 これまで見てきたように、ユーザからの対話型入力を安全に扱うのは、最初思って いたよりずっと複雑ですし、それを正確に取り込むことが、また信じられないくら い困難なのです。 入力処理についても、その適用のしかたが違えば、異なった方式が求められてきま す。そういうことなので、ここで示された数例をもって、すべてのプログラムに対 して、完璧に書かれているかのようには受け取らないでください。 できるなら、すべての可能な解決法を比較してみて、その目的に一番適ったものを 選び出すことです。 しかし、一般的な解決のしかたとして最もよいのは、ユーザからの入力を全体的に 読んでみて、何らかの問題が生じて、あなたの望まないエラーが起きたとしても、 それをすぐにもとに戻せるように、じっくりと分析してみることです。 これが、line of input をメモリに収納する上での、いちばん好ましい態度なので す。 (英文なんてカンタン、と思ったのがマチガイでした ... ) 2005-05-27 φ(-_-) ■ [lang]はじめての C 「ソート法」 ソートは基本 - basic - ですし、また C と C++ のプログラムでは、一般的な操作 方法です。なので、この両者についての基礎 - basics - はもちろん、どのソート 法を用いるのかについても、よく精通するようにしてください。 一般的なアドバイスとしては、プログラムの読みやすさと、そのメンテナンス性と を保てるように、プログラマは、まず最初は、もっとも単純なソートを使うことで す。 次の 2つの基本的なソート法は、実際のアプリケーションでよく使われているため 、これはいいアドバイスになりますね。 はじめに説明する挿入整列法 - inserting sort - は、より高性能なアルゴリズム の最終のステップで、しばしば使われます。それは、挿入整列法が、ほとんどのソ ートで、データ上を最高速で走査することができるからです。 2つ目のソートは、シェルソート - Shellsort - として知られていて、あなたは最 初のから変えてみるかもしれません。というのも、簡単で、お行儀もいいし - well behaved - 多くのアプリケーションで充分に高速だからです。 2005-05-28 φ(-_-) ■ [lang]はじめての C 「ソート法 2」 挿入整列法はとても簡単で、新しい要素 - new item - を挿入するため、はじめに 要素を右側に移動させることによって、それぞれの新しい要素をその位置 - position - にソートできるようにスペースをつくるのです。 例えば、次のような数のリストがあるとします▽ 1, 2, 3, 4, 6, 7 数字の 5 をこのリストに挿入するのでしたら、はじめに 5 より大きな要素 - elements - をシフトして、空白 - gap - を 1つセットします▽ 1, 2, 3, 4, , 6, 7 ひとたびシフトが終われば、新しい要素を空いている位置へとセットします▽ 1, 2, 3, 4, 5, 6, 7 挿入整列法で、なにか気をつけるとすれば、それは 1つの要素がセットされたとし ても、そこが最終的な位置になるとは限らない、ということです。 次に入る新しい要素がより小さければ、それより大きな要素はシフトすることを求 められるからです。 挿入整列法は、元のリストがどう並んでいる - ordering - か次第のところがあり ます。なぜなら、リストも順次に始まっているなら、挿入整列法は高速になります が、しかし、もしリストが逆順だとすると、より遅くなるからです。 このことは、挿入整列法を実装するときに、よく考えておかないといけない、設計 時の判定 - design decision - となってきます。 もしソートされるリストが、より逆順に並んでいる - reverse sorted - のなら、 ソートはその最後の要素から走査を始めるべきでしょう。 一般的な解決法 - solution - であれば、リストがたとえどんな順次であったとし ても、たぶんより前方向 - forward - にソートされているだろうとして、挿入整列 法の疑似コード - pseudocode - をつくってみることですね。 (疑似コードは省略) 2005-05-29 φ(-_-) ■ [lang]はじめての C 「ソート法 3」 void insertion_sort (int *list, int left, int right) { int step, i; /* <- これはリストの添字 */ int temp; /* <- こちらは値 */ /* * 左から右へ移動して、step と right の * 間の値 - values - をソートする */ for (step = left; step < right; step++) { /* h番目の要素、list[step] を選択 */ temp = list[step]; /* * (逆順に) step から left へ移動して、 * 必要なら値をシフトする */ for (i = step; i >= left; i -= left) /* * ソートした値をセットする場所 - room - を * つくるため、値をシフトする */ if (temp < list[i - left]) list[i] = list[i - left]; else break; /* ソートした値を新しい位置へセットする */ list[i] = temp; } } 挿入整列法では、リストの要素の全総数をソートするので、2つの代入値 - arguments - しか必要としません。ここで注意してほしいのは、この実装 - implementation - ではそれが 3つあるということです。つまり、リストと、ソート を開始する配列の左端 - left end -、それにソートが終了する配列の右端 - right end - です。 これには 2つ理由があり、まず 1つ目は、この実装では、常に 0 から始めて n ま で移動するかわりに、リストのある部分だけをソートできます。分割したリストの 部分 - piece - を渡して、そこだけソートできるわけです。 2つ目の理由としては、シェルソートの実装が簡単に行なえる、ということです。で は、どうするかを手短かに - ただし正確に - 説明しましょう。 2005-05-30 φ(-_-) ■ [lang]はじめての C 「ソート法 4」 シェルソートは、挿入整列法の 1つのバリエーションです。 挿入整列法であることを示す理由の 1つに、要素はその右側の要素としか互いに交 換できない、ということがあり、配列を通して、一度に 1ヶ所に動けるだけです。 それで、時間がかかってしまいます。 シェルソートは、その分岐操作 - subdriving - で、要素をインタリーブ(介在)グ ループ - interleaved groups - に収納し、各グループごとにソートすることで、 この問題を解決しています。 例題で考えてみましょう。 元になるリストです▽ 5, 6, 2, 7, 8, 4, 3, 1 <- 前の 4つの数字に 注意 シェルソートの実装によって、リストの要素は 4組のペアに分割されます▽ (5, 8) (6, 4) (2, 3) (7, 1) それぞれのペアをソートします▽ 5, 4, 2, 1, 8, 6, 3, 7 <- 1つとび毎の 数字に 注意 リストが 4要素ずつ 2セットに分割されます▽ (5, 2, 8, 3) (4, 1, 6, 7) <- 前のセットの 数字が ソート リストをソートします▽ 2, 1, 3, 4, 5, 6, 8, 7 もう一度全体をソートすれば▽ 1, 2, 3, 4, 5, 6, 7, 8 なんだか、カードマジックみたいだ ... 2005-06-01 φ(-_-) ■ [lang]はじめての C 「ソート法 5」 シェルソートの背後にあるアイデアとして、要素の交換が挿入整列法と比べてより 大きな距離で行なわれるということがあり、それで高速度が実現されるのです。 この分岐操作のテクニックは、"h-整列" - "h-sorting" - として知られていて、シ ェルソートでは通常、h 間でどのシーケンス(間隔) - sequence of h's - を使うか による設計がされています。 シェルソートが、どのように分岐操作をするかは、そのシーケンスにもとづいて決 められていて、前の例でいうと、4 と 2 と 1 になります。 どんなシーケンスでも、それが着実に減算していく間は、使うことができます。 h が 1 になると、そこで終わりとなりまた、ふつうの挿入整列法が使えますから、こ こで挿入整列法を選ぶことで、たいていのソートリストで動かすことができるよう になります。 あるシーケンス h のほうが、他のそれより優れていることがあります。評価の高い シーケンスとしては、1969年にクヌースによって推奨されたものがあり、このシー ケンスは、 1, 4, 13, 40, 121, 364, 1039, 3280, 9841, ... となっています。 これは簡単ですし、他のシーケンスでもっと効率的なのがあっても、それより効果 を 20% 以上増やすことはむずかしいのです。 C/C++ の実装では、これを用いることにしましょう。 ところで、h の値が 1 になったら即、シェルソートを挿入整列法にする、というこ とを忘れてはいませんね ? ここではうまい具合に、挿入整列法のためにコードを再実装しなくても、以前書い ておいた関数を使うことができます。 2005-06-02 φ(-_-) ■ [lang]はじめての C 「ソート法 6」 void shellsort(int *list, int n) { int h = 1; for ( ; h <= n / 9; h = 3 * h + 1) ; for ( ; h > 0; h /= 3) insertion_sort(list, h, n); } 結論として、この 2つの関数は、ソートルーティン - sorting routine - で最初に 選択するのには、オールアラウンドに適している関数だ、ということです。 まず初めに、プログラムの中でシェルソートを使ってみるのは、いいアイデアです 。目標に対し、あまりにも遅いことがわかったときだけ、より洗練されたソート法 に乗り換えればいいのです。 シェルソートは短いし速いし、それにいろいろなケースでも、ほんとにお行儀よく ふるまってくれます。 これだけの度合 - degree - で同じぐらい誇ってもいいようなソート法は、他には ないでしょうね。 "K&R 2nd" に載ってるシェルソートと比べてみるのもいいかも 2005-06-06 φ(-_-) ■ [lang]はじめての C 「ポインタ」 C では、データがどんな型であっても、その型のポインタをもつことができます (たとえ関数だったとしても !)。 ではポインタの使い方を少しだけ見てみましょう。 先へ進む前に、ポインタの 2つの特別なバリエーションに触れておくこともいいア イデアですね。 初めはあるポインタの型について、2つ目がその特別な値についてです。 まず最初は、void ポインタから。 void *pv; void ポインタとは、汎用 - generic - の特殊なポインタのことです。 void へは どのポインタの値であっても割り当て - assign - られますし、キャストを使えば 、それを元の型に戻すこともできます。 キャストが必要とされるのは、void ポインタでは間接参照 - dereference - する ことができないからです。 void *pv; int *pi; int i = 10; pi = &i; pv = pi; printf("%d\n", *pi); /* Prints 10 */ printf("%d\n", *(int *)pv); */ Also prints 10 */ 注意してほしいのは、キャストは間接参照を実行する "前に" つくられてることで す。このことは重要で、もしキャストが次のようだと、 (int *)*pv void ポインタが間接参照されてしまい、その正しくない参照からポインタを返すこ とになります。 どちらも、まったくのまちがいです。 (注) * 演算子のことも dereference という ... らしい。 2005-06-07 φ(-_-) ■ [lang]はじめての C 「ポインタ 2」 次が、null ポインタです。 どこも指さないポインタを特別に必要とするとき、指定する変数 - valuable - が null ポインタです。 この値は、ポインタ変数を安全に作動させたい場合や、malloc のような関数で、エ ラー時に返されるポインタに使われます。 null ポインタは、必要とされるどんな値 - any integral value - でも、それを 0 (ゼロ) として評価します。 使い方には 2つあって、必要なときは null を 0 に決めてしまうか、またはマクロ としてそれぞれの標準ヘッダで NULL と定義して呼び出すかです。 #include /* For NULL */ int *pl = 0; char *pc = NULL; null ポインタでは、間接参照することはできません。というのは、null がメモリ にアクセスすることの無効な箇所だからです。 単に、null を指定し、それでテストができるだけです。 if (pc != NULL) /* Do something */ if (pc != 0) /* Do something */ (注) stddef.h は、NULL や size_t, offsetof などをマクロとして定義しているヘッダ ファイル。 2005-06-08 φ(-_-) ■ [lang]はじめての C 「ポインタ 3」 ポインタとして返すことで (関数の) 返り値を効率よく改良することができ、変数 は、関数の外側で交換することが可能になります。 ただし、それを考慮に入れようとすれば、そこには 1つ大きな落し穴が待ち受けて います。 ローカル変数は、ブロックが閉じた時点でこわされて、そのメモリを回収されてし まいます。 そのため、ローカル変数をポインタにして返すということは、危険がいっぱいなの です。 int *f(void) { int i = 10; return *i; /* No! Returning a local variable is bad! */ } その場合でも、制御 - control - することで (例えば、malloc やその family に よって返されるような) メモリとして返せば、OK になります。 int *f(void) { int *i = malloc(sizeof(int)); return i; /* Okay, you control when the memory is released */ } 2005-06-09 φ(-_-) ■ [lang]はじめての C 「ポインタ 4」 ポインタは、実行中に - at runtime - (メモリの) 増減ができるので、データ構造 体では、さかんに使われます。 動的なサイズ設定 - dynamic sysing - では、プログラマに、malloc, calloc, realloc それと free を使うことで、ポインタを通してメモリ処理 - handle memory - をすることが求められます。 このようなデータ構造体は、(リンクリスト、二分木その他の) ノードや、(サイズ 変更の可能な配列 - resizable arrays - による) ブロックがその基本になってい ます。 配列と、求められる配列数に対して、その型の要素のサイズを増やす - multiplying - ための充分なメモリを確保する簡単な malloc をつくって、ポイン タを使ってみましょう。 int *parray = malloc(10 * sizeof(int)); if (parray != NULL) { /* Okay, use it */ } malloc, calloc それに realloc で注意してほしいのは、失敗したときにすべて null ポインタを返すことです。 上のコードは基本的には、静的な配列を使うのと同じになります。 int array[10]; ただし、大きな相違点として、realloc を使えば、parray のサイズの増減が、実行 中であっても、制御されるということがあります。 2つ目の大きな違いとしては、malloc, calloc あるいは realloc を使って割り当て たメモリを解放する - free the memory - ということを "必ず" 覚えておかないと いけない点です。 2005-06-10 φ(-_-) ■ [lang]はじめての C 「ポインタ 5」 もう一度注意してほしいのは、宣言や間接参照で余分に * をつけ加えたときの、ダ ブルポインタのシンタックスは、ポインタが 1つの場合に準じている、ということ です。 外部のポインタを間接参照するときには、よく確かめてください。 構造体のポインタへのポインタは、問題をひき起こすことがあり得るので、そのた め、メンバにアクセスするときには、最初の間接参照のところを ( と ) - paretheses - で囲まないといけません。 struct MYSTRUCT **ppmys; . . . . (**ppmys)->member; /* Works okay */ **ppmys->member; /* Doesn't work right :-( */ ポインタのところが - とびとびだけど - やっと終わった ... 2005-09-04 φ(-_-) ■[lang]はじめての C 7月11日分の日記がまちがっていたので、削除しました。訂正分は次のとおりです。 以前つくったクイックソートプログラムを元にして、シェルソートのコードを書いてみ る。 http://www4.kcn.ne.jp/~yoitiro/hatena/knr2nd_4.txt はじめに shell_sort ファイル /* shell_sort.c */ #include void insertion_sort(); void shell_sort(int *list, int n) { int h = 1; for ( ; h <= n / 9; h = 3 * h + 1) ; for ( ; h > 0; h /= 3) insertion_sort(list, h, n); } void insertion_sort(int *list, int left, int right) { int step, i; int temp; for (step = left; step < right; step++) { temp = list[step]; for (i = step; i >= left; i -= left) if (temp < list[i - left]) list[i] = list[i - left]; else break; list[i] = temp; } } read_array2 と print_array2 /* read_array2.c */ #include int read_array2(int a[], int limit) { int n = 0; while (n < limit && scanf("%d", &a[n]) != EOF) ++n; return n; } /* print_array2.c */ #include void print_array2(int a[], int n) { int i; for (i = 0; i < n; i++) { printf("%3d ", a[i]); if ((i + 1) % 10 == 0) putchar('\n'); } if (1 % 10 != 0) putchar('\n'); } 次が main ファイル /* s_main.c */ #include #include "s_header.h" main() { int *list; int n; n = read_array2(list, MAX); shell_sort(list, n); print_array2(list, n); return 0; } ヘッダファイルも /*s_header.h */ #define MAX 100 int read_array2(); int print_array2(); void shell_sort(); read_array2 と print_array2 では、仮引数が配列になってますがこの場合、ポインタ を使って渡しています。 あとはコンパイルして、クイックソートのときと同じく、random プログラムを使って確 認します。 $cc -c s_main.c shell_sort.c read_array2.c print_array2.c $cc -o s_sort s_main.o shell_sort.o read_array2.o print_array2.o $./random $./s_sort < random.txt (追記) クイックソートと、入出力のところが違ってました。あと、細かいミスもいろい ろと ... oLr