可变的列表结构

介绍 set-car! 和 set-cdr! 的用法、共享与同一性，以及 append! 等变动型操作对列表结构的影响。

变动一个序对

在第 2 单元中，我们用序对作为存储数据的数据结构的基石。现在我们已经进入一个可以变动数据的领域，有时我们也想变动数据结构中存储的内容。

(define x (cons 1 2))

假设 x 的 car 记录我从楼梯上摔下来的次数，cdr 记录我走错洗手间的次数。刚才我又从楼梯上摔了一跤，所以应该把 x 的 car 更新为 2。怎样才能不创建新序对就做到这一点？Scheme 提供了下面这个函数：

(set-car! x 2)

顾名思义，set-car! 接受一个序对和一个值，把该序对的 car 改成指向第二个参数指定的值。

一般形式为：

(set-car! <pair> <value>)

不出所料，Scheme 也提供了 set-cdr!：它接受一个序对和一个值，把该序对 cdr 的指针改为指向这个值。沿用前面的例子，调用

(set-cdr! x 3)

后，序对的变化如下图所示。

一般形式为：

(set-cdr! <pair> <value>)

下面看看 set-car! 和 set-cdr! 如何作用于更复杂的列表。给定以下序对：

(define x (cons (list a b) (list c d)))
(define y (list e f))

接下来对 set-car! 和 set-cdr! 的几次调用互相独立，都基于上面这个初始结构。做下面几道题时，强烈建议动手画盒式指针图。

对初始结构调用

(set-car! x y)

会得到下面的盒式指针图：

这次调用把 x 的 car 指针从原来指向的 (list a b) 改成指向 y 指向的地方，即 (list e f)。那么包含 a 和 b 的那个列表会怎样呢？其实它什么也没发生，只是由于再没有任何指针引用它，它变得不可达了。

检验理解

在上面例 1 中，x 会打印出什么？

假设我们有例 1 的初始结构，现在调用下面的表达式：

(set-car! (car x) 'z)

y 会打印出什么？

从初始结构出发，现在调用

(define z (cons y (cdr x)))

得到如下盒式指针图：

检验理解

从例 2 所示的结构出发，现在调用

(set-cdr! (cdr z) nil)

x 现在会打印出什么？

从例 2 所示的结构出发，我们应该怎样调用，才能让 z 返回 ((e f) b)？

set-car! 和 set-cdr! 修改的是已有的序对；而 cons、list 这类过程则会创建新序对。append 又属于哪一种？它是通过改变其中一个列表的 cdr 指针，把两个列表「拼接」起来的吗？回想一下我们一直在用的 append 定义：

(define (append x y)
  (if (null? x)
      y
      (cons (car x) (append (cdr x) y))))

append 把 x 和 y 的元素逐个 cons 起来，形成一个新列表。这说明 append 返回的是一个新列表。

检验理解

下面这段代码输入 STk 后会打印出什么？先凭经验猜一猜，再放到解释器里试一试。

> (define a (list 1 2 3 4 5))
a
> (set-cdr! (cdr a) (cdddr a))
okay
> a

过程 append! 与 append 类似，但它是变动器而不是构造函数。它通过把两个列表接在一起的方式追加列表：修改 x 的最后一个序对，让它的 cdr 指向 y。（用空的 x 调用 append! 是错误的。）例如：

(define (append! x y)
    (set-cdr! (last-pair x) y)
    x)

last-pair 过程接受一个列表，返回它的最后一个序对：

(define (last-pair x)
    (if (null? (cdr x))
        x
        (last-pair (cdr x))))

现在来看下面这段代码：

> (define x (list 'a 'b))
x
> (define y (list 'c 'd))
y
> (define z (append x y))
z
> z
(a b c d)

(cdr x) 会返回什么？放进 STk 之前先自己想一想。现在换用 append!：

> (define w (append! x y))
w
> w
(a b c d)

现在 (cdr x) 又会返回什么？

上面的练习敲响了一个大大的警钟：知道一个序对何时被共享、何时被创建，非常重要。在上面的代码里，x 和 y 引用的是同一批序对，而 z 创建的是另一个包含相同元素的序对。

(define x (cons 1 2))
(define y x)
(define z (cons 1 2))

还记得 equal? 谓词吗？它可以检查两个序对是否包含相同的元素。

(equal? x y)、(equal? x z)、(equal? y z) 都返回 #t，因为它们在相同的位置持有相同的元素。有没有办法区分出 x 和 z 指向的是不同的结构呢？有！Scheme 提供了 eq? 谓词，它接受两个参数，检查它们是否指向同一个序对。

> (eq? x y)
#t
> (eq? x z)
#f
> (eq? y z)
#f