Open Data Structures

プロジェクトの概要

Open Data Structures は Pat Morin 氏が執筆した、データ構造の入門書です。本プロジェクトでは、この本の和訳を作成し、PDF ファイルおよびそのソースコードを公開しています。

PDF ファイルはこのページの下部にあります。書籍のソースコードは GitHub のリポジトリ https://github.com/spinute/ods で公開しています。

また、本プロジェクトの校正・校閲をプロに依頼するための資金をクラウドファンディングで募りました。ご支援頂いた皆様には心より感謝を申し上げます。

スポンサー企業・団体

東京大学瀧本哲史ゼミ

瀧本ゼミはデータに基づく問題解決プロフェッショナル養成機関です。株式と政策を素材に実社会にインパクトを与えており、各界に広範なネットワークを広げています。


有限会社コンセントレーション

書籍情報

ラムダノート社より、本書の書籍版（紙書籍、電子書籍）を販売しています。https://www.lambdanote.com/products/opendatastructures

ラムダノート社は、本書の校正・校閲を担当してくださった技術出版社です。成果物をオープンソースライセンスで公開し続けることを了承した上で、出版の提案を持ちかけてくださいました。

書籍版とオープンソース版の主な違いは見た目で、内容はほぼ同じです。フォントや組版の調整により、読みやすさがこれほども違うのかと訳者一同感動しました。

書籍版を一部公開する許可を頂いたので、ぜひ見比べてみて、興味を持った方は購入をご検討いただければと思います！

ods-cpp-chapter01.pdf

オープンソース版 PDF ファイル

オープンソース版 Open Data Structures 日本語訳の PDF ファイルを以下で公開しています。最新のソースコードは GitHub のリポジトリ https://github.com/spinute にあり、適宜こちらの PDF ファイルに反映しています。

以下のものは C++ 版です（Java 版はこちら、疑似コード版はこちらにあります）。

ods-cpp.pdf

本書の内容

目次

訳者まえがき

本書の読み方

訳者謝辞

なぜこの本を書いたのか

謝辞

第1章 イントロダクション

  1. 効率の必要性

  2. インターフェース

  3. 数学的背景

  4. 計算モデル

  5. 正しさ、時間計算量、空間計算量

  6. コードサンプル

  7. データ構造の一覧

  8. ディスカッションと練習問題

第2章 配列を使ったリスト

  1. ArrayStack：配列を使った高速なスタック操作

  2. FastArrayStack：最適化された ArrayStack

  3. ArrayQueue：配列を使ったキュー

  4. ArrayDeque：配列を使った高速な双方向キュー

  5. DualArrayDeque：2つのスタックから作った双方向キュー

  6. RootishArrayStack：メモリ効率に優れた配列スタック

  7. ディスカッションと練習問題

第3章 連結リスト

  1. SLList：単方向連結リスト

  2. DLList: 双方向連結リスト

  3. SEList：空間効率の良い連結リスト

  4. ディスカッションと練習問題

第4章 スキップリスト

  1. 基本的な構造

  2. SkiplistSSet：効率的な SSet

  3. SkiplistList：効率的なランダムアクセス List

  4. スキップリストの解析

  5. ディスカッションと練習問題

第5章 ハッシュテーブル

  1. ChainedHashTable: チェイン法を使ったハッシュテーブル

  2. LinearHashTable：線形探索法

  3. ハッシュ値

  4. ディスカッションと練習問題

第6章 二分木

  1. BinaryTree：基本的な二分木

  2. BinarySearchTree：バランスされていない二分探索木

  3. ディスカッションと練習問題

第7章 ランダム二分探索木

  1. ランダム二分探索木

  2. Treap: 動的ランダム二分探索木の一種

  3. ディスカッションと練習問題

第8章 スケープゴート木

  1. ScapegoatTree：部分的に再構築する二分探索木

  2. ディスカッションと練習問題

第9章 赤黒木

  1. 2-4 木

  2. RedBlackTree：2-4 木をシミュレートする二分木

  3. 要約

  4. ディスカッションと練習問題

第10章 ヒープ

  1. BinaryHeap：二分木を間接的に表現する

  2. MeldableHeap：つなぎ合わせられるランダムなヒープ

  3. ディスカッションと練習問題

第11章 整列アルゴリズム

  1. 比較に基づく整列

  2. 計数ソートと基数ソート

  3. ディスカッションと練習問題

第12章 グラフ

  1. AdjacencyMatrix：行列によるグラフの表現

  2. AdjacencyLists：リストの集まりとしてのグラフ

  3. グラフの走査

  4. ディスカッションと練習問題

第13章 整数を扱うデータ構造

  1. BinaryTrie：二分トライ木

  2. XFastTrie：O(log(logn)) 時間での検索

  3. YFastTrie：O(log(logn)) 時間の SSet

  4. ディスカッションと練習問題

第14章 外部メモリの探索

  1. BlockStore

  2. B木

  3. ディスカッションと練習問題