第三篇：列表.pdf

第三章：列表 列表是 Lisp 的基本数据结构之⼀。在最早的 Lisp ⽅⾔⾥，列表是唯⼀的数据结构： “Lisp” 这个名字起初是 “LISt Processor” 的缩写。但 Lisp 经超越这个缩写很久了。 Common Lisp 是⼀个有着各式各样数据结构的通⽤性程序语⾔。 Lisp 程序开发通常呼应着开发 Lisp 语⾔⾃⾝。在最初版本的 Lisp 程序，你可能使⽤ 很多列表。然⽽之后的版本，你可能换到快速、特定的数据结构。本章描述了你可以 ⽤列表所做的很多事情，以及使⽤它们来演⽰⼀些普遍的 Lisp 概念。 3.1 构造 (Conses) 3.2 等式 (Equality) 3.3 为什么 Lisp 没有指针 (W y Lisp Has No Pointers) 3.4 建⽴列表 (Building Lists) 3.5 ⽰例：压缩 (Example: Compression) 3.6 存取 (Access) 3.7 映射函数 (Mapping Functions) 3.8 树 (Trees) 3.9 理解递归 (Understanding Recursion) 3.10 集合 (Sets) 3.11 序列 (Sequences) 3.12 栈 (Stacks) 3.13 点状列表 (Dotted Lists) 3.14 关联列表 (Assoc-lists) 3.15 ⽰例：最短路径 (Example: S ortest Pat ) 3.16 垃圾 (Garbages) C apter 3 总结 (Summary) C apter 3 习题 (Exercises) 3.1 构造 (Conses) 在 2.4 节我们介绍了 cons , car , 以及 cdr ，基本的 List 操作函数。 cons 真正所做 的事情是，把两个对象结合成⼀个有两部分的对象，称之为 Cons 对象。概念上来 说，⼀个 Cons 是⼀对指针；第⼀个是 car ，第⼆个是 cdr 。 Cons 对象提供了⼀个⽅便的表⽰法，来表⽰任何类型的对象。⼀个 Cons 对象⾥的⼀ 对指针，可以指向任何类型的对象，包括 Cons对象本⾝。它利⽤到我们之后可以 ⽤ cons 来构造列表的可能性。 我们往往不会把列表想成是成对的，但它们可以这样被定义。任何⾮空的列表，都可 以被视为⼀对由列表第⼀个元素及列表其余元素所组成的列表。 Lisp 列表体现了这个 概念。我们使⽤ Cons 的⼀半来指向列表的第⼀个元素，然后⽤另⼀半指向列表其余 的元素(可能是别的 Cons 或 nil ) 。 Lisp 的惯例是使⽤ car 代表列表的第⼀个元素， ⽽⽤ cdr 代表列表的其余的元素。所以现在 car 是列表的第⼀个元素的同义词， ⽽ cdr 是列表的其余的元素的同义词。列表不是不同的对象，⽽是像 Cons 这样的⽅ 式连结起来。 当我们想在 nil 上⾯建⽴东西时， (setf x (cons a nil)) (A) 图 3.2 三个元素的列表 (cdr y) (B C) 在⼀个有多个元素的列表中， car 指针让你取得元素，⽽ cdr 让你取得列表内其余 的东西。 ⼀个列表可以有任何类型的对象作为元素，包括另⼀个列表： (setf z (list a (list b c) d)) (A (B C) D) 当这种情况发⽣时，它的结构如图 3.3 所⽰；第⼆个 Cons 的 car 指针也指向⼀个列 表： (car (cdr z)) (B C) 学⽣在学习递归时，有时候是被⿎励在纸上追踪 (trace)递归程序调⽤ (invocation)的过 程。 (288页 「译注：附录 A 追踪与回溯」可以看到⼀个递归函数的追踪过程。)但这 种练习可能会误导你：⼀个程序员在定义⼀个递归函数时，通常不会特别地去想函数 的调⽤顺序所导致的结果。 如果⼀个⼈总是需要这样⼦思考程序，递归会是艰难的、没有帮助的。递归的优点是 它精确地让我们更抽象地来设计算法。你不需要考虑真正函数时所有的调⽤过程，就 可以判断⼀个递归函数是否是正确的。 要知道⼀个递归函数是否做它该做的事，你只需要问，它包含了所有的情况吗？举