sp-16. cons と種々のデータ構造

>100 Views

January 26, 22

スライド概要

(Scheme プログラミング)
URL: https://www.kkaneko.jp/cc/scheme/index.html

profile-image

金子邦彦(かねこくにひこ) 福山大学・工学部・教授 ホームページ: https://www.kkaneko.jp/index.html 金子邦彦 YouTube チャンネル: https://youtube.com/user/kunihikokaneko

シェア

埋め込む »CMSなどでJSが使えない場合

各ページのテキスト
1.

sp-16. cons と種々のデータ構 造 (Scheme プログラミング) URL: https://www.kkaneko.jp/cc/scheme/index.html 金子邦彦 1

2.

アウトライン 16-1 ペア 16-2 パソコン演習 16-3 課題 2

3.

16-1 ペア 3

4.

ペアとは 単純なペアの例 ペアとは: apple 100 car cdr 2つの構成部分のペアのこと. car と cdr に分かれる 4

5.

car と cdr • cons は2つの引数を取り,2つの引数を部分と して含むような「ペア」を返す 例) (define x (cons 'apple 100)) • ペアを構成する部分は,car, cdr で取り出せる 例) (car x) (cdr x) → 「apple」が得られる → 「100」が得られる • ペアは,「対」ともいう 5

6.

(cons 'apple 100) の箱とポインタ記法 100 apple ペアとは: 2つの構成部分のペアのこと. car と cdr に分かれる 6

7.

(cons 'apple 100) の箱とポインタ記法 100 car cdr apple 7

8.

(cons 'apple empty) の箱とポインタ記法 apple ペアは,上のように,箱とポインタ表記される 8

9.

(cons 'apple empty) の箱とポインタ記法 car cdr apple 9

10.

まとめ • 「リスト」は末尾が「空リスト」であるような 「ペアの並び」である • ペアの組み合わせによって,複雑な構造を表現で きる 10

11.

16-2 パソコン演習 11

12.

パソコン演習の進め方 • 資料を見ながら,「例題」を行ってみる • 各自,「課題」に挑戦する • 自分のペースで先に進んで構いません 12

13.

DrScheme の使用 • DrScheme の起動 • 今日の演習では「Full Scheme」 に設定 プログラム → PLT Scheme → DrScheme Language → Choose Language → Full Scheme → OK → 「Execute ボタン」 13

14.

Full Scheme では • ペアが,自由に扱えるようになる • 但し,「empty」が使えなくなる ので,代わりに「'()」を使う • Full Scheme で empty を使おうとす るとエラー • リストの表示が変わる (list 15 8 6) ⇒ (15 8 6) のように 14

15.

例題1.ペア • シンボルと数値のペアを作る • ペアを生成するために cons を使う • ペアを構成する部分('apple や 100 など)を 取り出すために car, cdr を使う 変数x: シンボル 'apple と数値 100 のペア 変数y: シンボル 'orange と数値 60 のペア 変数z: シンボル 'banana と数値 80 のペア 15

16.

「例題1.ペア」の手順 1. 次を「定義用ウインドウ」で,実行しなさい • 入力した後に,Execute ボタンを押す (define x (cons 'apple 100)) (define y (cons 'orange 60)) (define z (cons 'banana 80)) 2. その後,次を「実行用ウインドウ」で実行しなさい x (car x) (cdr x) ☆ 次は,例題2に進んでください 16

17.

ペアの生成 表示されたペア 17

18.

例題2.リストの変数定義 • リスト 15, 8, 6 を変数として定義し, 名前Aを付ける • 変数を定義するために define を使う • リストを作るために cons を使う 18

19.

「例題2.リストの変数定義」の手順 1. 次を「定義用ウインドウ」で,実行しなさい • 入力した後に,Execute ボタンを押す (define A (cons 15 (cons 8 (cons 6 '())))) 2. その後,次を「実行用ウインドウ」で実行しなさい A (car A) (cdr A) ☆ 次は,例題3に進んでください 19

20.

「'()」は,空リストの意味 20

21.

(cons 15 (cons 8 (cons 6 '()))) の箱とポインタ記法 15 8 6 • リストの要素が,「ペアの並び」と して順順につながる 21

22.

(cons 15 (cons 8 (cons 6 '()))) の箱とポインタ記法 car 15 6 8 cdr 22

23.

リストの car と cdr car • リストの car: 15 • リストの先頭要素 6 8 cdr • リストの cdr: • リストから先頭要素を取り除いた残り(やはりリスト) 23

24.

リストの末尾としての空リスト 15 8 6 「空リストである」こと を示す特別な値が 入っている 24

25.

リストを構成するペアの性質 (1/2) 15 8 6 • リストを構成するペアの個数:リストの要素数に 等しい • リストを構成するペアの car: リストの要素が入 る 25

26.

リストを構成するペアの性質 (2/2) 15 8 6 • リストを構成するペアの右側のセル(cdr フィールド) • 次の要素へのポインタか,「空リスト」であることを示す 特別な値(リストの末端であることを示す)が入る 26

27.

リストとは • Scheme では 末尾が「空リスト」であるようなペアの並び • 並びの最後のペアの cdr フィールドに空リスト が入っ ている • 行儀の良いリスト(proper list)と呼ぶこともある 27

28.

(cons 6 '()) car 6 cdr (cdr は空リスト) (cons 8 (cons 6 '())) car 8 6 cdr (cons 15 (cons 8 (cons 6 '()))) car 15 6 8 cdr 28

29.

cons の意味 • リストでは: • リストと要素をつなげて,新しいリスト を作る • 一般的には: • データとデータをつなげて,新しいペア を作る 29

30.

例題3.ペアから構成されたペア • 下記のペアを,変数aとして定義する 3 4 car 1 2 cdr 30

31.

「例題3.ペアから構成されたペア」の手順 1. 次を「定義用ウインドウ」で,実行しなさい • 入力した後に,Execute ボタンを押す (define a (cons (cons 1 2) (cons 3 4))) 2. その後,次を「実行用ウインドウ」で実行しなさい a (car a) (cdr a) ☆ 次は,例題4に進んでください 31

32.

ペアの生成 表示されたペア 32

33.

例題3のプログラム例 (define a (cons (cons 1 2) (cons 3 4))) ペアから構成されたペアは, 「cons の入れ子」で書ける 33

34.

(cons (cons 'a 'b) 'c) の箱とポインタ記 法 'c cdr car 'a 'b 34

35.

(cons 'a (cons 'b 'c)) の箱とポインタ記 法 car 'a 'b 'c cdr 35

36.

cons によるペアの表記 36

37.

例題4.car と cdr の組み合わせ • 例題3のペアについて,car と cdr を組 み合わせて,「1」,「2」,「3」, 「4」を得る 3 1 4 2 37

38.

「例題3.car と cdr の組み合わせ」の手順 1. 次を「定義用ウインドウ」で,実行しなさい • 入力した後に,Execute ボタンを押す (define a (cons (cons 1 2) (cons 3 4))) 2. その後,次を「実行用ウインドウ」で実行しなさい (car (car a)) (cdr (car a)) (car (cdr a)) (cdr (cdr a)) (caar a) (cdar a) (cadr a) (cddr a) ☆ 次は,例題4に進んでください 38

41.

例題4のプログラム例 (define a (cons (cons 1 2) (cons 3 4))) (car (car a)) (cdr (car a)) (car (cdr a)) (cdr (cdr a)) 41

42.

car, cdr の組み合わせ 3 1 4 (car (cdr a)) (cdr (cdr a)) 2 (car (car a)) (cdr (car a)) 42

43.

car, cdr の組み合わせ • (caar pair) • (cadr pair) ... • (cdddr pair) car, cdr を4つまで組み合わせることができる 43

44.

ペアに関する関数 • (cons obj1 obj2) ペアの生成 • (car pair) car の取り出し • (cdr pair) cdr の取り出し • (caar pair) • (cadr pair) ... • (cdddr pair) car, cdr を4つまで組み合わせることができる 44

45.

例題5. cons と list の組み合わせ(1) • 下記のようなペアの集まりを,変数 xとして定義する cdr 5 4 6 car 1 2 3 45

46.

cons と list の組み合わせ (1/2) cdr 5 4 6 car 1 2 3 (define x (cons (list 1 2 3) (list 4 5 6))) 46

49.

例題6. cons と list の組み合わせ(2) • 下記のようなペアの集まりを,変数 xとして定義する b a car 20 cdr 10 y x 49

50.

cons と list の組み合わせ (2/2) b a car 20 cdr 10 y x (define x (list (cons 'x 'y) (cons 'a 'b) (cons 10 20))) 50

52.

例題7. list と list の組み合わせ • 下記のようなペアの集まりを,変数 xとして定義する cdr 3 car 1 4 2 52

53.

list と list の組み合わせ cdr 3 car 1 4 2 (define x (list (list 1 2) (list 3 4))) 53

55.

ドット対の例 (cons 'a 'b) ⇒ (a . b) と表示される (cons (cons 'a 'b) 'c) ⇒ ((a . b) . c) と表示される (cons 'a (cons 'b 'c)) ⇒ (a b . c) と表示される (cons (cons 'a 'b) (cons 'c 'd)) ⇒ (( a . b) c . d) と表示される 55

57.

ドット対 • ペアの cdr がリストになっていない場合 • つまり,cdr 方向にペアの並びをみたときに,末 尾が「空リスト」になっていなければ ⇒ ドットを,末尾の要素の前に追加 57

58.

2 (cons 1 2) (1 . 2) 1 3 (cons (cons 1 2) 3) ((1 . 2) . 3) 2 1 (1 2 . 3) (cons 1 (cons 2 3)) 1 2 3 58

59.

16-3 課題 59

60.

課題① • 実行結果を報告しなさい • 実行上の注意: DrScheme で,必ず「Full Scheme」を選んでから実行すること. (list (cons 1 2) (cons 3 4)) (list (list 1 2) (list 3 4)) (car (list ...)) の実行 結果 (cdr (list ...)) の実行 結果 (cadr (list ...)) の実 行結果 (cddr (list ...)) の実 行結果 60

61.

さらに勉強したい人への 補足説明事項 二分探索木 61

62.

例題8.二分探索木 例題9.二分探索木による探索 ・入れ子になった構造 62

63.

木構造 • 幾つかの節点(node)と,それらを結ぶ枝(branch)か ら構成 • 節点がデータに対応 • 枝がデータ間の親子関係に対応 • 子: 節点の中で下方に分岐する枝の先にあるもの • 親: 分岐元の節点 親 節点(node) 枝(branch) 子 図.単純な木構造 63

64.

木構造 根(root) 葉(leaf) 部分木 • 根(root): 木の一番上の節点を根(root) • 葉(leaf): 子を持たない節点 • 部分木: 木の中のある節点を相対的な根と考えた ときの,そこから枝分かれした枝と節点の集合 64

65.

二分木 (binary tree) • 木構造で,各節点から出る枝が二本以下のも の • 木構造に関するアルゴリズムの中で,中心的 なデータ構造 65

66.

二分探索木 (binary search tree) • 二分木の一種 • データの配置に規則あり • 左側のすべての子は親より小さい • 右側のすべての子は親より大きい • データの探索のためのデータ構造 35 21 13 46 40 61 69 66

67.

二分探索木による探索 • 根(root)から始める • 探索キーの値と,各節点のデータを比較し, 目標となるデータを探す • 探索キーよりも節点のデータが小さいときは,右 側の子をたどる • 探索キーよりも節点のデータが大きいときは,左 側の子をたどる 67

68.

二分探索木による探索の例 (例) 40である節点を探す場合 1. 根の値(35)と,探索キー(40)を比較 2. 探索キーの方が大きいので,右側の子節点へ移る 3. 次に移った節点の値(46)と探索キー(40)を比較し 4. 探索キーの方が小さいので,左の子節点へ移る 5. 次に移った節点(40)が,目標の節点である 35 21 13 46 40 61 69 68

69.

データ構造 • 複雑なプログラムを作成する時,データ構造 について考える必要がある • データ構造 • アルゴリズムを容易にするために工夫されたデー タの並び • 基本的なデータ構造は,配列,キュー,スタック, リスト構造,木構造など 69

70.

二分探索木のための node structure (define-struct node value (value left right)) left right 枝 枝 value left value right left right 70

71.

例題8.二分探索木 • 二分探索木のプログラムを作り,実行する • 二分探索木の節点を扱うために,define struct 文を 使って,node structure を定義する • 1つの二分探索木は,節点が集まって,入れ子の構造 になる 71

72.

二分探索木の節点 • 二分探索木の節点を,define-struct 文を使って定義する 名前 (define-struct node (value left right)) 属性の並び (それぞれの属性にも名前がある) 72

73.

define-struct の機能 (define-struct node (value left right)) • 上記のプログラムの実行によって • make-node • node-value 属性 value, left, • node-left right の取得 • node-right が使えるようになる 73

74.

(make-node 35 (make-node 21 (make-node 13 false false) false) (make-node 46 (make-node 40 false false) (make-node 61 false (make-node 69 false false)))) 35 21 13 上のプログラムが表現する 2分探索木 (「false」は「データが無い」こと を示す特別な値) 46 40 61 69 74

75.

例題9.二分探索木による探索 • 二分探索木の探索のプログラムを作り, 実行する • データが二分探索木の中にあれば → true • 無ければ → false 75

76.

(define-struct node (value left right)) (define (search x a-tree) (cond 左を探す [(eq? a-tree false) false] [(< x (node-value a-tree)) (search x (node-left a-tree))] [(< (node-value a-tree) x) (search x (node-right a-tree))] [else true])) 右を探す 76

78.

まとめ • 2分探索木を「入れ子になった node structure」 として表現した 78