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

アルゴリズムは、入力から目的の出力を得るための有限の処理手順です。探索、整列、集計など、同じ目的でも複数のアルゴリズムが存在します。

データ構造は、データ同士の関係や操作方法を扱いやすくするための表現方法です。代表例として、配列、リスト、スタック、キュー、木構造などがあります。

例えば二分探索は、単に値が並んでいるだけでは使えません。探索対象がキー順に整列されていることが前提です。このように、アルゴリズムには利用できる条件があります。

配列は、複数の要素を並べ、添字を使って特定の要素へアクセスするデータ構造です。要素番号が分かっていれば目的の位置を直接指定しやすい点が特徴です。

リストは、各要素が次の要素などとのつながりを持つことで順序を表します。連結リストでは、要素の挿入や削除時に周囲のリンクを変更して関係をつなぎ替えます。

配列とリストのどちらが常に優れているわけではありません。添字によるアクセスを重視するか、途中への追加・削除を重視するかなど、必要な操作によって選びます。

スタックは、最後に追加した要素を最初に取り出すLIFO（Last In First Out）のデータ構造です。要素を追加する操作をpush、取り出す操作をpopと呼びます。

キューは、最初に追加した要素を最初に取り出すFIFO（First In First Out）のデータ構造です。待ち行列のように、到着した順に処理したい場面で使われます。

試験では名称だけでなく、実際に値を追加・削除した後にどの値が残るか、どの値が次に取り出されるかを追えることが重要です。

木構造は、要素を節（ノード）として階層的につなぐデータ構造です。最上位の節を根（ルート）、下位に節を持たない節を葉（リーフ）と呼びます。

二分木は、各節が持つ子の数が高々2個の木です。二分探索木では、節の値の大小関係に一定の規則を持たせることで探索を行いやすくします。

木はファイルの階層、組織構造、探索用の索引など、親子関係を表したい場面で利用されます。

線形探索は、先頭などから要素を一つずつ調べ、目的の値と一致するか確認する方法です。データが整列されていなくても使えます。

二分探索は、整列済みのデータについて中央の値と比較し、探索対象が存在する可能性のある半分だけを残す操作を繰り返します。整列済みであることが重要な前提です。

整列はデータを決められた順序へ並べ替える処理です。バブルソート、選択ソート、クイックソートなど複数の方法があり、手順や効率が異なります。

このページでは各アルゴリズムの動きと利用条件を中心に扱います。入力サイズに対する処理量の増え方は、別記事「計算量とアルゴリズムの効率」で詳しく扱う想定です。