数据结构

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)