跳表(skiplist)的代码实现

跳表(skiplist)的代码实现

ID:1941108

大小:36.63 KB

页数:8页

时间:2017-11-13

跳表(skiplist)的代码实现_第1页
跳表(skiplist)的代码实现_第2页
跳表(skiplist)的代码实现_第3页
跳表(skiplist)的代码实现_第4页
跳表(skiplist)的代码实现_第5页
资源描述:

《跳表(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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。