构造一个单元素的 cdr-circular
列表,可以将一个列表的 cdr
设置成列表自身:
这样 x
就是一个环形列表,其结构如图 12.12 (左) 所示。
图 12.12 环状列表。
> (setf *print-circle* t )
T
> x
#1=(A . #1#)
如果你需要,你也可以使用 #n=
和 #n#
这两个读取宏,来自己表示共享结构。
cdr-cicular
列表十分有用,比如,可以用来表示缓冲区、池。下面这个函数,可以将一个普通的非空列表,转换成一个对应的 列表:
另外一种环状列表叫做 car-circular
列表。car-circular
列表是一个树,并将其自身当作自己的子树的结构。因为环是通过一个 cons
的 car
形成的,所以叫做 car-circular
。这里构造了一个 car-circular
,它的第二个元素是它自身:
(setf (car y) y)
y)
#i=(#i#)
图 12.12 (右) 展示了其结构。这个 car-circular
是一个正规列表。 cdr-circular
列表都不是正规列表,除开一些特殊情况 car-circular
列表是正规列表。
很难想像这样的一个列表有什么用。实际上,了解环形列表的主要目的就是为了避免因为偶然因素构造出了环形列表,因为,将一个环形列表传给一个函数,如果该函数遍历这个环形列表,它将进入死循环。
环形结构的这种问题在列表以外的其他对象中也存在。比如,一个数组可以将数组自身当作其元素:
> (setf *print-array* t )
> (let ((a (make-array 1)) )
(setf (aref a 0) a)
a)
#1=#(#1#)
实际上,任何可以包含元素的对象都可能包含其自身作为元素。
用 defstruct
构造出环形结构是相当常见的。比如,一个结构 c
是一颗树的元素,它的 parent
字段所指向的结构 p
的 child
字段也恰好指向 c
。