C によるアルゴリズムとデータ構造 (改訂 2 版)

良いプログラムを書くための必須知識をまとめたテキストであり、五輪の書。
本書は、長年にわたって数多くの優秀なシステムエンジニア、プログラマーに愛読されてきた、良いプログラムを書くための必須知識をまとめたテキストです。
うまくつくられたプログラムは、理解しやすく実行効率も高いものですが、一方、そうでないものは解読も困難なうえに、やたら時間や領域をくいます。さらに、そのようなまずいプログラムには、えてしてミスや内容的な誤りも隠されているものです。
本書は、新たなアルゴリズムで新たなプログラミングを行うために覚えておかなくてはいけない必須知識、そしてアルゴリズムの設計、実現における基礎を、実用上の価値に重点を置いてまとめています。
今回の改訂においては、多くの読者の声をよく参考にして、よりわかりやすく、簡明になるよう見直しを行ったほか、接尾辞木について新たな解説を加えています。
システムエンジニア、プログラマーとして活躍される方の五輪書です。

『C によるアルゴリズムとデータ構造 改訂 2 版』 (茨木 俊秀 著、オーム社、2019 年 5 月刊) は、計算量の考え方を土台に、基本的なデータ構造、整列、アルゴリズムの設計手法、最適化やグラフ、文字列の問題までを C 言語のプログラムとともに学ぶ教科書です。版元は対象として大学の情報工学科の 1、2 年生のアルゴリズムの授業を挙げており、紹介文ではアルゴリズムの設計と実現の基礎を実用上の価値に重点を置いてまとめたテキストと説明しています。C を一通り書けるようになった段階で、速く正しいプログラムを組むための理屈を体系立てて身につけたい人に向いた一冊です。

全 6 章の構成、計算量の基礎から最適化と計算幾何まで

構成は全 6 章に、付記の C メモと演習問題のヒントと略解が続き、各章の終わりに演習問題が置かれています。第 1 章は計算とアルゴリズムの関係と計算量の評価、第 2 章はリスト、スタックと待ち行列、グラフと木、集合と辞書、ハッシュ表、集合族の併合といった基本的なデータ構造を扱います。第 3 章は順序つき集合の処理として、優先度つき待ち行列とヒープ、2 分探索木、平衡探索木を取り上げ、第 4 章はバブルソートからバケットソートと基数ソート、ヒープソート、クイックソートまでの整列と、整列の計算量の下界、第 p 要素の選択を論じます。第 5 章はアルゴリズムの設計として、整列データの処理、マージソートや長大数の掛け算を例にした分割統治法、SUBSET-SUM 問題などの動的計画法を、第 6 章はアルゴリズムの実現として、資源配分問題やナップサック問題、最小木と最短路と深さ優先探索、文字列の照合、計算幾何、関係データベースの処理を扱います。後半の 2 章は、前半で学んだデータ構造と設計手法を具体的な問題に当てはめる応用編として組まれていると読めます。

計算量で設計を選ぶ考え方と、C で実装する意味

同じ結果を出すプログラムでも、入力が大きくなったときの手間の増え方はアルゴリズムによって大きく違います。要素数の 2 乗に比例して時間が延びる整列と、要素数とその対数の積に比例する整列とでは、扱うデータが数百万件規模になると差が決定的になります。こうした違いを 計算量の見積もり として比べられるようになることが、データ構造を選ぶ判断の出発点です。本書が第 1 章で計算量の評価を置き、第 4 章で整列そのものの計算量の下界まで扱うのは、個々の手法を覚えるだけでなく、どこまで速くできるかの限界も含めて判断できるようにするためだと読めます。C で実装する意味は、リストや木を自分でメモリ上に組み立てる点にあります。ポインターで要素をつなぐ手間や、ハッシュ表 の衝突を処理する仕組みを自分の手で書くと、高水準の言語が標準ライブラリの裏で何をしているかが見えるようになります。版元は本書に掲載したプログラムコードを zip ファイルで配布しており、手元で動かしながら読み進められます。

改訂 2 版で加わった接尾辞木と、見直しの範囲

版元の紹介文によれば、改訂 2 版では読者の声を参考に、よりわかりやすく簡明になるよう見直しを行ったうえで、接尾辞木について新たな解説を加えています。接尾辞木は、ある文字列のすべての接尾辞を一つの木にまとめたデータ構造で、いったん作っておけば、長い文章の中からパターンを探す処理をパターンの長さに比例する手間で行えます。全文検索や遺伝子配列の解析など、同じ文字列に何度も問い合わせる場面で効く考え方です。ただし目次の節題に接尾辞木の語は出てこないため、どの節でどこまで扱うかは目次からは確認できません。

大学 1、2 年生向けの前提知識と、アルゴリズムの本の選び分け

読み進めるには、C の基本文法、とくに配列と構造体、ポインター、再帰呼び出しを書けることが前提になります。付記の C メモは補足であり、本書は C の入門を兼ねる構成ではないと読めます。また再帰方程式の漸近解や確率アルゴリズムの節もあるため、数列や対数、確率の初歩に抵抗がないと理解が早くなります。反対に、競技プログラミングの解法の型を短期間で身につけたい人や、Python などで手早く動かしながら学びたい人には別の本のほうが合う場合があり、目的ごとの選び方は アルゴリズムの本の選び方 で整理できます。アルゴリズムの授業の教科書として、あるいは独学で基礎を固め直したいエンジニアにとって、全 6 章を演習問題と略解で確かめながら進められる本書は、言語が変わっても使える設計の判断力を養う手堅い選択肢です。