#define MAXLEVEL 100
struct Node
{
　 int key;
　 Node* next[];
};
struct SkipList
{
　int level;
　 Node* head;
};
Node* CreateNode(int key, int level)
{
　Node* node = (Node*)malloc(sizeof(Node)+(level+1)*sizeof(Node*));
　 node->key = key;
　 for (int i = 0; i <= level; ++i) node->next[i] = NULL;
　 return node;
}
int RandLevel()
{
　 int level = 0;
　while ((rand() & 1) == 0 && level < MAXLEVEL) ++level；
　 return level;
}
SkipList* CreateSkipList()
{
　 SkipList* sl = new SkipList;
　 sl->level = 0;
　sl->head = CreateNode(0, MAXLEVEL);
　return sl;
}
bool Insert(SkipList* sl, int key)
{
　Node* pre = sl->head;
　Node* cur = sl->head;
　 Node* update[MAXLEVEL];
　 for (int i = sl->level; i >=0; --i)
　{
　　 while (cur!= NULL&&cur->key < key)
　　 {
　　　 pre = cur;
　　　 cur = cur->next[i];
　　 }
　　 update[i] = pre;
　　cur = pre;
　}
　if (cur!=NULL&&cur->key == key) return false;
　 int level = RandLevel();
　if (level > sl->level)
　 {
　　for (int i = sl->level+1; i <= level; ++i) update[i] = sl->head;
　　sl->level = level;
　 }
　Node* temp = CreateNode(key, level);
　 for (int i = 0; i <= level; ++i)
　 {
　　 temp->next[i] = update[i]->next[i];
　　 update[i]->next[i] = temp;
　}
　 return true;
}
bool Remove(SkipList* sl, int key)
{
　int level = sl->level;
　Node* pre = sl->head;
　 Node* cur = sl->head;
　for (int i = level; i >=0; --i)
　 {
　　 while (cur != NULL&&cur->key < key)
　　 {
　　　 pre = cur;
　　　 cur = cur->next[i];
　　 }
　　 if (cur!=NULL&&cur->key == key)
　　 {
　　　 pre->next[i] = cur->next[i];
　　　 if (NULL == sl->head->next[i]) --sl->level;
　　 }
　　 if(i>0) cur = pre;
　}
　 if (cur != NULL&&cur->key == key)
　{
　　free(cur);
　　return true;
　 }
　return false;
}
int Query(SkipList* sl,int key)
{
　int level = sl->level;
　 Node* pre = NULL;
　Node* cur = sl->head;
　for (int i = level; i >= 0; --i)
　{
　　 while (cur != NULL&&cur->key < key)
　　{
　　　 pre = cur;
　　　 cur = cur->next[i];
　　 }
　　 if (cur != NULL&&cur->key == key) return key;
　　 cur = pre;
　 }
　 return -1;
}

代码是看了网上的代码，自己再实现一遍的。我本尝试着对代码进行优化，没想到踩了不少坑。在插入的时候，我想去掉update数组，但那样做可能导致插入到一半才发现该键已存在。我定义头结点时，改成像链表那样头结点只存地址，测试之后才意识到自己对跳跃表的理解不够，跳跃表是查不到就回溯节点到下一层的，头结点必须存一个最小值。