跳表(skiplist)的代码实现

《跳表(skiplist)的代码实现》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、跳表（skiplist）的代码实现跳表（skiplist）是一个非常优秀的数据结构，实现简单，插入、删除、查找的复杂度均为O(logN)。LevelDB的核心数据结构是用跳表实现的，redis的sortedset数据结构也是有跳表实现的。其结构如下所示：所有操作均从上向下逐层查找，越上层一次next操作跨度越大。其实现是典型的空间换时间。具体的细节，可参考维基百科http://en.wikipedia.org/wiki/Skip_list 本文作者将redis的sortedset代码进行整理，将跳表部分的实

2、现抽取出来，供参考。skiplist.h1#ifndef__SKIPLIST_H2#define__SKIPLIST_H34#defineSKIPLIST_MAXLEVEL856typedefstructskiplistNode{7doublescore;8structskiplistNode*backward;9structskiplistLevel{10structskiplistNode*forward;11}level[];12}skiplistNode;1314typedefstructskipl

3、ist{15structskiplistNode*header,*tail;16unsignedlonglength;17intlevel;18}skiplist;1920#endifskiplist.c1#include"skiplist.h"2#include3#include45skiplistNode*slCreateNode(intlevel,doublescore){6skiplistNode*sn=malloc(sizeof(*sn)+level*size

4、of(structskiplistLevel));7sn->score=score;8returnsn;9}1011skiplist*slCreate(void){12intj;13skiplist*sl;1415sl=malloc(sizeof(*sl));16sl->level=1;17sl->length=0;18sl->header=slCreateNode(SKIPLIST_MAXLEVEL,0);19for(j=0;jheader->l

5、evel[j].forward=NULL;21}22sl->header->backward=NULL;23sl->tail=NULL;24returnsl;25}2627voidslFreeNode(skiplistNode*sn){28free(sn);29}3031voidslFree(skiplist*sl){32skiplistNode*node=sl->header->level[0].forward,*next;3334free(sl->header);35while(node){36next

6、=node->level[0].forward;37slFreeNode(node);38node=next;39}40free(sl);41}4243intslRandomLevel(void){44intlevel=1;45while((rand()&0xFFFF)<(0.5*0xFFFF))46level+=1;47return(level

7、sl,doublescore){51skiplistNode*update[SKIPLIST_MAXLEVEL];52skiplistNode*node;5354node=sl->header;55inti,level;56for(i=sl->level-1;i>=0;i--){57while(node->level[i].forward&&node->level[i].forward->scorelevel[i].forward;59}60update[i]=no

8、de;61}62level=slRandomLevel();63if(level>sl->level){64for(i=sl->level;iheader;66}67sl->level=level;68}69node=slCreateNode(level,score);70for(i=0;ilevel[i].forwa