前置き
第6回からはプログラミング系の話に移ります。
データ構造
配列
複数のデータを一度に管理できる。
静的配列 | 同じデータ型のデータを予め決めた数しか収納できない |
動的配列 | データの数に応じて可変長の配列とすることが可能 |
スタック
後入れ先出し(LIFO)のデータ構造。CPUのレジスタやプログラムでの関数呼び出しなど、今のコンピュータシステムで非常に広範囲で使われている。
push操作…スタックにデータを入れる操作
pop操作…スタックからデータを取り出す操作
キュー(待ち行列)
先入れ先出し(FIFO)のデータ構造。データを取り出すときには、最初に入れたデータが取り出される。
プリンタの出力やタスク管理など、順番通りに処理が必要な場合で使用される。
enqueue操作…キューにデータを入れる操作
dequeue操作…キューからデータを取り出す操作
データに優先度を付けて、優先度を考慮して順番を決定する優先度付きキューもよく用いられる。
リスト
線形リストとも言い、順序付けられたデータの並びです。
データ部…データそのものを格納する部分
ポインタ部…データの並びを格納する部分(前のポインタから次のポインタへ)
先頭ポインタ…データの先頭を指し示す
末尾ポインタ…最後方のデータにかんたんにたどり着けるようにする。
単方向リスト…次のデータへのポインタのみ持つ
双方向リスト…前と次、両方へのポインタを持つ
環状リスト……最後尾のデータから先頭に戻って環状に繋げる
ハッシュ
あるデータが与えられた時に、そのデータを代表する値に変換する関数。
一方向性の関数でy=h(x)があった場合、x→yは変換出来るが、y→xは出来ない。
この関数で求められた値をハッシュ値または単にハッシュと言う。
典型例としては割り算の余りを求める関数などがあります。
木
グラフ理論で出てきた木を用いたデータ構造。
2分木…親nodeに対する子nodeが二つまでに限定
多分木…子nodeが三つ以上
完全2分木…2分木のうち、形が完全に決まっているもの(その段が全て終わるまで次の段に行かない)
2分探索木…データの大小を木を使って辿っていく
構文木…構文や文法を表現
AVL木…2分探索木を完全2分木に変換した
ヒープ…根から葉に向けてだけデータを整列
B木…完全多分木で2分探索木の多分木バージョン
ヒープ
最大値または最小値を求めるのに適したデータ構造
「子要素は親要素より常に大きいか等しい」
「子要素は親要素より常に小さいか等しい」
のどちらかになる。
最後に
アプリ・インフラ系の仕事してるとこのあたりの知識は割かし出てくるんじゃないでしょうか。
