表的表示
讲解如何用可变列表实现一维和二维表，包括 assoc、lookup、insert! 以及过程式的局部表对象。
引言
在第 2 单元我们提到过，可以用二维表来存储数据：给出两个键，就能取到想要的数据。我们可以用可变列表来表示这种数据结构：先构造一维表，再把这个思想推广开来。
预备知识：assoc
在深入表之前，必须先认识另一个 Scheme 复合过程 assoc，它在本节扮演着重要角色。assoc 接受一个 key（键）和一个由序对组成的列表，返回第一个 car 是该键的序对；如果不存在这样的序对，就返回 #f。看下面的例子，理解 assoc 的作用：
> (assoc 1 '((1 2) (3 4)))
(1 2) ; 返回 car 为 1 的序对
> (assoc 'cupcake '((1 2) (3 4) (cupcake donut) (galaxy star)))
(cupcake donut) ; 任何东西都可以当键
> (assoc 2 '((1 2) (3 4)))
#f ; 没有序对的 car 是 2，因此返回 #f
> (assoc 'froyo '((cupcake donut eclair)
(froyo gingerbread honeycomb)
(sandwich jellybean kitkat)))
(froyo gingerbread honeycomb) ; 序对可以有任意长度下面是 assoc 的形式化定义：
(define (assoc key records)
(cond ((null? records) false)
((equal? key (caar records)) (car records))
(else (assoc key (cdr records)))))一维表
在一维表（1D table）中，每个值只用一个键来存储。我们把表设计成一个序对组成的列表，每个序对的 car 保存对应值的键。
在上面这张表里，键和值的对应关系如下：
| 键 | 值 |
|---|---|
a | 1 |
b | 2 |
c | 3 |
为什么表的第一个序对里没有任何键值对？这是我们的特意设计：第一个序对装有符号 *table*，用来标记当前这个列表结构是一张表。
make-table
下面是表的简单构造函数：
(define (make-table)
(list '*table*))lookup
要从表中提取信息，我们使用选择函数 lookup：它接受一个键作为参数，返回关联的值（若该键下没有存值，则返回 #f）。定义如下：
(define (lookup key table)
(let ((record (assoc key (cdr table))))
(if record
(cdr record)
false)))> (lookup 'b table) ; table 指上面创建的表
2insert!
向表中插入一个键值对，遵循以下简单算法：
- 如果键已在表中，直接更新它的值；
- 否则，新建一个键值序对，挂到表上。
(define (insert! key value table)
(let ((record (assoc key (cdr table))))
(if record
(set-cdr! record value)
(set-cdr! table (cons (cons key value) (cdr table)))))
'ok)二维表
在二维表（2D table）中，每个值要由两个键来确定。我们可以把二维表构造成一维表，其中每个键标识一张子表。假设我们有两张表：「math」和「letters」，键值对如下：
math:
+ : 43
- : 45
* : 42
letters:
a : 97
b : 98我们可以把它们放进一张大表：
lookup
在二维表中查找值需要两个键：第一个键用来找到正确的子表，第二个键用来在该子表中找到正确的值。
(define (lookup key-1 key-2 table)
(let ((subtable (assoc key-1 (cdr table))))
(if subtable
(let ((record (assoc key-2 (cdr subtable))))
(if record
(cdr record)
#f))
#f)))insert
向二维表插入同样需要两个键：第一个键用来尝试找到正确的子表——若该键对应的子表不存在，就新建一张子表；若子表已存在，就沿用一维表 insert! 的算法。
(define (insert! key-1 key-2 value table)
(let ((subtable (assoc key-1 (cdr table))))
(if subtable
(let ((record (assoc key-2 (cdr subtable))))
(if record
(set-cdr! record value)
(set-cdr! subtable
(cons (cons key-2 value)
(cdr subtable)))))
(set-cdr! table
(cons (list key-1
(cons key-2 value))
(cdr table)))))
'ok)局部表
上面定义的 lookup 和 insert! 都把表作为参数，这让我们能编写访问多张表的程序。处理多张表的另一种办法是：为每张表配备独立的 lookup 和 insert! 过程。具体做法是把表过程式地表示为一个对象，它把一张内部表作为局部状态来维护。当收到恰当的消息时，这个「表对象」就给出操作内部表所用的过程。下面是按这种方式表示的二维表的生成器：
(define (make-table)
(let ((local-table (list '*table*)))
(define (lookup key-1 key-2)
(let ((subtable (assoc key-1 (cdr local-table))))
(if subtable
(let ((record (assoc key-2 (cdr subtable))))
(if record
(cdr record)
false))
false)))
(define (insert! key-1 key-2 value)
(let ((subtable (assoc key-1 (cdr local-table))))
(if subtable
(let ((record (assoc key-2 (cdr subtable))))
(if record
(set-cdr! record value)
(set-cdr! subtable
(cons (cons key-2 value)
(cdr subtable)))))
(set-cdr! local-table
(cons (list key-1
(cons key-2 value))
(cdr local-table)))))
'ok)
(define (dispatch m)
(cond ((eq? m 'lookup-proc) lookup)
((eq? m 'insert-proc!) insert!)
(else (error "Unknown operation -- TABLE" m))))
dispatch))get 和 put
在第 2 单元的「数据导向」小节中，我们曾用二维表把值存储在两个键之下，用的正是 get 和 put 这两个过程：
(put <key-1> <key-2> <value>)
(get <key-1> <key-2>)现在可以用我们的表来定义这两个过程了：
(define operation-table (make-table))
(define get (operation-table 'lookup-proc))
(define put (operation-table 'insert-proc!))get 接受两个键作为参数，put 接受两个键和一个值。两个操作访问的是同一张局部表，它被封装在 make-table 调用所创建的对象内部。