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

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

• https://www.kkaneko.jp/pro/scheme/index.html

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

16-1 ペア 3

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

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

(cons 'apple 100) の箱とポインタ記法 １００ apple ペアとは： ２つの構成部分のペアのこと． car と cdr に分かれる 6

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

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

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

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

16-2 パソコン演習 11

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

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

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

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

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

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

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

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

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

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

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

リストの car と cdr car • リストの car: １５ • リストの先頭要素 ６ ８ cdr • リストの cdr: • リストから先頭要素を取り除いた残り（やはりリスト） 23

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

リストを構成するペアの性質 (1/2) １５ ８ ６ • リストを構成するペアの個数：リストの要素数に 等しい • リストを構成するペアの car： リストの要素が入 る 25

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

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

(cons 6 '()) car ６ cdr （cdr は空リスト） (cons 8 (cons 6 '())) car ８ ６ cdr (cons 15 (cons 8 (cons 6 '()))) car １５ ６ ８ cdr 28

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

例題３．ペアから構成されたペア • 下記のペアを，変数aとして定義する ３ ４ car １ ２ cdr 30

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

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

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

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

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

cons によるペアの表記 36

例題４．car と cdr の組み合わせ • 例題３のペアについて，car と cdr を組 み合わせて，「１」，「２」，「３」， 「４」を得る ３ １ ４ ２ 37

「例題３．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) ☆ 次は，例題４に進んでください 38

39

40

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

car, cdr の組み合わせ ３ １ ４ (car (cdr a)) (cdr (cdr a)) ２ (car (car a)) (cdr (car a)) 42

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

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

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

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

47

48

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

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

51

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

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

54

ドット対の例 (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

56

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

２ (cons 1 2) (1 . 2) １ ３ (cons (cons 1 2) 3) ((1 . 2) . 3) ２ １ (1 2 . 3) (cons 1 (cons 2 3)) １ ２ ３ 58

16-3 課題 59

課題① • 実行結果を報告しなさい • 実行上の注意： 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

例題８．二分探索木 例題９．二分探索木による探索 ・入れ子になった構造 62

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

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

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

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

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

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

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

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

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

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

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

(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 上のプログラムが表現する ２分探索木 （「false」は「データが無い」こと を示す特別な値） 46 40 61 69 74

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

(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

77

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