跳表SkipList的原理及实现

所需积分/C币:6 2019-07-02 17:16:58 511KB PDF
179
收藏 收藏
举报

跳表是由William Pugh发明。他在 Communications of the ACM June 1990, 33(6) 668-676 发表了Skip lists: a probabilistic alternative to balanced trees,在该论文中详 细解释了跳表的数据结构和插入删除操作。
上面的每个结构体对应着图中的每个节点,如果一个节点是一层的节点的话(如7,12等节 点),那么对应的 forward将指向一个只含一个元素的数组,以此类推。 定义跳表数据类型: ∥/定义跳表数据类型 typedef struct listStructuref nt level; maximum level of the list (1 more than the number of levels in the list)*/ struct node Structure header; / pointer to header * 跳表数据类型中包含了维护跳表的必要信息,leve表明跳表的层数, header如下所示: NIL 264 sheader 定义辅助变量: 定义上图中的NL变量: node n|L; #define maxnumberoflevels 16 #define maxlevel maxNumberofLevels-1) 定义辅助方法: / new Nodeoflevel生成一个 destructure结构体,同时生成个node*数组指针 #define new node ofLevel(node)malloc(sizeof(struct node structure)+ ()* sizeof(node为) 好的基本的数据结构定义已经完成,接下来来分析对于跳表的一个操作。 <4>跳表的代码实现分析 4.1初始化 初始化的过程很简单,仅仅是生成下图中红线区域内的部分,也就是跳表的基础结构: 6 N正 anNum占 erOfLe we ls list newListo int I ∥/申请it类型大小的内存 I =(ist)malloc(sizeof (struct liststructure)) ∥/设置跳表的层leve,初始的层为0层(数组从0开始 >level =0 ∥/生成 header部分 1->header new ofLevel(MaxNumberofLevels) ∥/将 header的 forward数组清空 for(i=0; i< MaxNumberofLevels; i ++)l->header->forward[]= nil return (; 4.2插入操作 由于跳表数据结构整体上是有序的,所以在插入时,需要首先查找到合适的位置,然后就是 修改指针(和链表中操作类似),然后更新跳表的leve变量。 Seareh palh 1.酉书合运的插入位置 update[i] formard[i] update数组内容 N 回四画画国国 original list, 17 to be inserted 2更新节点的和跳表的lev NIL 25 19-2 list after insertion, updated pointers in gre boolean insert(l, key, value) register list I register key Type key register value l ype valuei register int k ∥/使用了 update数组 node update[MaxNumberOfLevels] register node p, q: p=l->header; k=->level 大★大大大大太大k大大大大大大大太大 1步 大★大大大大太太大大大大★大大大大x大 do ∥/查找插入位置 while(q= p->forward[k], q->key< key) /设置 update数组 update[k]= p } While(-k>=0);//对于每一层进行遍历 ∥/这里已经查找到了合适的位置,并且 update数组已经 ∥/填充好了元素 if (q->key = key) g->value= value return(false) ∥/随机生成一个层数 k= randomLevelo if k>|->level) /如果新生成的层数比跳表的层数大的话 〃增加整个跳表的层数 K=++->level. ∥/在 update数组中将新添加的层指向> header update[k]=1->header 体*大*大大2步 大;大大大大大大大大大大古大大大大大大大大 ∥/生成层数个节点数目 q= new NodeofLevel(k) g->key key g->value value ∥/更新两个指针域 do p =update[k] ->forward[k]=p->forward[k] p->forward[k]= q: I while(k>=0) ∥/如果程序运行到这里,程序已经插入了该节点 return(true); 43删除某个节点 和插入是相同的,首先查找需要删除的节点,如果找到了该节点的话,那么只需要更新指针 域,如果跳表的 level需要更新的话,进行更新 1.百先查找需要删喉的节点17井设置 update数组 6 NIL 9 2維护跳专的据构 Search vath 指的维护和跳evl的维拍 NIL boolean delete(l, key) register list I; register keyType key register int k, m ∥/生成一个辅助数组 update node update[MaxNumberofLevels register node p, q p=l->header >eve ∥/这里和查找部分类似,最终 update中包含的是 ∥/指向该节点对应层的前驱节点 do while(q= p->forward[], q->key key) update[k]=p: f while(-k>=0) ∥/如果找到了该节点,才进行删除的动作 if (q->key == key ∥/指针运算 for(k=0; k<=m &&(p=update[])->forward[k]==g: k++) ∥/这里可能修改|-> header-> forward数组的值的 p->forward[k]=q-forward[k] ∥/释放实际内存 free( q) ∥/如果删除的是最大层的节点,那么需要重新维护跳表的 /层数 Tlevel while(l->header ->forward[m]== nil &&m>0) 1->level= m return(true) else ∥/没有找到该节点,不进行删除动作 return(false) 4.4查找 查找操作其实已经在插入和删除过程中包含,比较简单,可以参考源代码。 ≤5>.论文,代码下载及参考资料 Skiplist论文 /Files/xuqiang/skipLists. rar 增加跳表c#实现代码2011-5-29下午 上面给岀的数据结构的模型是直接按照跳表的模型得到的,另外还有一种数据结构的模型 跳表节点类型,每个跳表类型中仅仅存储了左侧的节点和下面的节点: skiplistNode<TKey, Tvalue> Generic Class E Fields s downNode: SkipListNode< TKey, Tvalue> s rightNode SkipListNode<TKey, Tvalue> 1 thisValue: TValue E Properties Ear Down I get; set; ) SkipListNode-TKey, TValue e Key i get; set; 1: TKey Ho Right( get; set; ): SkipList Node< TKey, TValue value i get; set; ) Tvalue Methods G Skip ListNode (TKey key, Tvalue val) 我们现在来看对于这种模型的操作代码 1.初始化完成了如下的操作: SkipList Node<TKey, Tvalue> maxLevell Right+ ta114 Downt 2.插入操作:和上面介绍的插入操作是类似的,首先查找到插入的位置,生成 update数 组,然后随机生成一个 clevel,然后修改指针。 3.删除操作:和上面介绍的删除操作是类似的,查找到需要删除的节点,如果查找不到, 抛出异常,如果査找到的需要删除的节点的话,修改指针,释放删除节点的內存

...展开详情
试读 9P 跳表SkipList的原理及实现
立即下载
限时抽奖 低至0.43元/次
身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 分享王者

关注 私信
上传资源赚钱or赚积分
最新推荐
跳表SkipList的原理及实现 6积分/C币 立即下载
1/9
跳表SkipList的原理及实现第1页
跳表SkipList的原理及实现第2页

试读结束, 可继续读1页

6积分/C币 立即下载