算法导论（十）－－基本数据结构

算法所操作的集合可以随时间改变而增大、缩小或产生其它变化，我们称这种集合是动态的。动态集合上的操作可分为两类：查询操作，返回有关集合的信息；修改操作，对集合进行修改。下面是一些典型的操作：
SEARCH(S, k)：给定一个集合S和一个关键字k，返回指向S中一个元素的指针x，使得x.key = k。
INSERT(S, x)：一个修改操作，将由x指向的元素添加到S中去。
DELETE(S, x)：修改操作，将指向S中某元素的指针x从S中删除。
MINIMUM(S)：返回指向S中具有最小关键字的元素的指针。
MAXIMUM(S)：返回指向S中具有最大关键字的元素的指针。
SUCCESSOR(S, x)：返回S中比x大的下一个元素的指针。当x为最大元素时，返回NIL。
PREDECESSOR(S, x)：返回S中比x小的下一个元素的指针。当x为最小元素时，返回NIL。

栈和队列

栈是后进先出（last-in, first-out，LIFO）的结构，它的INSERT操作称为压入（PUSH），而无参数的DELETE操作称为弹出（POP）。栈有一属性top，指向最近插入的元素。

下面是相关操作的伪代码（用数组实现）：

STACK_EMPTY(S) {
1      if S.top == 0
2                  return TRUE;
3         else return FALSE;
}

PUSH(S, x) {
1      S.top += 1;
2         S[S.top] = x;
}

POP(S) {
1      if STACK_EMPTY(S)
2                  error "underflow";
3         else {
4                  x = S[S.top];
5                  S.top -= 1;
6                  return x;
7         }
}

上述三种操作运行时间都为O(1)。

队列是先进先出（first-in, first-out，FIFO）的结构。它的INSERT操作称为入队（ENQUEUE），而无参数的DELETE操作称为出队（DEQUEUE）。队列有两个属性head和tail。

用数组实现的队列看起来是这样：

各操作的伪代码如下，（不考虑上溢与下溢的情况）：

ENQUEUE(Q, x) {
1      Q[Q.tail] = x;
2         if Q.tail == Q.length
3                  Q.tail = 1;
4         else Q.tail += 1;
}

DEQUEUE(Q) {
1      x = Q[Q.head];
2      if Q.head == Q.length
3           Q.head = 1
4      else Q.head += 1;
5      return x;
}

上述两种操作运行时间都为O(1)。

链表

一个典型的（双向）链表看起来会像这样：

它的相关操作为：

LIST_SEARCH(L, k) {
1      x = L.head;
2         while x ≠ NIL and x.key ≠ k
3                  x = x.next;
4         return x;
}

（在链表头）插入：

LIST_INSERT(L, x) {
1      x.next = L.head;
2         if L.head ≠ NIL
3                  L.head.prev = x;
4         L.head = x;
5         x.prev = NIL;
}

删除：

LIST_DELETE(L, x) {
1      if x.prev ≠ NIL
2                  x.prev.next = x.next;
3         else
4                  L.head = x.next;
5         if x.next ≠ NIL
6                  x.next.prev = x.prev;
}

链表的插入和删除运行时间为O(1)，查找的运行时间为O(n)。

利用哨兵（sentinel）元素可以简化链表的操作，避免一些空指针的判断。链表的NIL属性会指向哨兵元素：

它的相关操作为：

LIST_DELETE'(L, x) {
1      x.prev.next = x.next;
2   x.next.prev = x.prev;
}

LIST_SEARCH'(L, k) {
1      x = L.nil.next;
2      while x ≠ L.nil and x.key ≠ k
3            x = x.next;
4      return x;
}

LIST_INSERT'(L, x) {
1      x.next = L.nil.next;
2      L.nil.next.prev = x;
3   L.nil.next = x;
4      x.prev = L.nil;
}

指针和对象的实现
有些语言（例如FORTRAN）并不支持指针与对象数据类型，这种情况下如何实现链表？

我们可以用三个数组key，next和prev来实现：

也可以用一个数组实现，这样的好处是比较灵活，允许同一数组存放不同长度的对象：

可以看到数组中有些是未使用的空间（可以在此空间创建新的对象），其它的都是已经存放了对象的空间。我们需要一个机制来管理这些空闲的空间，它便是自由表。

下图的数组里维护了两个（双向）链表，同时用一个自由表（单向链表）来管理空闲的空间：

分配和去配（释放）对象的伪代码如下：

ALLOCATE_OBJECT() {
1      if free == NIL
2                  error "out of space";
3         else {
4                  x = free;
5                  free = free.next;
6                  return x;
7         }
}

FREE_OBJECT(x) {
1      x.next = free;
2         free = x;
}

上面管理空闲空间的两个过程运行时间都为O(1)。

有根树的表示

二叉树可以这样表示：每个结点维护三个域，分别存放指向父亲、左儿子和右儿子的指针。看下图：

而对于有任意数量子女的有根树来 说，用以上方法，维护child1、child2、...、childn指针分别指向各子女是不切实际的，因为首先这些指针的总数是不确定的。如果每个结 点都维护很大数量的子结点指针的话，对于一些并没有这么多子女的结点来说无疑是一种浪费。我们可以用二叉树来表示这样的有根树：它有三个域，left- child指向它的最左孩子，right-sibling指向它的右兄弟，parent指向它的父亲：