アウトライン
16-1 ペア
16-2 パソコン演習
16-3 課題
2
16-1 ペア
3
apple 100
car cdr
ペアとは： ２つの構成部分のペアのこと．
car とcdr に分かれる
単純なペアの例
ペアとは
4
•cons は２つの引数を取り，２つの引数を部分と
して含むような「ペア」を返す
例） (define x (cons 'apple 100))
•ペアを構成する部分は，car, cdr で取り出せる
例） (car x) → 「apple」が得られる
(cdr x) → 「100」が得られる
•ペアは，「対」ともいう
car とcdr
5
１００
apple
ペアとは： ２つの構成部分のペアのこと．
car とcdr に分かれる
(cons 'apple 100) の箱とポインタ記法
6
１００
apple
car cdr
(cons 'apple 100) の箱とポインタ記法
7
apple
ペアは，上のように，箱とポインタ表記される
(cons 'apple empty) の箱とポインタ記法
8
apple
car cdr
(cons 'apple empty) の箱とポインタ記法
9
•「リスト」は末尾が「空リスト」であるような
「ペアの並び」である
•ペアの組み合わせによって，複雑な構造を表現で
きる
まとめ
10
16-2 パソコン演習
11
•資料を見ながら，「例題」を行ってみる
•各自，「課題」に挑戦する
•自分のペースで先に進んで構いません
パソコン演習の進め方
12
•DrScheme の起動
プログラム → PLT Scheme → DrScheme
•今日の演習では「Full Scheme」
に設定
Language
→ Choose Language
→ Full Scheme
→ OK
→ 「Execute ボタン」
DrScheme の使用
13
•ペアが，自由に扱えるようになる
•但し，「empty」が使えなくなる
ので，代わりに「'()」を使う
•Full Scheme でempty を使おうとす
るとエラー
•リストの表示が変わる
(list 15 8 6) ⇒(15 8 6) のように
Full Scheme では
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
１５ ８６
car
cdr
(cons 15 (cons 8 (cons 6 '()))) の箱とポインタ記法
22
１５ ８６
car
cdr
•リストの car:
•リストの先頭要素
•リストの cdr:
•リストから先頭要素を取り除いた残り（やはりリスト）
リストの car とcdr
23
１５ ８６
「空リストである」こと
を示す特別な値が
入っている
リストの末尾としての空リスト
24
１５ ８６
•リストを構成するペアの個数：リストの要素数に
等しい
•リストを構成するペアの car： リストの要素が入
る
リストを構成するペアの性質 (1/2)
25
１５ ８６
•リストを構成するペアの右側のセル(cdr フィールド)
•次の要素へのポインタか，「空リスト」であることを示す
特別な値（リストの末端であることを示す）が入る
リストを構成するペアの性質 (2/2)
26
•Scheme では
末尾が「空リスト」であるようなペアの並び
•並びの最後のペアの cdr フィールドに空リスト が入っ
ている
•行儀の良いリスト（proper list）と呼ぶこともある
リストとは
27
１５ ８６
car
cdr
(cons 15 (cons 8 (cons 6 '())))
８６
car
cdr
(cons 8 (cons 6 '()))
６
car cdr （cdr は空リスト）
(cons 6 '())
28
•リストでは：
•リストと要素をつなげて，新しいリスト
を作る
•一般的には：
•データとデータをつなげて，新しいペア
を作る
cons の意味
29
•下記のペアを，変数aとして定義する
１２
３４
cdr
car
例題３．ペアから構成されたペア
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
'c
car
cdr
'a 'b
(cons (cons 'a 'b) 'c) の箱とポインタ記
法
34
car
cdr
'a 'b 'c
(cons 'a (cons 'b 'c)) の箱とポインタ記
法
35
cons によるペアの表記
36
•例題３のペアについて，car とcdr を組
み合わせて，「１」，「２」，「３」，
「４」を得る
１２
３４
例題４．car とcdr の組み合わせ
37
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)
「例題３．car とcdr の組み合わせ」の手順
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 (car a)) (cdr (car a))
(car (cdr a)) (cdr (cdr a))
car, cdr の組み合わせ
42
•(caar pair)
•(cadr pair)
...
•(cdddr pair)
car, cdr を４つまで組み合わせることができる
car, cdr の組み合わせ
43
•(cons obj1 obj2)
ペアの生成
•(car pair)
car の取り出し
•(cdr pair)
cdr の取り出し
•(caar pair)
•(cadr pair)
...
•(cdddr pair)
car, cdr を４つまで組み合わせることができる
ペアに関する関数
44
•下記のようなペアの集まりを，変数
xとして定義する
car
123
456
cdr
例題５． cons とlist の組み合わせ(1)
45
car
(define x (cons (list 1 2 3)
(list 4 5 6)))
123
456
cdr
cons とlist の組み合わせ (1/2)
46
47
48
•下記のようなペアの集まりを，変数
xとして定義する
car
x
y
bcdr
a
20
10
例題６． cons とlist の組み合わせ(2)
49
car
(define x (list (cons 'x 'y)
(cons 'a 'b)
(cons 10 20)))
x
y
bcdr
a
20
10
cons とlist の組み合わせ (2/2)
50
51
•下記のようなペアの集まりを，変数
xとして定義する
car
12
cdr
34
例題７． list とlist の組み合わせ
52
car
(define x (list (list 1 2)
(list 3 4)))
12
cdr
34
list とlist の組み合わせ
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)
３
２３
(cons 1 (cons 2 3)) (1 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)か
ら構成
•節点がデータに対応
•枝がデータ間の親子関係に対応
•子： 節点の中で下方に分岐する枝の先にあるもの
•親：分岐元の節点
親
子
枝(branch)
節点(node)
図．単純な木構造
木構造
63
•根(root)： 木の一番上の節点を根(root)
•葉(leaf)： 子を持たない節点
•部分木： 木の中のある節点を相対的な根と考えた
ときの，そこから枝分かれした枝と節点の集合
部分木
根(root)
葉(leaf)
木構造
64
•木構造で，各節点から出る枝が二本以下のも
の
•木構造に関するアルゴリズムの中で，中心的
なデータ構造
二分木 (binary tree)
65
•二分木の一種
•データの配置に規則あり
•左側のすべての子は親より小さい
•右側のすべての子は親より大きい
•データの探索のためのデータ構造
35
21
13 40 61
46
69
二分探索木 (binary search tree)
66
•根(root)から始める
•探索キーの値と，各節点のデータを比較し，
目標となるデータを探す
•探索キーよりも節点のデータが小さいときは，右
側の子をたどる
•探索キーよりも節点のデータが大きいときは，左
側の子をたどる
二分探索木による探索
67
(例） 40である節点を探す場合
1. 根の値(35)と，探索キー(40)を比較
2. 探索キーの方が大きいので，右側の子節点へ移る
3. 次に移った節点の値(46)と探索キー(40)を比較し
4. 探索キーの方が小さいので，左の子節点へ移る
5. 次に移った節点(40)が，目標の節点である
35
21
13 40 61
46
69
二分探索木による探索の例
68
•複雑なプログラムを作成する時，データ構造
について考える必要がある
•データ構造
•アルゴリズムを容易にするために工夫されたデー
タの並び
•基本的なデータ構造は，配列，キュー，スタック，
リスト構造，木構造など
データ構造
69
(define-struct node
(value left right))
left right
value
left right
value
left right
value
枝
枝
二分探索木のための node structure
70
•二分探索木のプログラムを作り，実行する
•二分探索木の節点を扱うために，define struct 文を
使って，node structure を定義する
•１つの二分探索木は，節点が集まって，入れ子の構造
になる
例題８．二分探索木
71
•二分探索木の節点を，define-struct
文を使って定義する
(define-struct node
(value left right))
名前
属性の並び
（それぞれの属性にも名前がある）
二分探索木の節点
72
define-struct の機能
•上記のプログラムの実行によって
•make-node
•node-value
•node-left
•node-right
が使えるようになる
(define-struct node
(value left right))
属性 value, left,
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 40 61
46
69
上のプログラムが表現する
２分探索木
（「false」は「データが無い」こと
を示す特別な値）
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
