c++怎么实现跳跃表的方法示

这篇文章主要介绍c++怎么实现跳跃表的方法示,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!

<强>前言

跳跃表是一种随机化的数据结构,基于并联的链表,其效率可比拟于二叉查找树(对于大多数操作需要O (log n)平均时间)。基本上,跳跃列表是对有序的链表增加上附加的前进链接,增加是以随机化的方式进行的,所以在列表中的查找可以快速的跳过部分列表(因此得名)。所有操作都以对数随机化的时间进行.Skip列表可以很好解决有序链表查找特定值的困难。

跳表是平衡树的一种替代的数据结构,但是和红黑树不相同的是,跳表对于树的平衡的实现是基于一种随机化的算法的,跳跃表使用概率均衡技术而不是使用强制性均衡,因此,对于插入和删除结点比传统上的平衡树算法更为简洁高效。

<强>一个跳表具有以下特征:

,,,,,1 .一个跳表应该有几个层(高度)组成;

,,,,,2 .跳表的第一层包含所有的元素;

,,,,,3 .每一层都是一个有序的链表;

,,,,,4 .如果元素x出现在第层,则所有比我小的层都包含x;

,,,,,5 .我第层的元素通过一个向下指针指向下一层拥有相同值的元素;

,,,,,6.顶级指针指向最高层的第一个元素。

下面来研究一下跳表的核心思想:先从链表开始,如果是一个简单的链表,那么我们知道在链表中查找一个元素我的话,需要将整个链表遍历一次。

如果是说链表是排序的,并且节点中还存储了指向前面第二个节点的指针的话,那么在查找一个节点时,仅仅需要遍历N/2个节点即可。

如上图所示,是一个即为简单的跳跃表。传统意义的单链表是一个线性结构,向有序的链表中插入一个节点需要O (N)的时间,查找操作需要O (N)的时间。如果我们使用上图的跳跃表,就可以减少查找所需时间为O (N/2),因为我们可以先通过每个节点的最上面的指针先进行查找,这样子就能跳过一半的节点。比如我们想查找19日首先和6比较,大6之于后,在和9进行比较,然后在和12进行比较……最后比较到21岁的时候,发现21大于19日说明查找的点在17日和21日之间,从这个过程中,我们可以看的出,查找的时候跳过了3、7、12等点,因此查找的复杂度为O (N/2)。

当然上面只是最简单的就是跳跃表,真正的跳表每一个结点不单单只包含指向下一个结点的指针,可能包含很多个指向后续结点的指针,这样就可以跳过一些不必要的结点,从而加快查找,删除等操作。对于一个链表内每一个结点包含多少个指向后续元素的指针,这个过程是通过一个随机函数生成器得到,就是通过随机生成一个结点中指向后续结点的指针数目。

通过上面的跳表的很容易设计这样的数据结构:

定义每个节点类型: