Javaデータ構造とアルゴリズム基礎講座

2019年1月26日

技術評論社

著者：長尾和彦

はじめに
目次

第1章アルゴリズムと計算量
1.1 アルゴリズムとは
1.1.1 鶴亀算
1.1.2 問題の認識と解決
1.1.3 アルゴリズムの構造とフローチャート
1.1.4 アルゴリズムの停止性
1.2 アルゴリズムの性能評価と計算量
1.2.1アルゴリズムの評価基準
1.3 計算量の評価
1.3.1 最悪の場合の実行時間
1.3.2 計算量の漸近的な評価
1.3.3 O記法
1.3.4 計算量の和・積の公式
まとめ・演習問題

第2章アルゴリズムの設計手法
2.1 力ずく法
2.1.1 組み合わせの作り方
2.2 欲張り法
2.3分割統治法
2.3.1 機能的な分割の方法
2.3.2 再帰的定義
2.4 動的計画法
2.4.1 分割統治法がうまくいかない例
まとめ・演習問題

第3章配列
3.1 配列
3.1.1 配列の要素
3.1.2 配列の長さ
3.1.3 データの終端の表現
3.1.4 配列へのデータの挿入
3.1.5 配列のデータの削除
3.1.6 配列の複製
3.2 多次元配列
3.2.1 多次元配列
まとめ・演習問題

第4章スタックとキュー
4.1 スタック
4.1.1 スタックの実装
4.2 キュー
4.2.1 キューの実装
まとめ・演習問題

第5章リスト
5.1 連結リスト
5.1.1 データの挿入と削除
5.2 ポインタによるリストの実装
5.2.1 リストセルクラス：Cell
5.2.2 線形リストクラス：LinkedListCell
5.2.3 イテレータ
5.3 カーソルによるリストの実装
5.3.1 カーソルリストクラス：ListCursor
5.4 双方向リスト
5.4.1 双方向リストの実装
まとめ・演習問題

第6章木
6.1 木とは
6.1.1 木の定義
6.1.2 順序木と無順序木
6.1.3 順序木の探索
6.2 2分木
6.2.1 2分木
6.2.2 完全2分木
6.2.3 2分木の実装
6.3 2分探索木
6.3.1 2分探索木の実装
6.3.2 2分探索木の計算量
まとめ・演習問題

第7章グラフ
7.1 グラフとは
7.1.1 グラフの定義
7.1.2 グラフの用語
7.2 グラフの実装と探索
7.2.1 ノードクラス：Node
7.3 状態空間の探索
7.3.1 コンストラクタ
7.3.2 状態空間の定義：makeStateSpace
7.3.3 幅優先探索：breadthFirst
7.3.4 深さ優先探索：depthFirst
7.3.5 分岐限定法：branchAndBound
7.3.6 山登り法：hillClimbing
7.3.7 最良優先探索法：bestFirst
7.3.8 A（A∗）アルゴリズム
まとめ・演習問題

第8章データの検索
8.1 線形検索
8.1.1 番兵による線形検索の改良
8.2 2分検索
8.3 ハッシュ法
8.3.1 ハッシュ法とは
8.3.2 チェイン法
8.3.3 オープンアドレス法
まとめ・演習問題

第9章ソート
9.1 ソートとは
9.1.1 内部ソートと外部ソート
9.1.2 アニメーションによるソートの表示―――Sorting
9.2 単純交換ソート（バブルソート）
9.3 単純選択ソート
9.4 単純挿入ソート
9.5 シェルソート
9.5.1 ギャップの選択
9.6 クイックソート
9.7 マージソート
9.7.1 ソート済み配列のマージ
9.7.2 マージソートのアルゴリズム
9.7.3 プログラムと実行結果
9.8 ヒープソート
9.8.1 ヒープ
9.8.2 ヒープソート
9.8.3 ヒープソートの計算量
まとめ・演習問題