1. アルゴリズムとは? 2
1.1 はじめに
1.2 アルゴリズムとデータ構造の関係
1.3 なぜアルゴリズムを勉強するのか?
2. 計算量 9
2.1 アルゴリズムの性能の基準
2.2.1 線形探索法による探索の計算量
2.2.2 二分探索法による探索の計算量
2.2.3 データの登録に必要な計算量
2.2.4 線形探索法と二分探索法の比較
2.2.5 ハッシュ法
2.2.6 アルゴリズムを選択する基準
3. データ構造とは? 25
3.1 抽象データ型
3.2 データ構造の実現
3.2.1 基本データ型
3.2.2 列挙型
3.2.3 配列と構造体
3.2.4 ポインタ
4. 配列 34
4.1 リスト
4.2 スタック
4.3 待ち行列
4.4 配列によるデータ構造の実現
4.4.1 リストの実現
4.4.2 スタックの実現
4.4.3 待ち行列の実現
5. 連結リスト 50
5.1 連結リスト
5.1.1 連結リストとは?
5.1.2 連結リストの基本的性質
5.1.3 連結リストとメモリ管理
5.1.4 連結リストの操作
5.1.4.1 要素の挿入
5.1.4.2 要素の削除
5.1.4.3 境界条件の扱い
5.2 循環リスト
5.2.1 循環リストとは?
5.2.2 循環リストの操作
5.2.3 リストの頭を用いた循環リスト
5.3 双方向リスト
5.3.1 双方向リストとは?
5.3.2 双方向リストの操作
5.4 多重リスト構造
6. 木構造 86
6.1 木構造とは?
6.2 順序木と無順序木
6.3 二分木
6.4 木のなぞり
6.4.1 木をなぞる手順
6.4.2 行きがけ順のなぞり
6.4.3 通りがけ順のなぞり
6.4.4 帰りがけ順のなぞり
6.5 数式の木
6.6 木の実現
7. 探索とは? 106
7.1 探索という操作
7.2 線形探索法と二分探索法
8. ハッシュ法 108
8.1 ハッシュ法の原理
8.2 衝突
8.3 チェイン法
8.3.1 チェイン法の原理
8.3.2 チェイン法のプログラム
8.3.3 チェイン法の解析
8.4 オープンアドレス法
8.4.1 オープンアドレス法の原理
8.4.2 オープンアドレス法のプログラム
8.4.3 再ハッシュ手順
8.4.4 オープンアドレス法の解析
8.5 ハッシュ関数
8.6 ハッシュ法の応用
8.7 ハッシュ法の性質
9. 二分探索木 130
9.1 二分探索木とは?
9.2 二分探索木の操作
9.2.1 二分探索木の探索
9.2.2 二分探索木への挿入
9.2.3 二分探索木からの削除
9.3 二分探索木の性質
10. 平衡木 148
10.1 平衡木とは?
10.2 AVL木
10.2.1 AVL木の考え方
10.2.2 AVL木の操作
10.3 B木
11. 整列とは? 178
11.1 整列という操作
11.1.1 内部整列と外部整列
11.1.2 比較による整列と比較によらない整列
11.2 整列アルゴリズムの種類
11.3 整列の計算量
11.4 安定な整列
12. 単純な整列アルゴリズム 185
12.1 単純な整列アルゴリズムとは?
12.2 バブルソート
12.3 選択ソート
12.4 挿入ソート
12.5 単純な整列アルゴリズムの性能
13. シェルソート 194
13.1 シェルソートの原理
13.2 シェルソートの計算量
13.3 増分の選択
13.4 シェルソートのプログラム
14. クイックソート 203
14.1 クイックソートの原理
14.1.1 クイックソートの考え方
14.1.2 分割のアルゴリズム
14.2 クイックソートのプログラム
14.3 クイックソートの計算量
14.4 クイックソートの改善
15. マージソート 217
15.1 マージソートの原理
15.1.1 マージ
15.1.2 マージソートのアルゴリズム
15.2 配列によるマージソート
15.3 マージソートの性質
15.4 連結リストによるマージソート
15.5 外部整列
15.5.1 外部記憶の性質
15.5.2 マージソートを利用した外部整列
16. ヒープソート 237
16.1 ヒープソートの原理
16.1.1 探索の整列への応用
16.1.2 優先順位付き待ち行列
16.1.3 半順序木
16.1.4 ヒープ
16.1.5 ヒープによるdelete_minの実現
16.1.6 ヒープによるinsertの実現
16.2 ヒープソートのプログラム
17. 比較によらないソート 257
17.1 比較によらない整列アルゴリズム
17.2 ビンソート
17.2.1 ビンソートの原理
17.2.2 ビンソートのプログラム
17.2.3 ビンソートの性質
17.3 分布数え上げソート
17.3.1 分布数え上げソートの原理
17.3.2 分布数え上げソートのプログラム
17.3.3 分布数え上げソートの性質
17.4 基数ソート
17.4.1 基数ソートの原理
17.4.2 基数ソートのプログラム
17.4.3 基数ソートの性質
18. 文字列の探索 276
18.1 文字列に対する探索
18.2 力まかせのアルゴリズム
18.2.1 力まかせのアルゴリズムの原理
18.2.2 力まかせのアルゴリズムの計算量
18.3 洗練されたアルゴリズム
18.4 Knuth-Morris-Prattのアルゴリズム
18.4.1 KMP法の原理
18.4.2 KMP法の性質
18.5 Boyer-Mooreのアルゴリズム
18.5.1 BM法の原理
18.5.2 BM法の実際
18.5.3 BM法のプログラム
18.5.4 BM法の性質
19. 正規表現 297
19.1 正規表現とは?
19.2 正規表現の実現
19.2.1 正規表現とオートマトン
19.2.2 非決定性有限オートマトンと決定性有限オートマトン
19.2.3 正規表現からNFAへの変換
19.2.4 NFAからDFAへの変換
19.3 正規表現のプログラム
20. バックトラック法 332
20.1 バックトラック法とは?
20.2 8クイーン問題
20.2.1 8クイーン問題とは?
20.2.2 8クイーンの解法
20.2.3 バックトラック法の実現
20.2.4 8クイーンのプログラム
20.2.5 すべての解を求める
21. 動的計画法 348
21.1 動的計画法とは?
21.2 ナップザック問題
21.2.1 ナップザック問題とは?
21.2.2 ナップザック問題の解き方
21.2.3 ナップザック問題を解くプログラム
21.2.4 ナップザック問題の計算量
22. メモリ管理アルゴリズム 363
22.1 メモリ管理とは?
22.2 メモリ管理アルゴリズム
22.2.1 静的割り当てと動的割り当て
22.2.2 動的割り当ての分類
22.2.3 ガベージコレクタ
22.2.4 断片化と詰め直し
22.2.5 双方向リストによるメモリ管理
22.2 メモリ管理のプログラム
23. キャッシュ 382
23.1 キャッシュとは?
23.2 キャッシュメモリ
23.3 I/Oへの応用
23.3.1 ディスクのバッファリング
23.3.1 ディスクのキャッシング
23.3.1 LRU法
23.4 出力用ファイルのキャッシング
近藤 嘉雪 (こんどう よしゆき)
Perlの「ラクダ本」「リャマ本」の訳者です。 著書に「定本 Cプログラマのためのアルゴリズムとデータ構造」 「定本Javaプログラマのためのアルゴリズムとデータ構造」があります。 現在某ネット企業に勤務。
詳しいプロフィールはこちらをご覧ください。