基礎から学ぶデータ構造とアルゴリズム 改訂版

大学や高専、専門学校などで情報処理を学ぶ学生を主対象に、基礎的なデータ構造とアルゴリムについて、その概念を把握しやすいよう、できるだけ図表を用いて丁寧に解説している。表現言語としては 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 図式化による整列法の比較

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

配列やリスト、木といった基本のデータ構造と、その上で動く探索と整列のアルゴリズムを、計算量を物差しにして学ぶ教科書です。『基礎から学ぶデータ構造とアルゴリズム 改訂版』 (穴田 有一 著、共立出版、2022 年 9 月刊) は、版元の紹介によると大学や高専、専門学校などで情報処理を学ぶ学生を主な対象に、概念をつかみやすいよう、できるだけ図表を用いて丁寧に解説した本です。アルゴリズムの表現には Java を使い、必要に応じて C の例も示しています。

全 4 章の構成、計算量から探索と整列へ

第 1 章「データ構造とアルゴリズムの基本」は、両者の関係、アルゴリズムの表現、アルゴリズムと計算量、プログラムの基本構造を扱います。版元の紹介は、最初に計算量を説明し、その後の個々のアルゴリズムでもできるだけ計算量にふれる方針を挙げています。第 2 章「データ構造」は配列、リスト、スタックとキュー、木構造の 4 節で、連結リストの作り方と基本操作、スタックを使う逆ポーランド記法、キューを配列で実現するときの問題点、再帰と木の走査が並びます。第 3 章「探索」は 2 分探索木と平衡木、ソート済みの配列を半分ずつ絞り込む 2 分探索、ハッシュ関数と衝突までのハッシュ法を、第 4 章「整列」はバブルソート、選択ソート、挿入ソートから、シェルソート、ヒープソート、クイックソート、マージソートへ進み、最後に図式化による整列法の比較を置きます。整列の章では、シェルソート以降の各手法には計算量の節が続き、手法を増やすたびに速さの根拠を確かめていく組み立てと読めます。

改訂版で加わった構造化プログラミング、決定木、フローチャート

版元が公開している「改訂版へのはじめに」によると、初版の刊行から 20 年余りを経た改訂で、説明の足りない点を補うために 3 つの追加が行われました。1 つめが構造化プログラミングの説明で、目次では 1.1.4「プログラムの基本構造」にあたります。2 つめがアルゴリズムを図で表す方法としてのフローチャートの説明で、付録に代表的なフローチャート記号も収められています。3 つめが 2.4.4「決定木」で、機械学習でしばしば使われる手法の一つとして加えたと説明されています。同じ文章によると、初版は林 雄二 氏との共著でした。初版を持っている人が買い替えを考える場合は、この 3 点が差分の目安になります。

計算量を物差しに手法を選ぶ力と、扱わない範囲

基本のデータ構造とアルゴリズムを学ぶ意味は、同じ結果を出す手順のあいだに大きな速さの差があることを、根拠とともに説明できるようになる点にあります。たとえばバブルソートや挿入ソートはデータ量の 2 乗に比例して手間が増えますが、マージソートやヒープソートは n log n の増え方に収まり、件数が増えるほど差が開きます。クイックソートは平均では速いものの、基準値の選び方が悪いと 2 乗の手間に落ちる弱点を持ちます。こうした差を 計算量 で見積もる習慣は、ライブラリの関数を選ぶときや処理が遅い原因を探すときにも役立ちます。各手法の考え方を整理したい人は ソートアルゴリズム の解説も参考になります。一方で、目次にはグラフや最短路、動的計画法の章がありません。グラフ探索や設計手法まで学びたい人は、続けて読む本を別に用意する必要があります。

情報処理の授業でデータ構造とアルゴリズムを初めて学ぶ学生や、探索と整列の基本を図表と Java のコードで固めたい人にとって、本書は計算量の考え方と基本の手法を一度に押さえられる一冊です。巻末の問題解答と照らし合わせながら、第 1 章の計算量から順に進めてみてください。