第十四章 向量和結(jié)構(gòu)體

14.1 簡(jiǎn)介

本章中，我將講解向量和結(jié)構(gòu)體。向量是一組通過(guò)整數(shù)索引的數(shù)據(jù)。與C語(yǔ)言中的數(shù)組不同，一個(gè)向量可以儲(chǔ)存不同類型的數(shù)據(jù)。與表相比，向量更加緊湊且存取時(shí)間更短。但從另外一方面來(lái)說(shuō)，向量是通過(guò)副作用來(lái)操作的，這樣會(huì)造成負(fù)擔(dān)。Scheme中的結(jié)構(gòu)體與C語(yǔ)言中的結(jié)構(gòu)體類似。但Scheme中的結(jié)構(gòu)體比C語(yǔ)言中的更容易使用，這是因?yàn)镾cheme為結(jié)構(gòu)體自動(dòng)創(chuàng)建了讀取函數(shù)和寫(xiě)入函數(shù)，這受益于Lisp/Scheme程序設(shè)計(jì)語(yǔ)言中的宏。

14.2 向量

14.2.1 字面值

向量通過(guò)閉合的#(和)表示，例如#(1 2 3)。作為字面值時(shí)，它們應(yīng)該被引用，例如：

'#(1 2 3)             ; 整數(shù)向量
'#(a 0 #\a)           ; 由符號(hào)、整數(shù)和字符構(gòu)成的向量

14.2.2 向量函數(shù)

下面的函數(shù)都是R5RS規(guī)定的函數(shù)：

(vector? obj) 如果obj是一個(gè)向量則返回#t。 (make-vector k) (make-vector k fill) 放回一個(gè)有k個(gè)元素的向量。如果指定了第二個(gè)參數(shù)fill，那么所有的元素都會(huì)被初始化為fill。 (vector obj …) 返回由參數(shù)列表構(gòu)成的向量。 (vector-length vector) 返回向量vector的長(zhǎng)度。 (vector-ref vector k) 返回向量vector的索引為k的元素。（譯注：和C語(yǔ)言類似，向量從0開(kāi)始索引。） (vector-set! vector k obj) 將向量vector的索引為k的元素修改為obj。 (vector->list vector) 將vector轉(zhuǎn)換為表。 (list->vector list) 將list轉(zhuǎn)換為向量。 (vector-fill! vector fill) 將向量vector的所有元素設(shè)置為fill。

例：一個(gè)對(duì)向量中元素求和的函數(shù)。

(define (vector-add v1 v2)
  (let ((lenv1 (vector-length v1))
         (lenv2 (vector-length v2)))
    (if (= lenv1 lenv2)
      (let ((v (make-vector lenv1)))
        (let loop ((i 0))
            (if (= i lenv1)
                 v
               (begin
                 (vector-set! v i (+ (vector-ref v1 i) (vector-ref v2 i)))
                 (loop (1+ i))))))
              (error "different dimensions."))))

練習(xí)1

編寫(xiě)一個(gè)用于計(jì)算兩向量?jī)?nèi)積的函數(shù)。

14.3 結(jié)構(gòu)體

14.3.1 大體功能

雖然R5RS中沒(méi)有定義結(jié)構(gòu)體，但是在很多Scheme實(shí)現(xiàn)中，都實(shí)現(xiàn)了類似于Common Lisp中的結(jié)構(gòu)體。這些結(jié)構(gòu)體本質(zhì)上來(lái)說(shuō)都是向量。每一個(gè)槽都通過(guò)使用一個(gè)宏來(lái)命名，我將會(huì)在下一章（十五章）中講解這個(gè)問(wèn)題。結(jié)構(gòu)體通過(guò)不同的屬性清楚地表示數(shù)據(jù)。定義結(jié)構(gòu)體的宏自動(dòng)為結(jié)構(gòu)體創(chuàng)建讀?。╝ccessor）函數(shù)和設(shè)置（setter）函數(shù)。你可以通過(guò)“程序”來(lái)寫(xiě)程序，這被認(rèn)為是Lisp/Scheme最好之處之一。

14.3.2 MIT-Scheme中的結(jié)構(gòu)體

在MIT-Scheme中，結(jié)構(gòu)體通過(guò)函數(shù)define-structure來(lái)定義。為了使你更加容易理解，我會(huì)用一個(gè)實(shí)例來(lái)講解。請(qǐng)考慮書(shū)籍。書(shū)籍都有下列屬性：

• 標(biāo)題
• 作者
• 出版商
• 出版年份
• ISBN號(hào)

因此結(jié)構(gòu)體book就可以像下面這樣定義：

(define-structure book title authors publisher year isbn)

下面演示了如何注冊(cè)《大教堂與市集（The Cathedral and Bazaar）》。

(define bazaar 
  (make-book 
   "The Cathedral and the Bazaar"
   "Eric S. Raymond"
   "O'Reilly"
   1999
   0596001088))

然而，這樣做多多少少有點(diǎn)不便，因?yàn)閷傩耘c值的關(guān)聯(lián)并不清楚。參量keyword-constructor可以用于解決這個(gè)問(wèn)題。下面的代碼就是使用這個(gè)參量的重寫(xiě)版，這個(gè)版本中，屬性與值的關(guān)聯(lián)就非常清楚了。更進(jìn)一步來(lái)說(shuō)，制定這個(gè)參量后，參數(shù)的順序就不重要了。

參量copier可用于為結(jié)構(gòu)體創(chuàng)建一個(gè)拷貝（copier）函數(shù)。

(define-structure (book keyword-constructor copier) 
  title authors publisher year isbn)

(define bazaar 
  (make-book 
   'title "The Cathedral and the Bazaar"
   'authors "Eric S. Raymond"
   'publisher "O'Reilly"
   'year 1999   
   'isbn 0596001088))

• 一個(gè)名字形如[結(jié)構(gòu)體名稱]?的函數(shù)用于檢查某對(duì)象是否為特定結(jié)構(gòu)體。例如，可使用函數(shù)book?來(lái)檢查bazaar是否為book結(jié)構(gòu)體的一個(gè)實(shí)例。

(book? bazaar)
;Value: #t

• 一個(gè)名字形如copy-[結(jié)構(gòu)體名稱]的函數(shù)用于拷貝結(jié)構(gòu)體。例如，下面的代碼演示了將bazaar拷貝到cathedral。

(define cathedral (copy-book bazaar))

• 一個(gè)名字形如[結(jié)構(gòu)體名稱]-[屬性名稱]的函數(shù)用于讀取結(jié)構(gòu)體某屬性的值。例如，下面的代碼演示了如何讀取bazaar的title屬性。

(book-title bazaar)
;Value 18: "The Cathedral and the Bazaar"

• 一個(gè)名字形如set-[結(jié)構(gòu)體名稱]-[屬性名稱]!用于將某屬性設(shè)定為特定值。下面的代碼演示了如何將bazaar的year字段更新到2001（《大教堂與市集》2001年再版）。

(set-book-year! bazaar 2001)
;Unspecified return value

(book-year bazaar)
;Value: 2001

請(qǐng)參閱MIT/GNU Scheme Reference: 2.10 Structure Definitions以獲得關(guān)于結(jié)構(gòu)體的跟多信息。

14.4 The Mastermind — 一個(gè)簡(jiǎn)單的密碼破解游戲

作為向量的示例，我會(huì)演示一個(gè)簡(jiǎn)單地密碼破解游戲。這是一個(gè)猜對(duì)手密碼的游戲。密碼是由0到9中四個(gè)不同的數(shù)組成的四位數(shù)。