セジウィック：アルゴリズムC 第1~4部 基礎・データ構造・整列・探索
セジウィック：アルゴリズムC 第1〜4部 ―基礎・データ構造・整列・探索―
近代科学社
著者：Robert Sedgewick
訳者：野下浩平、星守、佐藤創、田口東
まえがき
第1部 基礎
第1章 はじめに
1.1 アルゴリズム
1.2 例題――連結性問題
1.3 合併-発見アルゴリズム
1.4 展望
1.5 話題の概要
第2章 アルゴリズム解析の原理
2.1 実現と実験による解析
2.2 アルゴリズムの解析
2.3 関数の増加度
2.4 O記法
2.5 基本漸化式
2.6 アルゴリズム解析の例
2.7 保証，予測，限界
第1部の参考文献
第2部 データ構造
第3章 基本データ構造
3.1 部品
3.2 配列
3.3 リンクによるリスト
3.4 初等的なリスト処理
3.5 リストに対する記憶領域の割付け
3.6 文字列
3.7 複合データ構造
第4章 抽象データ型
4.1 抽象オブジェクトとオブジェクトの集合
4.2 プッシュダウンスタック抽象データ型
4.3 スタック抽象データ型クライアントの例
4.4 スタック抽象データ型の実現
4.5 新しい抽象データ型の生成
4.6 FIFOキューと一般化キュー
4.7 要素の重複と添字要素
4.8 一級抽象データ型
4.9 応用に基づく抽象データ型
4.10 展望
第5章 再帰と木
5.1 再帰アルゴリズム
5.2 分割統治法
5.3 動的計画法
5.4 木
5.5 2分木の数学的な性質
5.6 木の走査
5.7 再帰的な2分木アルゴリズム
5.8 グラフの走査
5.9 展望
第2部の参考文献
第3部 整列
第6章 初等的な整列法
6.1 ゲームのルール
6.2 選択整列法
6.3 挿入整列法
6.4 バブル整列法
6.5 初等的整列法の性能
6.6 シェルソート
6.7 ほかの型のデータの整列法
6.8 添字整列とポインタ整列
6.9 リンクリストの整列
6.10 キー添字計数法
第7章 クイックソート
7.1 基本アルゴリズム
7.2 クイックソートの性能
7.3 スタックの大きさ
7.4 小さい部分ファイル
7.5 3要素の中央値
7.6 重複したキー
7.7 文字列とベクトル
7.8 選択
第8章 併合とマージソート
8.1 2ウェイ併合
8.2 抽象的なその場の併合
8.3 トップダウン型マージソート
8.4 基本アルゴリズムの改良
8.5 ボトムアップ型マージソート
8.6 マージソートの性能
8.7 リンクリストによるマージソート
8.8 再帰呼出しの再考
第9章 順位キューとヒープソート
9.1 初等的な実現
9.2 ヒープのデータ構造
9.3 ヒープのアルゴリズム
9.4 ヒープソート
9.5 順位キューADT
9.6 添字による順位キュー
9.7 2項キュー
第10章 基数整列
10.1 ビット，バイト，ワード
10.2 2進クイックソート
10.3 MSD 基数整列法
10.4 3分岐基数クイックソート
10.5 LSD 基数整列法
10.6 基数整列法の性能
10.7 線形未満の時間の整列法
第11章 特殊目的の整列法
11.1 Batcher奇偶マージソート
11.2 整列ネットワーク
11.3 外部整列
11.4 整列-併合の実現
11.5 並列的整列-併合
第3部の参考文献
第4部 探索
第12章 記号表と2分探索木
12.1 記号表抽象データ型
12.2 キー添字探索
12.3 逐次探索
12.4 2分探索法
12.5 2分探索木
12.6 BSTの性能特性
12.7 間接的2分探索木
12.8 根への挿入
12.9 他のADT関数のBSTによる実現
第13章 平衡木
13.1 ランダム化BST
13.2 スプレイBST
13.3 トップダウン2-3-4木
13.4 赤黒木
13.5 スキップリスト
13.6 性能特性
第14章 ハッシュ法
14.1 ハッシュ関数
14.2 分離連鎖法
14.3 線形探査法
14.4 2重ハッシュ法
14.5 動的ハッシュ法
14.6 まとめ
第15章 基数探索
15.1 離散探索木
15.2 トライ
15.3 パトリシア
15.4 マルチウェイ基数探索法
15.5 テキスト-文字列-索引アルゴリズム
第16章 外部探索
16.1 ゲームのルール
16.2 索引順アクセス法
16.3 B木
16.4 拡張可能ハッシュ法
16.5 まとめ
第4部の参考文献
訳者あとがき
索引