跳表SkipList的原理和C实现

跳表SkipList，顾名思义是链表的一种，或者说它是单链表的变异实现，使用跳表可以将查询操作的复杂度控制到θ(lg N)，而普通的链表只能通过顺序查找，复杂度为θ(N)，如此跳表的优势就很明显了，虽然它是通过以空间换时间搞定的。

先看一下普通的有序单链表：

要在里面查找一个值就需要顺序比较，复杂度大家都清楚了。如何降低复杂度，折半查找也却可以将复杂度降到θ(lg N)，但不适应单链表，那就将折半的思想抽出来，隔一段位置就建立一个标签索引，根据标签索引缩短查找范围，就是跳表，如下图：

跳表通过对间隔的数据做一个标签索引，产生了多层单链表，在最高层依次确定查找数据的范围，最终将范围缩小到可接受值，我们看跳表其实就是一个二叉查找树的变形，只是所有的数据都在最左段，其他节点用来建立查找索引，如此跳表的插入删除就比二叉查找树方便多了。

查找过程：

例子：查找元素 117

比较 21，比 21 大，往后面找
比较 37, 比 37大，比链表最大值小，从 37 的下面一层开始找
比较 71, 比 71 大，比链表最大值小，从 71 的下面一层开始找
比较 85，比 85 大，从后面找
比较 117，等于 117，找到了节点。

查找代码：

EnlighterJS 3 Syntax Highlighter

DataType *search(DataType x)

while (p->right->data < x)

DataType *search(DataType x) { DataType *p = Top; while(1) { while (p->right->data < x) { p = p->right; } if (p->down == NULL) { return p->right; } p = p->down; } }

DataType *search(DataType x) { DataType *p = Top;

while(1)
{
     while (p->right->data < x)
     {    p = p->right;
     }
     if (p->down == NULL)
     {
          return p->right;
     }
     p = p->down;
}

}

插入过程：

首先需要确定插入数值的层数K，即数值要建立K-1个索引。K通过随机数random(0,1)掷硬币得出，即为投掷出0的次数

如：

EnlighterJS 3 Syntax Highlighter

int get_level() { k=1; while(random(0,1)) { k++; } return k; }

如果插入的值是119,层数为2,则遍历倒数2层，插入相关的数据节点。

具体代码:

EnlighterJS 3 Syntax Highlighter

int skipnode_insert(int value)

int max_level = get_skiplist_level();

int random_level = get_random_levle();

/*define point to mark insert location*/ skipnode *skiplist_heads[random_level];

memset(skiplist_heads,0,sizeof(skipnode));

while(p->next->value < value)

if(level < = random_level)

skiplist_heads[level-1] = p;

for (int i = 0; i < random_level; i++)

skipnode *node = (skipnode*)malloc(sizeof(skipnode));

/*add new line*/ if(p == NULL)

skipnode *node_head = (skipnode*)malloc(sizeof(skipnode));

int skipnode_insert(int value) { int max_level = get_skiplist_level(); int random_level = get_random_levle(); int level = max_level; /*define point to mark insert location*/ skipnode *skiplist_heads[random_level]; memset(skiplist_heads,0,sizeof(skipnode)); skipnode *p = TOP; while(p) { while(p->next->value < value) { p = p->next; } if(level < = random_level) { skiplist_heads[level-1] = p; p = p->down; level--; } } p = NULL; skipnode * down = NULL; for (int i = 0; i < random_level; i++) { p = skiplist_heads[i]; skipnode *node = (skipnode*)malloc(sizeof(skipnode)); /*add new line*/ if(p == NULL) { skipnode *node_head = (skipnode*)malloc(sizeof(skipnode)); node_head->value = -1; node_head->down = TOP; node_head->next = NULL; p = node_head; TOP = node_head; } node->value = value; node->next = p->next; node->down = down; p->next = node; down = p; } }

int skipnode_insert(int value) {

int max\_level = get\_skiplist\_level();
int random\_level = get\_random\_levle();
int level = max\_level;

/\*define point to mark insert location\*/    skipnode \*skiplist\_heads\[random\_level\];
memset(skiplist\_heads,0,sizeof(skipnode));

skipnode \*p = TOP;
while(p)
{
    while(p->next->value < value)
    {
        p = p->next;
    }
    if(level < = random\_level)
    {
        skiplist\_heads\[level-1\] = p;
        p = p->down;
        level--;
    }
}

p = NULL;
skipnode \* down = NULL;

for (int i = 0; i < random\_level; i++)
{
     p = skiplist\_heads\[i\];
     skipnode \*node = (skipnode\*)malloc(sizeof(skipnode));
     /\*add new line\*/         if(p == NULL)
     {
        skipnode \*node\_head = (skipnode\*)malloc(sizeof(skipnode));
        node\_head->value = -1;
        node\_head->down = TOP;
        node\_head->next = NULL;

        p = node\_head;
        TOP = node\_head;
    }
    node->value = value;
    node->next = p->next;
    node->down = down;
    p->next = node;
    down = p;

}

}

跳表SkipList的原理和C实现来自于OenHan

链接为:http://oenhan.com/skiplist-principle