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


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


技術評論社


著者:長尾和彦


はじめに
目次

第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 ヒープソートの計算量
まとめ・演習問題

付録A Eclipseのインストール
A.1 Eclipseの入手
A.2 Eclipseの日本語化
A.3 Eclipseの起動

付録B Eclipseによるプログラミング入門
B.1 初めてのプログラミング
B.1.1 プロジェクトの作成
B.1.2 テストファースト

付録C アルゴリズム公式集
等差数列・等比数列
対数(log)の公式
指数の公式

付録D 漸化式の解き方
D.1 漸化式の解き方
D.1.1 例:2分検索
D.1.2 例:階乗の計算
D.1.3 例:フィボナッチ数列
D.1.4 クイックソート
D.1.5 その他の漸化式1
D.1.6 その他の漸化式2

付録E フラクタル
E.1 プロジェクトの説明
E.2 コッホ曲線
E.3 樹木曲線
E.4 ヒルベルト曲線
E.5 シェルピンスキー曲線

参考文献
おわりに
索引

書籍目次

Posted by shi-n