跳表

相关资料

https://en.wikipedia.org/wiki/Skip_list

https://www.cnblogs.com/xuqiang/archive/2011/05/22/2053516.html
https://www.iteye.com/blog/dsqiu-1705530

In computer science, a skip list is a data structure that allows O(log n) search complexity as well as O(log n) insertion complexity within an ordered sequence of n elements.

A skip list is built in layers. The bottom layer is an ordinary ordered linked list. Each higher layer acts as an "express lane" for the lists below, where an element in layer i appears in layer i+1 with some fixed probability p (two commonly used values for p are 1/2 or 1/4).

/*
 * 跳表（skip list）
 */
#include <stdio.h>
#include <stdlib.h>

#define MAX_LEVEL 10 //最大层数

struct node
{
    int key;
    int value;
    struct node *forward[];
};
struct skiplist
{
    int level;
    struct node *header;
};

struct node *createnode(int level, int key, int value);
struct skiplist *create();
void insert(struct skiplist *sl, int key, int value);
void del(struct skiplist *sl, int key);
void display(struct skiplist *sl);
int randomLevel();

int main()
{
    int i;
    struct skiplist *sl=create();

    for(i = 0; i < 20; i++)
    {
        insert(sl,i,i*2);
    }
    display(sl);
    
    del(sl,4);
    display(sl);

    return 0;
}

// 创建节点
struct node *createnode(int level, int key, int value)
{
    struct node *slnode = (struct node *)malloc(sizeof(struct node)+level*sizeof(struct node *));
    slnode->key = key;
    slnode->value = value;

    return slnode;
}

struct skiplist *create()
{
    int i;
    struct skiplist *sl = (struct skiplist *)malloc(sizeof(struct skiplist));

    sl->level = 1;
    sl->header = createnode(MAX_LEVEL, -1, -1);

    for(i = 0; i < MAX_LEVEL; i++)
    {
        sl->header->forward[i] = NULL;
    }

    return sl;
}

void insert(struct skiplist *sl, int key, int value)
{
    struct node *update[MAX_LEVEL];
    struct node *x;
    int i, level;

    x = sl->header;
    for(i = sl->level-1; i >= 0; i--)
    {
        while(x->forward[i] && x->forward[i]->key < key)
        {
            x = x->forward[i];
        }
        update[i] = x;
    }

    // key不能重复
    if(x->forward[0] && x->forward[0]->key == key)
    {
        return ;
    }
    
    level = randomLevel();
    if(level > sl->level)
    {
        for(i = sl->level; i < level; i++)
        {
            update[i] = sl->header;
        }
        sl->level = level;
    }
    
    x = createnode(level,key,value);
    for(i = 0; i < level; i++)
    {
        x->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = x;
    }
}

void del(struct skiplist *sl, int key)
{
    struct node *update[MAX_LEVEL];
    struct node *x;
    int i;

    x = sl->header;
    for(i = sl->level-1; i >= 0; i--)
    {
        while(x->forward[i] && x->forward[i]->key < key)
        {
            x = x->forward[i];
        }
        update[i] = x;
    }

    x = x->forward[0];
    if(x && x->key == key)
    {
        for(i = 0; i < sl->level; i++)
        {
            if(update[i]->forward[i] == x)
            {
                update[i]->forward[i] = x->forward[i];
            }
        }
        free(x);

        while(sl->level > 1 && sl->header->forward[sl->level-1] == NULL)
        {
            sl->level--;
        }
    }
}

void display(struct skiplist *sl)
{
    struct node *x;
    int i;
    
    for(i = sl->level-1; i >= 0; i--)
    {
        x = sl->header;
        while(x->forward[i])
        {
            printf("%d -> ",x->value);
            x = x->forward[i];
        }
        printf("%d\n",x->value);
    }
    printf("\n");
}

// 随机产生层数
int randomLevel()
{
    int k = 1;

    while(rand()%2) k++;
    k = (k < MAX_LEVEL) ? k : MAX_LEVEL;

    return k;
}