Cプログラマのためのアルゴリズムとデータ構造
Cプログラマのためのアルゴリズムとデータ構造 (SOFTBANK BOOKS)
ソフトバンク
近藤嘉雪
はじめに
第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 ポインタ
第2部 基本的なデータ構造
4. 配列
4.1 リスト
4.2 スタック
4.3 待ち行列
4.4 配列によるデータ構造の実現
4.4.1 リストの実現
4.4.2 スタックの実現
4.4.3 待ち行列の実現
5. 連結リスト
5.1 連結リスト
5.1.1 連結リストとは?
5.1.2 連結リストの基本的性質
5.1.3 連結リストとメモリ管理
5.1.4 連結リストの操作
5.1.4.1 要素の挿入
5.1.4.2 要素の削除
5.1.4.3 境界条件の扱い
5.2 循環リスト
5.2.1 循環リストとは?
5.2.2 循環シストの操作
5.2.3 リストの頭を用いた循環リスト
5.3 双方向リスト
5.3.1 双方向リストとは?
5.3.2 双方向リストの操作
5.4 多重リスト構造
6. 木構造
6.1 木構造とは?
6.2 順序木と無順序木
6.3 二分木
6.4 木のなぞり
6.4.1 木をなぞる手順
6.4.2 行きがけ順のなぞり
6.4.3 通りがけ順のなぞり
6.4.4 帰りがけ順のなぞり
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.2.1 B木の探索
10.3.2.2 B木への挿入
10.3.2.3 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 安定な整列
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 マージソートを利用した外部整列
索引