跳表(skiplist)的代码实现

跳表(skiplist)的代码实现

编程入门hacker2018-01-16 8:23:269232A+A-

跳表(skiplist)是一个非常优秀的数据结构,实现简单,插入、删除、查找的复杂度均为O(logN)。LevelDB的核心数据结构是用跳表实现的,redis的sorted set数据结构也是有跳表实现的。


其结构如下所示:




所有操作均从上向下逐层查找,越上层一次next操作跨度越大。其实现是典型的空间换时间。


具体的细节,可参考维基百科http://en.wikipedia.org/wiki/Skip_list


本文作者将redis的sorted set代码进行整理,将跳表部分的实现抽取出来,供参考。


skiplist.h


#ifndef __SKIPLIST_H

#define __SKIPLIST_H


#define SKIPLIST_MAXLEVEL 8


typedef struct skiplistNode {

    double score;

    struct skiplistNode *backward;

    struct skiplistLevel {

        struct skiplistNode *forward;

    }level[];

}skiplistNode;


typedef struct skiplist {

    struct skiplistNode *header, *tail;

    unsigned long length;

    int level;

}skiplist;


#endif


skiplist.c


#include "skiplist.h"

#include <stdlib.h>

#include <stdio.h>


skiplistNode *slCreateNode(int level, double score) {

    skiplistNode * sn = malloc(sizeof(*sn) + level*sizeof(struct skiplistLevel));

    sn->score = score;

    return sn;

}


skiplist *slCreate(void) {

    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) {

    free(sn);

}


void slFree(skiplist *sl) {

    skiplistNode *node = sl->header->level[0].forward, *next;


    free(sl->header);

    while(node) {

        next = node->level[0].forward;

        slFreeNode(node);

        node = next;

    }

    free(sl);

}


int slRandomLevel(void) {

    int level = 1;

    while((rand()&0xFFFF) < (0.5 * 0xFFFF)) 

        level += 1;

    return (level < SKIPLIST_MAXLEVEL) ? level : SKIPLIST_MAXLEVEL;

}


skiplistNode *slInsert(skiplist *sl, double score) {

    skiplistNode *update[SKIPLIST_MAXLEVEL];

    skiplistNode *node;


    node = sl->header;

    int i, level;

    for ( i = sl->level-1; i >= 0; i--) {

        while(node->level.forward && node->level.forward->score < score


点击这里复制本文地址 以上内容由黑资讯整理呈现,请务必在转载分享时注明本文地址!如对内容有疑问,请联系我们,谢谢!
  • 2条评论
  • 青迟语酌2022-06-03 09:42:03
  • 1;    sl->length = 0;    sl->header = slCreateNode(SKIPLIST_MAXLEVEL
  • 忿咬千夜2022-06-03 06:45:51
  • ->level.forward->score < score

支持Ctrl+Enter提交

黑资讯 © All Rights Reserved.  
Copyright Copyright 2015-2020 黑资讯
滇ICP备19002590号-1
Powered by 黑客资讯 Themes by 如有不合适之处联系我们
网站地图| 发展历程| 留言建议| 网站管理