データ構造の基本

要点と定義

データ構造は、データのまとまりや関係を表し、格納・取出しなどの操作を支える仕組みです。選ぶときは、データの並び方と必要な操作を対応させます。

配列は要素を位置に対応付けて格納します。配列を使ってリストを実現し、最大個数分の領域を先に確保する方式では、実際の要素数が少ないと未使用領域が生じることがあります。これは過去の出題で扱った補足です。

リストは要素を順につないで表します。単方向リストは各要素から次の要素へたどります。先頭と末尾のポインタがあっても、末尾からその直前の要素へ戻ることはできません。末尾を削除するには、直前の要素を先頭からたどって探します。これは過去の出題で扱った補足です。

スタックは後入れ先出しの構造です。後から入れた要素から取り出し、追加をプッシュ、取出しをポップと呼びます。再帰呼出しでは、呼出しごとの状態を保存し、呼出しが戻る順に復元します。この順序とスタックの対応は、過去の出題で扱った補足です。

入力順を保ったままスタックに入れて取り出す場合、出力順はスタックの上下関係に制約されます。全ての並べ替えが可能とは限らず、操作を順に追って可否を判断します。これは過去の出題で扱った補足です。

後置記法では、演算子の後に続く値を読むのではなく、演算子に出会った時点で直前のオペランドを使います。例えば M N + は M + N を表します。複合式では値を順にスタックへ積み、演算子ごとに必要な値を取り出して計算結果を積み直します。これは過去の出題で扱った補足です。

木構造は、親子関係を枝で表す階層的な構造です。最上位を根、子を持たない節を葉と呼びます。二分木では各節の子は最大二つです。木を巡回する順序には、深さ優先や幅優先などがあります。

BNFは、記号と生成規則を使って構造を定義する方法です。規則をたどり、どの要素の並びや入れ子が構成できるかを読み取ります。

過去の出題で扱った補足として、剰余ハッシュ h(x) = x mod n では、二つのキーの余りが等しいと衝突します。これはキーの差が n で割り切れることと同じです。

三つ以上のキーが同じ剰余になるかは、キー同士の差が除数で割り切れるかを調べます。例えばキーが 14、26、38 なら、差は 12、12、24 です。除数がこれらの差を全て割り切れば、三つの余りは等しくなります。これは過去の出題で扱った補足です。

適用条件と例

配列は位置を指定して要素を扱う構造です。配列をリストとして使う場合、途中への挿入では後続要素を移動することがあります。挿入位置が分かっていても、移動の要否は別に確認します。末尾への追加は、空き領域がある場合には要素の移動なしで行えることがあります。これらは過去の出題で扱った補足です。

単方向リストで、挿入位置の直前の要素を既に参照できていれば、次ポインタをつなぎ替えて挿入できます。末尾ポインタは末尾への追加に利用できますが、末尾削除には直前の要素が必要です。双方向リストなどでは前後のたどり方が異なるため、単方向リストの説明をそのまま当てはめません。前二つの操作特性は過去の出題で扱った補足です。

スタックの出力可能性は、入れる順と取り出す順を一操作ずつ追って確かめます。例えば K、L、M の順に入れ、M を取り出した後は、残る L が K より上にあります。そのため、次に K だけを取り出して L を残すことはできません。この制約を使った出力順の判断は過去の出題で扱った補足です。

再帰処理では、呼出し元の状態を保存しておき、呼出し先から戻るときに復元します。後から始まった呼出しが先に戻るため、スタックの後入れ先出しの順序が対応します。これは過去の出題で扱った補足です。

剰余ハッシュの例では h(17) = 17 mod 6 = 5、h(29) = 29 mod 6 = 5 となり、異なるキーが同じハッシュ値になります。衝突はキーが等しいことではなく、ハッシュ値が等しいことです。ハッシュ値から元のキーを一意に決められるとは限らないので、衝突時の扱いも必要です。これらは過去の出題で扱った補足です。