第11回放送授業.

Presentation on theme: "第11回放送授業."— Presentation transcript:

1 第11回放送授業

2 「ソフトウェアのしくみ」

3 11 リスト構造とデータベース

4 11.1 データベースとは

5 データベース（DB） キー 原則、重なるキーはない方がよい 値（複数ある場合もある） キーとして配列番号もありうる

6 11.2 配列、ハッシュ関数

7 配列 キー: 配列番号 値: 同じサイズに収まるデータ 任意の番号のデータのアドレス =先頭アドレス +配列番号×データサイズ

8

9 ポインタ配列 データサイズが不定の場合には ポインタ配列を使う データは配列とは別のところへ置き、 そのデータを指すポインタを配列と する

10

11 ハッシュ法 広い領域にまばらに存在するキーをまとめる手法 数字キー 文字列キー 高速で検索できる。

12 ハッシュ法 ハッシュ関数 ハッシュ表 ハッシュ値

13

14 衝突 オープンアドレス法 連鎖法

15 ハッシュ関数 除算法 中央二乗法 折り畳み法

16 11.3 スタック、キュー

17 スタック 最後に入れたデータのみを 見たり消したりできる構造 先端 終端 プッシュ ポップ LIFO、FILO

18

19 線形リスト ノード = データ + ポインタ（複数も可） 線形リスト = ノード（1ポインタ）を 直線的に繋いだもの
終端のノードのポインタはNull 先端ノードのアドレスを見張る 先端ポインタが必要

20 線形リストによるスタック プッシュ = ノードの追加 ポップ = ノードの削除 空リストの検出

21

22

23

24 キュー 待ち行列のように最初に入った データのみを見たり消したりできる 構造 線形リストで実現 先端のみならず終端を見張る ポインタも必要

25