数据结构

Table of Contents

1. 列表（list）

list 只是一种数据抽象，list 是由多个 cons 组成的，cons 是 construct（构造）的简称。

cons 也叫作“有序对”，cons 也是 Lisp 程序的基本数据结构。有序对有两个对象组成的搜集，元素1叫做“左投影”，元素2叫做“右投影”。有序对可有其他有序对做投影，比如 (a, b, c) 可以定义为 (a, (b, c))，Lisp 就是用的这种作为数据结构，比如 (1 2 3 4 5) 变换为 (1 (2 (3 (4 (5 None)))))，更多请见维基百科词条页：http://zh.wikipedia.org/wiki/%E6%9C%89%E5%BA%8F%E5%AF%B9 

(type-of '(1 2 3)) ; => CONS
(typep '(1 2 3) 'list) ; => T

当要表达 list 这种数据结构时，实质是指 nil 或者 CONS。

'(1 2 3)，这是一个列表。在 Lisp 内部，list 是由 cons cell 链组成的，每个 cons cell 有两个指针，第一个指针指向元素值，第二个指针指向下一个 cons cell。

想象下学习数据结构的“链表”：每个链表的单元都有一个或多个指针指向其他链表（比如下一个），一个链表由 N 个这样的单元组成，在 Lisp 里，这样的单元就是 cons cell: 

|cons cell 1| ------> |cons cell 2| ------> |cons cell 3|

我们可以看一下 SBCL 对 list 分配内存的代码： 

src/runtime/alloc.c：

143 lispobj
144 alloc_cons(lispobj car, lispobj cdr)
145 {
146     struct cons *ptr =
147         (struct cons *)pa_alloc(ALIGNED_SIZE(sizeof(struct cons)),
148                                 BOXED_PAGE_FLAG);
149
150     ptr->car = car;
151     ptr->cdr = cdr;
152
153     return make_lispobj(ptr, LIST_POINTER_LOWTAG);
154 }

如果 list 的最后个元素是 nil，表明这是一个 proper list（合规列表）；如果 cons cell 的右指针不是指向 nil，则不是 proper list，打印时会出现一个“点”，被称为 dotted list： 

(cons 1 2)                              ; => (1 . 2)

上面的例子说明这个 cons cell 是以“2”结尾的（右指针指向数字2），注意 length 函数是依赖右指针的，所以 dotted list 不能求长度

list 中可以嵌套其他 list： 

(1 (2 3))

这被称为 nested list（嵌套列表），非 nested list 被成为 flat lists（平坦列表）。

列表长度： (1 (2 3))的长度是多少呢？答：2。 列表长度是顶层列表的元素个数，而上面的列表只有两个元素——1和一个列表 (2 3)，所以长度为2。

空列表和nil： () 和 nil 是同一个东西，就是说，nil 不仅可以表示 false，也能表示空列表。 n

判断两个列表是否相等： 

(equal '(1 2 3) '(1 2 3)) ; => T
(equal '(1 2 3) '(1 2 3 nil)) ; => NIL

consp 和 listp 主要差别在： 

(listp nil) ; => T
(consp nil) ; => NIL

几个可以解构的函数：

  • first
  • last
  • second
  • third

CAR 和 CDR： 已知一个 cons cell 有两个指针，左边的叫 car，右边的叫 cdr： 

(car '(1 2 3)) ; => 1
(cdr '(1 2 3)) ; => (2 3)

可以说：first 函数返回 list 的 car，rest 返回 list 的 cdr。

注意 cadr 和 cdar 两个函数：

cadr 的意思是：car of the cdr，就是 cdr 的car，等同于(cdr (car list)) 

(car (cdr '(1 2 3))) ; => 2
(cadr '(1 2 3)) ; => 2

cdar 是：cdr of the car，就是 car 的 cdr，所以 car 返回的必须是一个 list，否则会出错： 

(cdar '(1 2 3)) ; => ERROR: The value 1 is not of type LIST.
(cdar '((1 2) 3)) ; => (2)

caddr 等同于 (car (cdr (cdr list)))： 

(car (cdr (cdr '(1 2 3 4)))) ; => 3
(caddr '(1 2 3 4)) ; => 3

1.1. circular list（循环列表）

如下代码： 

(setf *print-circle* t)
(defvar x '(1 2 3))
(setf (cdddr x) x)

这样 x 是无法打印出来的，因为这是个死循环的 list。list 最后一个元素——即 nil 被指向了 list 的开头，头脑中想象遍历列表并打印的过程吧（是不是找不到终结的打印的条件了？）。如果设置 *print-circle* 为 t，则可以正常打印： 

#1=(1 2 3 . #1#)

并且循环列表是不能求长度的： 

LENGTH: A proper list must not be circular: #1=(1 2 3 . #1#)

1.2. 环表

(defvar x '(1 2 3))
(setf (cddr x) x)   ; 注意会陷入死循环，得事先设置 *print-circle* 为 t

2. 数组

一维数组也称为向量（vector），可以通过 vector 函数创建： 

(vector 1 2 3)                          ; => #(1 2 3)
;;; 与 vector 等价的符号
#(1 2 3)                                ; => #(1 2 3)
(type-of #(1 2 3))                      ; => (SIMPLE-VECTOR 3)
                                        ; SIMPLE-ARRAY 表示没有设置 adjustable 和 fill pointer 的数组，后面讲到

数组的元素是放在一块内存块中的，在内存的布局大概如下： 

|Array header | element1 | elment2 |

Array header 保存了数组的元信息，比如数组大小。

数组通过下标引用来访问： 

(elt #(1 2 3) 1)                        ; => 2

上面创建的数组是 定长数组 ，意味着数组长度不可改变。可改变长度的数组成为 变长数组 ，通过 make-array 创建： 

(defvar a-array (make-array 3 :fill-pointer 0))
(vector-push 0 a-array)                 ; => 0
(vector-push 1 a-array)                 ; => 1
(vector-push 2 a-array)                 ; => 2
(vector-push 3 a-array)                 ; => NIL

make-array 比 vector 更加灵活，因为它可以指定数组是变长还是定长、元素的类型以及多维数组等。

创建变长数组只需要为 make-array 指定 fill-pointer 参数，fill-pointer 用于保存数组索引位置。上例代码创建了一个包含 3 个元素数组，fill-pointer 意味着索引位置指到第 0 个，每调用 vector-push 一次就往向量中填充一个元素，并返回下标位置，但最多只能填充 3 个元素，超出范围后返回 nil。

真正变长向量应该是让我们不关注大小，可随意向向量中填充数据。指定 adjustable 参数为 t 即可： 

(defvar adj-array (make-array 3 :fill-pointer 0 :adjustable t))

;;; 调用 vector-push-extend，当超出数组大小时自动扩充空间
(loop for i from 1 to 100 do (vector-push-extend i adj-array)) ; => NIL
adj-array ; => #(1 2 3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100)

字符串也是个向量（由字符组成）： 

(defvar hello "hello world")
(aref hello 1)                          ; => #\e
;;; 修改元素
(setf (aref hello 0) #\H)               ; => #\H
hello                                   ; => "Hello world"

2.1. 元素类型

手册中的定义：

  • 每个元素可以是 Common Lisp 任意对象称为 General array。
  • 每个元素都是同一种类型称为 Specialized array。
;;; make-array 指定 element-type 参数可创建特定类型的数组：
(make-array 3 :element-type 'string)
(make-array 3 :element-type 'integer)
(make-array 3 :element-type 'character)
(make-array 3 :element-type 'float)

;;; 位向量
(make-array 10 :element-type 'bit)

;; 也可以用#*创建：
#*0011

2.2. 多维数组

;;; Common Lisp 支持真正的多维数组，通过 make-array 创建

;;; 创建一个二维数组
(defvar array1 (make-array '(3 3)))
array1                               ; => #2A((0 0 0) (0 0 0) (0 0 0))
;;; “维度”又称作为 rank
(array-rank array1)                     ; => 2

;;; 索引多维数组，以及修改元素
(aref array1 0 1)                       ; => 0
(setf (aref array1 0 0) 1)              ; => 1
(setf (aref array1 0 1) 2)              ; => 2
array1                               ; => #2A((1 2 0) (0 0 0) (0 0 0))

2.3. 数组的限制

数组的大小受限于几个常量：

  • 维度限制：array-rank-limit
  • 数组总大小：array-total-size-limit
  • 数组的元素数量：array-dimension-limit

不同的 Common Lisp 实现、不同的平台，数字是不一样的。

数组 vs 列表（list）：

  • 数组内存分布更加紧密，直接通过下标访问，因此比列表快。
  • 数组中的元素不是 cons cell，不能用 car、cdr 等操作列表的函数。

3. 集合（set）

集合包含不重复元素。 

;;; intersection 函数求两个集合的交集，函数原型如下：
;;; (intersection list1 list2 &key key (test #'eql) test-not)
(intersection '(1 2 3) '(4 5 6))        ; => NIL
(intersection '(1 2 3) '(1 3 5))        ; => (3 1)

;;; union 函数求两个集合的并集，函数原型如下：
;;; (union list1 list2 &key key (test #'eql) test-not)
(union '(1 2 3) '(4 5 6))               ; => (3 2 1 4 5 6)
(union '(1 2 3) '(1 2 3 4))             ; => (4 1 2 3)

;;; set-difference 函数求两个集合的集合差，原型如下：
;;; (set-difference list1 list2 &key key (test #'eql) test-not)
(set-difference '(1 2 3) '(1 2 3))      ; => NIL
(set-difference '(1 2 3) '(1 2))        ; => (3)

;;; subsetp 函数提供了判断一个集合是否是另个集合的子集，subsetp 原型如下：
;;; (subsetp list1 list2 &key key (test #'eql) test-not)
(subsetp '(a e) '(a e i o u))           ; => T
(subsetp '(b c) '(a e i o u))           ; => NIL

4. 结构体（struct）

;;; 定义结构体
(defstruct my-info (name "lu4nx") (site "www.shellcodes.org")) ; => MY-INFO
;;; 结构体为每个成员分配了默认值，如果不需要默认值：
(defstruct my-info1 name site)          ; => MY-INFO1

;;; 创建新示例以“make-类型名”形式的函数创建：
(make-my-info) ; => #s(MY-INFO :NAME "lu4nx" :SITE "www.shellcodes.org")
                                        ; “#S”是 Common Lisp 显示结构体的符号。

;;; 创建时指定元素的值：
(make-my-info :name "lx")               ; => #S(MY-INFO :NAME "lu4nx" :SITE "www.shellcodes.org")

;;; 结构体的谓词函数，在这里的实例中是 my-info-p：
(my-info-p (make-my-info))              ; => T

;;; 访问结构体成员：
(my-info-name (make-my-info))           ; => "lu4nx"

;;; 修改结构体成员：
(defvar my-self (make-my-info))
my-self                                 ; => #S(MY-INFO :NAME "lu4nx" :SITE "www.shellcodes.org")
(setf (my-info-name my-self) "lux")
my-self                                 ; => #S(MY-INFO :NAME "lux" :SITE "www.shellcodes.org")

;;; 结构体继承：创建新结构体时，可继承原结构体的成员。
;; 如，继承 my-info 结构体
(defstruct (new-my-info (:include my-info)) (sex "man"))
(make-new-my-info) ; => #S(NEW-MY-INFO :NAME "lu4nx" :SITE "www.shellcodes.org" :SEX "man")

5. 键值索引

Common Lisp 键值索引方式有如下三种：

1、hash 表，也是最常见的，剩下两种都是基于列表来完成的

2、association list

3、property list

5.1. hash表

;;; 创建 hash 表
(defvar ahash (make-hash-table))

;;; 设置键值
(setf (gethash 'a ahash) 1)             ; => 1
(setf (gethash 'b ahash) 2)             ; => 2
(setf (gethash 'c ahash) 3)             ; => 3

;;; 移除键值
(remhash 'a ahash)                      ; => T
(gethash 'a ahash)                      ; => NIL

;;; 获得 hash 表大小
(hash-table-count ahash)                ; => 2

;;; 清空 hash 表
(clrhash ahash)     ; => #<HASH-TABLE :TEST EQL :COUNT 0 {10066276A3}>
(hash-table-count ahash)                ; => 0

;;; 遍历 hash 方法 1：
(maphash (lambda (k v)
           (format t "~A: ~A~%" k v))
         ahash)

;;; 遍历 hash 方法 2：

(loop for k being the hash-keys in ahash
   using (hash-value v)
   do
     (format t "key:~A value:~A~%" k v))

5.2. 关联表（association list）

;;; 关联表实质是上是一个有规律的嵌套列表：
'((a . 1) (b . 2) (c . 3))

;;; 使用示例：
(defvar alist '((a . 1) (b . 2) (c . 3)))
;; 通过 assoc 函数检索
(assoc 'a alist)                        ; => (A . 1)
;; 取 value
(cdr (assoc 'a alist))                  ; => 1
;; 取 key
(car (assoc 'a alist))                  ; => A
;; 通过 acons 函数增加新的键值，但是 acons 是无副作用的函数，不会直接修改内容，而是返回新的：
(acons 'd 4 alist)                      ; => ((D . 4) (A . 1) (B . 2) (C . 3))
;; 如果要修改内容，可以用 setf
(setf alist (acons 'd 4 alist)) ; => ((D . 4) (A . 1) (B . 2) (C . 3))
;; 或者 push，更为简单
(push '(e . 5) alist)                   ; => ((E . 5) (D . 4) (A . 1) (B . 2) (C . 3))

5.3. 属性表（property list）

;;; 属性表也是基于列表，但无嵌套：
'(a 1 b 2 c 3)
(defvar plist '(a 1 b 2 c 3))

;; 索引
(getf plist 'a)                         ; => 1
;; 重新赋值
(setf (getf plist 'a) 10)               ; => 10
;; 设置新值
(setf (getf plist 'e) 4)                ; => 4
;; 删除元素
(remf plist 'e)                         ; => T
plist                                   ; => (A 1 B 2 C 3)