入門 データ構造とアルゴリズム
オライリー・ジャパン
著者：Narasimha Karumanchi
訳者：黒川利明、木下哲也
格言(動機づけと啓発のため)
謝辞
序
1章 はじめに
変数
データ型
データ構造
抽出データ型(ADT)
アルゴリズムとは
なぜアルゴリズムの解析なのか
実行時解析とは
どのようにアルゴリズムを比較するのか
増加率とは
一般に用いられている増加率
解析の種類
漸近表記法
0表記法
Ω表記
Θ表記
なぜ漸近的解析と呼ぶのか
漸近的解析のガイドライン
表記の特性
よく使われる対数と和
分割統治マスター定理
分割統治マスター定理の問題
減算統治再帰(Subtract and Conquer Recurrences)マスター定理
減算統治再帰マスター定理の変形
ならし解析
アルゴリズム解析の問題
2章 再帰と後戻り
はじめに
再帰とは
再帰関数の形式
再帰とメモリ(可視化)
再帰と反復
再帰に関する注意
再帰アルゴリズムの例
再帰の問題
後戻りとは
後戻りの問題
3章 連結リスト
連結リストとは
連結リストADT
連結リストを使う自由
配列の概観
連結リストの配列や動的配列との比較
単一連結リスト
二重連結リスト
循環連結リスト
メモリ効率二重連結リスト
連結リストの問題
4章 スタック
スタックとは
スタックはどのように使われるか？
スタックADT
応用
実装
実装の比較
スタックの問題
5章 キュー
キューとは
キューはどのように使われるか
キューADT
例外
応用
実装
キューの問題
6章 木
木とは
木の用語
二分木
二分木の型
二分木の性質
二分来横断
一般木(N分木)
スレッド二分木横断(スタック／キュー不要横断)
式木
XOR木
二分探索木(BST)
平衡二分探索木
AVL木
木の他の形式
7章 優先度付きキューとヒープ
優先度付きキューとは
優先度付きキューADT
優先度付きキューの実装
ヒープ
二分ヒープ
優先度付きキュー(ヒープ)の問題
８章 互いに素な集合ADT
はじめに
同値関係と同値類
互いに素な集合ADT
互いに素な集合ADT実装のトレードオフ
まとめ
互いに素な集合の問題
9章 グラフアルゴリズム
はじめに
グラフとは
グラフの適用例
グラフ表現
グラフ横断
トポロジカルソート
最短経路アルゴリズム
最小全域木
グラフアルゴリズムの問題
10章 整列
整列とは
分類
その他の分類
バブルソート
選択ソート
挿入ソート
シェルソート
マージソート
ヒープソート
クイックソート
ツリーソート
整列アルゴリズムの比較
線形整列アルゴリズム
数え上げソート
バケツソート(ビンソート)
基数ソート
トポロジカルソート
外部整列
整列の問題
11章 探索
探索とは
なぜ探索を行うのか？
順不同線形探索
整列／順序線形探索
二分探索
探索の問題
12章 選択アルゴリズム[中央値]
選択アルゴリズムとは
選択アルゴリズム
選択アルゴリズムの問題
13章 記号表
はじめに
記号表とは
記号表の実装
14章 ハッシュ
ハッシュとは
ハッシュ表ADT
ハッシュを理解する
ハッシュの構成要素
衝突解消手法の比較
ハッシュはどのようにして計算量O(1)を実現するのか？
ハッシュ手法
ハッシュの問題
15章 文字列アルゴリズム
はじめに
文字列照合アルゴリズム
力任せ法
ラビン・カープ文字列照合アルゴリズム
有限オートマトンを使った文字列照合
KMPアルゴリズム
ボイヤー・ムーアアルゴリズム
文字列を格納するためのデータ構造
文字列のためのハッシュ表
文字列のための二分探索木
トライ
三分探索木(TST)
二分探索木、トライ、三分探索木の比較
接尾辞木
文字列に関する問題
16章 アルゴリズム設計技法
はじめに
分類
実装方法による分類
設計方法による分類
その他の分類
17章 貪欲アルゴリズム
はじめに
ハフマン符号化アルゴリズム
貪欲アルゴリズムの問題
18章 分割統治アルゴリズム
はじめに
分割統治法の可視化
分割統治法を理解する
分割統治法の利点
分割統治法の欠点
マスター定理
分割統治法の問題
19章 動的プログラミング
はじめに
動的プログラミングの方法
動的プログラミングの例
動的プログラミングの問題
20章 計算量クラス
はじめに
計算量クラスの種類
帰着／簡約
計算量クラスの問題
21章 その他の各種概念
はじめに
ビット単位プログラミング
その他のプログラミング問題
参考文献
訳者あとがき
索引