アルゴリズムとデータ構造

データ構造を配列からポインターでつなぐ形へ、探索と整列を素朴な方法から効率のよい方法へと、手を動かしながら段階的に理解したい人のための教科書です。『アルゴリズムとデータ構造』 (湯田 幸八、伊原 充博 共著、コロナ社、2002 年 6 月刊) は、電気 / 電子系教科書シリーズの第 18 巻として刊行されました。版元は初心者や入門者向けの教科書と位置づけ、プログラムと図解を組み合わせて難解なアルゴリズムを説明している点と、プログラムを C++ で記述している点を特徴に挙げています。

全 6 章の構成、アルゴリズムと計算量からいろいろな問題まで

本文は全 6 章で、どの章も末尾に演習問題が置かれ、巻末には付録、参考文献、演習問題解答、索引が続きます。第 1 章「アルゴリズムと計算量」はアルゴリズムの性能評価、計算量の漸近的な評価、O 記法などを扱います。第 2 章「基本的なデータ構造」は配列による順配置とポインターによるリンク配置から始まり、構造体とクラス、リスト、双方向連結リスト、スタック、キュー、木へと進みます。連結リストには C による実現と C++ による表現の両方の節があり、キューにはリングバッファーによる実現、木には 2 分木の走査や数式を表す木の節が立てられています。第 3 章「探索」は線形探索、2 分探索、ハッシュ法に加えて、力まかせアルゴリズム、クヌース-モリス-プラット法、ボイヤ-ムーア法による文字列の探索と、2 分探索木や B 木による木の探索を取り上げます。第 4 章「整列」は選択、交換、挿入、併合によるソートと外部ソートを扱い、交換の節にはバブルソート、シェーカソート、クイックソート、挿入の節には単純挿入ソートとシェルソートが置かれています。第 5 章「グラフ」はグラフの定義と表現法、深さ優先探索と幅優先探索、グラフの応用を、第 6 章「いろいろな問題」はハノイの塔、8 クイーン問題、ナップサック問題と、樹木曲線、ヒルベルト曲線、シェルピンスキー曲線の描画を扱います。

データの持ち方で手間が変わる理由と、C++ で読む意味

この科目で身につけたいのは、同じ問題を解く方法のあいだで、データが増えたときの手間の伸び方がまったく違うことを自分の言葉で説明できる力です。たとえば配列は添字を指定すれば一定の手間で要素を参照できますが、途中に要素を差し込むと後ろの要素を順にずらす必要があります。要素どうしをポインターでつなぐ 連結リスト は、差し込みや取り除きがつなぎ替えだけで済む代わりに、何番目の要素へ直接たどり着くことができません。こうした違いを入力の大きさに対する増え方として表すのが 計算量のオーダー で、先頭から順に調べる方法と、並べ替え済みの列を半分ずつ絞り込む方法、キーから格納位置を計算する ハッシュ表 とでは、現実的に扱えるデータの規模が大きく変わります。

本書のプログラムは C++ で書かれています。ポインターを直接扱える言語では、要素がメモリ上でどうつながり、差し込みや取り除きのときにどのポインターを付け替えるのかが、コードにそのまま現れます。第 2 章はポインター、構造体、クラスを順に取り上げたうえで、連結リストを C で実現する節と C++ で表現する節を並べているため、手続きとして書く形と、データと操作をクラスにまとめる形の違いも見比べられます。刊行は 2002 年 6 月で、コードは刊行時点の処理系を前提にしています。

入門向けの教科書として選ぶ人と、別の本が合う人

版元は本書を初心者や入門者向けと案内しています。ただしプログラムは C と C++ で書かれているので、変数、関数、配列、ポインターといった言語の基本を一通り知っていると、図とコードを突き合わせながら読み進めやすくなります。Python や Java など別の言語で手を動かしたい人は、コードを読み替える手間がかかります。また、版元の位置づけは入門の教科書なので、アルゴリズムの正しさや計算量を数学的に厳密に証明する専門書を探している人には、目的が合わない場合があります。

授業でアルゴリズムとデータ構造を学ぶ電気 / 電子系や情報系の学生、あるいはスタックやキュー、木、ハッシュ法、ソートを名前だけでなく動くコードとして理解し直したい人に向けて、本書は計算量の考え方からデータ構造、探索、整列、グラフ、古典的な問題までを C と C++ の実装と図解で通して扱い、演習問題と解答を収めています。