演習でマスターする C 言語とデータ構造

本書は、C 言語の基本をマスターした人を対象とし、150 以上の演習問題を解くことで、基本的なデータ構造を理解し、それを利用するプログラムを作成できることを目標としている。さらに、データ構造を抽象化・カプセル化することで、抽象データ型の考えを理解できるようにしている。
大学での演習の経験をもとに、大学での演習用の教科書としても独習書としても利用できるように、次の工夫を凝らしている。
(1) 身近な例や具体的な値からデータ構造の特徴や動作を理解する。
(2) データ構造を操作する関数を少しずつ完成していく。
(3) データ構造を利用するプログラムの書き方を説明する。
(4) 節ごとにあげた演習問題を解くことで、プログラムを作成する力を付けられる。

C の文法は一通り学んだものの、スタックや連結リストを自分で書いたことはない。その段階の学習者に向けて、150 以上の演習問題で基本的なデータ構造の実装を積み上げるのが『演習でマスターする C 言語とデータ構造』 (内藤 広志、齊藤 隆 著、共立出版、2006 年 9 月刊 / 版元の発売日は 2006 年 9 月 25 日) です。版元の紹介によると、対象は C 言語 の基本をマスターした人で、基本的なデータ構造を理解し、それを利用するプログラムを作れるようになることを目標にしています。さらに、データ構造を抽象化とカプセル化で扱い、抽象データ型の考えを理解できるようにしていると説明されています。

スタックから 2 分探索木までの全 11 章

本文は全 11 章です。第 1 章でスタックを配列で実現して push と pop の関数を定義し、第 2 章では待ち行列、つまり キュー を配列とリングバッファーで実現します。第 3 章はリストを配列で実現し、挿入や削除の関数を定義したうえで、データ構造とカプセル化、分割コンパイルの方法へ進みます。第 4 章から第 7 章はポインター、配列と文字列、構造体、構造体と関数の章で、変数とアドレスの関係から動的メモリ割付けまでを扱います。第 8 章と第 9 章は 連結リスト で、セルの挿入と削除、抽象データ型としての連結リスト、リストとイテレーターの実現法を扱います。第 10 章は再帰的関数と 2 分木、第 11 章は 2 分探索木で、最後の節は写像への応用です。版元の目次に並ぶ 11 章にはグラフの章はなく、扱うのは線形の構造と木構造です。

配列で作ってからポインターで作り直す順序

章の並びには、はっきりした意図が読み取れます。前半の 3 章は、ポインターを使わずに配列だけでスタック、待ち行列、リストを作ります。データ構造の振る舞いを先に理解し、push や insert のような操作を関数として定義しておくと、内部の作りを配列から連結リストに替えても、利用する側のプログラムは同じ操作で書けます。これが抽象データ型とカプセル化の考え方で、第 3 章の「データ構造とカプセル化」と第 9 章の「データ構造と抽象データ型」は、この発想を前後から押さえる位置にあると読めます。ポインターを第 4 章から改めて取り上げるのは、連結リストや木のようにデータどうしを指し示してつなぐ構造に、その道具が欠かせないからです。版元の紹介にある工夫の 4 項目のうち、身近な例や具体的な値から特徴や動作を理解すること、データ構造を操作する関数を少しずつ完成していくことは、この順序とよく噛み合っています。

デバッグの節が多い、手を動かす前提の教科書

もう 1 つの特徴は、エラーへの対処を扱う節が多いことです。第 2 章のデバッグの方法とエラーの記録、第 3 章のエラーの原因を調べる節に続き、ポインター、配列と文字列、構造体へのポインター、連結リストのアクセス違反と、つまずきやすい箇所のデバッグが多くの章に置かれています。版元の紹介によると演習問題は節ごとに設けられており、大学の演習用の教科書としても独習書としても使えるように作られています。第 10 章は、再帰 を使う関数を先に学び、そのあと 2 分木の作成となぞる処理へ進む並びです。逆に、整列や探索のアルゴリズムの比較、グラフの探索、計算量の理論を体系的に学びたい場合は、アルゴリズムを主題にした別の本を組み合わせる必要があります。2006 年刊の本なので、第 1 章のコンパイルの方法のような開発環境の手順は刊行時点のものとして読むことになります。

C の文法の授業を終えたあとで、ポインターと構造体を本当に使える形で身につけたい学生や、連結リストや 2 分探索木を自分の手で一から組み立てた経験を持っておきたい独習者にとって、配列からポインターへ、線形の構造から木へと段階を踏む本書は、演習を解いた分だけ実装力が積み上がる教科書です。