跳跃表(skiplist详解及代码实现(C/C++

概念介绍

跳跃表，其实是一种可以跳跃着进行查询的链表，其的本质仍然是链表，因此要想掌握跳跃表首先需要较好的理解链表这个基础的数据结构。

以下是一个跳跃表的例子，图源博主DanielWang_

从功能角度来看，跳跃表就像在链表之上架起了查询的“高速公路”，可以在普通链表上快速的查找到所要的元素。在查找元素时，跳表能够提供 $O (l o g n)$ 的时间复杂度。

从结构角度来看，跳跃表就像一个不完整的十字链表，如果比较熟悉十字链表那么跳跃表就很好理解了。
（10.13更新：想了一下，这个地方和十字链表还是有一定差别，这里的纵向是类似数组的结构而横向是链表结构）

算法原理

对于普通的链表我们知道，如果想要查询链表中的一个元素，必须从头向后依次扫描，直到找到该元素或者扫描完整个链表。现在考虑有序链表，有序链表的搜索和普通链表并无明显区别，但是如果我们将其中一些结点作为索引提取出来就可以更快速的找到所要的元素，例如下图（图源博主DanielWang_）：

正常情况下我们想要搜索元素39需要经过结点3,7,13,18，但是在这个链表中我们将3,18,77作为索引提取出来，此时如果我们再想搜索元素39就可以先在上层链表查询，3<39，18<39，77>39，因此确定查询的结点在18和77中间，从而可以减少查询的次数，虽然在本例中不是很明显，但是在规模较大的链表中就会有很好的效果，同理由于索引本身也是链表，我们还可以给索引建立索引，依次类推形成了最终的跳跃表。

那么这就会引出一个新的问题：那就是究竟选哪些结点作为索引以及一共要搭建几层索引。
这里我们首先引入完全跳跃表的概念，也就是对于一个长度为n的有序链表，可以通过构建索引，使得每一个k级结点有k+1个指针，分别跳过 $2^k-1$ ， $2^{k-1}-1$ ， $⋯\cdots$ ， $2^0-1$ 个结点，这样就可以在时间 $O (l o g n)$ 内完成集合成员的搜索运算。（完全跳跃表示例如下）

但是这只适用于静态的情况，一旦进行结点的插入操作就会导致结构变化从而打乱原有平衡，为了在动态变化中维持跳跃表中索引结点的平衡性，必须使跳跃表中 k 级结点数维持在总结点数的一定比例范围内。因此我们可以事先确定一个实数 $0 < p < 1$ ，并要求在跳跃表中具有k级指针的结点在同时具有k+1级指针的结点所占比例约为p。这里我们不妨令 $p=12p=\frac{1}{2}$ ，则我们很容易得到，在这个跳跃表中50%的指针是0级指针，25%的指针是1级指针， … …， $1002k+1\frac{100}{2^{k+1}}$ %的指针是 k级指针。这样我们就可以通过概率来解决插入时破坏平衡的问题，也就是插入新结点时这个结点有50%的概率是0级结点，25%的概率是1级结点， $1002k+1\frac{100}{2^{k+1}}$ %的概率是k级结点，这样就维持了跳跃表的平衡。

代码实现（C/C++）

跳跃表和结点的数据结构

//结点结构
typedef struct node
{int key;//键值struct node *next[1];//多层链表结点
} Node;//跳跃表结构
typedef struct skiplist
{int level;//最大层数Node *head;//表头结点
} Skiplist;

创建结点

//创建结点
Node *create_node(int level, int key)
{Node *p = (Node*)malloc(sizeof(Node)+level*sizeof(Node*));//分配对应层次的结点if(!p)return NULL;p->key = key;return p;
}

这里要注意给结点分配空间的时候大小需要仔细考虑。

创建跳跃表

//创建跳跃表
Skiplist *create_sl()
{Skiplist *sl = (Skiplist*)malloc(sizeof(Skiplist));if(!sl)return NULL;sl->level = 0;//初始化跳跃表层数为0层Node *h = create_node(MAX_L-1, 0);//创建跳跃表头结点if(!h){free(sl);return NULL;}sl->head = h;for(int i=0; i<MAX_L; i++)h->next[i] = NULL;//初始化数组return sl;
}

这里的MAX_L是人为规定的以避免过多的空间浪费，取MAX_L=16，也就是最多可以有15层索引。

搜索结点

本来这部分应该是插入，但是插入比较复杂而且插入过程中要用到搜索这部分的思想，所以把搜索写在前面，这里我们假设跳跃表已经建好了。

//查找跳跃表中元素
Node *search(Skiplist *sl, int key)
{Node *q=NULL, *p=sl->head;for(int i=sl->level-1; i>=0; i--){while((q=p->next[i]) && q->key<key)p=q;if(q && q->key==key)return q;}return NULL;
}

由于跳跃表是有序的（本题升序）所以查找并不难理解。

插入新结点

这里是跳跃表中最复杂的部分，我们分为三个部分：找到插入位置、确定新结点层数、逐层插入。

找到插入位置：

//step1:查找到在每层待插入位置,更新update数组
Node *update[MAX_L];
Node *q=NULL, *p=sl->head;
//找到每一层插入前的一个结点,放在update数组中
for(int i=sl->level-1; i>=0; i--)
{while((q=p->next[i]) && q->key<key)p=q;update[i]=p;
}
if(q && q->key == key)//如果插入的结点已经存在
{return true;
}

update数组是一个储存插入位置的数组，里面储存着每一层该插入位置的前一个结点信息，这一步和上面的搜索操作有很多相似之处。

确定新结点层数：

//step2:随机产生一个层数
int level = level_rand();//随机产生新结点的层数
//如果新生成的结点层数比原跳跃表大
if(level > sl->level)
{for(int i=sl->level; i<level; i++){update[i] = sl->head;//多出的层数讲跳跃表头结点放入update数组}sl->level = level;//更新跳跃表的层数
}

关于随机层数的生成，根据前面的分析，我们在插入一个新结点时，先将其结点级别初始化为0，然后用随机数生成器反复地产生一个[0，1]间的随机实数q。如果q<p，则使新结点级别增加1，直至 $q≥pq\geq p$ 。由此产生新结点级别的过程可知，所产生的新结点的级别为0的概率为1-p,级别为1的概率为p(1-p)，…，级别为k的概率为 $p^k(1- p)$ .
代码如下：

double random()//生成0~1的随机数
{double q = rand()/(double)RAND_MAX;return q;
}int level_rand()//生成新结点的级数
{int level = 1;while(random() <= prob)level++;return (level<=MAX_L)?level:MAX_L;
}

逐层插入

这部分只需要根据update数组中的结点把新结点的每一层插在对应结点的后面即可，插入操作和链表完全相同。

//step3:从高层至下插入
q = create_node(level, key);//创建新结点
if(!q)return false;
//根据update数组在每一层中插入新结点
for(int i=level-1; i>=0; i--)
{q->next[i] = update[i]->next[i];update[i]->next[i] = q;
}
return true;

删除结点

删除操作相当于在插入操作中省略了计算层数这一步，其余部分基本相同。

完整代码（C/C++）

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>using namespace std;
#define MAX_L 16 //最大层数  
#define prob 0.5 //有i+1级指针的结点占有i级指针的结点的比例//结点结构
typedef struct node
{int key;//键值struct node *next[1];//多层链表结点
} Node;//跳跃表结构
typedef struct skiplist
{int level;//最大层数Node *head;//表头结点
} Skiplist;//创建结点
Node *create_node(int level, int key)
{Node *p = (Node*)malloc(sizeof(Node)+level*sizeof(Node*));//分配对应层次的结点if(!p)return NULL;p->key = key;return p;
}//创建跳跃表
Skiplist *create_sl()
{Skiplist *sl = (Skiplist*)malloc(sizeof(Skiplist));if(!sl)return NULL;sl->level = 0;//初始化跳跃表层数为0层Node *h = create_node(MAX_L-1, 0);//创建跳跃表头结点if(!h){free(sl);return NULL;}sl->head = h;for(int i=0; i<MAX_L; i++)h->next[i] = NULL;//初始化数组return sl;
}double random()//生成0~1的随机数
{double q = rand()/(double)RAND_MAX;return q;
}int level_rand()//生成新结点的级数
{int level = 1;while(random() <= prob)level++;return (level<=MAX_L)?level:MAX_L;
}//向跳跃表中插入元素
bool insert(Skiplist *sl, int key)
{//step1:查找到在每层待插入位置,更新update数组Node *update[MAX_L];Node *q=NULL, *p=sl->head;//找到每一层插入前的一个结点,放在update数组中for(int i=sl->level-1; i>=0; i--){while((q=p->next[i]) && q->key<key)p=q;update[i]=p;}if(q && q->key == key)//如果插入的结点已经存在{return true;}/**************************************///step2:随机产生一个层数int level = level_rand();//随机产生新结点的层数//如果新生成的结点层数比原跳跃表大if(level > sl->level){for(int i=sl->level; i<level; i++){update[i] = sl->head;//多出的层数讲跳跃表头结点放入update数组}sl->level = level;//更新跳跃表的层数}/****************************************///step3:从高层至下插入q = create_node(level, key);//创建新结点if(!q)return false;//根据update数组在每一层中插入新结点for(int i=level-1; i>=0; i--){q->next[i] = update[i]->next[i];update[i]->next[i] = q;}return true;
}//删除跳跃表中的元素
bool erase(Skiplist *sl, int key)
{Node *update[MAX_L];Node *q=NULL, *p=sl->head;//找到每一层待删除前的一个结点,放在update数组中for(int i=sl->level-1; i>=0; i--){while((q=p->next[i]) && q->key<key)p=q;update[i]=p;}//判断q是否为待删除的结点if(!q || (q && q->key!=key))return false;//从最高层开始逐层删除结点for(int i=sl->level-1; i>=0; i--){if(update[i]->next[i] == q){update[i]->next[i]=q->next[i];//如果删除了最高层唯一的结点，则层数减一if(sl->head->next[i] == NULL)sl->level--;}}free(q);return true;
}//查找跳跃表中元素
Node *search(Skiplist *sl, int key)
{Node *q=NULL, *p=sl->head;for(int i=sl->level-1; i>=0; i--){while((q=p->next[i]) && q->key<key)p=q;if(q && q->key==key)return q;}return NULL;
}//从最高层开始逐层打印
void print(Skiplist *sl)
{Node *q;for(int i=sl->level-1; i>=0; i--){q=sl->head->next[i];printf("level %d:\n", i+1);while(q){printf("key:%d\t", q->key);q = q->next[i];}printf("\n");}
}//释放跳跃表
void free_sl(Skiplist *sl)
{if(!sl)return;Node *q = sl->head;Node *next;while(q){next = q->next[0];free(q);q = next;}free(sl);
}int main()
{srand((int)time(0));//随机数种子Skiplist *sl=create_sl();for(int i=1; i<20; i++){insert(sl, i);}print(sl);cout << "******************************" << endl;for(int i=11; i<20; i++){if(!erase(sl, i))printf("No!\n");}print(sl);free_sl(sl);return 0;
}

参考链接：https://blog.csdn.net/daniel_ustc/article/details/20218489