Dokusyo-nissi Bessitu

<< 2005/07 >>
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
31

[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-07-07 φ(-_-)

[]はじめての C

リンクリスト 8

リンクを ソートするのは 楽しい課題です。そこで 基本的な ソートの実装については、読者に 残しておくことにしましょう。

詳細な ソートの説明を するつもりは ありません。というのも、この tutorial が リンクリストについての ものだからです。ここでは、私の 小さな リストライブラリにある マージソートを 取り上げてみます。

(プログラムは 省略)

マージソートの アルゴリズムは、リンクリストであっても、変わりは ありません。ですので、どんな アルゴリズムの本を 開いても、そこには このコード そのままの やり方が 見つかるでしょう。

マージソートは、NlogN time での 実行が 保証され、また 安定性に 強い、よくできた 汎用の ソートアルゴリズムです。

競争相手である クイックソートヒープソートでは、一番の 決定的要素としての 安定性を 欠いているのです。

リンクリストを ソートする 他の 代わりとなる やり方は、初めのうちは、明らかでは ありません。しかし 二分木 - binary tree - では、いつでも この ソートするという 事実を 活用します。

単に リストを 渡っていくのであれば、最初の 項目を 削除して、二分木に 挿入します。このとき、規則に 則って tree を たどっていき、新しい リストの 末端へと 挿入していくのです。


人が やらせようと することとは 関係なく、たびたび、構造体の間での 交換 - switch - が 意味を もつことが あります。

この続きは、次の トピックで ...

最後の ところが よく わからない。誤訳かも ?

(追記) 一部 訳文を訂正。

 | 

[シラノの新聞]

[枇杷と柿]

[馬葉礼 談話]

[My Links]

[Network Archives]


[かうんた→ 553163]