Cプログラマのためのアルゴリズムとデータ構造 Part 2

2019年1月22日

Cプログラマのためのアルゴリズムとデータ構造〈Part2〉 (SOFTBANK BOOKS)

ソフトバンク

近藤嘉雪

はじめに

第1部アルゴリズムとデータ構造の基礎
1 アルゴリズムとは?
1.1 アルゴリズムとデータ構造
1.2 計算量
1.3 アルゴリズムの選択基準
2 基本的なデータ構造
2.1 リスト
2.1.1 リストとは?
2.1.2 スタック
2.1.3 待ち行列
2.2 配列
2.3 連結リスト
2.3.1 連結リストとは?
2.3.2 循環リストと双方向リスト
2.4 木構造
2.5 探索
2.5.1 探索とは?
2.5.2 配列を利用した探索アルゴリズム
2.5.3 本構造を利用した探索アルゴリズム

第2部探索
3 文字列の探索
3.1 文字列に対する探索
3.2 カまかせのアルゴリズム
3.2.1 カまかせのアルゴリズムの原理
3.2.2 カまかせのアルゴリズムの計算量
3.3 洗練されたアルゴリズム
3.4 Knuth-Morris‐Prattのアルゴリズム
3.4.1 KMP法の原理
3.4.2 KMP法の性質
3.5 Boyer‐Mooreのアルゴリズム
3.5.l BM法の原理
3.5.2 BM法の実際
3.5.3 BM法のプログラム
3.5.4 BM法の性質
4 正規表現
4.1 正規表現とは?
4.2 正規表現の実現
4.2.1 正規表現とオートマトン
4.2.2 非決定性有限オートマトンと決定性有限オートマトン
4.2.3 正規表現からNFAへの変換
4.2.4 NFAからDFAへの変換
4.3 正規表現のプログラム

第3部ソート
5 ヒープソート
5.1 整列アルゴリズムのあれこれ
5.2 ヒープソートの原理
5.2.1 探索の整列への応用
5.2.2 優先順位付き待ち行列
5.2.3 半順序木
5.2.4 ヒーフ
5.2.5 ヒープによるdelete_minの実現
5.2.6 ヒープによるinsertの実現
5.3 ヒーブソートのプログラム
6 比較によらないソート
6.1 比較によらない整列アルゴリズム
6.2 ビンソート
6.2.1 ビンソートの原理
6.2.2 ビンソートのプログラム
6.2.3 ビンソートの性質
6.3 分布数え上|プツート
6.3.1 分布数え上げソートの原理
6.3.2 分布数え上げソートのプログラム
6.3.3 分布数え上げソートの性質
6.4 基数ソート
6.4.1 基数ソートの原理
6.4.2 基数ソートのプログラム
6.4.3 基数ソートの性質

第4部いろいろなアルゴリズム
7 バックトラック法
7.1 バックトラック法とは?
7.2 8クイーン問題
7.2.1 8クイーン問題とは?
7.2.2 8クイーンの解法
7.2.3 バックトラツク法の実現
7.2.4 8クイーンのプログラム
7.2.5 すべての解を求める
8 動的計画法
8.1 動的計画法とは?
8.2 ナップザック問題
8.2.1 ナップザック問題とは?
8.2.2 ナップザック問題の解き方
8.2.3 ナップザック問題を解くプログラム
8.2.4 ナップザック問題の計算量
9 メモリ管理アルゴリズム
9.1 メモリ管理とは?
9.2 メモリ管理のアルゴリズム
9.2.1 静的割り当てと動的割り当て
9.2.2 動的割り当ての分類
9.2.3 ガベージコレクタ
9.2.4 断片化と詰め直し
9.2.5 双方向リストによるメモリ管理
9.3 メモリ管理のプログラム