アルゴリズム

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

近藤嘉雪
ソフトバンククリエイティブ

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

  • 1 アルゴリズムとは?
    • 1.1 はじめに
    • 1.2 アルゴリズムとデータ構造の関係
    • 1.3 なぜアルゴリズムを勉強するのか?
  • 2 計算量
    • 2.1 アルゴリズムの性能の基準
    • 2.2 計算量
      • 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 列挙型
    • 3.3 ジェネリック型

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

  • 4 配列
    • 4.1 リスト
    • 4.2 スタック
    • 4.3 待ち行列
    • 4.4 配列によるデータ構造の表現
      • 4.4.1 リストの表現
      • 4.4.2 スタックの実現
      • 4.4.3 スタックの使用例 - 逆ポーランド電卓
      • 4.4.4 待ち行列の実現
  • 5 連結リスト
    • 5.1 連結リスト
      • 5.1.1 連結リストとは?
      • 5.1.2 連結リストの基本的性質
      • 5.1.3 連結リストの操作
      • 5.1.4 連結リストに対するイテレータ
    • 5.2 循環リスト
      • 5.2.1 循環リストとは?
      • 5.2.2 循環リストの操作
      • 5.2.3 リストの頭を用いた循環リスト
    • 5.3 双方向リスト
      • 5.3.1 双方向リストとは?
      • 5.3.2 双方向リストの操作
      • 5.3.3 双方リストを実現する
  • 6 木構造
    • 6.1 木構造とは?
    • 6.2 順序木と無順序木
    • 6.3 二分木
    • 6.4 木のなぞり
      • 6.4.1 木をなぞる手順
      • 6.4.2 行きがけ順のなぞり
      • 6.4.3 通りがけ順のなぞり
      • 6.4.4 帰りがけ順のなぞり
      • 6.4.5 二分木をなぞるメソッド
    • 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木
      • 10.3.1 B木の考え方
      • 10.3.2 B木の操作
      • 10.3.3 B木のプログラム
      • 10.3.4 B*木

第4部 整列

  • 11 整列とは?
    • 11.1 整列という操作
      • 11.1.1 内部整列と外部整列
      • 11.1.2 比較による整列と比較によらない整列
    • 11.2 整列アルゴリズムの種類
    • 11.3 整列の計算量
    • 11.4 安定な整列
    • 11.5 java.util.Arraysクラスのsortメソッド
  • 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 Heapクラス:ヒープを実現する
      • 16.1.6 ヒープによるdeleteMinの実現
      • 16.1.7 ヒープによる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法の性質

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

  • 19 バックトラック法
    • 19.1 バックトラック法とは?
    • 19.2 8クイーン問題
      • 19.2.1 8クイーン問題とは?
      • 19.2.2 8クイーンの解法
      • 19.2.3 バックトラック法の実現
      • 19.2.4 8クイーンのプログラム
      • 19.2.5 すべての解を求める
  • 20 動的計画法
    • 20.1 動的計画法とは?
    • 20.2 ナップザック問題
      • 20.2.1 ナップザック問題とは?
      • 20.2.2 ナップザック問題の解き方
      • 20.2.3 ナップザック問題を解くプログラム
      • 20.2.4 ナップザック問題の計算量

参考文献
索引