在之前的章節(jié)里，我們討論了列表，Lisp 最多功能的數(shù)據(jù)結(jié)構(gòu)毡惜。本章將演示如何使用 Lisp 其它的數(shù)據(jù)結(jié)構(gòu)：數(shù)組（包含向量與字符串），結(jié)構(gòu)以及哈希表斯撮。它們或許不像列表這么靈活经伙，但存取速度更快并使用了更少空間。

Common Lisp 還有另一種數(shù)據(jù)結(jié)構(gòu)：實(shí)例（instance）勿锅。實(shí)例將在 11 章討論帕膜，講述 CLOS。

4.1 數(shù)組 (Array)

在 Common Lisp 里粱甫，你可以調(diào)用?make-array?來構(gòu)造一個數(shù)組泳叠，第一個實(shí)參為一個指定數(shù)組維度的列表。要構(gòu)造一個?2?x?3?的數(shù)組茶宵，我們可以：

> (setf arr (make-array '(2 3) :initial-element nil))

#2A((NIL NIL NIL) (NIL NIL NIL))

Common Lisp 的數(shù)組至少可以達(dá)到七個維度危纫，每個維度至少可以容納 1023 個元素。

:initial-element?實(shí)參是選擇性的。如果有提供這個實(shí)參种蝶，整個數(shù)組會用這個值作為初始值契耿。若試著取出未初始化的數(shù)組內(nèi)的元素，其結(jié)果為未定義（undefined）螃征。

用?aref?取出數(shù)組內(nèi)的元素搪桂。與 Common Lisp 的存取函數(shù)一樣，?aref?是零索引的（zero-indexed）：

CL-USER> (aref arr 0 0)

NIL

要替換數(shù)組的某個元素盯滚，我們使用?setf?與?aref?：

CL-USER> (setf (aref arr 0 0) 'b)

B

CL-USER> (aref arr 0 0)

B

要表示字面常量的數(shù)組（literal array）踢械，使用?#na?語法，其中?n?是數(shù)組的維度魄藕。舉例來說内列，我們可以這樣表示?arr?這個數(shù)組：

#2a((b nil nil) (nil nil nil))

如果全局變量?*print-array*?為真，則數(shù)組會用以下形式來顯示：

CL-USER> (setf *print-array* t)

T

CL-USER> arr

#2A((B NIL NIL) (NIL NIL NIL))

如果我們只想要一維的數(shù)組背率，你可以給?make-array?第一個實(shí)參傳一個整數(shù)话瞧，而不是一個列表：

CL-USER> (setf vec (make-array 4 :initial-element nil))

#(NIL NIL NIL NIL)

一維數(shù)組又稱為向量（vector）。你可以通過調(diào)用?vector?來一步驟構(gòu)造及填滿向量寝姿，向量的元素可以是任何類型：

CL-USER> (vector "a" 'b 3)

#("a" B 3)

字面常量的數(shù)組可以表示成?#na?交排，字面常量的向量也可以用這種語法表達(dá)。

可以用?aref?來存取向量饵筑，但有一個更快的函數(shù)叫做?svref?埃篓，專門用來存取向量。

CL-USER> (svref vec 0)

NIL

在?svref?內(nèi)的 “sv” 代表“簡單向量”（“simple vector”）根资，所有的向量缺省是簡單向量都许。

4.2 示例：二叉搜索 (Example: Binary Search)

作為一個示例，這小節(jié)演示如何寫一個在排序好的向量里搜索對象的函數(shù)嫂冻。如果我們知道一個向量是排序好的，我們可以比（65頁）?find?做的更好塞椎，?find?必須依序檢查每一個元素桨仿。我們可以直接跳到向量中間開始找。如果中間的元素是我們要找的對象案狠，搜索完畢服傍。要不然我們持續(xù)往左半部或往右半部搜索，取決于對象是小于或大于中間的元素骂铁。

圖 4.1 包含了一個這么工作的函數(shù)吹零。其實(shí)這兩個函數(shù)：?bin-search?設(shè)置初始范圍及發(fā)送控制信號給?finder?，?finder?尋找向量?vec?內(nèi)?obj?是否介于?start?及end?之間拉庵。

圖 4.1: 搜索一個排序好的向量

如果要找的?range?縮小至一個元素灿椅，而如果這個元素是?obj?的話，則?finder?直接返回這個元素，反之返回?nil?茫蛹。如果?range?大于?1?操刀，我們設(shè)置?middle?(round?返回離實(shí)參最近的整數(shù)) 為?obj2?。如果?obj?小于?obj2?婴洼，則遞歸地往向量的左半部尋找骨坑。如果?obj?大于?obj2?，則遞歸地往向量的右半部尋找柬采。剩下的一個選擇是?obj=obj2?欢唾，在這個情況我們找到要找的元素，直接返回這個元素粉捻。

如果我們插入下面這行至?finder?的起始處：

(format t "~A~%" (subseq vec start (+ end 1)))

我們可以觀察被搜索的元素的數(shù)量礁遣，是每一步往左減半的：

>(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)

字符串是字符組成的向量。我們用一系列由雙引號包住的字符杀迹，來表示一個字符串常量亡脸，而字符?c?用?#\c?表示。

每個字符都有一個相關(guān)的整數(shù) ── 通常是 ASCII 碼树酪，但不一定是浅碾。在多數(shù)的 Lisp 實(shí)現(xiàn)里，函數(shù)?char-code?返回與字符相關(guān)的數(shù)字续语，而?code-char?返回與數(shù)字相關(guān)的字符垂谢。

字符比較函數(shù)?char<?（小于），?char<=?（小于等于)疮茄，?char=?（等于)滥朱，?char>=?（大于等于) 衡招，?char>?（大于)呀打，以及?char/=?（不同)。他們的工作方式和 146 頁（譯注 9.3 節(jié))比較數(shù)字用的操作符一樣契讲。

CL-USER> (sort "elbow" #'char<)

"below"

由于字符串是字符向量畸裳，序列與數(shù)組的函數(shù)都可以用在字符串缰犁。你可以用?aref?來取出元素，舉例來說怖糊，

CL-USER> (aref "abc" 1)

#\b

但針對字符串可以使用更快的?char?函數(shù)：

CL-USER> (char "abc" 1)

#\b

可以使用?setf?搭配?char?（或?aref?）來替換字符串的元素：

CL-USER> (let ((str (copy-seq "Merlin")))

? (setf (char str 3) #\k)

? str)

"Merkin"

果你想要比較兩個字符串帅容，你可以使用通用的?equal?函數(shù)，但還有一個比較函數(shù)伍伤，是忽略字母大小寫的?string-equal?：

CL-USER> (equal "fred" "fred")

T

CL-USER> (equal "fred" "Fred")

NIL

CL-USER> (string-equal "fred" "Fred")

T

Common Lisp 提供大量的操控并徘、比較字符串的函數(shù)。收錄在附錄 D扰魂，從 364 頁開始麦乞。

有許多方式可以創(chuàng)建字符串蕴茴。最普遍的方式是使用?format?。將第一個參數(shù)設(shè)為?nil?來調(diào)用?format?路幸，使它返回一個原本會印出來的字符串：

CL-USER> (format nil "~A or ~A" "truth" "dare")

"truth or dare"

CL-USER> (format t "~A or ~A" "truth" "dare")

truth

但若你只想把數(shù)個字符串連結(jié)起來荐开，你可以使用?concatenate?，它接受一個特定類型的符號简肴，加上一個或多個序列：

CL-USER> (concatenate 'string "not " "to worry")

"not to worry"

4.4 序列 (Sequences)

在 Common Lisp 里晃听，序列類型包含了列表與向量（因此也包含了字符串）。有些用在列表的函數(shù)砰识，實(shí)際上是序列函數(shù)能扒，包括?remove?、?length?辫狼、?subseq?初斑、reverse?、?sort?膨处、?every?以及?some?见秤。所以 46 頁（譯注 3.11 小節(jié)的?mirror??函數(shù)）我們所寫的函數(shù)，也可以用在其他種類的序列上：

CL-USER> (mirror? "abba")

T

我們已經(jīng)看過四種用來取出序列元素的函數(shù)： 給列表使用的?nth?真椿， 給向量使用的?aref?及?svref?鹃答，以及給字符串使用的?char?。 Common Lisp 也提供了通用的elt?突硝，對任何種類的序列都有效：

CL-USER> (elt '(a b c) 1)

B

針對特定類型的序列测摔，特定的存取函數(shù)會比較快，所以使用?elt?是沒有意義的解恰，除非在代碼當(dāng)中锋八，有需要支持通用序列的地方。

使用?elt?护盈，我們可以寫一個針對向量來說更有效率的?mirror??版本：

CL-USER> (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))))))

這個版本也可用在列表挟纱，但這個實(shí)現(xiàn)更適合給向量使用。頻繁的對列表調(diào)用?elt?的代價是昂貴的腐宋，因?yàn)榱斜韮H允許順序存取樊销。而向量允許隨機(jī)存取，從任何元素來存取每一個元素都是廉價的脏款。

許多序列函數(shù)接受一個或多個，由下表所列的標(biāo)準(zhǔn)關(guān)鍵字參數(shù)：

一個接受所有關(guān)鍵字參數(shù)的函數(shù)是?position?裤园，返回序列中一個元素的位置撤师，未找到元素時則返回?nil?。我們使用?position?來演示關(guān)鍵字參數(shù)所扮演的角色拧揽。

CL-USER> (position #\a "fantasia")

1

CL-USER> (position #\a "fantasia" :start 3 :end 5)

4

第二個例子我們要找在第四個與第六個字符間剃盾，第一個?a?所出現(xiàn)的位置腺占。?:start?關(guān)鍵字參數(shù)是第一個被考慮的元素位置，缺省是序列的第一個元素痒谴。?:end?關(guān)鍵字參數(shù)衰伯，如果有給的話，是第一個不被考慮的元素位置积蔚。

如果我們給入?:from-end?關(guān)鍵字參數(shù)意鲸，

CL-USER> (position #\a "fantasia" :from-end t)

7

我們得到最靠近結(jié)尾的?a?的位置。但位置是像平常那樣計(jì)算尽爆；而不是從尾端算回來的距離怎顾。

:key?關(guān)鍵字參數(shù)是序列中每個元素在被考慮之前，應(yīng)用至元素上的函數(shù)漱贱。如果我們說槐雾，

CL-USER> (position 'a '((c d) (a b)) :key #'car)

1

那么我們要找的是，元素的?car?部分是符號?a?的第一個元素幅狮。

:test?關(guān)鍵字參數(shù)接受需要兩個實(shí)參的函數(shù)募强，并定義了怎樣是一個成功的匹配。缺省函數(shù)為?eql?崇摄。如果你想要匹配一個列表擎值，你也許想使用?equal?來取代：

CL-USER> (position '(a b) '((a b) (c d)))

NIL

CL-USER> (position '(a b) '((a b) (c d)) :test #'equal)

0

:test?關(guān)鍵字參數(shù)可以是任何接受兩個實(shí)參的函數(shù)。舉例來說配猫，給定?<?幅恋，我們可以詢問第一個使第一個參數(shù)比它小的元素位置：

CL-USER> (position 3 '(1 0 7 5) :test #'<)

2

使用?subseq?與?position?，我們可以寫出分開序列的函數(shù)泵肄。舉例來說捆交，這個函數(shù)。返回字符串中第一個單字空格后的第二個單字

CL-USER> (defun second-word (str)

? (let ((p1 (+ (position #\? str) 1)))

? ? (subseq str p1 (position #\? str :start p1))))

SECOND-WORD

CL-USER> (second-word "Form follows function")

"follows"

要找到滿足謂詞的元素腐巢，其中謂詞接受一個實(shí)參品追，我們使用?position-if?。它接受一個函數(shù)與序列冯丙，并返回第一個滿足此函數(shù)的元素：

CL-USER> (position-if #'oddp '(2 3 4 5))

1

position-if?接受除了?:test?之外的所有關(guān)鍵字參數(shù)肉瓦。

有許多相似的函數(shù)，如給序列使用的?member?與?member-if?胃惜。分別是泞莉，?find?（接受全部關(guān)鍵字參數(shù)）與?find-if?（接受除了?:test?之外的所有關(guān)鍵字參數(shù)）

CL-USER> (find #\a "cat")

#\a

CL-USER> (find-if #'characterp "ham")

#\h

不同于?member?與?member-if?，它們僅返回要尋找的對象船殉。

通常一個?find-if?的調(diào)用鲫趁，如果解讀為?find?搭配一個?:key?關(guān)鍵字參數(shù)的話，會顯得更清楚利虫。舉例來說挨厚，表達(dá)式

?(find-if #'(lambda (x)

? ? ? ? ? ? (eql (car x) 'complete))

? ? ? ? lst)

可以更好的解讀為

(find 'complete lst :key #'car)

函數(shù)?remove?（22 頁）以及?remove-if?通常都可以用在序列堡僻。它們跟?find?與?find-if?是一樣的關(guān)系。另一個相關(guān)的函數(shù)是?remove-duplicates?疫剃，僅保留序列中每個元素的最后一次出現(xiàn)钉疫。

CL-USER> (remove-duplicates "abracadabra")

"cdbra"

這個函數(shù)接受前表所列的所有關(guān)鍵字參數(shù)。

函數(shù)?reduce?用來把序列壓縮成一個值巢价。它至少接受兩個參數(shù)牲阁，一個函數(shù)與序列。函數(shù)必須是接受兩個實(shí)參的函數(shù)蹄溉。在最簡單的情況下咨油，一開始函數(shù)用序列前兩個元素作為實(shí)參來調(diào)用，之后接續(xù)的元素作為下次調(diào)用的第二個實(shí)參柒爵，而上次返回的值作為下次調(diào)用的第一個實(shí)參役电。最后調(diào)用最終返回的值作為?reduce?整個函數(shù)的返回值。也就是說像是這樣的表達(dá)式：

(reduce #'fn '(a b c d)) 等同于 (fn (fn (fn 'a 'b) 'c) 'd)

們可以使用?reduce?來擴(kuò)充只接受兩個參數(shù)的函數(shù)棉胀。舉例來說法瑟，要得到三個或多個列表的交集(intersection)，我們可以：

CL-USER> (reduce #'intersection '((b r a d 's) (b a d) (c a t)))

(A)

4.5 示例：解析日期 (Example: Parsing Dates)

作為序列操作的示例唁奢，本節(jié)演示了如何寫程序來解析日期霎挟。我們將編寫一個程序，可以接受像是 “16 Aug 1980” 的字符串麻掸，然后返回一個表示日酥夭、月、年的整數(shù)列表脊奋。

圖 4.2 辨別符號 (token)

圖 4.2 里包含了某些在這個應(yīng)用里所需的通用解析函數(shù)熬北。第一個函數(shù)?tokens?，用來從字符串中取出語元 （token）诚隙。給定一個字符串及測試函數(shù)讶隐，滿足測試函數(shù)的字符組成子字符串，子字符串再組成列表返回久又。舉例來說巫延，如果測試函數(shù)是對字母返回真的?alpha-char-p?函數(shù)，我們得到：

CL-USER> (tokens "ab12 3cde.f" #'alpha-char-p 0)

("ab" "cde" "f")

所有不滿足此函數(shù)的字符被視為空白 ── 他們是語元的分隔符地消，但永遠(yuǎn)不是語元的一部分。

函數(shù)?constituent?被定義成用來作為?tokens?的實(shí)參脉执。

在 Common Lisp 里，圖形字符是我們可見的字符竿开，加上空白字符玻熙。所以如果我們用?constituent?作為測試函數(shù)時，

CL-USER> (tokens "ab12 3cde.f gh" #'constituent 0)

("ab12" "3cde.f" "gh")

則語元將會由空白區(qū)分出來列荔。

圖 4.3 包含了特別為解析日期打造的函數(shù)枚尼。函數(shù)?parse-date?接受一個特別形式組成的日期，并返回代表這個日期的整數(shù)列表：

圖 4.3 解析日期的函數(shù)

CL-USER> (parse-date "16 Aug 1980")

(16 8 1980)

parse-date?使用?tokens?來解析日期字符串署恍，接著調(diào)用?parse-month?及?parse-integer?來轉(zhuǎn)譯年崎溃、月、日盯质。要找到月份袁串，調(diào)用?parse-month?，由于使用的是string-equal?來匹配月份的名字呼巷，所以輸入可以不分大小寫囱修。要找到年和日，調(diào)用內(nèi)置的?parse-integer?王悍，?parse-integer?接受一個字符串并返回對應(yīng)的整數(shù)破镰。

如果需要自己寫程序來解析整數(shù)，也許可以這么寫：

CL-USER> (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 中压储，字符是如何轉(zhuǎn)成數(shù)字的 ── 函數(shù)?digit-char-p?不僅測試字符是否為數(shù)字鲜漩，同時返回了對應(yīng)的整數(shù)。

4.6 結(jié)構(gòu) (Structures)

結(jié)構(gòu)可以想成是豪華版的向量渠脉。假設(shè)你要寫一個程序來追蹤長方體宇整。你可能會想用三個向量元素來表示長方體：高度、寬度及深度芋膘。與其使用原本的?svref?鳞青，不如定義像是下面這樣的抽象，程序會變得更容易閱讀为朋，

(defun block-height (b) (svref b 0))

而結(jié)構(gòu)可以想成是臂拓，這些函數(shù)通通都替你定義好了的向量。

要想定義結(jié)構(gòu)习寸，使用?defstruct?胶惰。在最簡單的情況下孵滞，只要給出結(jié)構(gòu)及字段的名字便可以了：

CL-USER> (defstruct point

? x

? y)

這里定義了一個?point?結(jié)構(gòu)坊饶，具有兩個字段?x?與?y?蟋滴。同時隱式地定義了?make-point?津函、?point-p?、?copy-point?散庶、?point-x?及?point-y?函數(shù)屋讶。

2.3 節(jié)提過皿渗， Lisp 程序可以寫出 Lisp 程序。這是目前所見的明顯例子之一挤土。當(dāng)你調(diào)用?defstruct?時仰美，它自動生成了其它幾個函數(shù)的定義咖杂。有了宏以后，你將可以自己來辦到同樣的事情（如果需要的話壤圃，你甚至可以自己寫出?defstruct?）撩匕。

每一個?make-point?的調(diào)用，會返回一個新的?point?漠趁。可以通過給予對應(yīng)的關(guān)鍵字參數(shù)卤妒，來指定單一字段的值：

CL-USER> (setf p (make-point :x 0 :y 0))

#S(POINT :X 0 :Y 0)

存取?point?字段的函數(shù)不僅被定義成可取出數(shù)值共缕，也可以搭配?setf?一起使用图谷。

CL-USER> (point-x p)

0

CL-USER> (setf (point-y p) 2)

2

CL-USER> p

#S(POINT :X 0 :Y 2)

定義結(jié)構(gòu)也定義了以結(jié)構(gòu)為名的類型。每個點(diǎn)的類型層級會是承璃，類型?point?盔粹，接著是類型?structure?，再來是類型?atom?咬崔，最后是?t?類型郎仆。所以使用?point-p?來測試某個東西是不是一個點(diǎn)時扰肌，也可以使用通用性的函數(shù)曙旭，像是?typep?來測試。

CL-USER> (point-p p)

T

CL-USER> (typep p 'point)

T

我們可以在本來的定義中剂习，附上一個列表鳞绕，含有字段名及缺省表達(dá)式，來指定結(jié)構(gòu)字段的缺省值垂蜗。

(defstruct polemic

? (type (progn

? ? ? ? ? (format t "What kind of polemic was it? ")

? ? ? ? ? (read)))

? (effect nil))

如果?make-polemic?調(diào)用沒有給字段指定初始值贴见，則字段會被設(shè)成缺省表達(dá)式的值：

CL-USER> (make-polemic)

What kind of polemic was it? nosee

#S(POLEMIC :TYPE NOSEE :EFFECT NIL)

結(jié)構(gòu)顯示的方式也可以控制，以及結(jié)構(gòu)自動產(chǎn)生的存取函數(shù)的字首档悠。以下是做了前述兩件事的?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?關(guān)鍵字參數(shù)指定了要放在字段前面的名字辖所，并用這個名字來生成存取函數(shù)吆视。預(yù)設(shè)是?point-?啦吧；現(xiàn)在變成只有?p?。不使用缺省的方式使代碼的可讀性些微降低了般堆，只有在需要常常用到這些存取函數(shù)時郁妈，你才會想取個短點(diǎn)的名字。

:print-function?是在需要顯示結(jié)構(gòu)出來看時极阅，指定用來打印結(jié)構(gòu)的函數(shù) ── 需要顯示的情況比如筋搏，要在頂層顯示時。這個函數(shù)需要接受三個實(shí)參：要被印出的結(jié)構(gòu)髓迎，在哪里被印出排龄，第三個參數(shù)通抽衔可以忽略争舞。?[2]?我們會在 7.1 節(jié)討論流（stream）。現(xiàn)在來說流译，只要知道流可以作為參數(shù)傳給?format?就好了福澡。

函數(shù)?print-point?會用縮寫的形式來顯示點(diǎn)：

CL-USER> (make-point)

#<0, 0>

4.7 示例：二叉搜索樹 (Example: Binary Search Tree)

由于?sort?本身系統(tǒng)就有了除秀，極少需要在 Common Lisp 里編寫排序程序册踩。本節(jié)將演示如何解決一個與此相關(guān)的問題暂吉，這個問題尚未有現(xiàn)成的解決方案：維護(hù)一個已排序的對象集合慕的。本節(jié)的代碼會把對象存在二叉搜索樹里（?binary search tree?）或稱作 BST。當(dāng)二叉搜索樹平衡時嫉父，允許我們可以在與時間成?log?n?比例的時間內(nèi)绕辖，來尋找、添加或是刪除元素弟头，其中?n?是集合的大小赴恨。

圖 4.4: 二叉搜索樹

二叉搜索樹是一種二叉樹雨饺，給定某個排序函數(shù)额港，比如?<?，每個元素的左子樹都?<?該元素绢馍，而該元素?<?其右子樹舰涌。圖 4.4 展示了根據(jù)?<?排序的二叉樹瓷耙。

圖 4.5 包含了二叉搜索樹的插入與尋找的函數(shù)长搀。基本的數(shù)據(jù)結(jié)構(gòu)會是?node?（節(jié)點(diǎn)）轿钠，節(jié)點(diǎn)有三個部分：一個字段表示存在該節(jié)點(diǎn)的對象，以及各一個字段表示節(jié)點(diǎn)的左子樹及右子樹贷腕。可以把節(jié)點(diǎn)想成是有一個?car?和兩個?cdr?的一個 cons 核（cons cell）涮总。

圖 4.5 二叉搜索樹：查詢與插入

一棵二叉搜索樹可以是?nil?或是一個左子烹笔、右子樹都是二叉搜索樹的節(jié)點(diǎn)。如同列表可由連續(xù)調(diào)用?cons?來構(gòu)造允蜈，二叉搜索樹將可以通過連續(xù)調(diào)用?bst-insert?來構(gòu)造陷寝。這個函數(shù)接受一個對象凤跑，一棵二叉搜索樹及一個排序函數(shù)，并返回將對象插入的二叉搜索樹咖耘。和?cons?函數(shù)一樣儿倒，?bst-insert?不改動做為第二個實(shí)參所傳入的二叉搜索樹。以下是如何使用這個函數(shù)來構(gòu)造一棵叉搜索樹：

CL-USER> (setf nums nil)

NIL

CL-USER> (dolist (x '(5 8 4 2 1 9 6 7 3))

? ? (setf nums (bst-insert x nums #'<)))

NIL

圖 4.4 顯示了此時?nums?的結(jié)構(gòu)所對應(yīng)的樹。

我們可以使用?bst-find?來找到二叉搜索樹中的對象微谓，它與?bst-insert?接受同樣的參數(shù)。先前敘述所提到的?node?結(jié)構(gòu)买乃，它像是一個具有兩個?cdr?的 cons 核岩馍。如果我們把 16 頁的?our-member?拿來與?bst-find?比較的話蛀恩，這樣的類比更加明確茂浮。

與?member?相同双谆，?bst-find?不僅返回要尋找的元素，也返回了用尋找元素做為根節(jié)點(diǎn)的子樹：

CL-USER> (bst-find 12 nums #'<)

NIL

CL-USER> (bst-find 4 nums #'<)

#<4>

這使我們可以區(qū)分出無法找到某個值席揽，以及成功找到?nil?的情況顽馋。

找到二叉搜索樹的最小及最大的元素是很簡單的。要找到最小的幌羞，我們沿著左子樹的路徑走寸谜，如同?bst-min?所做的。要找到最大的属桦，沿著右子樹的路徑走巾陕，如同?bst-max?所做的：

CL-USER> (bst-min nums)

#<1>

CL-USER> (bst-max nums)

#<9>

要從二叉搜索樹里移除元素一樣很快混聊，但需要更多代碼植康。圖 4.6 演示了如何從二叉搜索樹里移除元素睡毒。

圖 4.6 二叉搜索樹：移除

勘誤:?此版?bst-remove?的定義已被匯報(bào)是壞掉的胎源，請參考?這里?獲得修復(fù)版。

函數(shù)?bst-remove?接受一個對象，一棵二叉搜索樹以及排序函數(shù)，并返回一棵與本來的二叉搜索樹相同的樹泻云，但不包含那個要移除的對象婆瓜。和?remove?一樣，它不改動做為第二個實(shí)參所傳入的二叉搜索樹：

CL-USER> (setf nums (bst-remove 2 nums #'<))

#<5>

CL-USER> (bst-find 2 nums #'<)

NIL

此時?nums?的結(jié)構(gòu)應(yīng)該如圖 4.7 所示弄息。 （另一個可能性是?1?取代了?2?的位置祝迂。）

圖 4.7: 二叉搜索樹

移除需要做更多工作朴则，因?yàn)閺膬?nèi)部節(jié)點(diǎn)移除一個對象時坐榆，會留下一個空缺，需要由其中一個孩子來填補(bǔ)交播。這是?percolate?函數(shù)的用途。當(dāng)它替換一個二叉搜索樹的樹根（topmost element）時，會找其中一個孩子來替換，并用此孩子的孩子來填補(bǔ)，如此這般一直遞歸下去。

為了要保持樹的平衡，如果有兩個孩子時，?perlocate?隨機(jī)擇一替換。表達(dá)式?(random?2)?會返回?0?或?1?霞丧，所以?(zerop?(random?2))?會返回真或假。

圖 4.8 二叉搜索樹：遍歷

旦我們把一個對象集合插入至二叉搜索樹時制市，中序遍歷會將它們由小至大排序。這是圖 4.8 中，?bst-traverse?函數(shù)的用途：

CL-USER> (bst-traverse #'princ nums)

13456789

NIL

（函數(shù)?princ?僅顯示單一對象）

本節(jié)所給出的代碼筷畦，提供了一個二叉搜索樹實(shí)現(xiàn)的腳手架刺洒。你可能想根據(jù)應(yīng)用需求抹剩，來充實(shí)這個腳手架勿侯。舉例來說矢空，這里所給出的代碼每個節(jié)點(diǎn)只有一個?elt?字段眷茁；在許多應(yīng)用里炕泳，有兩個字段會更有意義，?key?與?value?上祈。本章的這個版本把二叉搜索樹視為集合看待培遵，從這個角度看，重復(fù)的插入是被忽略的雇逞。但是代碼可以很簡單地改動荤懂，來處理重復(fù)的元素茁裙。

二叉搜索樹不僅是維護(hù)一個已排序?qū)ο蟮募系姆椒ㄌ猎摇Ｋ麄兪欠袷亲詈玫姆椒ǎQ于你的應(yīng)用晤锥。一般來說掉蔬，二叉搜索樹最適合用在插入與刪除是均勻分布的情況。有一件二叉搜索樹不擅長的事矾瘾，就是用來維護(hù)優(yōu)先隊(duì)列（priority queues）女轿。在一個優(yōu)先隊(duì)列里，插入也許是均勻分布的壕翩，但移除總是在一個另一端蛉迹。這會導(dǎo)致一個二叉搜索樹變得不平衡，而我們期望的復(fù)雜度是?O(log(n))?插入與移除操作放妈，將會變成?O(n)?北救。如果用二叉搜索樹來表示一個優(yōu)先隊(duì)列，也可以使用一般的列表芜抒，因?yàn)槎嫠阉鳂渥罱K會作用的像是個列表珍策。

4.8 哈希表 (Hash Table)

第三章演示過列表可以用來表示集合（sets）與映射（mappings）。但當(dāng)列表的長度大幅上升時（或是 10 個元素）宅倒，使用哈希表的速度比較快攘宙。你通過調(diào)用make-hash-table?來構(gòu)造一個哈希表，它不需要傳入?yún)?shù)：

CL-USER> (setf ht (make-hash-table))

#<HASH-TABLE :TEST EQL size 0/60 #x2100C655DD>

和函數(shù)一樣拐迁，哈希表總是用?#<...>?的形式來顯示蹭劈。

一個哈希表，與一個關(guān)聯(lián)列表類似线召，是一種表達(dá)對應(yīng)關(guān)系的方式链方。要取出與給定鍵值有關(guān)的數(shù)值，我們調(diào)用?gethash?并傳入一個鍵值與哈希表灶搜。預(yù)設(shè)情況下祟蚀，如果沒有與這個鍵值相關(guān)的數(shù)值工窍，?gethash?會返回?nil?。

CL-USER> (gethash 'color ht)

NIL

NIL

在這里我們首次看到 Common Lisp 最突出的特色之一：一個表達(dá)式竟然可以返回多個數(shù)值前酿。函數(shù)?gethash?返回兩個數(shù)值患雏。第一個值是與鍵值有關(guān)的數(shù)值，第二個值說明了哈希表是否含有任何用此鍵值來儲存的數(shù)值罢维。由于第二個值是?nil?淹仑，我們知道第一個?nil?是缺省的返回值，而不是因?yàn)?nil?是與?color?有關(guān)的數(shù)值肺孵。

大部分的實(shí)現(xiàn)會在頂層顯示一個函數(shù)調(diào)用的所有返回值匀借，但僅期待一個返回值的代碼，只會收到第一個返回值平窘。 5.5 節(jié)會說明吓肋，代碼如何接收多個返回值。

要把數(shù)值與鍵值作關(guān)聯(lián)瑰艘，使用?gethash?搭配?setf?：

CL-USER> (setf (gethash 'color ht) 'red)

RED

現(xiàn)在如果我們再次調(diào)用?gethash?是鬼，我們會得到我們剛插入的值：

CL-USER> (gethash 'color ht)

RED

T

第二個返回值證明，我們?nèi)〉昧艘粋€真正儲存的對象紫新，而不是預(yù)設(shè)值均蜜。

存在哈希表的對象或鍵值可以是任何類型。舉例來說芒率，如果我們要保留函數(shù)的某種訊息囤耳，我們可以使用哈希表，用函數(shù)作為鍵值偶芍，字符串作為詞條（entry）：

CL-USER> (setf bugs (make-hash-table))

#<HASH-TABLE :TEST EQL size 0/60 #x2100C601FD>

CL-USER> (push "Doesn't take keyword arguments."

? ? ? ? (gethash #'our-member bugs))

("Doesn't take keyword arguments.")

;這段代碼測試報(bào)錯了充择，還不知道為什么，先留著腋寨。

由于?gethash?缺省返回?nil?聪铺，而?push?是?setf?的縮寫，可以輕松的給哈希表新添一個詞條萄窜。 （有困擾的?our-member?定義在 16 頁铃剔。）

可以用哈希表來取代用列表表示集合。當(dāng)集合變大時查刻，哈希表的查詢與移除會來得比較快键兜。要新增一個成員到用哈希表所表示的集合，把?gethash?用?setf?設(shè)成?t：

CL-USER> (setf fruit (make-hash-table))

#<HASH-TABLE :TEST EQL size 0/60 #x2100C2303D>

CL-USER> (setf (gethash 'apricot fruit) t)

T

然后要測試是否為成員穗泵，你只要調(diào)用：

CL-USER> (gethash 'apricot fruit)

T

T

由于?gethash?缺省返回真普气，一個新創(chuàng)的哈希表，會很方便地是一個空集合佃延。

要從集合中移除一個對象现诀，你可以調(diào)用?remhash?夷磕，它從一個哈希表中移除一個詞條：

CL-USER> (remhash 'apricot fruit)

T

返回值說明了是否有詞條被移除；在這個情況里仔沿，有坐桩。

哈希表有一個迭代函數(shù)：?maphash?，它接受兩個實(shí)參封锉，接受兩個參數(shù)的函數(shù)以及哈希表绵跷。該函數(shù)會被每個鍵值對調(diào)用，沒有特定的順序：

CL-USER> (setf (gethash 'shape ht) 'spherical

? ? ? ? (gethash 'size ht) 'giant)

GIANT

CL-USER> (maphash #'(lambda (k v)

? ? ? ? ? ? ? (format t "~A = ~A~%" k v))

? ? ? ? ? ht)

SHAPE = SPHERICAL

COLOR = RED

SIZE = GIANT

NIL

maphash?總是返回?nil?成福，但你可以通過傳入一個會累積數(shù)值的函數(shù)碾局，把哈希表的詞條存在列表里。

哈希表可以容納任何數(shù)量的元素奴艾，但當(dāng)哈希表空間用完時净当，它們會被擴(kuò)張。如果你想要確保一個哈希表握侧，從特定數(shù)量的元素空間大小開始時蚯瞧，可以給?make-hash-table?一個選擇性的?:size?關(guān)鍵字參數(shù)嘿期。做這件事情有兩個理由：因?yàn)槟阒拦１頃兊煤艽笃非妫阆胍苊鈹U(kuò)張它；或是因?yàn)槟阒拦１頃呛苄”感欤悴幌胍速M(fèi)內(nèi)存萄传。?:size?參數(shù)不僅指定了哈希表的空間，也指定了元素的數(shù)量蜜猾。平均來說秀菱，在被擴(kuò)張前所能夠容納的數(shù)量。所以

(make-hash-table?:size?5)

會返回一個預(yù)期存放五個元素的哈希表蹭睡。

和任何牽涉到查詢的結(jié)構(gòu)一樣衍菱，哈希表一定有某種比較鍵值的概念。預(yù)設(shè)是使用?eql?肩豁，但你可以提供一個額外的關(guān)鍵字參數(shù)?:test?來告訴哈希表要使用?eq?脊串，equal?，還是?equalp?：

CL-USER> (setf writers (make-hash-table :test #'equal))

#<HASH-TABLE :TEST EQUAL size 0/60 #x2100C98A0D>

CL-USER> (setf (gethash '(ralph waldo emerson) writers) t)

T

這是一個讓哈希表變得有效率的取舍之一清钥。有了列表琼锋，我們可以指定?member?為判斷相等性的謂詞。有了哈希表祟昭，我們可以預(yù)先決定缕坎，并在哈希表構(gòu)造時指定它。

大多數(shù) Lisp 編程的取舍（或是生活篡悟，就此而論）都有這種特質(zhì)谜叹。起初你想要事情進(jìn)行得流暢匾寝，甚至賠上效率的代價。之后當(dāng)代碼變得沉重時荷腊，你犧牲了彈性來換取速度旗吁。

Chapter 4 總結(jié) (Summary)

1）Common Lisp 支持至少 7 個維度的數(shù)組。一維數(shù)組稱為向量停局。

2）字符串是字符的向量很钓。字符本身就是對象。

3）序列包括了向量與列表董栽。許多序列函數(shù)都接受標(biāo)準(zhǔn)的關(guān)鍵字參數(shù)码倦。

4）處理字符串的函數(shù)非常多，所以用 Lisp 來解析字符串是小菜一碟锭碳。

5）調(diào)用?defstruct?定義了一個帶有命名字段的結(jié)構(gòu)袁稽。它是一個程序能寫出程序的好例子。

6）二叉搜索樹見長于維護(hù)一個已排序的對象集合擒抛。

7）哈希表提供了一個更有效率的方式來表示集合與映射 (mappings)推汽。

筆記：

一、常用函數(shù)函數(shù)

1）make-array：第一個實(shí)參為一個指定數(shù)組維度的列表

2）aref：取出數(shù)組內(nèi)的元素

3）setf：替換數(shù)組的某個元素

4）vector：一維數(shù)組又稱為向量（vector）歧沪。你可以通過調(diào)用?vector?來一步驟構(gòu)造及填滿向量歹撒，向量的元素可以是任何類型。

5）svref：專門用來存取向量

6）string-equal：比較兩個字符串诊胞，忽略字母大小寫的暖夭。

7）concatenate：把數(shù)個字符串連結(jié)起來。它接受一個特定類型的符號撵孤，加上一個或多個序列

8）elt：取出序列元素的函數(shù)迈着，通用的。

9）position：返回序列中一個元素的位置邪码，未找到元素時則返回?nil?裕菠。

10）defstruct：定義結(jié)構(gòu)。在最簡單的情況下闭专，只要給出結(jié)構(gòu)及字段的名字便可以了奴潘。

11）make-hash-table：構(gòu)造一個哈希表。