みんなのデータ構造


みんなのデータ構造


ラムダノート


著者:Pat Morin
訳者:堀江慧、陣内佑、田中康隆


訳者まえがき
本書の読み方
訳者謝辞
なぜこの本を書いたのか
謝辞
C++版のまえがき

第1章 イントロダクション
1.1 効率の必要性
1.2 インターフェース
1.3 数学的背景
1.4 計算モデル
1.5 正しさ、時間計算量、空間計算量
1.6 コードサンプル
1.7 データ構造の一覧
1.8 ディスカッションと練習問題

第2章 配列を使ったリスト
2.1 ArrayStack:配列を使った高速なスタック操作
2.2 FastArrayStack:最適化されたArrayStack
2.3 ArrayQueue:配列を使ったキュー
2.4 ArrayDeque:配列を使った高速な双方向キュー
2.5 DualArrayDeque:2つのスタックから作った双方向キュー
2.6 RootishArrayStack:メモリ効率に優れた配列スタック
2.7 ディスカッションと練習問題

第3章 連結リスト
3.1 SLList:単方向連結リスト
3.2 DLList: 双方向連結リスト
3.3 SEList:空間効率の良い連結リスト
3.4 ディスカッションと練習問題

第4章 スキップリスト
4.1 基本的な構造
4.2 SkiplistSSet:効率的なSSet
4.3 SkiplistList:効率的なランダムアクセスList
4.4 スキップリストの解析
4.5 ディスカッションと練習問題

第5章 ハッシュテーブル
5.1 ChainedHashTable: チェイン法を使ったハッシュテーブル
5.2 LinearHashTable:線形探索法
5.3 ハッシュ値
5.4 ディスカッションと練習問題

第6章 二分木
6.1 BinaryTree:基本的な二分木
6.2 BinarySearchTree:バランスされていない二分探索木
6.3 ディスカッションと練習問題

第7章 ランダム二分探索木
7.1 ランダム二分探索木
7.2 Treap: 動的ランダム二分探索木の一種
7.3 ディスカッションと練習問題

第8章 スケープゴート木
8.1 ScapegoatTree:部分的に再構築する二分探索木
8.2 ディスカッションと練習問題

第9章 赤黒木
9.1 2-4 木
9.2 RedBlackTree:2-4 木をシミュレートする二分木
9.3 要約
9.4 ディスカッションと練習問題

第10章 ヒープ
10.1 BinaryHeap:二分木を間接的に表現する
10.2 MeldableHeap:つなぎ合わせられるランダムなヒープ
10.3 ディスカッションと練習問題

第11章 整列アルゴリズム
11.1 比較に基づく整列
11.2 計数ソートと基数ソート
11.3 ディスカッションと練習問題

第12章 グラフ
12.1 AdjacencyMatrix:行列によるグラフの表現
12.2 AdjacencyLists:リストの集まりとしてのグラフ
12.3 グラフの走査
12.4 ディスカッションと練習問題

第13章 整数を扱うデータ構造
13.1 BinaryTrie:二分トライ木
13.2 XFastTrie:O„log„logn…… 時間での検索
13.3 YFastTrie:O„log„logn…… 時間のSSet
13.4 ディスカッションと練習問題

第14章 外部メモリの探索
14.1 BlockStore
14.2 B木
14.3 ディスカッションと練習問題

参考文献
索引

書籍目次

Posted by shi-n