跳表SkipList的原理及实现跳表是由William Pugh发明。他在 Communicatio

文件名称: 跳表SkipList的原理及实现

所属分类: Java

开发工具:

文件大小: 511kb

下载次数: 0

上传时间: 2019-07-02

提供者: aba****

下载 (511kb)

不能下载？报告错误

详细说明：跳表是由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 Generic Class E Fields s downNode: SkipListNode< TKey, Tvalue> s rightNode SkipListNode 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 maxLevell Right+ ta114 Downt 2.插入操作:和上面介绍的插入操作是类似的,首先查找到插入的位置,生成 update数组,然后随机生成一个 clevel,然后修改指针。 3.删除操作:和上面介绍的删除操作是类似的,查找到需要删除的节点,如果查找不到, 抛出异常,如果査找到的需要删除的节点的话,修改指针,释放删除节点的內存

(系统自动生成,下载前可以参看下载内容)