欢迎来到天天文库
浏览记录
ID:15698964
大小:36.63 KB
页数:8页
时间:2018-08-04
《跳表(skiplist)的代码实现》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、跳表(skiplist)的代码实现跳表(skiplist)是一个非常优秀的数据结构,实现简单,插入、删除、查找的复杂度均为O(logN)。LevelDB的核心数据结构是用跳表实现的,redis的sortedset数据结构也是有跳表实现的。其结构如下所示:所有操作均从上向下逐层查找,越上层一次next操作跨度越大。其实现是典型的空间换时间。具体的细节,可参考维基百科http://en.wikipedia.org/wiki/Skip_list 本文作者将redis的sortedset代码进行整理,将跳表部分的实现抽取出来,供参考。skiplist.h1
2、#ifndef__SKIPLIST_H2#define__SKIPLIST_H34#defineSKIPLIST_MAXLEVEL856typedefstructskiplistNode{7doublescore;8structskiplistNode*backward;9structskiplistLevel{10structskiplistNode*forward;11}level[];12}skiplistNode;1314typedefstructskiplist{15structskiplistNode*header,*tail;16un
3、signedlonglength;17intlevel;18}skiplist;1920#endifskiplist.c1#include"skiplist.h"2#include3#include45skiplistNode*slCreateNode(intlevel,doublescore){6skiplistNode*sn=malloc(sizeof(*sn)+level*sizeof(structskiplistLevel));7sn->score=score;8returnsn;9}1011skipl
4、ist*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->level[j].forward=NULL;21}22sl->header->backward=NULL;23sl->tail=NULL;24returnsl;25}26
5、27voidslFreeNode(skiplistNode*sn){28free(sn);29}3031voidslFree(skiplist*sl){32skiplistNode*node=sl->header->level[0].forward,*next;3334free(sl->header);35while(node){36next=node->level[0].forward;37slFreeNode(node);38node=next;39}40free(sl);41}4243intslRandomLevel(void){44intl
6、evel=1;45while((rand()&0xFFFF)<(0.5*0xFFFF))46level+=1;47return(levelheader;55inti,level;56for(i=sl->leve
7、l-1;i>=0;i--){57while(node->level[i].forward&&node->level[i].forward->scorelevel[i].forward;59}60update[i]=node;61}62level=slRandomLevel();63if(level>sl->level){64for(i=sl->level;iheader;66}67sl->level=level;68}69node=slCreateNo
8、de(level,score);70for(i=0;ilevel[i].forwa
此文档下载收益归作者所有