スタック(stack)
入れ、
出し(
)のデータ構造
に格納したデータは、必ず
に取り出される
データの到着順とは、
に処理したい場面で用いる
<用途>
・
・
・
・
・
・
キュー(queue)
入れ、
出し(
)のデータ構造
に格納したデータは、必ず
に取り出される
データの
に処理したい場面で用いる
<用途>
・
(
)
・
(
)
・
(
)
・
(
)
・
連結リスト(linked list)
と
を持つデータを作るデータ構造
と
の持たせ方で様々な種類がある
リスト
リスト
リスト
<用途>
リストは非常に柔軟なデータ構造で、様々な場面で用いられる。
・
・
、
・
(
、
、
)
・
「
」
木構造(tree)
間の
を表すデータ構造
・データは
に格納
・
を持つデータを
で連結する
・ノードの共有は
木構造は
と
の利点を合わせ持つ
：探索は
(ランダムデータ…
探索 O(
), ソート済みデータ…
探索 O(
))
データの挿入・削除は
(ソート済みのデータの削除…データの
が必要)
：探索は
(データの状態によらず、可能なのは
探索のみ O(
))
データの挿入・削除は
(データの
は連結先を繋ぎ替えるだけで、データの移動は
)
<二分探索木>
・全てのノードについて、 左の子ノードの値 < 右の子ノードの値 の関係が成り立っている(定義は逆でも可)
・探索：木がバランスしていれば(平衡木)、必ず
分の比較回数で目的のノードが見つかる。ノード数がnなら、O(
)
・追加・削除：
と同様、
のみ
<用途>
のデータを保存し、
に検索・更新・追加・削除を行う場面
・
・
・
(
)
と同じ用途(
は木の部分集合)
(文法構造は木で表現される(
))
グラフ(graph)
ノードの共有を
、ノード間の
関係を表すデータ構造
※
関係に、
や
を持たせることもある
※
や
はグラフの
→グラフの特殊形
<用途>
、
・
、
(
等を使った
)
(
)
ハッシュテーブル
の集合を、インデックス(索引)で管理するデータ構造
データ操作(検索・追加・更新・削除は、
(O(
))で可能
<用途>
・
(
)
…C++言語の
や
ルックアップテーブル(look up table)
処理において、
を保存しておき、保存されている計算結果を高速に検索することができるデータ構造
検索には、
等を使う。目的の値が存在しないときは、補完を行い、近似値を得る。
画像処理にも使用可能で、カラーとグレースケールの相互変換の際に、ピクセルごとの計算を全画素に適用すると、時間がかかるため、カラーとグレースケールに対応する値をルックアップテーブルにしておくことがある。
[プロ技]よく使われる代表的データ構造
これを完璧にしておけば赤点回避！(隠してある部分があまりにも多いので減らす予定です)
ログインすると、チェック機能を利用できるようになります。