第11回放送授業
「ソフトウェアのしくみ」
11 リスト構造とデータベース
11.1 データベースとは
データベース（DB）
• キー
– 原則、重なるキーはない方がよい
• 値（複数ある場合もある）
• キーとして配列番号もありうる
11.2 配列、ハッシュ関数
配列
• キー: 配列番号
• 値: 同じサイズに収まるデータ
• 任意の番号のデータのアドレス
=先頭アドレス
+配列番号×データサイズ
ポインタ配列
• データサイズが不定の場合には
ポインタ配列を使う
• データは配列とは別のところへ置き、
そのデータを指すポインタを配列と
する
ハッシュ法
• 広い領域にまばらに存在するキーを
まとめる手法
– 数字キー
– 文字列キー
• 高速で検索できる。
ハッシュ法
• ハッシュ関数
• ハッシュ表
• ハッシュ値
衝突
• オープンアドレス法
• 連鎖法
ハッシュ関数
• 除算法
• 中央二乗法
• 折り畳み法
11.3 スタック、キュー
スタック
• 最後に入れたデータのみを
見たり消したりできる構造
• 先端
• 終端
• プッシュ
• ポップ
• LIFO、FILO
線形リスト
• ノード = データ + ポインタ（複数も可）
• 線形リスト = ノード（1ポインタ）を
直線的に繋いだもの
• 終端のノードのポインタはNull
• 先端ノードのアドレスを見張る
先端ポインタが必要
線形リストによるスタック
• プッシュ = ノードの追加
• ポップ = ノードの削除
• 空リストの検出
キュー
• 待ち行列のように最初に入った
データのみを見たり消したりできる
構造
• 線形リストで実現
• 先端のみならず終端を見張る
ポインタも必要