はじめに

第1章 アルゴリズムの基礎概念
1.1 アルゴリズムの計算量
1.2 漸近計算量とO-, Ω-, Θ-記法
1.3 素朴な アルゴリズムの計算量
1.4 難しい 問題
1.5 解答付き演習問題
1.6 演習問題

第2章 根付き木と再帰法
2.1 グラフと木
2.2 再帰法
2.3 根付き木のラベリング
2.4 発展:拡張ユークリッド互除法
2.5 演習問題

第3章 ソーティング
3.1 ソーティングアルゴリズム
3.2 マージソート
3.3 クイックソート
3.4 基数ソート (ラディックスソート)
3.5 ソーティングの計算量の下界
3.6 解答付き演習問題
3.7 演習問題

第4章 基本データ構造1: 配列とヒープ
4.1 辞書と優先度付きキュー
4.2 優先度付きキューとヒープ
4.3 ヒープ構成の計算量
4.4 ヒープソート
4.5 ヒープソートのプログラム例
4.6 解答付き演習問題
4.7 演習問題

第5章 基本データ構造2:配列とリスト
5.1 辞書
5.2 二分探索と2倍探索
5.3 辞書とリスト
5.4 リストの変種
5.5 リストの配列による実現
5.6 配列の領域管理を用いたリストの実現
5.7 リストのプログラム例
5.8 根付き木表現のデータ構造
5.9 先行順・後行順・幅優先順ラベリングのプログラム例
5.10 解答付き演習問題
5.11 演習問題

第6章 基本データ構造3: 配列と二分探索木
6.1 二分探索木
6.2 二分探索木の平均的振舞い、
6.3 二分探索木のプログラム例、
6.4 演習問題

第7章 高速データ構造:配列と二色木
7.1 平衡探索木
7.2 二色木
7.3 二色木のプログラム例
7.4 演習問題

第8章 基本データ構造4: 配列とハッシング
8.1 ハッシング
8.2 チェーン法によるハッシング
8.3 普遍ハッシング: 乱択化技法の応用
8.4 演習問題

第9章 基本データ構造5: 配列と集合ユニオン・ファインド森
9.1 集合ユニオン・ファインドデータ構造
9.2 単純な集合ユニオン・ファインドデータ構造
9.3 集合ユニオン・ファインド森
9.4 さらなる改善: パス圧縮
9.5 集合ユニオン・ファインド森のプログラム例
9.6 演習問題

第10章 データ構造の応用1:凸包
10.1 凸包の定義
10.2 点のx座標のソートに基づく凸包アルゴリズム
10.3 1点の回りでの偏角順に基づく凸包アルゴリズム
10.4 Grahamの凸包アルゴリズムのプログラム例
10.5 演習問題

第11章 データ構造の応用2:交差線分対列挙
11.1 平面走査法
11.2 一直線上の線分の交差線分対列挙
11.3 水平線分・垂直線分の交差線分対列挙
11.4 水平線分・垂直線分の交差線分対列挙のプログラム例
11.5 演習問題

第12章 データ構造の応用3:最小全点木
12.1 最小全点木を求める Kruskalのアルゴリズム
12.2 Kruskalのアルゴリズムのプログラム例
12.3 演習問題

演習問題解答
参考文献
索引