数据结构之线性结构

1、数据结构之线性结构(一，表结构)作者：冲出宇宙时间：2006-10-24修改：2006-11-3转载请注明作者。作者主要参考了 上面的资料(因为Wikipedia上不去)和部 分较新学术论文(一般来自于acm, IEEE和springer)，如果有什么疑问，您 可以参考以上资料，我会努力的把重要的论文罗列在文章里面。本文主要介绍了线性数据结构部分，线性数据的分类来自于wikipedia，见 页面：/topic/list-of-data-structures1线性数据结构的分类线性数据结构的分类如下：.表(List).数组(Array).位图(Bitmaps).图片(Images).数字高程模型

2、(Heightfield).动态数组(Dynamic array).平行数组(Parallel array).向量(Vector).集合(Set).链表(Linked list).松散链表(Unrolled linked list).Xor 链表(Xor linked list).可变表(VList) .联合数组(Associative array).散列表(Hash table).跳跃表(Skip list).栈(Stack).队列(Queue).优先队列(Priority queue).双向队列(Deque).间隙缓冲(Gap buffer)2 表(List)表是一个抽象数据结构（ADT,

3、 abstract data type，它表示的是一种接口， 而不是实现），它表示的是一个有序实体集合。但是，表并没有一个确定的接口。 比如，可变的表会包含4种操作：1，建立空表；测试表十分为空；在前端插入一个数据到表里面去；返回一个新表，包含了除了第一个元素（也可能是最后一个元素）以外 的其它所有元素。在现实中，表通常由数组或者链表实现，因为它们都和表具有一些共同点。 通常人们会把表当成是链表的别名。序列也是表的另外一个名字，它突出了实体 之间的顺序关系。数组（Array）AhOu L n-l+J rk和数组相关的有向量、表（一维数组实现）、矩阵（二维数组实现），数组 是一种最简单的数据结构

4、。数组包含了一系列的数据元素，而且这些元素一般都 是同样的大小和类型。数组里面的元素通过索引来访问，一般的说，索引是一段 连续的整数范围，但是，它也可以为任何有序的数值。数组可以是多维的，比如， 2维数组。3维或者以上的数组很少被采用。时间复杂度：通过索引访问数组极快（o（1），但是，从数组里面插入或者删除一个数据的 代价很高（o（n），特别是删除数据可能会造成数组空闲太多，和插入数据造成数 组空间不够。这些可以利用动态数组来解决。链表虽然插入或者删除数据较快， 可是访问其中的元素十分慢（o（n）。空间复杂度：数组是最不浪费内存的数据结构，比较起来散列表是十分浪费内存的。数组 不占用任何额外的

5、空间（最多增加一个保存数组的大小，4字节）。程序：大部分程序都内置数组类型。位图（Bitmap）Op 1+j 1+j 0+j Ip 0+j Op 0+j-1+j 1+j 1+j 0+j Op位图其实是一个数组，数组的每个元素都是布尔值（0/1）。常常使用字节 数组来表示位图，因为每个字节可以表示8个位图的元素。位图最常用在空间处 理上，比如，磁盘分配。根据位图的个性，所有用来表示是和否的地方都可以使 用它。因为一个字节的位图可以表示8个是和否，所以，它也常常用来压缩数据。 不过，访问一位比访问一个字节会慢很多，访问一个字节比访问一个int会慢很 多（如果32位机器）。图片（Images）图片也

6、叫数字图片。图片是一个2维结构，每个元素对应于图片上的某点。 每个元素的大小根据其要显示的效果而变化，主要有1位，8位，16位，24位， 32位几种。根据显示色彩的不同，一般可以分为黑白、灰度、彩色（8位，16 位，24位，32位）、抖动色这几种。一般的图片都由很多像素组成，所以，一 个图片占用的空间十分大。一般情况下，压缩是必须的。最常见的几种压缩格式 为：gif（lzw 压缩）、png （未知）、jpg（DCT 压缩）、jpg2000 （小波压缩）。数字高程模型（Heightfield 也叫：Digital Elevation Model, or DEM）DEM也是一个位图，只是，它每个点

7、表示的意思是高度。动态数组(Dynamic Array)它同时的名字还有：可增数组(growable array),可变长数组(resizable array),动态表(dynamic table),数组表(array list)。它是一种能够自动 调整自己大小的数组。当加入一个新数据时，如果动态数组没有空间了，它会申请一个新的空间， 然后把旧数据全部拷贝过去，释放旧空间(有些动态数组的实现并不会拷贝旧数 据过去，也不会释放旧空间)。一般的时候，新分配的空间大小都是原来空间大 小的一个倍数，保证有一部分空间是空闲的。简单的计算一下，就能发现加入一 个数据的平均花销是0(1)。同样的道理，删除一

8、个数据的时候，如果空闲的空间 太多了，动态数组也可能申请一个新空间，然后删除旧空间。申请新空间时，申请多大的空间是一个值得考虑的问题。目前来说，一般认 为申请的新空间为旧空间的1.4-4倍之间都是合适的，最常见的是2倍。在浪费空间上面，有人证明了至少需要浪费。(时1/2)这么多空间才能保证插 入和删除都在常数时间内完成。Andrej Brodnik, Svante Carlsson, Erik D. Demaine, J. Ian Munro, and R obert Sedgewick. Resizable Arrays in Optimal Time and Space (1999). W

9、orkshop on Algorithms and Data Structures, pp.37 48动态数组还有很多变形，比如，为了加快删除的速度，可以把开始的数据放 到中间(如图)：这里，第一个数据放到数组的中间，第i个数据放到(i+n/2)%n的位置。当 删除数据的时候，最多只需要移动n/2次就行了。当然了，需要保存一个开始的 位置和实际的数组长度。比如，删除掉3,得到：5 6 7 1 2 4 *，删除掉7得 到：* 5 6 1 2 4 *。平行数组(Parallel Array)平行数组最初是为了在不支持记录(对象)的环境下面使用的。它把一个记 录切分成多个基本数组，每个数组的长度一样

10、。比如，struct Infoint char*age;name;Info person2;我们可以使用平行数组表示为：int ages = 1,2;char *names = good,zzp;平行数组拥有的结构简单，访问速度快速，同时，还能够节省结构可能需要 使用的指针(某些语言需要指针，某些不需要。比如，c语言不需要指针，而j ava语言需要指针)。但是，它的最大缺点是当记录含有很多域的时候，平行数 组将变得极难维护，同时，对它的顺序访问并不会实际问顺序的位置，对基于访 问局部性的缓冲策略是一大妨碍。向量(Vector)向量是一个十分基本的动态数组，它具有和动态数组一样的性质。集合(Se

11、t)集合是包含了一系列的数据，这些数据没有经过排序而且也没有重复的数 据。它比较严格的对应于数学上的集合的概念。集合必须是有限的，这点和数学 上的集合不同。集合一般来说必须支持以下几种操作：1)判断一个元素是否在 集合里面；2)对集合的所有元素进行遍历；3) 2个集合之间的交和并操作。虽 然联合数组是通常的建立集合的数据结构，但是，它并不能很好的支持集合之间 的交并操作。链表(Linked list)链表是计算机科学里面最基础的数据结构之一。它包含一系列的节点，每个 节点含有任意多个的域和一个或者两个的指针。指针可能指向前面一个节点也可 能指向后面一个节点。增加或者删除一个指定节点都是常数时间

12、，但是随机访问 一个节点的代价是o(n)。常用的3种链表为：单链表、双向链表和循环链表。见 图。单链表是最简单的链表形式，每个节点有一个指针，指向后一个节点。最后的那个节点的指针指向null。它访问任何节点都必须从头开始，一步一步的走到 待访问的节点。双向链表是一个复杂一点的结构，它的每个节点包含2个指针，一个指向前 一个节点，一个指向后一个节点。同样，第一个节点的前向指针指向null，最后 那个节点的后向指针指向null。它可以从头遍历也可以从尾遍历。循环链表把第一个节点和最后一个节点链接了起来。它可以在单向链表或者 双向链表的基础上构建。第一个节点的前向指针指向最后的那个节点，而最后那 个

13、节点的后向指针指向第一个节点。哨兵节点(Sentinel Nodes)是一个额外的未使用的节点，它常常在链表的 开头或者结尾。它用来加快或者简化某些计算的过程。 松散链表(unrolled linked list)链表的最大问题是访问非聚集(即连续的访问并不是访问连续的内存空间)， 松散链表的主要目的是为了解决这个问题(从而显著的提高缓冲性能)。松散链表改进了普通链表的结构，现在每个节点可以包含多个数据。每个节 点包含多个元素。其基本结构为：struct NodeNode next;/下一个节点int maxElement; /节点包含的最大元素个数Array Elements; /本节点包含

14、的元素个数链表里面的每个节点对应一个元素，而松散链表每个节点可以包含最多ma xElements个元素。从其定义可以看出，节点可以包含少于maxElement个元素。 那么，我们需要一个规则来决定如何包含元素到节点里面，同时尽量保证节点的 elements数组空间利用率高。基本的松散链表使用的是1-2规则，也就是说， 如果节点里面包含的元素个数将大于可以包含的元素个数，那么，就把这个节点 分裂成2个节点，而如果这个节点包含的元素数将小于maxElement/2，就从邻 近的节点借一些元素过来，如果邻近的节点在借给它之后，拥有的节点数小于m axElement/2的话，就把这2个节点合并成一个节

15、点。总之，1-2规则就是保证 (只有一个节点例外)每个节点至少空间利用在1/2。按照这个规律，最常使用 的还有2-3规则和3-4规则。再大一些的规则就十分难以控制了，因为笔者曾经 写过3-4规则的B*树，代码的复杂程度让我不敢重新再看一遍了。至于空间性能方面，每个节点至少有1/2的空间利用率，在平衡的情况下， 每个节点的利用率应该是(1+1/2)/2=3/4。但是，如果我们的插入和删除仅仅发生 在表头和表尾的话，那每个节点就几乎都是满的了。假设每个节点都是满的，链 表总共表示了 N个元素，每个元素的空间占用为e，同时，每个节点的指针和计 算开销为r，松散链表里每个节点最大可以包含的元素为M个，

16、那么，基本链表 占用的空间为：(e+r)*N，而松散链表的空间占用为：(e*M+r)*(N/M)。在时间性能方面，显然查找一个元素，基本的链表需要花费o(n)的时间，而 松散链表为o(n/M); XOR链表(XOR linked list或者zip链表，拉链式链表)双向链表虽然每个节点只包含了 2个指针，可是在内存紧张的地方(比如手 机或者单片机)还是占用了太多空间。于是，Xor链表就被设计出来减少空间的 占用，它使用一个值(前向指针xor后向指针)来同时保存前向指针和后向指 针。传统的双向链表中，每个节点需要2个指针来指向前一个节点和后一个节点: TOC o 1-5 h z ABCD-|-|

17、-|-|-| -xor链表试图把节点的前后指针合并起来(利用xor操作)：ABCD * xor满足如下性质：X xor ( X xor Y) = Y;这样，只要知道了.的值，就能够从前往后遍历整个链表，只要知道了 *， 就能够从后往前遍历节点。这种方式类似于拉拉链，所以，有人把它称为zip链 表。AdA9 O BaD Dp CH和T分别表示头和尾数据小为什么这种操作可行呢？因为xor的性质。xor有如下几个性质：1，m xor 0 = m; 2, m xor m = 0; 3, m xor n = n xor m;于是，就有了 m xor (m xor n) = n。在给定一个后向指针的初始值

18、m的时候，我们就能够根据上面的 这个式子一步一步的得到下一个节点的指针。xor的性质的另外一个运用就是swap函数。swap函数的版本有很多，但是， 最简单的还是下面的这种方式：swap(x,y)x = x xor y;y = x xor y;x = x xor y;建议不使用xor链表，因为它浪费计算时间及影响缓存性能。如果真的要节 省空间的话，推荐使用松散链表。2.2 可变表(VList)Ba$e Offset 一VList的显然是基于松散表的，它的每个节点都包含多个元素。下面是一个VList的例子：*-*2001000130这里有3个元素，为1000，130，200。共2个节点，第一个节点可以最多 包含2个元素，第2个最多可以包含一个元素。那么，在删除200的时候，VLi st会变成：*1000130这里，表示第一个节点的第一个元素为空。简单的说，VList包含多个节点，除了第一个节点以外，其他第i个节点包 含的空间是第i+1个节点的r倍。r是固定的，一般可以为2。每个节点包含的还 有下一个节点的指针及其有效数据的开始位置。同时，它还包含本节点的数组长 度，和当前数据的最大的