数据结构

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/有序对

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

CL-USER> (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,也能表示空列表。

判断两个列表是否相等:

(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 环表

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

2 数组

一维数组也称为向量(vector),可以通过 vector 函数创建:

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

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

|Array header | element1 | elment2 |

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

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

CL-USER> (elt #(1 2 3) 1)
2

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

CL-USER> (defvar a-array (make-array 3 :fill-pointer 0))
A-ARRAY
CL-USER> (vector-push 0 a-array)
0
CL-USER> (vector-push 1 a-array)
1
CL-USER> (vector-push 2 a-array)
2
CL-USER> (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 即可:

CL-USER> (defvar adj-array (make-array 3 :fill-pointer 0 :adjustable t))
ADJ-ARRAY
;;; 调用 vector-push-extend,当超出数组大小时自动扩充空间
CL-USER> (loop for i from 1 to 100 do (vector-push-extend i adj-array))
NIL
CL-USER> 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)

字符串也是个向量(由字符组成):

CL-USER> (defvar hello "hello world")
HELLO
CL-USER> (aref hello 1)
#\e
CL-USER> (setf (aref hello 0) #\H) ; 修改元素
#\H
CL-USER> 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 创建:

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

;;; 索引多维数组,以及修改元素
CL-USER> (aref array1 0 1)
0
CL-USER> (setf (aref array1 0 0) 1)
1
CL-USER> (setf (aref array1 0 1) 2)
2
CL-USER> 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 实现、不同的平台,数字是不一样的。

2.4 数组 vs 列表(list)

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

3 集合(set)

集合包含不重复元素。

3.1 交集

intersection 函数求两个集合的交集,函数原型如下:

(intersection list1 list2 &key key (test #'eql) test-not)
CL-USER> (intersection '(1 2 3) '(4 5 6))
NIL
CL-USER> (intersection '(1 2 3) '(1 3 5))
(3 1)

3.2 并集

union 函数求两个集合的并集,函数原型如下:

(union list1 list2 &key key (test #'eql) test-not)
CL-USER> (union '(1 2 3) '(4 5 6))
(3 2 1 4 5 6)
CL-USER> (union '(1 2 3) '(1 2 3 4))
(4 1 2 3)

3.3 集合差

set-difference 函数求两个集合的集合差,原型如下:

(set-difference list1 list2 &key key (test #'eql) test-not)
CL-USER> (set-difference '(1 2 3) '(1 2 3))
NIL
CL-USER> (set-difference '(1 2 3) '(1 2))
(3)

3.4 子集判断

subsetp 函数提供了判断一个集合是否是另个集合的子集,subsetp 原型如下:

(subsetp list1 list2 &key key (test #'eql) test-not)
CL-USER> (subsetp '(a e) '(a e i o u))
T
CL-USER> (subsetp '(b c) '(a e i o u))
NIL

4 结构体(struct)

4.1 定义结构体

CL-USER> (defstruct my-info (name "lu4nx") (site "www.shellcodes.org"))
MY-INFO

;;; 上面创建的结构体为每个成员分配了默认值,如果不需要默认值:
CL-USER> (defstruct my-info1 name site)
MY-INFO1

创建新示例以“make-类型名”形式的函数创建:

CL-USER> (make-my-info)
#S(MY-INFO :NAME "lu4nx" :SITE "www.shellcodes.org") ; “#S”是 Common Lisp 显示结构体的符号。

创建时指定元素的值:

CL-USER> (make-my-info :name "lx")
#S(MY-INFO :NAME "lu4nx" :SITE "www.shellcodes.org")

结构体的谓词函数,在这里的实例中是 my-info-p:

CL-USER> (my-info-p (make-my-info))
T

4.2 访问结构体成员

CL-USER> (my-info-name (make-my-info))
"lu4nx"

修改结构体成员:

CL-USER> (defvar my-self (make-my-info))
MY-SELF
CL-USER> my-self
#S(MY-INFO :NAME "lu4nx" :SITE "www.shellcodes.org")
CL-USER> (setf (my-info-name my-self) "lux")
"lux"
CL-USER> my-self
#S(MY-INFO :NAME "lux" :SITE "www.shellcodes.org")

4.3 结构体继承

创建新结构体时,可继承原结构体的成员。

CL-USER> (defstruct (new-my-info (:include my-info)) (sex "man"))
NEW-MY-INFO
CL-USER> (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

hash表是最常见的,剩下两种都是基于列表来完成的。

5.1 hash表

CL-USER> (defvar ahash (make-hash-table)) ; 创建 hash 表
AHASH
;;; 设置键值
CL-USER> (setf (gethash 'a ahash) 1)
1
CL-USER> (setf (gethash 'b ahash) 2)
2
CL-USER> (setf (gethash 'c ahash) 3)
3

;;; 移除键值
CL-USER> (remhash 'a ahash)
T
CL-USER> (gethash 'a ahash)
NIL

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

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

遍历Hash表的两种方式:

(maphash (lambda (k v)
           (format t "~A: ~A~%" k v))
         ahash)

;; 或者

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

它的使用也很简单:

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

5.3 属性表(property list)

属性表也是基于列表,但无嵌套:

'(a 1 b 2 c 3)
CL-USER> (defvar plist '(a 1 b 2 c 3))
PLIST
CL-USER> (getf plist 'a) ; 索引
1
CL-USER> (setf (getf plist 'a) 10) ; 重新赋值
10
CL-USER> (setf (getf plist 'e) 4) ; 设置新值
4

;; 删除元素
CL-USER> (remf plist 'e)
T
CL-USER> plist
(A 1 B 2 C 3)