跳表的实现

图示：

//转载
//SkipList
#include <stdlib.h>
#include <stdio.h>
#include<time.h>

#define SKIPLIST_MAXLEVEL 8

typedef struct skiplistNode
{
    int score;
    struct skiplistNode *backward;//prev
    struct skiplistLevel
    {
        struct skiplistNode *forward;//next。
    }level[0];//学习0长度数组的妙用。
}skiplistNode;

typedef struct skiplist
{
    struct skiplistNode *header, *tail;
    unsigned long length;
    int level;
}skiplist;

skiplistNode *slCreateNode(int level, double score) //创建结点。
{
    skiplistNode * sn = malloc(sizeof(*sn) + level*sizeof(struct skiplistLevel));//sizeof(*sn)=8字节（注意结构体对齐）,level*sizeof(struct skiplistLevel)=4*level字节.
    sn->score = score;
    return sn;
}

skiplist *slCreate() //创建表头。
{
    int j;
    skiplist *sl;
    sl = malloc(sizeof(*sl));
    sl->level = 1;
    sl->length = 0;
    sl->header = slCreateNode(SKIPLIST_MAXLEVEL, 0);
    for(j = 0; j < SKIPLIST_MAXLEVEL; j++)
    {
        sl->header->level[j].forward = NULL;
    }
    sl->header->backward = NULL;
    sl->tail = NULL;
    return sl;
}

void slFreeNode(skiplistNode *sn) //释放指针sn所指向结点的内存。
{
    free(sn);
}

void slFree(skiplist *sl)
{
    skiplistNode *node = sl->header->level[0].forward, *next;//即skiplistNode *node,*next; node= sl->header->level[0].forward.
    free(sl->header);
    while(node) //释放掉每个结点。
    {
        next = node->level[0].forward;
        slFreeNode(node);
        node = next;
    }
    free(sl);//释放掉表头。
}

int slRandomLevel(void) //随机产生level.
{
    int level = 1;
   // while((rand()&0xFFFF) < (0.5 * 0xFFFF))
    while(rand()%2)//抛硬币，如果为正面，就继续抛，否则停止。
        level += 1;
    return (level < SKIPLIST_MAXLEVEL) ? level : SKIPLIST_MAXLEVEL;
}

skiplistNode *slInsert(skiplist *sl, int score) //插入结点（双向链表）。
{
    int i, level;
    skiplistNode *update[SKIPLIST_MAXLEVEL];
    skiplistNode *node;
    node = sl->header;
    for ( i = sl->level-1; i >= 0; i--)
    {
        while(node->level[i].forward && node->level[i].forward->score < score)
        {
            node = node->level[i].forward;
        }
        update[i] = node;
    }
    level = slRandomLevel();
    if (level > sl->level)
    {
        for (i = sl->level; i< level ;i++)
        {
            update[i] = sl->header;
        }
        sl->level = level;
    }
    node = slCreateNode(level, score);
    for (i = 0; i < level; i++)
    {
        node->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = node;
    }
    node->backward = (update[0] == sl->header? NULL : update[0]);//跳表的第一个结点的backward为NULL。
    if (node->level[0].forward)
        node->level[0].forward->backward = node;
    else
        sl->tail = node;
    sl->length++;
    return node;
}

void slDeleteNode(skiplist *sl, skiplistNode *x, skiplistNode **update)
{
    int i;
    for (i = 0; i < sl->level; i++)
    {
        if (update[i]->level[i].forward == x)
        {
            update[i]->level[i].forward = x->level[i].forward;
        }
    }
    if (x->level[0].forward)
    {
        x->level[0].forward->backward = x->backward;
    }
    else
    {
        sl->tail = x->backward;
    }

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

int slDelete(skiplist *sl, double score)
{
    skiplistNode *update[SKIPLIST_MAXLEVEL], *node;
    int i;
    node = sl->header;
    for(i = sl->level-1; i >= 0; i--)
    {
        while (node->level[i].forward && node->level[i].forward->score < score)
        {
            node = node->level[i].forward;
        }
        update[i] = node;
    }
    node = node->level[0].forward;
    if (node && score == node->score)
    {
        slDeleteNode(sl, node, update);
        slFreeNode(node);
        return 1;
    }
    else
    {
        return 0;
    }
    return 0;
}

int slSearch(skiplist *sl, double score)//查找。
{
    skiplistNode *node;
    int i;
    node = sl->header;
    for (i = sl->level-1; i >= 0 ;i--)
    {
        while(node->level[i].forward && node->level[i].forward->score < score)
        {
            node = node->level[i].forward;
        }
    }
    node = node->level[0].forward;
    if (node && score == node->score)
    {
        printf("Found %d\n", score);
        return 1;
    }
    else
    {
        printf("Not found %d\n", score);
        return 0;
    }
}

void slPrint(skiplist *sl) //打印。
{
    skiplistNode *node;
    int i;
    for (i = 0; i < SKIPLIST_MAXLEVEL; i++)
    {
        printf("LEVEL[%d]: ", i);
        node = sl->header->level[i].forward;
        while(node)
        {
            printf("%d -> ", node->score);
            node = node->level[i].forward;
        }
        printf("NULL\n");
    }
}