データ構造

要点と定義

データ構造は、データの格納方法や関係を定め、格納・取出し・参照などの操作を可能にする仕組みです。用途に応じて、データの並び方と必要な操作を確認します。

配列は、要素を位置に対応付けて格納する構造です。添字で位置を指定できるため、その位置の要素を参照できます。固定容量で実現する場合、実際の要素数が最大個数に届かなければ未使用領域が生じることがあります。過去の出題で扱った補足として、二次元配列の条件を各行ごとの個数に分けて合計する考え方があります。例えば、行番号が零から五までで、各行に行番号と同じ個数の要素があるなら、合計は零足す一足す二足す三足す四足す五で十五個です。

リストは、要素を順につないで扱う構造です。配列で実現する方式では要素を連続して格納し、ポインタで実現する方式では要素と次の要素へのポインタを使います。単方向リストは次の要素へ進めますが、前の要素へ直接戻れません。過去の出題で扱った補足として、末尾ポインタを持つ単方向リストでも、末尾を削除するには末尾の直前の要素を見つけるため先頭からたどる必要があります。 配列方式で途中に要素を挿入するときは、後続要素の移動が必要になる場合があります。

スタックは後入れ先出し、キューは先入れ先出しで要素を扱います。スタックでは最後に格納した要素を先に取り出し、キューでは最初に格納した要素を先に取り出します。再帰処理では、呼出しごとの状態を保存し、後から呼び出された処理から復帰するため、スタックの順序が適します。 過去の出題で扱った補足として、スタックに入力順を保って要素を入れると、取り出し順は任意の並べ替えにはならず、スタックの積み重なり方で制約されます。

木構造は、親子関係でデータを表し、子を持たない節を葉と呼びます。過去の出題で扱った補足として、B+木の葉が分割されたときは、親から分割後の葉を参照できるようにし、葉同士の連結もキーの順序に保ちます。親に空きがある場合は、親の子ポインタを更新して分割後の葉を追加できます。

ハッシュ表は、キーから格納位置を求める方法の一つです。過去の出題で扱った補足として、剰余を使う関数では、二つのキーの差が除数の倍数なら余りが等しくなり、衝突します。例えば除数が六でキーが二十三と四十一なら、差は十八で除数の倍数なので余りは等しくなります。複数のキーが衝突するかを調べる場合は、それぞれの余りが一致するかを確かめます。 複数キーの余りが一致する除数を探す方法も過去の出題で扱われています。

適用条件と例

データ構造の操作時間を比べる際は、実現方法と操作をそろえて考えます。配列は添字で位置を指定して参照できますが、配列の途中への挿入では要素を移動することがあります。ポインタ方式のリストで位置が既に分かっている場合、要素同士のつなぎ替えは少数のポインタ更新で行えますが、目的の位置を探すには先頭からたどることがあります。

スタックとキューは、必要な取出し順に合わせて使います。例えば、到着した依頼を受付順に処理するなら、先に入れたものを先に取り出すキューが合います。再帰処理の状態復元では呼出しと復帰の順序が逆になるため、後入れ先出しのスタックが合います。