アルゴリズム

定本 Cプログラマのためのアルゴリズムとデータ構造

近藤 嘉雪

ソフトバンククリエイティブ

第1部 アルゴリズムとデータ構造の基本1. アルゴリズムとは?

1. アルゴリズムとは?

  • 1.1 はじめに
  • 1.2 アルゴリズムとデータ構造の関係
  • 1.3 なぜアルゴリズムを勉強するのか?

2. 計算量

  • 2.1 アルゴリズムの性能の基準
    • 2.2.1 線形探索法による探索の計算量
    • 2.2.2 二分探索法による探索の計算量
    • 2.2.3 データの登録に必要な計算量
    • 2.2.4 線形探索法と二分探索法の比較
    • 2.2.5 ハッシュ法
    • 2.2.6 アルゴリズムを選択する基準

3. データ構造とは?

  • 3.1 抽象データ型
  • 3.2 データ構造の実現
    • 3.2.1 基本データ型
    • 3.2.2 列挙型
    • 3.2.3 配列と構造体
    • 3.2.4 ポインタ

第2部 基本的なデータ構造

4. 配列

  • 4.1 リスト
  • 4.2 スタック
  • 4.3 待ち行列
  • 4.4 配列によるデータ構造の実現
    • 4.4.1 リストの実現
    • 4.4.2 スタックの実現
    • 4.4.3 待ち行列の実現

5. 連結リスト

  • 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. 木構造

  • 6.1 木構造とは?
  • 6.2 順序木と無順序木
  • 6.3 二分木
  • 6.4 木のなぞり
    • 6.4.1 木をなぞる手順
    • 6.4.2 行きがけ順のなぞり
    • 6.4.3 通りがけ順のなぞり
    • 6.4.4 帰りがけ順のなぞり
  • 6.5 数式の木
  • 6.6 木の実現

第3部 探索

7. 探索とは?

  • 7.1 探索という操作
  • 7.2 線形探索法と二分探索法

8. ハッシュ法

  • 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. 二分探索木

  • 9.1 二分探索木とは?
  • 9.2 二分探索木の操作
    • 9.2.1 二分探索木の探索
    • 9.2.2 二分探索木への挿入
    • 9.2.3 二分探索木からの削除
  • 9.3 二分探索木の性質

10. 平衡木

  • 10.1 平衡木とは?
  • 10.2 AVL木
    • 10.2.1 AVL木の考え方
    • 10.2.2 AVL木の操作
  • 10.3 B木

第4部 整列

11. 整列とは?

  • 11.1 整列という操作
    • 11.1.1 内部整列と外部整列
    • 11.1.2 比較による整列と比較によらない整列
  • 11.2 整列アルゴリズムの種類
  • 11.3 整列の計算量
  • 11.4 安定な整列

12. 単純な整列アルゴリズム

  • 12.1 単純な整列アルゴリズムとは?
  • 12.2 バブルソート
  • 12.3 選択ソート
  • 12.4 挿入ソート
  • 12.5 単純な整列アルゴリズムの性能

13. シェルソート

  • 13.1 シェルソートの原理
  • 13.2 シェルソートの計算量
  • 13.3 増分の選択
  • 13.4 シェルソートのプログラム

14. クイックソート

  • 14.1 クイックソートの原理
    • 14.1.1 クイックソートの考え方
    • 14.1.2 分割のアルゴリズム
  • 14.2 クイックソートのプログラム
  • 14.3 クイックソートの計算量
  • 14.4 クイックソートの改善

15. マージソート

  • 15.1 マージソートの原理
    • 15.1.1 マージ
    • 15.1.2 マージソートのアルゴリズム
  • 15.2 配列によるマージソート
  • 15.3 マージソートの性質
  • 15.4 連結リストによるマージソート
  • 15.5 外部整列
    • 15.5.1 外部記憶の性質
    • 15.5.2 マージソートを利用した外部整列

16. ヒープソート

  • 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. 比較によらないソート

  • 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 基数ソートの性質

第5部 文字列の探索

18. 文字列の探索

  • 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. 正規表現

  • 19.1 正規表現とは?
  • 19.2 正規表現の実現
    • 19.2.1 正規表現とオートマトン
    • 19.2.2 非決定性有限オートマトンと決定性有限オートマトン
    • 19.2.3 正規表現からNFAへの変換
    • 19.2.4 NFAからDFAへの変換
  • 19.3 正規表現のプログラム

第6部 いろいろなアルゴリズム

  • 20. バックトラック法
    • 20.1 バックトラック法とは?
    • 20.2 8クイーン問題
      • 20.2.1 8クイーン問題とは?
      • 20.2.2 8クイーンの解法
      • 20.2.3 バックトラック法の実現
      • 20.2.4 8クイーンのプログラム
      • 20.2.5 すべての解を求める

21. 動的計画法

  • 21.1 動的計画法とは?
  • 21.2 ナップザック問題
    • 21.2.1 ナップザック問題とは?
    • 21.2.2 ナップザック問題の解き方
    • 21.2.3 ナップザック問題を解くプログラム
    • 21.2.4 ナップザック問題の計算量

22. メモリ管理アルゴリズム

  • 22.1 メモリ管理とは?
  • 22.2 メモリ管理アルゴリズム
    • 22.2.1 静的割り当てと動的割り当て
    • 22.2.2 動的割り当ての分類
    • 22.2.3 ガベージコレクタ
    • 22.2.4 断片化と詰め直し
    • 22.2.5 双方向リストによるメモリ管理
  • 22.2 メモリ管理のプログラム

23. キャッシュ

  • 23.1 キャッシュとは?
  • 23.2 キャッシュメモリ
  • 23.3 I/Oへの応用
    • 23.3.1 ディスクのバッファリング
    • 23.3.2 ディスクのキャッシング
    • 23.3.3 LRU法
  • 23.4 出力用ファイルのキャッシング