sigma-se

目的

この記事では、応用情報技術者試験の出題分野であるデータ構造に関する覚書きを列挙する。

スタック
後入れ先出し（LIFO：Last In First Out）のデータ構造のこと。
スタックにデータを入れることをpush、データを出すことをpopという。
キュー
先入れ先出し（FIFO：First In First Out）のデータ構造のこと。
キューにデータを入れることをenqueue、データを出すことをdequeueという。

※ 線形リストは、単にリストとも呼ばれる。

線形リスト
順序付けされた関連データを集約したデータ構造のこと。

データ値を保持するデータ部と、データ順を保持するポインタ部で構成されている。
※ ポインタ部は、次データや前データ以外にも先頭ポインタ、末尾ポインタも含む。
単方向リスト
ポインタ部に次データへのポインタのみ保持するリスト。
双方向リスト
ポインタ部に次データと前データへのポインタを保持するリスト。
環状リスト
単方向リストのポインタに加え、末尾のポインタ部に先頭ポインタを持つリスト。

ハッシュ関数
データをあるルールに従って別の値に変換する一方向性の関数のこと。

変換後の値を変換前の値に戻すことができない。
例えば、\(x\) の剰余 \(n\) を求める関数 \(y = x \bmod n\) のように右辺から左辺の \(y\) は求められるが、その逆は求められない。
ハッシュテーブル（ハッシュ表）
キー（key）と値（value）を一つの単位としたデータ構造。
キー（key）→ 値（value）の一方向性が前提。
- 例 : ハッシュ関数を \(h(x) = x \bmod n\) とし、ハッシュテーブルとして、キーを自然数 \(x\)、値を \(n\) で管理する。
  この時、任意のキー \(a\)、\(b\) の値が一致する条件を考える。
  
  → 「値が一致する」ことより、次のように置ける。
  \(a = a^{\prime} \times n + m\)
  \(b = b^{\prime} \times n + m\)
  （\(a^{\prime}, b^{\prime}\) は整数、\(m\) は値）
  
  よって
  \(a = a^{\prime} \times n + b\) \(-\ b^{\prime} \times n\)
  \(a - b = n (a^{\prime} - b^{\prime})\)
  
  また、\(a^{\prime}\ -\ b^{\prime}\) は、整数である。
  
  よって
  \(a - b\) が \(n\) の倍数であることが条件となる。

木構造
木構造は、閉路（閉じたノード）を持たないグラフ構造でルート（根）、ノード（枝）、リーフ（葉）から構成される。

※ 上記は、応用数学の「5. グラフ理論」で触れた記載と同じ。
→ 応用情報技術 - 基礎覚書き：応用数学 > グラフ理論
\(2\) 分木
子ノードの数が \(2\) つ以下である木構造。
実用例として、データの大小関係を木構造でたどる \(2\) 分探索木や構文・文法を表現する構文木などがある。
多分木
子ノードの数が \(3\) つ以上である木構造。
完全 \(2\) 分木
子ノードの数がすべて \(2\) つである木構造。
実用例として、 \(2\) 分探索木を完全 \(2\) 分木に変換したAVL木や根から葉に向けてデータを整列させたヒープなどがある。
完全多分木
子ノードの数が \(3\) つ以上ですべて同じである木構造。
実用例として、\(2\) 分探索木の完全多分木バージョンであるB木などがある。