基礎から学ぶデータ構造とアルゴリズム 改訂版(キソカラマナブデータコウゾウトアルゴリズムカイテイバン)

大学や高専、専門学校などで情報処理を学ぶ学生を主対象に、基礎的なデータ構造とアルゴリムについて、その概念を把握しやすいよう、できるだけ図表を用いて丁寧に解説している。表現言語としては Java を用いたが、必要に応じて C の例も示した。アルゴリズムは計算量で評価する。計算量を理解することは、アルゴリズムを理解するうえで重要である。本書では、最初に計算量について説明し、データ構造で表現されたデータの探索や整列などの個々のアルゴリズムの解説においてもできるだけ計算量についてふれている。
改訂にあたって、“ 1.1.4 プログラムの基本構造”、“ 2.4.4 決定木”、“付録”としてフローチャートの解説を加えた。
第 1 章 データ構造とアルゴリズムの基本
1.1 データ構造とアルゴリズムの基本
1.1.1 データ構造とアルゴリズムの関係
1.1.2 アルゴリズムの表現
1.1.3 アルゴリズムと計算量
1.1.4 プログラムの基本構造

第 2 章データ構造
2.1 配列
2.1.1 配列とは何か
2.1.2 配列の基本操作
2.2 リスト
2.2.1 リストとは何か
2.2.2 連結リストの作り方
2.2.3 連結リストの基本操作
2.3 スタックとキュー
2.3.1 スタック
2.3.2 スタックの操作
2.3.3 逆ポーランド記法
2.3.4 キュー
2.3.5 キューの操作
2.3.6 キューを配列で実現するときの問題点
2.4 木構造
2.4.1 木の基本
2.4.2 再帰
2.4.3 木の走査
2.4.4 決定木

第 3 章 探索
3.1 2 分探索木
3.1.1 2 分探索木の定義
3.1.2 探索・挿入・削除のアルゴリズム
3.1.3 2 分探索木による探索の計算量
3.1.4 平衡木
3.2 2 分探索法
3.2.1 2 分探索法による探索
3.2.2 2 分探索法の計算量
3.3 ハッシュ法
3.3.1 ハッシュ法による探索
3.3.2 ハッシュ関数
3.3.3 データの登録と探索
3.3.4 衝突

第 4 章 整列
4.1 単純な整列アルゴリズム
4.1.1 バブルソート
4.1.2 選択ソート
4.1.3 挿入ソート
4.2 シェルソート
4.2.1 シェルソートのアルゴリズム
4.2.2 シェルソートの計算量
4.3 ヒープソート
4.3.1 半順序木
4.3.2 ヒープ
4.3.3 ヒープソート
4.3.4 ヒープソートの計算量
4.4 クイックソート
4.4.1 クイックソート
4.4.2 クイックソートのアルゴリズム
4.4.3 クイックソートの計算量
4.5 マージソート
4.5.1 マージソート
4.5.2 マージソートのアルゴリズム
4.5.3 マージソートの計算量
4.6 図式化による整列法の比較

付録
参考図書
問題解答
索引

配列、リスト、スタック、キュー、木、グラフといったデータ構造と、それらの上で動くソート・探索アルゴリズムは、プログラミングの土台でありながら独学だと体系的に学ぶ機会を逃しやすい分野です。本書は大学の情報系学部で使われることを想定した教科書で、各データ構造の定義と操作、計算量の評価方法を順序立てて解説します。擬似コードと図を併用しながら進むため、特定のプログラミング言語に縛られずに概念を理解できます。

改訂版では説明や図が見直されており、初版で分かりにくいと指摘された箇所が改善されています。前提知識としては高校数学程度で読み始められますが、計算量の議論ではオーダー記法を扱うため、数学的な記述に慣れていない人は最初のうち丁寧に読む必要があります。

競技プログラミングの高度なテクニックや、実務で使うライブラリの最適な使い方を学ぶ本ではありません。あくまで「なぜこのデータ構造を選ぶのか」「なぜこのアルゴリズムが速いのか」を根拠から理解するための基礎固めです。この土台を持っていると、後から応用的な書籍やコンテストに進んだときの吸収速度が変わります。