在之前的章節里，我們討論了列表，Lisp 最多功能的數據結構。本章將演示如何使用 Lisp 其它的數據結構：數組（包含向量與字符串），結構以及哈希表。它們或許不像列表這么靈活，但存取速度更快并使用了更少空間。
Common Lisp 還有另一種數據結構：實例（instance）。實例將在 11 章討論，講述 CLOS。
[TOC]
## 4.1 數組 (Array)[](http://acl.readthedocs.org/en/latest/zhCN/ch4-cn.html#array "Permalink to this headline")
在 Common Lisp 里，你可以調用?`make-array`?來構造一個數組，第一個實參為一個指定數組維度的列表。要構造一個?`2?x?3`?的數組，我們可以：
~~~
> (setf arr (make-array '(2 3) :initial-element nil))
#<Simple-Array T (2 3) BFC4FE>
~~~
Common Lisp 的數組至少可以達到七個維度，每個維度至少可以容納 1023 個元素。
`:initial-element`?實參是選擇性的。如果有提供這個實參，整個數組會用這個值作為初始值。若試著取出未初始化的數組內的元素，其結果為未定義（undefined）。
用?`aref`?取出數組內的元素。與 Common Lisp 的存取函數一樣，?`aref`?是零索引的（zero-indexed）：
~~~
> (aref arr 0 0)
NIL
~~~
要替換數組的某個元素，我們使用?`setf`?與?`aref`?：
~~~
> (setf (aref arr 0 0) 'b)
B
> (aref arr 0 0)
B
~~~
要表示字面常量的數組（literal array），使用?`#na`?語法，其中?`n`?是數組的維度。舉例來說，我們可以這樣表示?`arr`?這個數組：
~~~
#2a((b nil nil) (nil nil nil))
~~~
如果全局變量?`*print-array*`?為真，則數組會用以下形式來顯示：
~~~
> (setf *print-array* t)
T
> arr
#2A((B NIL NIL) (NIL NIL NIL))
~~~
如果我們只想要一維的數組，你可以給?`make-array`?第一個實參傳一個整數，而不是一個列表：
~~~
> (setf vec (make-array 4 :initial-element nil))
#(NIL NIL NIL NIL)
~~~
一維數組又稱為向量（*vector*）。你可以通過調用?`vector`?來一步驟構造及填滿向量，向量的元素可以是任何類型：
~~~
> (vector "a" 'b 3)
#("a" b 3)
~~~
字面常量的數組可以表示成?`#na`?，字面常量的向量也可以用這種語法表達。
可以用?`aref`?來存取向量，但有一個更快的函數叫做?`svref`?，專門用來存取向量。
~~~
> (svref vec 0)
NIL
~~~
在?`svref`?內的 “sv” 代表“簡單向量”（“simple vector”），所有的向量缺省是簡單向量。?[[1]](http://acl.readthedocs.org/en/latest/zhCN/ch4-cn.html#id5)
## 4.2 示例：二叉搜索 (Example: Binary Search)[](http://acl.readthedocs.org/en/latest/zhCN/ch4-cn.html#example-binary-search "Permalink to this headline")
作為一個示例，這小節演示如何寫一個在排序好的向量里搜索對象的函數。如果我們知道一個向量是排序好的，我們可以比（65頁）`find`?做的更好，?`find`?必須依序檢查每一個元素。我們可以直接跳到向量中間開始找。如果中間的元素是我們要找的對象，搜索完畢。要不然我們持續往左半部或往右半部搜索，取決于對象是小于或大于中間的元素。
圖 4.1 包含了一個這么工作的函數。其實這兩個函數：?`bin-search`?設置初始范圍及發送控制信號給?`finder`?，?`finder`?尋找向量?`vec`內?`obj`?是否介于?`start`?及?`end`?之間。
~~~
(defun bin-search (obj vec)
(let ((len (length vec)))
(and (not (zerop len))
(finder obj vec 0 (- len 1)))))
(defun finder (obj vec start end)
(let ((range (- end start)))
(if (zerop range)
(if (eql obj (aref vec start))
obj
nil)
(let ((mid (+ start (round (/ range 2)))))
(let ((obj2 (aref vec mid)))
(if (< obj obj2)
(finder obj vec start (- mid 1))
(if (> obj obj2)
(finder obj vec (+ mid 1) end)
obj)))))))
~~~
圖 4.1: 搜索一個排序好的向量
如果要找的?`range`?縮小至一個元素，而如果這個元素是?`obj`?的話，則?`finder`?直接返回這個元素，反之返回?`nil`?。如果?`range`?大于`1`?，我們設置?`middle`?(?`round`?返回離實參最近的整數) 為?`obj2`?。如果?`obj`?小于?`obj2`?，則遞歸地往向量的左半部尋找。如果?`obj`大于?`obj2`?，則遞歸地往向量的右半部尋找。剩下的一個選擇是?`obj=obj2`?，在這個情況我們找到要找的元素，直接返回這個元素。
如果我們插入下面這行至?`finder`?的起始處：
~~~
(format t "~A~%" (subseq vec start (+ end 1)))
~~~
我們可以觀察被搜索的元素的數量，是每一步往左減半的：
~~~
> (bin-search 3 #(0 1 2 3 4 5 6 7 8 9))
#(0 1 2 3 4 5 6 7 8 9)
#(0 1 2 3)
#(3)
3
~~~
## 4.3 字符與字符串 (Strings and Characters)[](http://acl.readthedocs.org/en/latest/zhCN/ch4-cn.html#strings-and-characters "Permalink to this headline")
字符串是字符組成的向量。我們用一系列由雙引號包住的字符，來表示一個字符串常量，而字符?`c`?用?`#\c`?表示。
每個字符都有一個相關的整數 ── 通常是 ASCII 碼，但不一定是。在多數的 Lisp 實現里，函數?`char-code`?返回與字符相關的數字，而?`code-char`?返回與數字相關的字符。
字符比較函數?`char<`?（小于），?`char<=`?（小于等于)，?`char=`?（等于)，?`char>=`?（大于等于) ，?`char>`?（大于)，以及?`char/=`?（不同)。他們的工作方式和 146 頁（譯注 9.3 節)比較數字用的操作符一樣。
~~~
> (sort "elbow" #'char<)
"below"
~~~
由于字符串是字符向量，序列與數組的函數都可以用在字符串。你可以用?`aref`?來取出元素，舉例來說，
~~~
> (aref "abc" 1)
#\b
~~~
但針對字符串可以使用更快的?`char`?函數：
~~~
> (char "abc" 1)
#\b
~~~
可以使用?`setf`?搭配?`char`?（或?`aref`?）來替換字符串的元素：
~~~
> (let ((str (copy-seq "Merlin")))
(setf (char str 3) #\k)
str)
~~~
如果你想要比較兩個字符串，你可以使用通用的?`equal`?函數，但還有一個比較函數，是忽略字母大小寫的?`string-equal`?：
~~~
> (equal "fred" "fred")
T
> (equal "fred" "Fred")
NIL
>(string-equal "fred" "Fred")
T
~~~
Common Lisp 提供大量的操控、比較字符串的函數。收錄在附錄 D，從 364 頁開始。
有許多方式可以創建字符串。最普遍的方式是使用?`format`?。將第一個參數設為?`nil`?來調用?`format`?，使它返回一個原本會印出來的字符串：
~~~
> (format nil "~A or ~A" "truth" "dare")
"truth or dare"
~~~
但若你只想把數個字符串連結起來，你可以使用?`concatenate`?，它接受一個特定類型的符號，加上一個或多個序列：
~~~
> (concatenate 'string "not " "to worry")
"not to worry"
~~~
## 4.4 序列 (Sequences)[](http://acl.readthedocs.org/en/latest/zhCN/ch4-cn.html#sequences "Permalink to this headline")
在 Common Lisp 里，序列類型包含了列表與向量（因此也包含了字符串）。有些用在列表的函數，實際上是序列函數，包括`remove`?、?`length`?、?`subseq`?、?`reverse`?、?`sort`?、?`every`?以及?`some`?。所以 46 頁（譯注 3.11 小節的?`mirror?`?函數）我們所寫的函數，也可以用在其他種類的序列上：
~~~
> (mirror? "abba")
T
~~~
我們已經看過四種用來取出序列元素的函數： 給列表使用的?`nth`?， 給向量使用的?`aref`?及?`svref`?，以及給字符串使用的?`char`?。 Common Lisp 也提供了通用的?`elt`?，對任何種類的序列都有效：
~~~
> (elt '(a b c) 1)
B
~~~
針對特定類型的序列，特定的存取函數會比較快，所以使用?`elt`?是沒有意義的，除非在代碼當中，有需要支持通用序列的地方。
使用?`elt`?，我們可以寫一個針對向量來說更有效率的?`mirror?`?版本：
~~~
(defun mirror? (s)
(let ((len (length s)))
(and (evenp len)
(do ((forward 0 (+ forward 1))
(back (- len 1) (- back 1)))
((or (> forward back)
(not (eql (elt s forward)
(elt s back))))
(> forward back))))))
~~~
這個版本也可用在列表，但這個實現更適合給向量使用。頻繁的對列表調用?`elt`?的代價是昂貴的，因為列表僅允許順序存取。而向量允許隨機存取，從任何元素來存取每一個元素都是廉價的。
許多序列函數接受一個或多個，由下表所列的標準關鍵字參數：
| 參數 | 用途 | 缺省值 |
| --- | --- | --- |
| :key | 應用至每個元素的函數 | identity |
| :test | 作來比較的函數 | eql |
| :from-end | 若為真，反向工作。 | nil |
| :start | 起始位置 | 0 |
| :end | 若有給定，結束位置。 | nil |
一個接受所有關鍵字參數的函數是?`position`?，返回序列中一個元素的位置，未找到元素時則返回?`nil`?。我們使用?`position`?來演示關鍵字參數所扮演的角色。
~~~
> (position #\a "fantasia")
1
> (position #\a "fantasia" :start 3 :end 5)
4
~~~
第二個例子我們要找在第四個與第六個字符間，第一個?`a`?所出現的位置。?`:start`?關鍵字參數是第一個被考慮的元素位置，缺省是序列的第一個元素。?`:end`?關鍵字參數，如果有給的話，是第一個不被考慮的元素位置。
如果我們給入?`:from-end`?關鍵字參數，
~~~
> (position #\a "fantasia" :from-end t)
7
~~~
我們得到最靠近結尾的?`a`?的位置。但位置是像平常那樣計算；而不是從尾端算回來的距離。
`:key`?關鍵字參數是序列中每個元素在被考慮之前，應用至元素上的函數。如果我們說，
~~~
> (position 'a '((c d) (a b)) :key #'car)
1
~~~
那么我們要找的是，元素的?`car`?部分是符號?`a`?的第一個元素。
`:test`?關鍵字參數接受需要兩個實參的函數，并定義了怎樣是一個成功的匹配。缺省函數為?`eql`?。如果你想要匹配一個列表，你也許想使用?`equal`?來取代：
~~~
> (position '(a b) '((a b) (c d)))
NIL
> (position '(a b) '((a b) (c d)) :test #'equal)
0
~~~
`:test`?關鍵字參數可以是任何接受兩個實參的函數。舉例來說，給定?`<`?，我們可以詢問第一個使第一個參數比它小的元素位置：
~~~
> (position 3 '(1 0 7 5) :test #'<)
2
~~~
使用?`subseq`?與?`position`?，我們可以寫出分開序列的函數。舉例來說，這個函數
~~~
(defun second-word (str)
(let ((p1 (+ (position #\ str) 1)))
(subseq str p1 (position #\ str :start p1))))
~~~
返回字符串中第一個單字空格后的第二個單字：
~~~
> (second-word "Form follows function")
"follows"
~~~
要找到滿足謂詞的元素，其中謂詞接受一個實參，我們使用?`position-if`?。它接受一個函數與序列，并返回第一個滿足此函數的元素：
~~~
> (position-if #'oddp '(2 3 4 5))
1
~~~
`position-if`?接受除了?`:test`?之外的所有關鍵字參數。
有許多相似的函數，如給序列使用的?`member`?與?`member-if`?。分別是，?`find`?（接受全部關鍵字參數）與?`find-if`?（接受除了?`:test`之外的所有關鍵字參數）：
~~~
> (find #\a "cat")
#\a
> (find-if #'characterp "ham")
#\h
~~~
不同于?`member`?與?`member-if`?，它們僅返回要尋找的對象。
通常一個?`find-if`?的調用，如果解讀為?`find`?搭配一個?`:key`?關鍵字參數的話，會顯得更清楚。舉例來說，表達式
~~~
(find-if #'(lambda (x)
(eql (car x) 'complete))
lst)
~~~
可以更好的解讀為
~~~
(find 'complete lst :key #'car)
~~~
函數?`remove`?（22 頁）以及?`remove-if`?通常都可以用在序列。它們跟?`find`?與?`find-if`?是一樣的關系。另一個相關的函數是`remove-duplicates`?，僅保留序列中每個元素的最后一次出現。
~~~
> (remove-duplicates "abracadabra")
"cdbra"
~~~
這個函數接受前表所列的所有關鍵字參數。
函數?`reduce`?用來把序列壓縮成一個值。它至少接受兩個參數，一個函數與序列。函數必須是接受兩個實參的函數。在最簡單的情況下，一開始函數用序列前兩個元素作為實參來調用，之后接續的元素作為下次調用的第二個實參，而上次返回的值作為下次調用的第一個實參。最后調用最終返回的值作為?`reduce`?整個函數的返回值。也就是說像是這樣的表達式：
~~~
(reduce #'fn '(a b c d))
~~~
等同于
~~~
(fn (fn (fn 'a 'b) 'c) 'd)
~~~
我們可以使用?`reduce`?來擴充只接受兩個參數的函數。舉例來說，要得到三個或多個列表的交集(intersection)，我們可以：
~~~
> (reduce #'intersection '((b r a d 's) (b a d) (c a t)))
(A)
~~~
## 4.5 示例：解析日期 (Example: Parsing Dates)[](http://acl.readthedocs.org/en/latest/zhCN/ch4-cn.html#example-parsing-dates "Permalink to this headline")
作為序列操作的示例，本節演示了如何寫程序來解析日期。我們將編寫一個程序，可以接受像是 “16 Aug 1980” 的字符串，然后返回一個表示日、月、年的整數列表。
~~~
(defun tokens (str test start)
(let ((p1 (position-if test str :start start)))
(if p1
(let ((p2 (position-if #'(lambda (c)
(not (funcall test c)))
str :start p1)))
(cons (subseq str p1 p2)
(if p2
(tokens str test p2)
nil)))
nil)))
(defun constituent (c)
(and (graphic-char-p c)
(not (char= c #\ ))))
~~~
圖 4.2 辨別符號 (token)
圖 4.2 里包含了某些在這個應用里所需的通用解析函數。第一個函數?`tokens`?，用來從字符串中取出語元 （token）。給定一個字符串及測試函數，滿足測試函數的字符組成子字符串，子字符串再組成列表返回。舉例來說，如果測試函數是對字母返回真的?`alpha-char-p`?函數，我們得到：
~~~
> (tokens "ab12 3cde.f" #'alpha-char-p 0)
("ab" "cde" "f")
~~~
所有不滿足此函數的字符被視為空白 ── 他們是語元的分隔符，但永遠不是語元的一部分。
函數?`constituent`?被定義成用來作為?`tokens`?的實參。
在 Common Lisp 里，*圖形字符*是我們可見的字符，加上空白字符。所以如果我們用?`constituent`?作為測試函數時，
~~~
> (tokens "ab12 3cde.f gh" #'constituent 0)
("ab12" "3cde.f" "gh")
~~~
則語元將會由空白區分出來。
圖 4.3 包含了特別為解析日期打造的函數。函數?`parse-date`?接受一個特別形式組成的日期，并返回代表這個日期的整數列表：
~~~
> (parse-date "16 Aug 1980")
(16 8 1980)
~~~
~~~
(defun parse-date (str)
(let ((toks (tokens str #'constituent 0)))
(list (parse-integer (first toks))
(parse-month (second toks))
(parse-integer (third toks)))))
(defconstant month-names
#("jan" "feb" "mar" "apr" "may" "jun"
"jul" "aug" "sep" "oct" "nov" "dec"))
(defun parse-month (str)
(let ((p (position str month-names
:test #'string-equal)))
(if p
(+ p 1)
nil)))
~~~
圖 4.3 解析日期的函數
`parse-date`?使用?`tokens`?來解析日期字符串，接著調用?`parse-month`?及?`parse-integer`?來轉譯年、月、日。要找到月份，調用`parse-month`?，由于使用的是?`string-equal`?來匹配月份的名字，所以輸入可以不分大小寫。要找到年和日，調用內置的?`parse-integer`?，?`parse-integer`?接受一個字符串并返回對應的整數。
如果需要自己寫程序來解析整數，也許可以這么寫：
~~~
(defun read-integer (str)
(if (every #'digit-char-p str)
(let ((accum 0))
(dotimes (pos (length str))
(setf accum (+ (* accum 10)
(digit-char-p (char str pos)))))
accum)
nil))
~~~
這個定義演示了在 Common Lisp 中，字符是如何轉成數字的 ── 函數?`digit-char-p`?不僅測試字符是否為數字，同時返回了對應的整數。
## 4.6 結構 (Structures)[](http://acl.readthedocs.org/en/latest/zhCN/ch4-cn.html#structures "Permalink to this headline")
結構可以想成是豪華版的向量。假設你要寫一個程序來追蹤長方體。你可能會想用三個向量元素來表示長方體：高度、寬度及深度。與其使用原本的?`svref`?，不如定義像是下面這樣的抽象，程序會變得更容易閱讀，
~~~
(defun block-height (b) (svref b 0))
~~~
而結構可以想成是，這些函數通通都替你定義好了的向量。
要想定義結構，使用?`defstruct`?。在最簡單的情況下，只要給出結構及字段的名字便可以了：
~~~
(defstruct point
x
y)
~~~
這里定義了一個?`point`?結構，具有兩個字段?`x`?與?`y`?。同時隱式地定義了?`make-point`?、?`point-p`?、?`copy-point`?、?`point-x`?及`point-y`?函數。
2.3 節提過， Lisp 程序可以寫出 Lisp 程序。這是目前所見的明顯例子之一。當你調用?`defstruct`?時，它自動生成了其它幾個函數的定義。有了宏以后，你將可以自己來辦到同樣的事情（如果需要的話，你甚至可以自己寫出?`defstruct`?）。
每一個?`make-point`?的調用，會返回一個新的?`point`?。可以通過給予對應的關鍵字參數，來指定單一字段的值：
~~~
(setf p (make-point :x 0 :y 0))
#S(POINT X 0 Y 0)
~~~
存取?`point`?字段的函數不僅被定義成可取出數值，也可以搭配?`setf`?一起使用。
~~~
> (point-x p)
0
> (setf (point-y p) 2)
2
> p
#S(POINT X 0 Y 2)
~~~
定義結構也定義了以結構為名的類型。每個點的類型層級會是，類型?`point`?，接著是類型?`structure`?，再來是類型?`atom`?，最后是`t`?類型。所以使用?`point-p`?來測試某個東西是不是一個點時，也可以使用通用性的函數，像是?`typep`?來測試。
~~~
> (point-p p)
T
> (typep p 'point)
T
~~~
我們可以在本來的定義中，附上一個列表，含有字段名及缺省表達式，來指定結構字段的缺省值。
~~~
(defstruct polemic
(type (progn
(format t "What kind of polemic was it? ")
(read)))
(effect nil))
~~~
如果?`make-polemic`?調用沒有給字段指定初始值，則字段會被設成缺省表達式的值：
~~~
> (make-polemic)
What kind of polemic was it? scathing
#S(POLEMIC :TYPE SCATHING :EFFECT NIL)
~~~
結構顯示的方式也可以控制，以及結構自動產生的存取函數的字首。以下是做了前述兩件事的?`point`?定義：
~~~
(defstruct (point (:conc-name p)
(:print-function print-point))
(x 0)
(y 0))
(defun print-point (p stream depth)
(format stream "#<~A, ~A>" (px p) (py p)))
~~~
`:conc-name`?關鍵字參數指定了要放在字段前面的名字，并用這個名字來生成存取函數。預設是?`point-`?；現在變成只有?`p`?。不使用缺省的方式使代碼的可讀性些微降低了，只有在需要常常用到這些存取函數時，你才會想取個短點的名字。
`:print-function`?是在需要顯示結構出來看時，指定用來打印結構的函數 ── 需要顯示的情況比如，要在頂層顯示時。這個函數需要接受三個實參：要被印出的結構，在哪里被印出，第三個參數通常可以忽略。?[[2]](http://acl.readthedocs.org/en/latest/zhCN/ch4-cn.html#id6)?我們會在 7.1 節討論流（stream）。現在來說，只要知道流可以作為參數傳給?`format`?就好了。
函數?`print-point`?會用縮寫的形式來顯示點：
~~~
> (make-point)
#<0,0>
~~~
## 4.7 示例：二叉搜索樹 (Example: Binary Search Tree)[](http://acl.readthedocs.org/en/latest/zhCN/ch4-cn.html#example-binary-search-tree "Permalink to this headline")
由于?`sort`?本身系統就有了，極少需要在 Common Lisp 里編寫排序程序。本節將演示如何解決一個與此相關的問題，這個問題尚未有現成的解決方案：維護一個已排序的對象集合。本節的代碼會把對象存在二叉搜索樹里（?*binary search tree*?）或稱作 BST。當二叉搜索樹平衡時，允許我們可以在與時間成?`log?n`?比例的時間內，來尋找、添加或是刪除元素，其中?`n`?是集合的大小。
圖 4.4: 二叉搜索樹
二叉搜索樹是一種二叉樹，給定某個排序函數，比如?`<`?，每個元素的左子樹都?`<`?該元素，而該元素?`<`?其右子樹。圖 4.4 展示了根據`<`?排序的二叉樹。
圖 4.5 包含了二叉搜索樹的插入與尋找的函數。基本的數據結構會是?`node`?（節點），節點有三個部分：一個字段表示存在該節點的對象，以及各一個字段表示節點的左子樹及右子樹。可以把節點想成是有一個?`car`?和兩個?`cdr`?的一個 cons 核（cons cell）。
~~~
(defstruct (node (:print-function
(lambda (n s d)
(format s "#<~A>" (node-elt n)))))
elt (l nil) (r nil))
(defun bst-insert (obj bst <)
(if (null bst)
(make-node :elt obj)
(let ((elt (node-elt bst)))
(if (eql obj elt)
bst
(if (funcall < obj elt)
(make-node
:elt elt
:l (bst-insert obj (node-l bst) <)
:r (node-r bst))
(make-node
:elt elt
:r (bst-insert obj (node-r bst) <)
:l (node-l bst)))))))
(defun bst-find (obj bst <)
(if (null bst)
nil
(let ((elt (node-elt bst)))
(if (eql obj elt)
bst
(if (funcall < obj elt)
(bst-find obj (node-l bst) <)
(bst-find obj (node-r bst) <))))))
(defun bst-min (bst)
(and bst
(or (bst-min (node-l bst)) bst)))
(defun bst-max (bst)
(and bst
(or (bst-max (node-r bst)) bst)))
~~~
圖 4.5 二叉搜索樹：查詢與插入
一棵二叉搜索樹可以是?`nil`?或是一個左子、右子樹都是二叉搜索樹的節點。如同列表可由連續調用?`cons`?來構造，二叉搜索樹將可以通過連續調用?`bst-insert`?來構造。這個函數接受一個對象，一棵二叉搜索樹及一個排序函數，并返回將對象插入的二叉搜索樹。和`cons`?函數一樣，?`bst-insert`?不改動做為第二個實參所傳入的二叉搜索樹。以下是如何使用這個函數來構造一棵叉搜索樹：
~~~
> (setf nums nil)
NIL
> (dolist (x '(5 8 4 2 1 9 6 7 3))
(setf nums (bst-insert x nums #'<)))
NIL
~~~
圖 4.4 顯示了此時?`nums`?的結構所對應的樹。
我們可以使用?`bst-find`?來找到二叉搜索樹中的對象，它與?`bst-insert`?接受同樣的參數。先前敘述所提到的?`node`?結構，它像是一個具有兩個?`cdr`?的 cons 核。如果我們把 16 頁的?`our-member`?拿來與?`bst-find`?比較的話，這樣的類比更加明確。
與?`member`?相同，?`bst-find`?不僅返回要尋找的元素，也返回了用尋找元素做為根節點的子樹：
~~~
> (bst-find 12 nums #'<)
NIL
> (bst-find 4 nums #'<)
#<4>
~~~
這使我們可以區分出無法找到某個值，以及成功找到?`nil`?的情況。
要找到二叉搜索樹的最小及最大的元素是很簡單的。要找到最小的，我們沿著左子樹的路徑走，如同?`bst-min`?所做的。要找到最大的，沿著右子樹的路徑走，如同?`bst-max`?所做的：
~~~
> (bst-min nums)
#<1>
> (bst-max nums)
#<9>
~~~
要從二叉搜索樹里移除元素一樣很快，但需要更多代碼。圖 4.6 演示了如何從二叉搜索樹里移除元素。
~~~
(defun bst-remove (obj bst <)
(if (null bst)
nil
(let ((elt (node-elt bst)))
(if (eql obj elt)
(percolate bst)
(if (funcall < obj elt)
(make-node
:elt elt
:l (bst-remove obj (node-l bst) <)
:r (node-r bst))
(make-node
:elt elt
:r (bst-remove obj (node-r bst) <)
:l (node-l bst)))))))
(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 rperc (bst)
(make-node :elt (node-elt (node-r bst))
:l (node-l bst)
:r (percolate (node-r bst))))
~~~
圖 4.6 二叉搜索樹：移除
**勘誤:**?此版?`bst-remove`?的定義已被匯報是壞掉的，請參考?[這里](https://gist.github.com/2868263)?獲得修復版。
函數?`bst-remove`?接受一個對象，一棵二叉搜索樹以及排序函數，并返回一棵與本來的二叉搜索樹相同的樹，但不包含那個要移除的對象。和?`remove`?一樣，它不改動做為第二個實參所傳入的二叉搜索樹：
~~~
> (setf nums (bst-remove 2 nums #'<))
#<5>
> (bst-find 2 nums #'<)
NIL
~~~
此時?`nums`?的結構應該如圖 4.7 所示。 （另一個可能性是?`1`?取代了?`2`?的位置。）
圖 4.7: 二叉搜索樹
移除需要做更多工作，因為從內部節點移除一個對象時，會留下一個空缺，需要由其中一個孩子來填補。這是?`percolate`?函數的用途。當它替換一個二叉搜索樹的樹根（topmost element）時，會找其中一個孩子來替換，并用此孩子的孩子來填補，如此這般一直遞歸下去。
為了要保持樹的平衡，如果有兩個孩子時，?`perlocate`?隨機擇一替換。表達式?`(random?2)`?會返回?`0`?或?`1`?，所以?`(zerop?(random2))`?會返回真或假。
~~~
(defun bst-traverse (fn bst)
(when bst
(bst-traverse fn (node-l bst))
(funcall fn (node-elt bst))
(bst-traverse fn (node-r bst))))
~~~
圖 4.8 二叉搜索樹：遍歷
一旦我們把一個對象集合插入至二叉搜索樹時，中序遍歷會將它們由小至大排序。這是圖 4.8 中，?`bst-traverse`?函數的用途：
~~~
> (bst-traverse #'princ nums)
13456789
NIL
~~~
（函數?`princ`?僅顯示單一對象）
本節所給出的代碼，提供了一個二叉搜索樹實現的腳手架。你可能想根據應用需求，來充實這個腳手架。舉例來說，這里所給出的代碼每個節點只有一個?`elt`?字段；在許多應用里，有兩個字段會更有意義，?`key`?與?`value`?。本章的這個版本把二叉搜索樹視為集合看待，從這個角度看，重復的插入是被忽略的。但是代碼可以很簡單地改動，來處理重復的元素。
二叉搜索樹不僅是維護一個已排序對象的集合的方法。他們是否是最好的方法，取決于你的應用。一般來說，二叉搜索樹最適合用在插入與刪除是均勻分布的情況。有一件二叉搜索樹不擅長的事，就是用來維護優先隊列（priority queues）。在一個優先隊列里，插入也許是均勻分布的，但移除總是在一個另一端。這會導致一個二叉搜索樹變得不平衡，而我們期望的復雜度是?`O(log(n))`?插入與移除操作，將會變成?`O(n)`?。如果用二叉搜索樹來表示一個優先隊列，也可以使用一般的列表，因為二叉搜索樹最終會作用的像是個列表。
## 4.8 哈希表 (Hash Table)[](http://acl.readthedocs.org/en/latest/zhCN/ch4-cn.html#hash-table "Permalink to this headline")
第三章演示過列表可以用來表示集合（sets）與映射（mappings）。但當列表的長度大幅上升時（或是 10 個元素），使用哈希表的速度比較快。你通過調用?`make-hash-table`?來構造一個哈希表，它不需要傳入參數：
~~~
> (setf ht (make-hash-table))
#<Hash-Table BF0A96>
~~~
和函數一樣，哈希表總是用?`#<...>`?的形式來顯示。
一個哈希表，與一個關聯列表類似，是一種表達對應關系的方式。要取出與給定鍵值有關的數值，我們調用?`gethash`?并傳入一個鍵值與哈希表。預設情況下，如果沒有與這個鍵值相關的數值，?`gethash`?會返回?`nil`?。
~~~
> (gethash 'color ht)
NIL
NIL
~~~
在這里我們首次看到 Common Lisp 最突出的特色之一：一個表達式竟然可以返回多個數值。函數?`gethash`?返回兩個數值。第一個值是與鍵值有關的數值，第二個值說明了哈希表是否含有任何用此鍵值來儲存的數值。由于第二個值是?`nil`?，我們知道第一個?`nil`是缺省的返回值，而不是因為?`nil`?是與?`color`?有關的數值。
大部分的實現會在頂層顯示一個函數調用的所有返回值，但僅期待一個返回值的代碼，只會收到第一個返回值。 5.5 節會說明，代碼如何接收多個返回值。
要把數值與鍵值作關聯，使用?`gethash`?搭配?`setf`?：
~~~
> (setf (gethash 'color ht) 'red)
RED
~~~
現在如果我們再次調用?`gethash`?，我們會得到我們剛插入的值：
~~~
> (gethash 'color ht)
RED
T
~~~
第二個返回值證明，我們取得了一個真正儲存的對象，而不是預設值。
存在哈希表的對象或鍵值可以是任何類型。舉例來說，如果我們要保留函數的某種訊息，我們可以使用哈希表，用函數作為鍵值，字符串作為詞條（entry）：
~~~
> (setf bugs (make-hash-table))
#<Hash-Table BF4C36>
> (push "Doesn't take keyword arguments."
(gethash #'our-member bugs))
("Doesn't take keyword arguments.")
~~~
由于?`gethash`?缺省返回?`nil`?，而?`push`?是?`setf`?的縮寫，可以輕松的給哈希表新添一個詞條。 （有困擾的?`our-member`?定義在 16 頁。）
可以用哈希表來取代用列表表示集合。當集合變大時，哈希表的查詢與移除會來得比較快。要新增一個成員到用哈希表所表示的集合，把?`gethash`?用?`setf`?設成?`t`?：
~~~
> (setf fruit (make-hash-table))
#<Hash-Table BFDE76>
> (setf (gethash 'apricot fruit) t)
T
~~~
然后要測試是否為成員，你只要調用：
~~~
> (gethash 'apricot fruit)
T
T
~~~
由于?`gethash`?缺省返回真，一個新創的哈希表，會很方便地是一個空集合。
要從集合中移除一個對象，你可以調用?`remhash`?，它從一個哈希表中移除一個詞條：
~~~
> (remhash 'apricot fruit)
T
~~~
返回值說明了是否有詞條被移除；在這個情況里，有。
哈希表有一個迭代函數：?`maphash`?，它接受兩個實參，接受兩個參數的函數以及哈希表。該函數會被每個鍵值對調用，沒有特定的順序：
~~~
> (setf (gethash 'shape ht) 'spherical
(gethash 'size ht) 'giant)
GIANT
> (maphash #'(lambda (k v)
(format t "~A = ~A~%" k v))
ht)
SHAPE = SPHERICAL
SIZE = GIANT
COLOR = RED
NIL
~~~
`maphash`?總是返回?`nil`?，但你可以通過傳入一個會累積數值的函數，把哈希表的詞條存在列表里。
哈希表可以容納任何數量的元素，但當哈希表空間用完時，它們會被擴張。如果你想要確保一個哈希表，從特定數量的元素空間大小開始時，可以給?`make-hash-table`?一個選擇性的?`:size`?關鍵字參數。做這件事情有兩個理由：因為你知道哈希表會變得很大，你想要避免擴張它；或是因為你知道哈希表會是很小，你不想要浪費內存。?`:size`?參數不僅指定了哈希表的空間，也指定了元素的數量。平均來說，在被擴張前所能夠容納的數量。所以
`(make-hash-table?:size?5)`
會返回一個預期存放五個元素的哈希表。
和任何牽涉到查詢的結構一樣，哈希表一定有某種比較鍵值的概念。預設是使用?`eql`?，但你可以提供一個額外的關鍵字參數?`:test`來告訴哈希表要使用?`eq`?，?`equal`?，還是?`equalp`?：
~~~
> (setf writers (make-hash-table :test #'equal))
#<Hash-Table C005E6>
> (setf (gethash '(ralph waldo emerson) writers) t)
T
~~~
這是一個讓哈希表變得有效率的取舍之一。有了列表，我們可以指定?`member`?為判斷相等性的謂詞。有了哈希表，我們可以預先決定，并在哈希表構造時指定它。
大多數 Lisp 編程的取舍（或是生活，就此而論）都有這種特質。起初你想要事情進行得流暢，甚至賠上效率的代價。之后當代碼變得沉重時，你犧牲了彈性來換取速度。
## Chapter 4 總結 (Summary)[](http://acl.readthedocs.org/en/latest/zhCN/ch4-cn.html#chapter-4-summary "Permalink to this headline")
1. Common Lisp 支持至少 7 個維度的數組。一維數組稱為向量。
2. 字符串是字符的向量。字符本身就是對象。
3. 序列包括了向量與列表。許多序列函數都接受標準的關鍵字參數。
4. 處理字符串的函數非常多，所以用 Lisp 來解析字符串是小菜一碟。
5. 調用?`defstruct`?定義了一個帶有命名字段的結構。它是一個程序能寫出程序的好例子。
6. 二叉搜索樹見長于維護一個已排序的對象集合。
7. 哈希表提供了一個更有效率的方式來表示集合與映射 (mappings)。
## Chapter 4 習題 (Exercises)[](http://acl.readthedocs.org/en/latest/zhCN/ch4-cn.html#chapter-4-exercises "Permalink to this headline")
1. 定義一個函數，接受一個平方數組（square array，一個相同維度的數組?`(n?n)`?)，并將它順時針轉 90 度。
~~~
> (quarter-turn #2A((a b) (c d)))
#2A((C A) (D B))
~~~
你會需要用到 361 頁的?`array-dimensions`?。
1. 閱讀 368 頁的?`reduce`?說明，然后用它來定義：
~~~
(a) copy-list
(b) reverse（針對列表）
~~~
1. 定義一個結構來表示一棵樹，其中每個節點包含某些數據及三個小孩。定義：
~~~
(a) 一個函數來復制這樣的樹（復制完的節點與本來的節點是不相等（ `eql` ）的）
(b) 一個函數，接受一個對象與這樣的樹，如果對象與樹中各節點的其中一個字段相等時，返回真。
~~~
1. 定義一個函數，接受一棵二叉搜索樹，并返回由此樹元素所組成的，一個由大至小排序的列表。
2. 定義?`bst-adjoin`?。這個函數應與?`bst-insert`?接受相同的參數，但應該只在對象不等于任何樹中對象時將其插入。
**勘誤:**?`bst-adjoin`?的功能與?`bst-insert`?一模一樣。
1. 任何哈希表的內容可以由關聯列表（assoc-list）來描述，其中列表的元素是?`(k?.?v)`?的形式，對應到哈希表中的每一個鍵值對。定義一個函數：
~~~
(a) 接受一個關聯列表，并返回一個對應的哈希表。
(b) 接受一個哈希表，并返回一個對應的關聯列表。
~~~
腳注
[[1]](http://acl.readthedocs.org/en/latest/zhCN/ch4-cn.html#id2) | 一個簡單數組大小是不可調整、元素也不可替換的，并不含有填充指針（fill-pointer）。數組缺省是簡單的。簡單向量是個一維的簡單數組，可以含有任何類型的元素。
[[2]](http://acl.readthedocs.org/en/latest/zhCN/ch4-cn.html#id3) | 在 ANSI Common Lisp 里，你可以給一個?`:print-object`?的關鍵字參數來取代，它只需要兩個實參。也有一個宏叫做`print-unreadable-object`?，能用則用，可以用?`#<...>`?的語法來顯示對象。
