Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1793353
  • 博文数量: 438
  • 博客积分: 9799
  • 博客等级: 中将
  • 技术积分: 6092
  • 用 户 组: 普通用户
  • 注册时间: 2012-03-25 17:25
文章分类

全部博文(438)

文章存档

2019年(1)

2013年(8)

2012年(429)

分类: C/C++

2012-04-06 12:21:39

算法所操作的集合可以随时间改变而增大、缩小或产生其它变化,我们称这种集合是动态的。动态集合上的操作可分为两类:查询操作,返回有关集合的信息;修改操作,对集合进行修改。下面是一些典型的操作:
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,指向最近插入的元素。

下面是相关操作的伪代码(用数组实现):


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


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

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

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


队列是先进先出(first-in, first-out,FIFO)的结构。它的INSERT操作称为入队(ENQUEUE),而无参数的DELETE操作称为出队(DEQUEUE)。队列有两个属性headtail

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

各操作的伪代码如下,(不考虑上溢与下溢的情况):


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

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

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


链表

一个典型的(双向)链表看起来会像这样:

它的相关操作为:


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

(在链表头)插入:
  1. LIST_INSERT(L, x) {
  2. 1   x.next = L.head;
  3. 2   if L.head ≠ NIL
  4. 3     L.head.prev = x;
  5. 4   L.head = x;
  6. 5   x.prev = NIL;
  7. }

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

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

利用哨兵(sentinel)元素可以简化链表的操作,避免一些空指针的判断。链表的NIL属性会指向哨兵元素:

它的相关操作为:


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


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


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


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

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

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

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

下图的数组里维护了两个(双向)链表,同时用一个自由表(单向链表)来管理空闲的空间:

分配和去配(释放)对象的伪代码如下:


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


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

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

有根树的表示

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

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

阅读(1818) | 评论(0) | 转发(9) |
给主人留下些什么吧!~~