算法所操作的集合可以随时间改变而增大、缩小或产生其它变化,我们称这种集合是动态的。动态集合上的操作可分为两类:查询操作,返回有关集合的信息;修改操作,对集合进行修改。下面是一些典型的操作:
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指向它的父亲:
阅读(1818) | 评论(0) | 转发(9) |