3.3 節(jié)中介紹了 Lisp 如何使用指針允許我們將任何值放到任何地方。這種說(shuō)法是完全有可能的，但這并不一定都是好事。
例如，一個(gè)對(duì)象可以是它自已的一個(gè)元素。這是好事還是壞事，取決于程序員是不是有意這樣設(shè)計(jì)的。
[TOC]
## 12.1 共享結(jié)構(gòu) (Shared Structure)[](http://acl.readthedocs.org/en/latest/zhCN/ch12-cn.html#shared-structure "Permalink to this headline")
多個(gè)列表可以共享?`cons`?。在最簡(jiǎn)單的情況下，一個(gè)列表可以是另一個(gè)列表的一部分。
~~~
> (setf part (list 'b 'c))
(B C)
> (setf whole (cons 'a part))
(A B C)
~~~
**圖 12.1 共享結(jié)構(gòu)**
執(zhí)行上述操作后，第一個(gè)?`cons`?是第二個(gè)?`cons`?的一部分 (事實(shí)上，是第二個(gè)?`cons`?的?`cdr`?)。在這樣的情況下，我們說(shuō)，這兩個(gè)列表是共享結(jié)構(gòu) (Share Structure)。這兩個(gè)列表的基本結(jié)構(gòu)如圖 12.1 所示。
其中，第一個(gè)?`cons`?是第二個(gè)?`cons`?的一部分 (事實(shí)上，是第二個(gè)?`cons`?的?`cdr`?)。在這樣的情況下，我們稱這兩個(gè)列表為共享結(jié)構(gòu) (Share Structure)。這兩個(gè)列表的基本結(jié)構(gòu)如圖 12.1 所示。
使用?`tailp`?判斷式來(lái)檢測(cè)一下。將兩個(gè)列表作為它的輸入?yún)?shù)，如果第一個(gè)列表是第二個(gè)列表的一部分時(shí)，則返回?`T`?：
~~~
> (tailp part whole)
T
~~~
我們可以把它想像成：
~~~
(defun our-tailp (x y)
(or (eql x y)
(and (consp y)
(our-tailp x (cdr y)))))
~~~
如定義所表明的，每個(gè)列表都是它自己的尾端，?`nil`?是每一個(gè)正規(guī)列表的尾端。
在更復(fù)雜的情況下，兩個(gè)列表可以是共享結(jié)構(gòu)，但彼此都不是對(duì)方的尾端。在這種情況下，他們都有一個(gè)共同的尾端，如圖 12.2 所示。我們像這樣構(gòu)建這種情況：
~~~
(setf part (list 'b 'c)
whole1 (cons 1 part)
whole2 (cons 2 part))
~~~
**圖 12.2 被共享的尾端**
現(xiàn)在?`whole1`?和?`whole2`?共享結(jié)構(gòu)，但是它們彼此都不是對(duì)方的一部分。
當(dāng)存在嵌套列表時(shí)，重要的是要區(qū)分是列表共享了結(jié)構(gòu)，還是列表的元素共享了結(jié)構(gòu)。頂層列表結(jié)構(gòu)指的是，直接構(gòu)成列表的那些`cons`?，而不包含那些用于構(gòu)造列表元素的?`cons`?。圖 12.3 是一個(gè)嵌套列表的頂層列表結(jié)構(gòu) (**譯者注：**圖 12.3 中上面那三個(gè)有黑色陰影的?`cons`?即構(gòu)成頂層列表結(jié)構(gòu)的?`cons`?)。
**圖 12.3 頂層列表結(jié)構(gòu)**
兩個(gè)?`cons`?是否共享結(jié)構(gòu)，取決于我們把它們看作是列表還是[樹](http://zh.wikipedia.org/wiki/%E6%A0%91_(%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84))?？赡艽嬖趦蓚€(gè)嵌套列表，當(dāng)把它們看作樹時(shí)，它們共享結(jié)構(gòu)，而看作列表時(shí)，它們不共享結(jié)構(gòu)。圖 12.4 構(gòu)建了這種情況，兩個(gè)列表以一個(gè)元素的形式包含了同一個(gè)列表，代碼如下：
~~~
(setf element (list 'a 'b)
holds1 (list 1 element 2)
holds2 (list element 3))
~~~
**圖 12.4 共享子樹**
雖然?`holds1`?的第二個(gè)元素和?`holds2`?的第一個(gè)元素共享結(jié)構(gòu) (其實(shí)是相同的)，但如果把?`holds1`?和?`holds2`?看成是列表時(shí)，它們不共享結(jié)構(gòu)。僅當(dāng)兩個(gè)列表共享頂層列表結(jié)構(gòu)時(shí)，才能說(shuō)這兩個(gè)列表共享結(jié)構(gòu)，而?`holds1`?和?`holds2`?沒(méi)有共享頂層列表結(jié)構(gòu)。
如果我們想避免共享結(jié)構(gòu)，可以使用復(fù)制。函數(shù)?`copy-list`?可以這樣定義：
~~~
(defun our-copy-list (lst)
(if (null lst)
nil
(cons (car lst) (our-copy-list (cdr lst)))))
~~~
它返回一個(gè)不與原始列表共享頂層列表結(jié)構(gòu)的新列表。函數(shù)?`copy-tree`?可以這樣定義：
~~~
(defun our-copy-tree (tr)
(if (atom tr)
tr
(cons (our-copy-tree (car tr))
(our-copy-tree (cdr tr)))))
~~~
它返回一個(gè)連原始列表的樹型結(jié)構(gòu)也不共享的新列表。圖 12.5 顯示了對(duì)一個(gè)嵌套列表使用?`copy-list`?和?`copy-tree`?的區(qū)別。
**圖 12.5 兩種復(fù)制**
## 12.2 修改 (Modification)[](http://acl.readthedocs.org/en/latest/zhCN/ch12-cn.html#modification "Permalink to this headline")
為什么要避免共享結(jié)構(gòu)呢？之前討論的共享結(jié)構(gòu)問(wèn)題僅僅是個(gè)智力練習(xí)，到目前為止，并沒(méi)使我們?cè)趯?shí)際寫程序的時(shí)候有什么不同。當(dāng)修改一個(gè)被共享的結(jié)構(gòu)時(shí)，問(wèn)題出現(xiàn)了。如果兩個(gè)列表共享結(jié)構(gòu)，當(dāng)我們修改了其中一個(gè)，另外一個(gè)也會(huì)無(wú)意中被修改。
上一節(jié)中，我們介紹了怎樣構(gòu)建一個(gè)是其它列表的尾端的列表：
~~~
(setf whole (list 'a 'b 'c)
tail (cdr whole))
~~~
因?yàn)?`whole`?的?`cdr`?與?`tail`?是相等的，無(wú)論是修改?`tail`?還是?`whole`?的?`cdr`?，我們修改的都是同一個(gè)?`cons`?：
~~~
> (setf (second tail ) 'e)
E
> tail
(B E)
> whole
(A B E)
~~~
同樣的，如果兩個(gè)列表共享同一個(gè)尾端，這種情況也會(huì)發(fā)生。
一次修改兩個(gè)對(duì)象并不總是錯(cuò)誤的。有時(shí)候這可能正是你想要的。但如果無(wú)意的修改了共享結(jié)構(gòu)，將會(huì)引入一些非常微妙的 bug。Lisp 程序員要培養(yǎng)對(duì)共享結(jié)構(gòu)的意識(shí)，并且在這類錯(cuò)誤發(fā)生時(shí)能夠立刻反應(yīng)過(guò)來(lái)。當(dāng)一個(gè)列表神秘的改變了的時(shí)候，很有可能是因?yàn)楦淖兞似渌c之共享結(jié)構(gòu)的對(duì)象。
真正危險(xiǎn)的不是共享結(jié)構(gòu)，而是改變被共享的結(jié)構(gòu)。為了安全起見(jiàn)，干脆避免對(duì)結(jié)構(gòu)使用?`setf`?(以及相關(guān)的運(yùn)算，比如：?`pop`?，`rplaca`?等)，這樣就不會(huì)遇到問(wèn)題了。如果某些時(shí)候不得不修改列表結(jié)構(gòu)時(shí)，要搞清楚要修改的列表的來(lái)源，確保它不要和其它不需要改變的對(duì)象共享結(jié)構(gòu)。如果它和其它不需要改變的對(duì)象共享了結(jié)構(gòu)，或者不能預(yù)測(cè)它的來(lái)源，那么復(fù)制一個(gè)副本來(lái)進(jìn)行改變。
當(dāng)你調(diào)用別人寫的函數(shù)的時(shí)候要加倍小心。除非你知道它內(nèi)部的操作，否則，你傳入的參數(shù)時(shí)要考慮到以下的情況：
1.它對(duì)你傳入的參數(shù)可能會(huì)有破壞性的操作
2.你傳入的參數(shù)可能被保存起來(lái)，如果你調(diào)用了一個(gè)函數(shù)，然后又修改了之前作為參數(shù)傳入該函數(shù)的對(duì)象，那么你也就改變了函數(shù)已保存起來(lái)作為它用的對(duì)象[1]。
在這兩種情況下，解決的方法是傳入一個(gè)拷貝。
在 Common Lisp 中，一個(gè)函數(shù)調(diào)用在遍歷列表結(jié)構(gòu) (比如，?`mapcar`?或?`remove-if`?的參數(shù))的過(guò)程中不允許修改被遍歷的結(jié)構(gòu)。關(guān)于評(píng)估這樣的代碼的重要性并沒(méi)有明確的規(guī)定。
## 12.3 示例：隊(duì)列 (Example: Queues)[](http://acl.readthedocs.org/en/latest/zhCN/ch12-cn.html#example-queues "Permalink to this headline")
共享結(jié)構(gòu)并不是一個(gè)總讓人擔(dān)心的特性。我們也可以對(duì)其加以利用的。這一節(jié)展示了怎樣用共享結(jié)構(gòu)來(lái)表示[隊(duì)列](http://zh.wikipedia.org/wiki/%E9%98%9F%E5%88%97)。隊(duì)列對(duì)象是我們可以按照數(shù)據(jù)的插入順序逐個(gè)檢出數(shù)據(jù)的倉(cāng)庫(kù)，這個(gè)規(guī)則叫做[先進(jìn)先出 (FIFO, first in, first out)](http://zh.wikipedia.org/zh-cn/%E5%85%88%E9%80%B2%E5%85%88%E5%87%BA)。
用列表表示[棧 (stack)](http://zh.wikipedia.org/wiki/%E6%A0%88)比較容易，因?yàn)闂Ｊ菑耐欢瞬迦牒蜋z出。而表示隊(duì)列要困難些，因?yàn)殛?duì)列的插入和檢出是在不同端。為了有效的實(shí)現(xiàn)隊(duì)列，我們需要找到一種辦法來(lái)指向列表的兩個(gè)端。
圖 12.6 給出了一種可行的策略。它展示怎樣表示一個(gè)含有 a，b，c 三個(gè)元素的隊(duì)列。一個(gè)隊(duì)列就是一對(duì)列表，最后那個(gè)?`cons`?在相同的列表中。這個(gè)列表對(duì)由被稱作頭端 (front)和尾端 (back)的兩部分組成。如果要從隊(duì)列中檢出一個(gè)元素，只需在其頭端?`pop`，要插入一個(gè)元素，則創(chuàng)建一個(gè)新的?`cons`?，把尾端的?`cdr`?設(shè)置成指向這個(gè)?`cons`?，然后將尾端指向這個(gè)新的?`cons`?。
**圖 12.6 一個(gè)隊(duì)列的結(jié)構(gòu)**
~~~
(defun make-queue () (cons nil nil))
(defun enqueue (obj q)
(if (null (car q))
(setf (cdr q) (setf (car q) (list obj)))
(setf (cdr (cdr q)) (list obj)
(cdr q) (cdr (cdr q))))
(car q))
(defun dequeue (q)
(pop (car q)))
~~~
**圖 12.7 隊(duì)列實(shí)現(xiàn)**
圖 12.7 中的代碼實(shí)現(xiàn)了這一策略。其用法如下：
~~~
> (setf q1 (make-queue))
(NIL)
> (progn (enqueue 'a q1)
(enqueue 'b q1)
(enqueue 'c q1))
(A B C)
~~~
現(xiàn)在，?`q1`?的結(jié)構(gòu)就如圖 12.6 那樣：
~~~
> q1
((A B C) C)
~~~
從隊(duì)列中檢出一些元素：
~~~
> (dequeue q1)
A
> (dequeue q1)
B
> (enqueue 'd q1)
(C D)
~~~
## 12.4 破壞性函數(shù) (Destructive Functions)[](http://acl.readthedocs.org/en/latest/zhCN/ch12-cn.html#destructive-functions "Permalink to this headline")
Common Lisp 包含一些允許修改列表結(jié)構(gòu)的函數(shù)。為了提高效率，這些函數(shù)是具有破壞性的。雖然它們可以回收利用作為參數(shù)傳給它們的?`cons`?，但并不是因?yàn)橄胍鼈兊母弊饔枚{(diào)用它們 (**譯者注：**因?yàn)檫@些函數(shù)的副作用并沒(méi)有任何保證，下面的例子將說(shuō)明問(wèn)題)。
比如，?`delete`?是?`remove`?的一個(gè)具有破壞性的版本。雖然它可以破壞作為參數(shù)傳給它的列表，但它并不保證什么。在大多數(shù)的 Common Lisp 的實(shí)現(xiàn)中，會(huì)出現(xiàn)下面的情況：
~~~
> (setf lst '(a r a b i a) )
(A R A B I A)
> (delete 'a lst )
(R B I)
> lst
(A R B I)
~~~
正如?`remove`?一樣，如果你想要副作用，應(yīng)該對(duì)返回值使用?`setf`?：
~~~
(setf lst (delete 'a lst))
~~~
破壞性函數(shù)是怎樣回收利用傳給它們的列表的呢？比如，可以考慮?`nconc`?——?`append`?的破壞性版本。[2]下面是兩個(gè)參數(shù)版本的實(shí)現(xiàn)，其清楚地展示了兩個(gè)已知列表是怎樣被縫在一起的：
~~~
(defun nconc2 ( x y)
(if (consp x)
(progn
(setf (cdr (last x)) y)
x)
y))
~~~
我們找到第一個(gè)列表的最后一個(gè)?*Cons*?核 (cons cells)，把它的?`cdr`?設(shè)置成指向第二個(gè)列表。一個(gè)正規(guī)的多參數(shù)的?`nconc`?可以被定義成像附錄 B 中的那樣。
函數(shù)?`mapcan`?類似?`mapcar`?，但它是用?`nconc`?把函數(shù)的返回值 (必須是列表) 拼接在一起的：
~~~
> (mapcan #'list
'(a b c)
'(1 2 3 4))
( A 1 B 2 C 3)
~~~
這個(gè)函數(shù)可以定義如下：
~~~
(defun our-mapcan (fn &rest lsts )
(apply #'nconc (apply #'mapcar fn lsts)))
~~~
使用?`mapcan`?時(shí)要謹(jǐn)慎，因?yàn)樗哂衅茐男?。它?`nconc`?拼接返回的列表，所以這些列表最好不要再在其它地方使用。
這類函數(shù)在處理某些問(wèn)題的時(shí)候特別有用，比如，收集樹在某層上的所有子結(jié)點(diǎn)。如果?`children`?函數(shù)返回一個(gè)節(jié)點(diǎn)的孩子節(jié)點(diǎn)的列表，那么我們可以定義一個(gè)函數(shù)返回某節(jié)點(diǎn)的孫子節(jié)點(diǎn)的列表如下：
~~~
(defun grandchildren (x)
(mapcan #'(lambda (c)
(copy-list (children c)))
(children x)))
~~~
這個(gè)函數(shù)調(diào)用?`copy-list`?時(shí)存在一個(gè)假設(shè) ——?`chlidren`?函數(shù)返回的是一個(gè)已經(jīng)保存在某個(gè)地方的列表，而不是構(gòu)建了一個(gè)新的列表。
一個(gè)?`mapcan`?的無(wú)損變體可以這樣定義：
~~~
(defun mappend (fn &rest lsts )
(apply #'append (apply #'mapcar fn lsts)))
~~~
如果使用?`mappend`?函數(shù)，那么?`grandchildren`?的定義就可以省去?`copy-list`?：
~~~
(defun grandchildren (x)
(mappend #'children (children x)))
~~~
## 12.5 示例：二叉搜索樹 (Example: Binary Search Trees)[](http://acl.readthedocs.org/en/latest/zhCN/ch12-cn.html#example-binary-search-trees "Permalink to this headline")
在某些情況下，使用破壞性操作比使用非破壞性的顯得更自然。第 4.7 節(jié)中展示了如何維護(hù)一個(gè)具有二分搜索格式的有序?qū)ο蠹?(或者說(shuō)維護(hù)一個(gè)[二叉搜索樹 (BST)](http://zh.wikipedia.org/zh-cn/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9))。第 4.7 節(jié)中給出的函數(shù)都是非破壞性的，但在我們真正使用BST的時(shí)候，這是一個(gè)不必要的保護(hù)措施。本節(jié)將展示如何定義更符合實(shí)際應(yīng)用的具有破壞性的插入函數(shù)和刪除函數(shù)。
圖 12.8 展示了如何定義一個(gè)具有破壞性的?`bst-insert`?(第 72 頁(yè)「**譯者注：**第 4.7 節(jié)」)。相同的輸入?yún)?shù)，能夠得到相同返回值。唯一的區(qū)別是，它將修改作為第二個(gè)參數(shù)輸入的 BST。 在第 2.12 節(jié)中說(shuō)過(guò)，具有破壞性并不意味著一個(gè)函數(shù)調(diào)用具有副作用。的確如此，如果你想使用?`bst-insert!`?構(gòu)造一個(gè) BST，你必須像調(diào)用?`bst-insert`?那樣調(diào)用它：
~~~
> (setf *bst* nil)
NIL
> (dolist (x '(7 2 9 8 4 1 5 12))
(setf *bst* (bst-insert! x *bst* #'<)))
NIL
~~~
~~~
(defun bst-insert! (obj bst <)
(if (null bst)
(make-node :elt obj)
(progn (bsti obj bst <)
bst)))
(defun bsti (obj bst <)
(let ((elt (node-elt bst)))
(if (eql obj elt)
bst
(if (funcall < obj elt)
(let ((l (node-l bst)))
(if l
(bsti obj l <)
(setf (node-l bst)
(make-node :elt obj))))
(let ((r (node-r bst)))
(if r
(bsti obj r <)
(setf (node-r bst)
(make-node :elt obj))))))))
~~~
**圖 12.8: 二叉搜索樹：破壞性插入**
你也可以為 BST 定義一個(gè)類似 push 的功能，但這超出了本書的范圍。(好奇的話，可以參考第 409 頁(yè) 「**譯者注：**即備注 204 」 的宏定義。)
與?`bst-remove`?(第 74 頁(yè)「**譯者注：**第 4.7 節(jié)」) 對(duì)應(yīng)，圖 12.9 展示了一個(gè)破壞性版本的?`bst-delete`?。同?`delete`?一樣，我們調(diào)用它并不是因?yàn)樗母弊饔?。你?yīng)該像調(diào)用?`bst-remove`?那樣調(diào)用?`bst-delete`?：
~~~
> (setf *bst* (bst-delete 2 *bst* #'<) )
#<7>
> (bst-find 2 *bst* #'<)
NIL
~~~
~~~
(defun bst-delete (obj bst <)
(if bst (bstd obj bst nil nil <))
bst)
(defun bstd (obj bst prev dir <)
(let ((elt (node-elt bst)))
(if (eql elt obj)
(let ((rest (percolate! bst)))
(case dir
(:l (setf (node-l prev) rest))
(:r (setf (node-r prev) rest))))
(if (funcall < obj elt)
(if (node-l bst)
(bstd obj (node-l bst) bst :l <))
(if (node-r bst)
(bstd obj (node-r bst) bst :r <))))))
(defun percolate! (bst)
(cond ((null (node-l bst))
(if (null (node-r bst))
nil
(rperc! bst)))
((null (node-r bst)) (lperc! bst))
(t (if (zerop (random 2))
(lperc! bst)
(rperc! bst)))))
(defun lperc! (bst)
(setf (node-elt bst) (node-elt (node-l bst)))
(percolate! (node-l bst)))
(defun rperc! (bst)
(setf (node-elt bst) (node-elt (node-r bst)))
(percolate! (node-r bst)))
~~~
**圖 12.9: 二叉搜索樹：破壞性刪除**
**譯注:**?此范例已被回報(bào)為錯(cuò)誤的，一個(gè)修復(fù)的版本請(qǐng)?jiān)煸L[這里](https://gist.github.com/2868339)。
## 12.6 示例：雙向鏈表 (Example: Doubly-Linked Lists)[](http://acl.readthedocs.org/en/latest/zhCN/ch12-cn.html#example-doubly-linked-lists "Permalink to this headline")
普通的 Lisp 列表是單向鏈表，這意味著其指針指向一個(gè)方向：我們可以獲取下一個(gè)元素，但不能獲取前一個(gè)。在[雙向鏈表](http://zh.wikipedia.org/wiki/%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8)中，指針指向兩個(gè)方向，我們獲取前一個(gè)元素和下一個(gè)元素都很容易。這一節(jié)將介紹如何創(chuàng)建和操作雙向鏈表。
圖 12.10 展示了如何用結(jié)構(gòu)來(lái)實(shí)現(xiàn)雙向鏈表。將?`cons`?看成一種結(jié)構(gòu)，它有兩個(gè)字段：指向數(shù)據(jù)的?`car`?和指向下一個(gè)元素的?`cdr`?。要實(shí)現(xiàn)一個(gè)雙向鏈表，我們需要第三個(gè)字段，用來(lái)指向前一個(gè)元素。圖 12.10 中的?`defstruct`?定義了一個(gè)含有三個(gè)字段的對(duì)象?`dl`?(用于“雙向鏈接”)，我們將用它來(lái)構(gòu)造雙向鏈表。`dl`?的?`data`?字段對(duì)應(yīng)一個(gè)?`cons`?的?`car`，`next`?字段對(duì)應(yīng)?`cdr`?。?`prev`?字段就類似一個(gè)`cdr`?，指向另外一個(gè)方向。(圖 12.11 是一個(gè)含有三個(gè)元素的雙向鏈表。) 空的雙向鏈表為?`nil`?，就像空的列表一樣。
~~~
(defstruct (dl (:print-function print-dl))
prev data next)
(defun print-dl (dl stream depth)
(declare (ignore depth))
(format stream "#<DL ~A>" (dl->list dl)))
(defun dl->list (lst)
(if (dl-p lst)
(cons (dl-data lst) (dl->list (dl-next lst)))
lst))
(defun dl-insert (x lst)
(let ((elt (make-dl :data x :next lst)))
(when (dl-p lst)
(if (dl-prev lst)
(setf (dl-next (dl-prev lst)) elt
(dl-prev elt) (dl-prev lst)))
(setf (dl-prev lst) elt))
elt))
(defun dl-list (&rest args)
(reduce #'dl-insert args
:from-end t :initial-value nil))
(defun dl-remove (lst)
(if (dl-prev lst)
(setf (dl-next (dl-prev lst)) (dl-next lst)))
(if (dl-next lst)
(setf (dl-prev (dl-next lst)) (dl-prev lst)))
(dl-next lst))
~~~
**圖 12.10: 構(gòu)造雙向鏈表**
**圖 12.11: 一個(gè)雙向鏈表。**
為了便于操作，我們?yōu)殡p向鏈表定義了一些實(shí)現(xiàn)類似?`car`?，?`cdr`?，?`consp`?功能的函數(shù)：`dl-data`?，?`dl-next`?和?`dl-p`?。?`dl->list`是?`dl`?的打印函數(shù)(`print-function`)，其返回一個(gè)包含?`dl`?所有元素的普通列表。
函數(shù)?`dl-insert`?就像針對(duì)雙向鏈表的?`cons`?操作。至少，它就像?`cons`?一樣，是一個(gè)基本構(gòu)建函數(shù)。與?`cons`?不同的是，它實(shí)際上要修改作為第二個(gè)參數(shù)傳遞給它的雙向鏈表。在這種情況下，這是自然而然的。我們?`cons`?內(nèi)容到普通列表前面，不需要對(duì)普通列表的`rest`?(**譯者注：**?`rest`?即?`cdr`?的另一種表示方法，這里的?`rest`?是對(duì)通過(guò)?`cons`?構(gòu)建后列表來(lái)說(shuō)的，即修改之前的列表) 做任何修改。但是要在雙向鏈表的前面插入元素，我們不得不修改列表的?`rest`?(這里的?`rest`?即指沒(méi)修改之前的雙向鏈表) 的?`prev`?字段來(lái)指向這個(gè)新元素。
幾個(gè)普通列表可以共享同一個(gè)尾端。因?yàn)殡p向鏈表的尾端不得不指向它的前一個(gè)元素，所以不可能存在兩個(gè)雙向鏈表共享同一個(gè)尾端。如果?`dl-insert`?不具有破壞性，那么它不得不復(fù)制其第二個(gè)參數(shù)。
單向鏈表(普通列表)和雙向鏈表另一個(gè)有趣的區(qū)別是，如何持有它們。我們使用普通列表的首端，來(lái)表示單向鏈表，如果將列表賦值給一個(gè)變量，變量可以通過(guò)保存指向列表第一個(gè)?`cons`?的指針來(lái)持有列表。但是雙向鏈表是雙向指向的，我們可以用任何一個(gè)點(diǎn)來(lái)持有雙向鏈表。?`dl-insert`?另一個(gè)不同于?`cons`?的地方在于?`dl-insert`?可以在雙向鏈表的任何位置插入新元素，而?`cons`?只能在列表的首端插入。
函數(shù)?`dl-list`?是對(duì)于?`dl`?的類似?`list`?的功能。它接受任意多個(gè)參數(shù)，它會(huì)返回一個(gè)包含以這些參數(shù)作為元素的?`dl`?：
~~~
> (dl-list 'a 'b 'c)
#<DL (A B C)>
~~~
它使用了?`reduce`?函數(shù) (并設(shè)置其?`from-end`?參數(shù)為?`true`，`initial-value`?為?`nil`)，其功能等價(jià)于
~~~
(dl-insert 'a (dl-insert 'b (dl-insert 'c nil)) )
~~~
如果將?`dl-list`?定義中的?`#'dl-insert`?換成?`#'cons`，它就相當(dāng)于?`list`?函數(shù)了。下面是?`dl-list`?的一些常見(jiàn)用法：
~~~
> (setf dl (dl-list 'a 'b))
#<DL (A B)>
> (setf dl (dl-insert 'c dl))
#<DL (C A B)>
> (dl-insert 'r (dl-next dl))
#<DL (R A B)>
> dl
#<DL (C R A B)>
~~~
最后，`dl-remove`?的作用是從雙向鏈表中移除一個(gè)元素。同?`dl-insert`?一樣，它也是具有破壞性的。
## 12.7 環(huán)狀結(jié)構(gòu) (Circular Structure)[](http://acl.readthedocs.org/en/latest/zhCN/ch12-cn.html#circular-structure "Permalink to this headline")
將列表結(jié)構(gòu)稍微修改一下，就可以得到一個(gè)環(huán)形列表。存在兩種環(huán)形列表。最常用的一種是其頂層列表結(jié)構(gòu)是一個(gè)環(huán)的，我們把它叫做?`cdr-circular`?，因?yàn)榄h(huán)是由一個(gè)?`cons`?的?`cdr`?構(gòu)成的。
構(gòu)造一個(gè)單元素的?`cdr-circular`?列表，可以將一個(gè)列表的?`cdr`?設(shè)置成列表自身：
~~~
> (setf x (list 'a))
(A)
> (progn (setf (cdr x) x) nil)
NIL
~~~
這樣?`x`?就是一個(gè)環(huán)形列表，其結(jié)構(gòu)如圖 12.12 (左) 所示。
**圖 12.12 環(huán)狀列表。**
如果 Lisp 試著打印我們剛剛構(gòu)造的結(jié)構(gòu)，將會(huì)顯示 (a a a a a …… —— 無(wú)限個(gè)?`a`)。但如果設(shè)置全局變量?`*print-circle*`?為?`t`?的話，Lisp 就會(huì)采用一種方式打印出一個(gè)能代表環(huán)形結(jié)構(gòu)的對(duì)象：
~~~
> (setf *print-circle* t )
T
> x
#1=(A . #1#)
~~~
如果你需要，你也可以使用?`#n=`?和?`#n#`?這兩個(gè)讀取宏，來(lái)自己表示共享結(jié)構(gòu)。
`cdr-cicular`?列表十分有用，比如，可以用來(lái)表示緩沖區(qū)、池。下面這個(gè)函數(shù)，可以將一個(gè)普通的非空列表，轉(zhuǎn)換成一個(gè)對(duì)應(yīng)的`cdr-cicular`?列表：
~~~
(defun circular (lst)
(setf (cdr (last lst)) lst))
~~~
另外一種環(huán)狀列表叫做?`car-circular`?列表。`car-circular`?列表是一個(gè)樹，并將其自身當(dāng)作自己的子樹的結(jié)構(gòu)。因?yàn)榄h(huán)是通過(guò)一個(gè)`cons`?的?`car`?形成的，所以叫做?`car-circular`。這里構(gòu)造了一個(gè)?`car-circular`?，它的第二個(gè)元素是它自身：
~~~
> (let ((y (list 'a )))
(setf (car y) y)
y)
#i=(#i#)
~~~
圖 12.12 (右) 展示了其結(jié)構(gòu)。這個(gè)?`car-circular`?是一個(gè)正規(guī)列表。?`cdr-circular`?列表都不是正規(guī)列表，除開一些特殊情況?`car-circular`?列表是正規(guī)列表。
一個(gè)列表也可以既是?`car-circular`?，又是?`cdr-circular`?。 一個(gè)?`cons`?的?`car`?和?`cdr`?均是其自身：
~~~
> (let ((c (cons 11)) )
(setf (car c) c
(cdr c) c)
c)
#1=(#1# . #1#)
~~~
很難想像這樣的一個(gè)列表有什么用。實(shí)際上，了解環(huán)形列表的主要目的就是為了避免因?yàn)榕既灰蛩貥?gòu)造出了環(huán)形列表，因?yàn)?，將一個(gè)環(huán)形列表傳給一個(gè)函數(shù)，如果該函數(shù)遍歷這個(gè)環(huán)形列表，它將進(jìn)入死循環(huán)。
環(huán)形結(jié)構(gòu)的這種問(wèn)題在列表以外的其他對(duì)象中也存在。比如，一個(gè)數(shù)組可以將數(shù)組自身當(dāng)作其元素：
~~~
> (setf *print-array* t )
T
> (let ((a (make-array 1)) )
(setf (aref a 0) a)
a)
#1=#(#1#)
~~~
實(shí)際上，任何可以包含元素的對(duì)象都可能包含其自身作為元素。
用?`defstruct`?構(gòu)造出環(huán)形結(jié)構(gòu)是相當(dāng)常見(jiàn)的。比如，一個(gè)結(jié)構(gòu)?`c`?是一顆樹的元素，它的?`parent`?字段所指向的結(jié)構(gòu)?`p`?的?`child`?字段也恰好指向?`c`?。
~~~
> (progn (defstruct elt
(parent nil ) (child nil) )
(let ((c (make-elt) )
(p (make-elt)) )
(setf (elt-parent c) p
(elt-child p) c)
c) )
#1=#S(ELT PARENT #S(ELT PARENT NIL CHILD #1#) CHILD NIL)
~~~
要實(shí)現(xiàn)像這樣一個(gè)結(jié)構(gòu)的打印函數(shù) (`print-function`)，我們需要將全局變量?`*print-circle*`?綁定為?`t`?，或者避免打印可能構(gòu)成環(huán)的字段。
## 12.8 常量結(jié)構(gòu) (Constant Structure)[](http://acl.readthedocs.org/en/latest/zhCN/ch12-cn.html#constant-structure "Permalink to this headline")
因?yàn)槌Ａ繉?shí)際上是程序代碼的一部分，所以我們也不應(yīng)該修改他們，或者是不經(jīng)意地寫了自重寫的代碼。一個(gè)通過(guò)?`quote`?引用的列表是一個(gè)常量，所以一定要小心，不要修改被引用的列表的任何?`cons`。比如，如果我們用下面的代碼，來(lái)測(cè)試一個(gè)符號(hào)是不是算術(shù)運(yùn)算符：
~~~
(defun arith-op (x)
(member x '(+ - * /)))
~~~
如果被測(cè)試的符號(hào)是算術(shù)運(yùn)算符，它的返回值將至少一個(gè)被引用列表的一部分。如果我們修改了其返回值，
~~~
> (nconc (arith-op '*) '(as i t were))
(* / AS IT WERE)
~~~
那么我就會(huì)修改?`arith-op`?函數(shù)中的一個(gè)列表，從而改變了這個(gè)函數(shù)的功能：
~~~
> (arith-op 'as )
(AS IT WERE)
~~~
寫一個(gè)返回常量結(jié)構(gòu)的函數(shù)，并不一定是錯(cuò)誤的。但當(dāng)你考慮使用一個(gè)破壞性的操作是否安全的時(shí)候，你必須考慮到這一點(diǎn)。
有幾個(gè)其它方法來(lái)實(shí)現(xiàn)?`arith-op`，使其不返回被引用列表的部分。一般地，我們可以通過(guò)將其中的所有引用(?`quote`?) 替換成?`list`來(lái)確保安全，這使得它每次被調(diào)用都將返回一個(gè)新的列表：
~~~
(defun arith-op (x)
(member x (list '+ '- '* '/)))
~~~
這里，使用?`list`?是一種低效的解決方案，我們應(yīng)該使用?`find`?來(lái)替代?`member`：
~~~
(defun arith-op (x)
(find x '(+ - * /)))
~~~
這一節(jié)討論的問(wèn)題似乎只與列表有關(guān)，但實(shí)際上，這個(gè)問(wèn)題存在于任何復(fù)雜的對(duì)象中：數(shù)組，字符串，結(jié)構(gòu)，實(shí)例等。你不應(yīng)該逐字地去修改程序的代碼段。
即使你想寫自修改程序，通過(guò)修改常量來(lái)實(shí)現(xiàn)并不是個(gè)好辦法。編譯器將常量編譯成了代碼，破壞性的操作可能修改它們的參數(shù)，但這些都是沒(méi)有任何保證的事情。如果你想寫自修改程序，正確的方法是使用閉包 (見(jiàn) 6.5 節(jié))。
## Chapter 12 總結(jié) (Summary)[](http://acl.readthedocs.org/en/latest/zhCN/ch12-cn.html#chapter-12-summary "Permalink to this headline")
1. 兩個(gè)列表可以共享一個(gè)尾端。多個(gè)列表可以以樹的形式共享結(jié)構(gòu)，而不是共享頂層列表結(jié)構(gòu)?？赏ㄟ^(guò)拷貝方式來(lái)避免共用結(jié)構(gòu)。
2. 共享結(jié)構(gòu)通?？梢员缓雎?，但如果你要修改列表，則需要特別注意。因?yàn)樾薷囊粋€(gè)含共享結(jié)構(gòu)的列表可能修改所有共享該結(jié)構(gòu)的列表。
3. 隊(duì)列可以被表示成一個(gè)?`cons`?，其的?`car`?指向隊(duì)列的第一個(gè)元素，?`cdr`?指向隊(duì)列的最后一個(gè)元素。
4. 為了提高效率，破壞性函數(shù)允許修改其輸入?yún)?shù)。
5. 在某些應(yīng)用中，破壞性的實(shí)現(xiàn)更適用。
6. 列表可以是?`car-circular`?或?`cdr-circular`?。 Lisp 可以表示圓形結(jié)構(gòu)和共享結(jié)構(gòu)。
7. 不應(yīng)該去修改的程序代碼段中的常量形式。
## Chapter 12 練習(xí) (Exercises)[](http://acl.readthedocs.org/en/latest/zhCN/ch12-cn.html#chapter-12-exercises "Permalink to this headline")
1. 畫三個(gè)不同的樹，能夠被打印成?`((A)?(A)?(A))`?。寫一個(gè)表達(dá)式來(lái)生成它們。
2. 假設(shè)?`make-queue`?，?`enqueue`?和?`dequeue`?是按照?qǐng)D 12.7 中的定義，用箱子表式法畫出下面每一步所得到的隊(duì)列的結(jié)構(gòu)圖：
~~~
> (setf q (make-queue))
(NIL)
> (enqueue 'a q)
(A)
> (enqueue 'b q)
(A B)
> (dequeue q)
A
~~~
1. 定義一個(gè)函數(shù)?`copy-queue`?，可以返回一個(gè) queue 的拷貝。
2. 定義一個(gè)函數(shù)，接受兩個(gè)輸入?yún)?shù)?`object`?和?`queue`?，能將?`object`?插入到?`queue`?的首端。
3. 定義一個(gè)函數(shù)，接受兩個(gè)輸入?yún)?shù)?`object`?和?`queue`，能具有破壞性地將?`object`?的第一個(gè)實(shí)例 (?`eql`?等價(jià)地) 移到?`queue`?的首端。
4. 定義一個(gè)函數(shù)，接受兩個(gè)輸入?yún)?shù)?`object`?和?`lst`?(?`lst`?可能是?`cdr-circular`?列表)，如果?`object`?是?`lst`?的成員時(shí)返回真。
5. 定義一個(gè)函數(shù)，如果它的參數(shù)是一個(gè)?`cdr-circular`?則返回真。
6. 定義一個(gè)函數(shù)，如果它的參數(shù)是一個(gè)?`car-circular`?則返回真。
腳注
[1] | 比如，在 Common Lisp 中，修改一個(gè)被用作符號(hào)名的字符串被認(rèn)為是一種錯(cuò)誤，因?yàn)閮?nèi)部的定義并沒(méi)聲明它是從參數(shù)復(fù)制來(lái)的，所以必須假定修改傳入內(nèi)部的任何參數(shù)中的字符串來(lái)創(chuàng)建新的符號(hào)是錯(cuò)誤的。
[2] | 函數(shù)名稱中 n 的含義是 “non-consing”。一些具有破壞性的函數(shù)以 n 開頭。
- 前言
- 第一章：簡(jiǎn)介
- 第二章：歡迎來(lái)到 Lisp
- 第三章：列表
- 第四章：特殊數(shù)據(jù)結(jié)構(gòu)
- 第五章：控制流
- 第六章：函數(shù)
- 第七章：輸入與輸出
- 第八章：符號(hào)
- 第九章：數(shù)字
- 第十章：宏
- 第十一章：Common Lisp 對(duì)象系統(tǒng)
- 第十二章：結(jié)構(gòu)
- 第十三章：速度
- 第十四章：進(jìn)階議題
- 第十五章：示例：推論
- 第十六章：示例：生成 HTML
- 第十七章：示例：對(duì)象
- 附錄 A：調(diào)試
- 附錄 B：Lisp in Lisp
- 附錄 C：Common Lisp 的改變
- 備注