12.1 共享结构 (Shared Structure)

多个列表可以共享 cons 。在最简单的情况下，一个列表可以是另一个列表的一部分。

> (setf part (list 'b 'c))
(B C)
> (setf whole (cons 'a part))
(A B C)

图 12.1 共享结构

执行上述操作后，第一个 cons 是第二个 cons 的一部分 (事实上，是第二个 cons 的 cdr )。在这样的情况下，我们说，这两个列表是共享结构 (Share Structure)。这两个列表的基本结构如图 12.1 所示。

其中，第一个 cons 是第二个 cons 的一部分 (事实上，是第二个 cons 的 cdr )。在这样的情况下，我们称这两个列表为共享结构 (Share Structure)。这两个列表的基本结构如图 12.1 所示。

使用 tailp 判断式来检测一下。将两个列表作为它的输入参数，如果第一个列表是第二个列表的一部分时，则返回 T ：

> (tailp part whole)
T

我们可以把它想像成：

(defun our-tailp (x y)
  (or (eql x y)
      (and (consp y)
                         (our-tailp x (cdr y)))))

如定义所表明的，每个列表都是它自己的尾端， nil 是每一个正规列表的尾端。

在更复杂的情况下，两个列表可以是共享结构，但彼此都不是对方的尾端。在这种情况下，他们都有一个共同的尾端，如图 12.2 所示。我们像这样构建这种情况：

(setf part (list 'b 'c)
                        whole1 (cons 1 part)
                        whole2 (cons 2 part))

图 12.2 被共享的尾端

现在 whole1 和 whole2 共享结构，但是它们彼此都不是对方的一部分。

当存在嵌套列表时，重要的是要区分是列表共享了结构，还是列表的元素共享了结构。顶层列表结构指的是，直接构成列表的那些 cons ，而不包含那些用于构造列表元素的 cons 。图 12.3 是一个嵌套列表的顶层列表结构 (译者注：图 12.3 中上面那三个有黑色阴影的 cons 即构成顶层列表结构的 cons )。

图 12.3 顶层列表结构

两个 cons 是否共享结构，取决于我们把它们看作是列表还是树)。可能存在两个嵌套列表，当把它们看作树时，它们共享结构，而看作列表时，它们不共享结构。图 12.4 构建了这种情况，两个列表以一个元素的形式包含了同一个列表，代码如下：

(setf element (list 'a 'b)
      holds1 (list 1 element 2)
      holds2 (list element 3))

图 12.4 共享子树

虽然 holds1 的第二个元素和 holds2 的第一个元素共享结构 (其实是相同的)，但如果把 holds1 和 holds2 看成是列表时，它们不共享结构。仅当两个列表共享顶层列表结构时，才能说这两个列表共享结构，而 holds1 和 holds2 没有共享顶层列表结构。

如果我们想避免共享结构，可以使用复制。函数 copy-list 可以这样定义：

(defun our-copy-list (lst)
   (if (null lst)
       nil
       (cons (car lst) (our-copy-list (cdr lst)))))

它返回一个不与原始列表共享顶层列表结构的新列表。函数 copy-tree 可以这样定义：

(defun our-copy-tree (tr)
   (if (atom tr)
        tr
        (cons (our-copy-tree (car tr))
              (our-copy-tree (cdr tr)))))

它返回一个连原始列表的树型结构也不共享的新列表。图 12.5 显示了对一个嵌套列表使用 copy-list 和 copy-tree 的区别。

图 12.5 两种复制