Dokusyo-nissi Bessitu

<< 2005/06 >>
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30

[Debian Memo] (for Woody)
[sekiyo HPへ]

[はじめてのC] C言語のページ (1)
[その 2] (2)
[その 3] ABC of C
[その 4] CPP World Tutorial (1) (by Prelude) linkrot
[その 5] The Standard C Library (Null)
[その 6] CPP World Tutorial (2) linkrot
[その 7] (3)
[その 8] (4)
[その 9] 作ってわかる Cプログラミング (1)
[その 10] (2)
[その 11] Arrays and Pointers in C
[その 12] Learning GNU C (1)
[その 13] (2)
[その 14] (3)
[その 15] (4)
[その 16] アドレスブック
[K & R 2nd] The C Programming Language (1)
[その 2] (2)
[その 3] (3)
[その 4] (4)
[その 5] (5)
[その 6] (6)

[my bookcase]

(サーチエンジンから 来られた方で 該当する
キーワードが 見つからないときには、上の
はてな検索窓から 再度検索してください ←
[日記] のほうを クリック)

 | 

2005-06-30 φ(-_-)

[]はじめての C

リンクリスト 3

先頭が ダミーで、末尾が null ▽

初期化:

struct Item list;
list->next = NULL;

item の後に n を 挿入:

n->next = item->next;
item->next = n;

item の後を 削除:

save = item->next;
item->next = item->next->next;

移動:

for (item = list->next; item != NULL; item = item->next)

先頭も 末尾も ダミー ▽

初期化:

struct Item list;
struct Item sentinel;
list->next = sentinel;
sentinel->next = sentinel;

item の後に n を 挿入:

n->next = item->next;
item->next = n;

item の後を 削除:

save = item->next;
item->next = item->next->next;

移動:

for (item = list->next; item != sentinel; item = item->next)

循環リスト ▽

初期化:

list->next = list;

item の後に n を 挿入:

n->next = item->next;
item->next = n;

item の後を 削除:

save = item->next;
item->next = item->next->next;

移動:

item = list;
do {
/* Work with item */
item = item->next;
} while (item != head);

すべての リンクリストの 組み合わせは、上で述べた 組み合わせの どれかに 従っています。

なので これら全部が 理解できれば、初歩的な リストの 進行コードを まちがえずに 読みとれますし、より 複雑な アルゴリズムの ロジックの基礎を 追いかけることも できます。

(注) do-while ループ

他の while や for ループと 違って、ループ本体が 実行された後で 条件式が 計算される。

そのため、ループ本体は、少なくとも 1回は 実行されることになる (KandR 2nd p77)。

(追記) 不注意による ミスを訂正。(7/4)

2005-06-29 φ(-_-)

[]はじめての C

リンクリスト 2

先に 進む前に、番兵について 少しだけ 述べてみましょう。

番兵には 3つの 型があります。 null ポインタ、ダミーノード (特別な、中身のない - invalid value - 項目で、番兵として 使うことが できます) それと 循環リンクです。

null ポインタ、それに ダミーノードは とても 簡単です。 でも、循環リンクって 何なんでしょう ?

循環リンクでは、リストを リング型の 構造体へと 変えて、いつ どこからでも、末尾を 見つけ出して - get the end - 次の項目へと 移ります。

リストの 各々の 型での、ほんの わずかな、基本となる 組み合わせ - basic conversation - は 次の とおりです。シンプルに 留めるために、ここでは (next ポインタのみの) 線形リスト - single linked list - を 使うことにします。

末尾が null ポインタ ▽

初期化:

list = NULL;

item の後に n を 挿入:

if (item == NULL) {
list = n;
list->next = NULL;
}
else {
n->next = item->next;
item->next = n;
}

item の後を 削除:

save = item->next;
item->next = item->next->next;

移動:

for (item = list; item != NULL; item = item->next)

2005-06-26 φ(-_-)

[]はじめての C

リンクリスト

リンクリストって 何なのだろう ?

リンクリストとは、要するに、それぞれの項目 - item - が その次を 指し示している、そんな項目が 集まった ものなんです。

|1| -> |2| -> |3| -> |4| -> |5| -> -

そのシーケンスは、番兵 - sentinel - と 呼ばれる 特別の 項目の 値を 最後尾に もっていて、多くの 場合では、シンプルな null ポインタが それに なります。

各々の 項目は ポインタを 伴った 構造体で、ポインタの 示す 先には 同じ型の "next" ポインタが あります。 ポインタが、全体の どこにあるかを 捜して 知らせるのです。

struct Item {
T data;
struct Item *next;
};

単純だけど、1つの 方向に 進む - travel - だけなら、これで 十分です (first から 始まって last で 終わるような)。

でも、行きすぎてから、その項目まで 帰りたいときには、"prev" ポインタという 別の ポインタが 必要になります。

struct Item {
T data;
struct Item *prev;
struct Item *next;
};

この構造体を 使うことで、前方にも 後方にも 進むことが できる、項目のリストを つくることが できます。

別の 言い方だと、全体の 中の それぞれの 項目が、どこに いても、手に 入るわけです。

簡単に 示してみましょう。

- <- |1| <- |2| <- |3| <- |4| <- |5| (prev)
|1| -> |2| -> |3| -> |4| -> |5| -> - (next)

まずい 図ですが、もし 読みとれるようでしたら、prev ポインタが next ポインタと 同じ 道のり - way - で 動くことに 注目してください。

例えば、リストの 最初の 項目の前に 番兵が あるとすると、prev ポインタの 最終点で それは 現れてきます。

リストの 中の どれかの 項目に アクセスする 際には、間接参照 - derefering - が 使えます。

次の 項目に 行く : item = item->next;

前の 項目へ 帰る : item = item->prev;

次の 次の 項目へ : item = item->next->next;

元にも 戻れる :p : item = item->next->prev;

ループを 用いるのも、たいていは 簡単です。

リストを 渡っていく 普通の 表現法は こんな 感じです。

for (item = list; item != NULL; item = item->next) {
visit(item); /* visit does something with a single item */
}

とっても 簡単で、それに、 ちょうど C や C++ で、配列を 渡っていくとき 用いる もう 1つの 別の 表現法と 同じようなことに 気が つくでしょう。

for (i = 0; i < size; i++) {
visit(array[i]);
}

2005-06-24 φ(-_-)

[]はじめての C

ついでに C Library の Apprendix C から、

引数 (argument) : 関数 呼び出し時に、1つの パラメータに 対し その初期値 - initial value - を 規定する 表記のこと。

表記法 (expression) : C プログラムでは、トークンの 連続した シーケンスを 指し、どのように 値を 計算するかを 指定する、そして 思わぬ結果 - side effect - が 起きることも。

型 (type) : 値の 属性。表示を 確定することで、その機能を 操作することが できる。または 関数の 属性。どの引数が 求められているか、と 返り値が 何かを 確定する。

表記 (representation) : さまざまな ビットパターンの もつ 内容により、データオブジェクトタイプを 表示する - represent - ため 使われる ビット数 - the number of bits - のこと。

(追記) やはり expression は、「式」と 訳したほうが わかりやすいかも しれません。

2005-06-22 φ(-_-)

[]はじめての C

(続き)

この本の スタイルとしては、できるだけ NULL を 使うようにします。

null ポインタが 差し出す、役に 立ちますよ という 合図 - useful signal - に 気が ついた からです。

関数ポインタには、null ポインタ定数を 生成する - generate - キャスト型を 使います。

また キャストは、 特に、求められる 型が void への ポインタとは 別な 場合、関数への引数を、可変引数リストを 引き受けるために 用います。

NULL が、2分の1 ダースもの 異なった ヘッダで 宣言されているのに 気づいたでしょう。

それは、このマクロを 使うための 選択を 容易に するためです。

1つだけ アドバイスすると すれば、いつでも 一定の スタイルを 選んでおき、それを 見限ることの ないように すること、ですね。(p221)

(追記) ちょこっと 訂正。

2005-06-21 φ(-_-)

[]はじめての C

(続き)

このような 実装のうち、最も 安全な NULL の 定義が (void *)0 です。

保証されては いませんが、しかし、この void への ポインタは、その表記が 他の どのポインタとも 同じになります。

ただし、もちろん、関数への ポインタには 割り当てられず 適合も しません。

その意味は、全般的な - universal - null ポインタ定数としての NULL は 書くことが できないからです。

また、任意の データオブジェクトポインタの 位置にある 引数表記としても、安全に 使うことは できません。

単に、文字ポインタ - character pointer - のように、または 一般的な - generic - void への ポインタのように 正確に ふるまうことを 保証されている、ということです。(p221)

2005-06-20 φ(-_-)

[]はじめての C

(続き)

初期の C の 実装では、すべての ポインタが 同じ表記法 - representation - を もっていました。

通常、この表記法だと、integer 型の int か long の 1つと 同じサイズに なります。

ですので、10進法定数 - decimal constant - の 0 または 0L の いずれかが、うまいぐあいに、どの型に ついても、 null ポインタのように 振舞います。

2つの 定数のうちの 1つを NULL で 定義すれば、任意のポインタ - arbitrary pointer - に 対して 割り当てることが できます。

このマクロは、特に、引数表記 - argument expression - として 役立ちます。

注意してほしいのは、この表記法が、いくつかの ポインタの 型を もつ、null ポインタ定数だと いうことです。(p220)

2005-06-19 φ(-_-)

[]はじめての C

(続き)

現在の プログラミングスタイルでは、呼び出された すべての 関数に対して、プロトタイプ - function prototype - が 宣言されます。

にもかかわらず、関数の 引数 - function argument - が どこかは、パラメータ宣言と 対応していない という 重要な コンテクスト - context - が いまだに 存在しています。

これは、関数が 呼び出された 時点で、可変引数リスト - variable argument list - を 引き受けている、ということです (例えば <stdio.h> で 宣言される printf が そうです)。

特別な 引数については、古い C の ルールが 適用されます。

少数の 例外を 除くと、多くの スタンダードな 型変換 - type conversion - では、各変数を 正しく 受け取ることは、プログラマの 自由に まかせられて - be up to you - います。(p220)

2005-06-18 φ(-_-)

[]miscellanies

崎山氏の 理不尽な 暴露工作によって、sarasa さんの page が 閉鎖された。

彼の 意図が どこに あったかに ついて ネット上で 議論されているが、それを 一言に 集約すると intelligence という ことだろう。

辞書を 引くと、知性、情報 あるいは 報道、と 載っているが、この場合 "謀略" と いったほうが 本来の 意味に 近い。 情報操作の "情報" が これに あたる。

また、intelligence は 諜報とも 訳せるが、それだと 国家による 市民生活の 監視という 意味が 強調されて、上の 論旨とは ずれてしまう。 どうも この単語は うまく 訳せない。

* * *

かつて 東欧の 国々が 社会主義体制から 離脱していったとき、意外なほど 影響を 与えたのが、VOA (Voice of America) による 謀略宣伝で あった (その 経緯を、マスメディアでは 東欧の 「民主化」と 称しているが、ぼくは 地方権力による 民族国家の 分割/資本主義的 再編成だと 考えている)。

テレビジョンで VOA が 流す 映像を 見ながら、人々は 思ったわけだ、「西ヨーロッパには "ハンバーガーショップ" がある !」と。

発信元の CIA でさえ、こんな 単純なことが、人々の 心情を 動かすとは 考えていなかった フシが ある。 連中は その頃、共産党内部の 醜態を 暴くことに 忙しかったのだから。

この「映像による 謀略」という 手法は、ヒトラーのラジオ 以来、最大の 成功例だろう。 ただし、成果は そこまでで あり、それ以後 急激に その 効力を 減少させてしまった。

その 理由の 1つに、放送網に 対する コントロールの 完成が あげられる。

U.S.A.だけでなく、ヨーロッパに おいても フランスを 典型として、テレビジョン ネットワークが 完全に 政府の コントロール下に 収まってしまったのだ。

「敵対する 国家の 非難」 と 「自らの 体制への 賞賛」 とが、連日 どのスタジオからも 流されれば、いくら スキャンダルで 味付けしたところで、受け取る 側としては やりきれない。 たとえ 口では 同意したと しても、だ。

自分たちの 実際の 生活が、それぞれが 考える 良い方向に 向かっているのなら 別だが、それは 現実には あり得ない。

かつて 東欧で、VOA の 流す 画面が 信じられたのは、少なくとも 自分たちの 体制からは "自由" だと 人々が 思った 結果だろう。 その多くが 幻影でしか なかったとしても。

* * *

インターネットの 世界では、その システム上 "自立分散性" という 特性が あり、それを 一定の コントロールの 下に 置くことは 非常に 困難だ。

現在、警察/検察が、法に 違反してまで、プロバイダーに log の 提出を 強要するのには ここに 理由がある。

* * *

たとえ インターネットといえども、現実の 社会の上に 成り立っている 以上、直接 間接に 影響を 被るのは 免れ得ない。

2ちゃんねるへの マスメディア側からの すり寄りが 懸念されているが、もし 2ちゃんねるが 崩壊するとすれば、それは 内部からだろう。 意図的な 情報を - 虚偽で あることを 隠蔽する 必要から "正確な" 事実を つけて - 流すことも 考えられる。 これが intelligence だ。

たとえ 膨大な 情報量を もっていたところで、それが ネット上にしか 存在しないのであれば、議論が 活発化しているように 見えたとしても、結局 人々は 掲示板から 離れていってしまう。

マスメディアを 流れる ニュースを 考えれば、そのことが よく 理解できるはずだ。そして それを - 意図せずして - 焙りだしたのも インターネットの 世界だった。 なにも 連中と 同じ 轍を踏む 必要は ない。

(追記) 3つの part に (4つ かな?) 分けてみた ...

2005-06-17 φ(-_-)

[]はじめての C

(続き)

NULL は、たいていの 一般的な null ポインタ変数としての 目的に 適っています。

データオブジェクトポインタとして 用いることで、プログラムでは、宣言された - declare - (または 割り当てられている - allocate -) データを含まない オブジェクトを 指し示します。

216 ページで 触れたように、このマクロは、0, 0L または (void *)0 の どれかを 定義 - definition - として もつことが できます。

最後の 定義ですと、他の オブジェクトポインタとも 一致します。

ただし、関数へのポインタ - function pointer -とだけは 矛盾してしまいます。

というのも、次のようには 書けないからです。

int (*pfun)(void) = NULL; /* WRONG */

この変換 - translation - だと、たぶん エラーが でて - complain - しまいます。この表記された型 - expression type - は、初期値として セット - initialize - させたい データオブジェクトと 一致しません。(p220)

(注) 関数へのポインタ

tutorial には、引数を もたず、返り値のない 例が あげられている。

main()
{
void (*pf)(void); /* 関数のポインタの宣言 */
void f(void)
{
printf("Hello, world.\n");
}
/* pf に 値をセット */
pf = f;
/* 呼び出しは 次のどちらでも OK */
(*pf)();
pf();
}

(追記) コードが アヤフヤだったので、書き直し。

nucnuc 2005/06/23 01:40 はじめまして。nucと申します。
関数の中で関数を宣言するのはgcc拡張と呼ばれるgccというコンパイラのみで使える技で、http://www-cms.phys.s.u-tokyo.ac.jp/~naoki/CIPINTRO/gccextend.html
でも警告されていますが、「はじめての C」ではよろしくないかと。

sekiyosekiyo 2005/06/23 20:12 nuc さん、こんばんは。(ちょっと 返事が 遅れました)
そうですね。
Linux では $cc で コンパイルしても、gcc に 自動的に リンクされるのを 忘れてました。

2005-06-16 φ(-_-)

[]はじめての C

ヘッダファイルの stddef.h が tutorial に チラッと でてきたので、The Standard C Library を のぞいてみた。

Standard C Library, The

手元に あっても なかなか 読むことが ないし、NULL の ところだけでも チェックしてみる。

NULL - the macro NULL - を 実現させるには、単に、もっとも 適切な いくつかの 選択肢 - 0, 0L あるいは (void *)0 - を 選ぶことです。

適正に 作動させるため、ポインタの型の 引数として、関数原型 - function prototype - を 欠いている void型を (あるいは char, signed char または unsigned char) を 1種類 選択します。

(NULL の詳細の 多くについては、220 ページで 検討します)

より 簡潔に するのであれば、おそらく、 C 固有の null ポインタ定数 - null-pointer constant - を 含むことに なります。

何度かは、そのような 忠告が 生じることも あるでしょう。

にもかかわらず、通常では、NULL が 用いられる場合の 方法としては、この種類の なかの 1つで 十分です。(p216)

(訂正) 本の名前を まちがってた ... oLr

2005-06-11 φ(-_-)

[]useless tips

tutorial の 訳で ど〜も 煮詰まっていて、調子が よくない。っていうか、他のことに 興味が 向いてこない。

それでは ということで、debian sarge も リリースされたことだし と思い、ちょっと 手を出してみました。

結論から いえば ... 1日 つぶれてしまった。

はじめは woody から アップグレードしてみる。

http://www.jp.debian.org/releases/sarge/i386/release-notes.ja.txt

うまくいったら sarge に 移れると 思ったけど、そんなわけは ない。X-window の 設定で、どうしても 画面が 15% ほど 縮まってしまう。

次が、新規インストールに 挑戦、フロッピー 2枚に 収まる インストーラーを ダウンロードしてきて、実行する。

ハードからでなく、フロッピーから 起動させることには 成功。次に、デスクトップを 選択したら、Open Office が ダウンロードされてきた。

これは ちょっと 困る。今の サイズ - ウィンドマネージャーが twm でブラウザが w3m です - が 丸木船だとすると、戦艦なみだ。

後から、日本語入力の 設定も しないといけないし - 実際に やりましたが - 他にも やるべき作業が 山ほど ありそう。mozilla にも 少し 不具合が ...

というわけで、3回目は 元の woody に 戻すことにする。ところが sarge の リリースに 伴って、サーバにある woody の ファイルが、大幅に 変更されている。

インストール用の CD-R が なければ、元には 戻りませんでした。

はてダラの 設定が 済んで、なんとか 元どおりに なった時には、夜に なってた。ほんとは、上の debian memo にも 書き直すところが でてきたんだけど、限界です。

明日は ゆっくりと 休みたい。

2005-06-10 φ(-_-)

[]はじめての C

ポインタ 5

もう一度 注意してほしいのは、宣言や 間接参照で 余分に * を つけ加えたときの、ダブルポインタの シンタックスは、ポインタが 1つの場合に 準じている、ということです。

外部の ポインタを 間接参照するときには、よく 確かめてください。

構造体の ポインタへの ポインタは、問題を ひき起こすことが あり得るので、そのため、メンバに アクセスするときには、最初の 間接参照のところを ( と ) - paretheses - で 囲まないと いけません。

struct MYSTRUCT **ppmys;
. . . .
(**ppmys)->member; /* Works okay */
**ppmys->member; /* Doesn't work right :-( */

ポインタの ところが - とびとび だけど - やっと 終わった ...

2005-06-09 φ(-_-)

[]はじめての 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-08 φ(-_-)

[]はじめての 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-07 φ(-_-)

[]はじめての C

ポインタ 2

次が、null ポインタです。

どこも 指さない ポインタを 特別に 必要とするとき、指定する 変数 - valuable - が null ポインタです。

この値は、ポインタ変数を 安全に 作動させたい場合や、malloc のような 関数で、エラー時に 返される ポインタに 使われます。

null ポインタは、必要とされる どんな値 - any integral value - でも、それを 0 (ゼロ) として 評価します。

使い方には 2つ あって、必要なときは null を 0 に 決めてしまうか、または マクロとして それぞれの 標準ヘッダで NULL と 定義して 呼び出すかです。

#include <stddef.h> /* 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-06 φ(-_-)

[]はじめての 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-02 φ(-_-)

[]はじめての 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-01 φ(-_-)

[]はじめての 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 に なったら 即、シェルソートを 挿入整列法に する、ということを 忘れては いませんね ?

ここでは うまい具合に、挿入整列法のために コードを 再実装しなくても、以前 書いておいた関数を 使うことができます。

 | 

[シラノの新聞]

[枇杷と柿]

[馬葉礼 談話]

[My Links]

[Network Archives]


[かうんた→ 539993]