12.7 环状结构 (Circular Structure)

将列表结构稍微修改一下，就可以得到一个环形列表。存在两种环形列表。最常用的一种是其顶层列表结构是一个环的，我们把它叫做 cdr-circular ，因为环是由一个 cons 的 cdr 构成的。

构造一个单元素的 cdr-circular 列表，可以将一个列表的 cdr 设置成列表自身：

  1. > (setf x (list 'a))
  2. (A)
  3. > (progn (setf (cdr x) x) nil)
  4. NIL

这样 x 就是一个环形列表，其结构如图 12.12 (左) 所示。

../_images/Figure-12.12.png

图 12.12 环状列表。

如果 Lisp 试着打印我们刚刚构造的结构，将会显示 (a a a a a …… —— 无限个 a)。但如果设置全局变量 *print-circle* 为 t 的话，Lisp 就会采用一种方式打印出一个能代表环形结构的对象：

  1. > (setf *print-circle* t )
  2. T
  3. > x
  4. #1=(A . #1#)

如果你需要，你也可以使用 #n= 和 #n# 这两个读取宏，来自己表示共享结构。

cdr-cicular 列表十分有用，比如，可以用来表示缓冲区、池。下面这个函数，可以将一个普通的非空列表，转换成一个对应的 cdr-cicular 列表：

  1. (defun circular (lst)
  2.         (setf (cdr (last lst)) lst))

另外一种环状列表叫做 car-circular 列表。car-circular 列表是一个树，并将其自身当作自己的子树的结构。因为环是通过一个 cons 的 car 形成的，所以叫做 car-circular。这里构造了一个 car-circular ，它的第二个元素是它自身：

  1. > (let ((y (list 'a )))
  2. (setf (car y) y)
  3.      y)
  4. #i=(#i#)

图 12.12 (右) 展示了其结构。这个 car-circular 是一个正规列表。 cdr-circular 列表都不是正规列表，除开一些特殊情况 car-circular 列表是正规列表。

一个列表也可以既是 car-circular ，又是 cdr-circular 。 一个 cons 的 car 和 cdr 均是其自身：

  1. > (let ((c (cons 11)) )
  2.      (setf (car c) c
  3.             (cdr c) c)
  4.      c)
  5. #1=(#1# . #1#)

很难想像这样的一个列表有什么用。实际上，了解环形列表的主要目的就是为了避免因为偶然因素构造出了环形列表，因为，将一个环形列表传给一个函数，如果该函数遍历这个环形列表，它将进入死循环。

环形结构的这种问题在列表以外的其他对象中也存在。比如，一个数组可以将数组自身当作其元素：

  1. > (setf *print-array* t )
  2. T
  3. > (let ((a (make-array 1)) )
  4.           (setf (aref a 0) a)
  5.           a)
  6. #1=#(#1#)

实际上，任何可以包含元素的对象都可能包含其自身作为元素。

用 defstruct 构造出环形结构是相当常见的。比如，一个结构 c 是一颗树的元素，它的 parent 字段所指向的结构 p 的 child 字段也恰好指向 c 。

  1. > (progn (defstruct elt
  2.           (parent nil ) (child nil) )
  3.      (let ((c (make-elt) )
  4.                (p (make-elt)) )
  5.           (setf (elt-parent c) p
  6.                     (elt-child p) c)
  7.           c) )
  8. #1=#S(ELT PARENT #S(ELT PARENT NIL CHILD #1#) CHILD NIL)

要实现像这样一个结构的打印函数 (print-function)，我们需要将全局变量 *print-circle* 绑定为 t ，或者避免打印可能构成环的字段。