1、 由很多層結(jié)構(gòu)組成
2、 每一層都是一個(gè)有序的鏈表
3、 最底層(原始鏈表)的鏈表包含所有元素
4、 如果一個(gè)元素出現(xiàn)在 Level i 的鏈表中，則它在 Level i 之下的鏈表也都會(huì)出現(xiàn)。
5、 每個(gè)節(jié)點(diǎn)包含兩個(gè)指針，一個(gè)指向同一鏈表中的下一個(gè)元素，一個(gè)指向下面一層的元素。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <time.h>



#define MAX_LEVEL 15

struct node {
    int val;
    int max_level;
    struct node *forward[MAX_LEVEL];
};

struct skip_list {
    struct node head;
    int max_level;
    int max_level_nodes;
};

void node_init(struct node* node)
{
    memset(node, 0, sizeof(struct node));
}

void skip_list_init(struct skip_list* sl)
{
    node_init(&sl->head);
    sl->max_level = 0;
    sl->max_level_nodes = 0;
}

void random_init()
{
    static bool done = false;

    if (done)
        return;

    srandom(time(NULL)); //設(shè)種子為隨機(jī)的
    done = true;
}

//插入元素獲得層數(shù)，是隨機(jī)產(chǎn)生的
int random_level(void)
{
    int i, level = 1;

    random_init();

    for (i = 1; i < MAX_LEVEL; i++)
        if (random() % 2 == 1) //生成的隨機(jī)數(shù)
            level++;

    return level;
}


void insert(struct skip_list *sl, int val)
{
    int level = random_level();
    struct node *update[MAX_LEVEL]; //用來(lái)更新每層的指針
    struct node *new, *p;
    int i;

    //申請(qǐng)update空間用于保存每層的指針
    new = (struct node*)malloc(sizeof(struct node));
    if (!new)
        return;

    new->max_level = level; //獲取插入元素的隨機(jī)層數(shù)，并更新跳表的最大層數(shù)
    new->val = val; //創(chuàng)建當(dāng)前數(shù)據(jù)節(jié)點(diǎn)

    for ( i = 0; i < MAX_LEVEL; i++)
        update[i] = &sl->head;
    //逐層查詢節(jié)點(diǎn)的
    p = &sl->head;
    for (i = level - 1; i >= 0; i--) 
    {
        //初始化每level層的頭指針
        while(p->forward[i] && p->forward[i]->val < val)
            p = p->forward[i];

        update[i] = p;
    }

    //逐層更新節(jié)點(diǎn)的指針
    for (i = 0; i < level; i++) 
    {
        new->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = new;
    }
    //更新最大層數(shù)
    if (sl->max_level < level) 
    {
        sl->max_level = level;
        sl->max_level_nodes = 1;
    } 
    else if (sl->max_level == level)
        sl->max_level_nodes++;
}

struct node *find(struct skip_list* sl, int val)
{
    struct node *node = &sl->head;
    int i;

    for (i = sl->max_level - 1; i >= 0; i--) {
        while (node->forward[i] && node->forward[i]->val < val)
            node = node->forward[i];
    }

    if (node->forward[0] && node->forward[0]->val == val) {
        return node->forward[0];
    }
    else
        return NULL;
}

void delete(struct skip_list* sl, int val)
{
    struct node *update[MAX_LEVEL]; //用來(lái)更新每層的指針
    struct node *p;
    int i;

    p = &sl->head; //逐層查詢節(jié)點(diǎn)的

    for (i = sl->max_level; i >= 0; i--) 
    {
        //初始化每level層的頭指針
        while (p->forward[i] && p->forward[i]->val < val)
            p = p->forward[i];

        update[i] = p;
    }

    if (p->forward[0] == NULL || p->forward[0]->val != val)
        return;

    //更新level的層數(shù)
    if (p->forward[0]->max_level == sl->max_level)
        sl->max_level_nodes--;

    for (i = sl->max_level-1; i >= 0; i--) 
    {
        if (update[i]->forward[i] && update[i]->forward[i]->val == val)
            update[i]->forward[i] = update[i]->forward[i]->forward[i]; 
    }

    if (sl->max_level_nodes == 0) 
    {

        p = &sl->head;

        for (i = sl->max_level - 2; i >= 0; i--) 
        {
            while (p->forward[i]) 
            {
                sl->max_level_nodes++;
                p = p->forward[i];
            }

            if (sl->max_level_nodes) 
            {
                sl->max_level = i + 1;
                break;
            } else
                sl->max_level = i;
        }
    }
}


void print_sl(struct skip_list* sl)
{
    struct node *node;
    int level;

    // 從低層到最高層開(kāi)始打印
    printf("%d level skip list with %d nodes on top\n",
        sl->max_level, sl->max_level_nodes);

    for (level = sl->max_level - 1; level >= 0; level--) {
        node = &sl->head;
        printf("Level[%02d]:", level);
        while (node->forward[level]) {
            printf("%4d", node->forward[level]->val);
            node = node->forward[level];
        }
        printf("\n");
    }
}

int main(int argc,char **argv)
{
    struct skip_list sl;
    struct node *node = NULL;
    int i;

    skip_list_init(&sl);
    print_sl(&sl);

    for (i = 0; i < 10; i++)
        insert(&sl, i);
    print_sl(&sl);

    node = find(&sl, 8);
    if (node)
        printf("find 8 in sl %d\n", node->val);
    else
        printf("8 not in sl\n");

    for (i = 0; i < 10; i++) {
        delete(&sl, i);
        print_sl(&sl);
    }

    return 0;
}