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木などがある。

比較する項目	整理するポイント
スタックとキュー	最後に入れたものを出すのがスタック、先に入れたものを出すのがキュー。
配列とリスト	配列は添字アクセスが得意、リストは挿入・削除の構造変更に向く。
ハッシュ値とキー	キーをハッシュ関数に通した結果がハッシュ値。
木とグラフ	木は閉路を持たない階層的なグラフ。
ヒープとヒープ領域	データ構造のヒープとメモリ領域のヒープは文脈が異なる。