定本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 ナップザック問題の計算量
参考文献
索引