skipmain.cpp

经典c++程序的实现

#include "stdlib.h"

#include "book.h"

typedef int ELEM;
typedef int KEY;

#define key(X) (X)
#define UNSUCCESSFUL -1

class SkipNode {
public:
  ELEM value;
  SkipNode** forward;
  SkipNode(ELEM r, int level) {
    value = r;
    forward = new SkipNode* [level];
    for (int i=0; i<level; i++)
      forward[i] = NULL;
  }
  ~SkipNode() { delete [] forward; }
};

class SkipList {
private:
  SkipNode* head;
  int level;
  void AdjustHead(int) {};
public:
  ELEM search(KEY);
  void insert(ELEM);
};

int randomLevel(void) { // Pick a level on exponential distribution
  for (int level=0; Random(2) == 0; level++); // Do nothing
  return level;
}

ELEM SkipList::search(KEY searchKey) { // Skiplist Search
  SkipNode *x = head;                  // Dummy header node
  for (int i=level; i>=0; i--)
    while ((x->forward[i] != NULL) &&
           (key(x->forward[i]->value) < searchKey))
      x = x->forward[i];
  x = x->forward[0];  // Move to actual record, if it exists
  if (key(x->value) == searchKey) return x->value;
  else return UNSUCCESSFUL;
}

void SkipList::insert(ELEM newValue) { // Insert into skiplist
  SkipNode *x = head;           // Start at header node
  int newLevel = randomLevel(); // Select level for new node
  if (newLevel > level) {       // New node will be deepest in list
    AdjustHead(newLevel);       // Add null pointers to header
    level = newLevel;
  }
  SkipNode* update[level];      // Update tracks end of each level
  for(int i=level; i>=0; i--) { // Search for insert position
    while((x->forward[i] != NULL) &&
          (key(x->forward[i]->value) < key(newValue)))
      x = x->forward[i];
    update[i] = x;              // Keep track of end at level i
  }
  x = new SkipNode(newValue, level); // Create new node
  for (i=0; i<=newLevel; i++) { // Splice into list
    x->forward[i] = update[i]->forward[i]; // Who x points to
    update[i]->forward[i] = x;             // Who y points to
  }
}

int main(int argc, char** argv) {
  return 0;
}