c++实现跳跃表(Skip List)的方法示例

前言

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

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

一个跳表具有以下特征:

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

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

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

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

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

6.Top指针指向最高层的第一个元素。

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

如果是说链表是排序的,并且节点中还存储了指向前面第二个节点的指针的话,那么在查找一个节点时,仅仅需要遍历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)。

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

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

定义每个节点类型:

typedef struct nodeStructure *node;
typedef struct nodeStructure
{
 keyType key; // key值
 valueType value; // value值
 // 向前指针数组,根据该节点层数的
 // 不同指向不同大小的数组
 node forward[1];
};

上面的每个结构体对应着图中的每个节点,如果一个节点是一层的节点的话(如7,12等节点),那么对应的forward将指向一个只含一个元素的数组,以此类推。

定义跳表数据类型:

// 定义跳表数据类型
typedef struct listStructure{
 int level;
 struct nodeStructure * header;
} * list; 

先不看代码先用图来描述一下Skip List构造,插入和删除的过程:

构造Skip List

1、给定一个有序的链表。

2、选择连表中最大和最小的元素,然后从其他元素中按照一定算法(随机)随即选出一些元素,将这些元素组成有序链表。这个新的链表称为一层,原链表称为其下一层。

3、为刚选出的每个元素添加一个指针域,这个指针指向下一层中值同自己相等的元素。Top指针指向该层首元素

4、重复2、3步,直到不再能选择出除最大最小元素以外的元素。

插入过程

例子:插入 119, level = 2

如果 K 大于链表的层数,则要添加新的层。

例子:插入 119, K = 4

删除 21

看到这就很清楚了,上面已经提到所谓的Skip List是每层从它的下一层按照某种规律抽出一些元素,它的操作也很简单,它的操作其实按层来操作链表,基本上是从上往下来操作。

具体的实现如下:

定义数据结构

//
// skiplist_def.h
// test
//
// Created by 杜国超 on 17/9/24.
// Copyright © 2017年 杜国超. All rights reserved.
//

#ifndef skiplist_def_h
#define skiplist_def_h

#define MAX_LEVEL 8
typedef int KeyType;
typedef int ValueType;

//定义节点信息数据结构
template <typename K,typename V>
struct NodeStructure {
 K key;
 V value;
 NodeStructure* forward[1];
};

//定义跳跃表数据结构
template <typename K,typename V>
struct SkipLisStructure{
 int level;
 NodeStructure<K,V>* header;
};

typedef struct NodeStructure<KeyType,ValueType> NodeType;
typedef struct SkipLisStructure<KeyType,ValueType> ListType;

typedef NodeType* Node;
typedef ListType* List;

#define NEW_LEVEL_NODE(level) (Node)malloc(sizeof(NodeType) + (level) * sizeof(Node))

#endif /* skiplist_def_h */

增删查操作实现

//
// skiplist.h
// test
//
// Created by 杜国超 on 17/9/24.
// Copyright © 2017年 杜国超. All rights reserved.
//

#ifndef skiplist_h
#define skiplist_h

#include "skiplist_def.h"

class CSkipList{
public:
 CSkipList();
 ~CSkipList();
public:
 ValueType* Search(const KeyType& key);
 bool Insert(KeyType& key,ValueType& value);
 bool Delete(const KeyType& key,ValueType& value);
 void FreeList();

private:
 int RandomLevel();
private:
 List _skipList;
 int _size;

};

#endif /* skiplist_h */
//
// skiplist.cpp
// test
//
// Created by 杜国超 on 17/9/24.
// Copyright © 2017年 杜国超. All rights reserved.
//

#include "skiplist_def.h"
#include "skiplist.h"
#include <stdlib.h>

CSkipList::CSkipList(){
 _skipList = (List)malloc(sizeof(ListType));
 // 设置跳表的层level,初始的层为0层(数组从0开始)
 _skipList->level = 0;
 _skipList->header = NEW_LEVEL_NODE(MAX_LEVEL);
 // 将header的forward数组清空
 for(int i = 0; i < MAX_LEVEL; ++i)
  _skipList->header->forward[i] = NULL;
 _size = 0;
}

CSkipList::~CSkipList()
{
 FreeList();
}

ValueType* CSkipList::Search(const KeyType& key){
 Node node = _skipList->header;
 Node indexNode = NULL;
 for(int i = _skipList->level - 1; i >= 0; --i){
  while((indexNode = node->forward[i]) && (indexNode->forward[i]->key <= key))
  {
   if (indexNode->key == key)
   {
    return &(indexNode->value);
   }
   node = indexNode;
  }
 }
 return NULL;
}

bool CSkipList::Insert(KeyType& key, ValueType& value)
{
 Node update[MAX_LEVEL];
 int i;
 Node node = _skipList->header;
 Node indexNode = NULL;
 //寻找key所要插入的位置
 for(i = _skipList->level - 1; i >= 0; --i){
  while((indexNode = node->forward[i]) && (indexNode->forward[i]->key < key))
  {
   node = indexNode;
  }
  update[i] = node;
 }
 node = node->forward[0];
 //如果key已经存在
 if(node->key == key){
  node->value = value;
  return false;
 }else{
  //随机生成新结点的层数
  int level = RandomLevel();
  if(level > _skipList->level){
   for (int i = _skipList->level;i < level;++i)
   {
    update[i] = _skipList->header;
   }
   _skipList->level = level;
  }

  //申请新的结点
  Node newNode = NEW_LEVEL_NODE(level);
  newNode->key = key;
  newNode->value = value;

  //调整forward指针
  for(int i = level - 1; i >= 0; --i){
   node = update[i];
   newNode->forward[i] = node->forward[i];
   node->forward[i] = newNode;
  }

  //更新元素数目
  ++_size;
  return true;
 }
}

bool CSkipList::Delete(const KeyType& key,ValueType& value){
 Node update[MAX_LEVEL];
 int i;
 Node node = _skipList->header;
 Node indexNode = NULL;
 //寻找key所要插入的位置
 for(i = _skipList->level - 1; i >= 0; --i){
  while((indexNode = node->forward[i]) && (indexNode->forward[i]->key < key))
  {
   node = indexNode;
  }
  update[i] = node;
 }
 node = node->forward[0];
 //结点不存在
 if(node->key != key){
  return false;
 }else{
  value = node->value;
  //调整指针
  for(i = 0; i < _skipList->level; ++i){
   if(update[i]->forward[i] != node)
    break;
   update[i]->forward[i] = node->forward[i];
  }
  //删除结点
  free(node);
  for(int i = _skipList->level - 1; i >= 0; i--){
   if(_skipList->header->forward[i]==NULL){
    _skipList->level--;
   }
  }
  //更新链表元素数目
  --_size;
  return true;
 }
}

int CSkipList::RandomLevel()
{
 int k = 1;
 while (rand()%2)
 {
  k++;
 }
 k=(k<MAX_LEVEL)?k:MAX_LEVEL;
 return k;
}

void CSkipList::FreeList(){
 Node p = _skipList->header;
 Node q;
 while(p != NULL){
  q = p->forward[0];
  free(p);
  p = q;
 }
 free(p);
 free(_skipList);
 _size = 0;
}

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,如果有疑问大家可以留言交流,谢谢大家对我们的支持。

(0)

相关推荐

  • Java实现跳跃表(skiplist)的简单实例

    跳跃链表是一种随机化数据结构,基于并联的链表,其效率可比拟于二叉查找树(对于大多数操作需要O(log n)平均时间),并且对并发算法友好. 基本上,跳跃列表是对有序的链表增加上附加的前进链接,增加是以随机化的方式进行的,所以在列表中的查找可以快速的跳过部分列表(因此得名).所有操作都以对数随机化的时间进行. 实现原理: 跳跃表的结构是:假如底层有10个节点, 那么底层的上一层理论上就有5个节点,再上一层理论上就有2个或3个节点,再上一层理论上就有1个节点.所以从这里可以看出每一层的节点个数为其下

  • JS实现线性表的顺序表示方法示例【经典数据结构】

    本文实例讲述了JS实现线性表的顺序表示方法.分享给大家供大家参考,具体如下: 线性表的顺序表示指的是用一组地址连接的存储单元依次存储线性表的数据元素.通常称这种存储结构的线性表为顺序表. 顺序表的特点是以元素在计算机内物理位置相邻来表示数据元素之间的逻辑关系.每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数.也就是说只要确定了存储线性表的起始位置,线性表中的任一元素都可以随机存储,所以说,顺序表是一种随机存取的存储结构. 高级语言中的数组与其相似,所以我

  • Smarty简单生成表单元素的方法示例

    本文实例讲述了Smarty简单生成表单元素的方法.分享给大家供大家参考,具体如下: smarty生成表单元素功能实现的原理是:给smarty一个数组,用于生成和显示菜单或选项,另外在传递一个选项的值,用于默认选择的匹配: 示例如下: php文件:index.php <?php include("smarty_inc.php"); $smarty->assign('cust_ids',array(1000,1001,1002,1003)); $smarty->assig

  • JavaScript实现动态添加Form表单元素的方法示例

    本文实例讲述了JavaScript实现动态添加Form表单元素的方法.分享给大家供大家参考,具体如下: 之前写过类似的文章(如:javascript实现的动态添加表单元素input,button等),现在看来比较初级,弄一个高级的简单的 情景: 后台要上传游戏截图,截图数量不确定,因此使用动态添加input节点的方法去实现这个效果 主要用到的函数有: document.getElementById(); objNode.parentNode; objNode.cloneNode(); objNo

  • JPA的多表复杂查询的方法示例

    最近工作中由于要求只能用hibernate+jpa 与数据库进行交互,在简单查询中,jpa继承CrudRepository接口 ,然后利用jpa的方法命名规范进行jpql查询,然而在进行复杂查询时,需要继承JpaSpecificationExecutor接口 利用Specification 进行复杂查询,由于我自己就遇到了这一问题,查了好多资料,虽然有方法,但是都没有一个详细的讲解,以至于知道方法而不能很好的利用jpa复杂查询的方便之处.我将举几个栗子,来详细的说一下我自己在使用jpa多表复杂查

  • MySQL查看数据库表容量大小的方法示例

    本文介绍MySQL查看数据库表容量大小的命令语句,提供完整查询语句及实例,方便大家学习使用. 1.查看所有数据库容量大小 select table_schema as '数据库', sum(table_rows) as '记录数', sum(truncate(data_length/1024/1024, 2)) as '数据容量(MB)', sum(truncate(index_length/1024/1024, 2)) as '索引容量(MB)' from information_schema

  • SQL语句多表联查的实现方法示例

    目录 前言 三表联查 内连接 外连接 附:多表联合查询训练 总结 前言 最近面试实习生,发现一般来说,公司喜欢通过一些 SQL 语句来考察你对数据库的使用熟不熟悉.所以我来总结一下我在面试中遇到多表联查是怎么联查的. 三表联查 首先来说多表联查的一些知识点. 多表是指等于或者多余三个表以上的数据库查询.多表联查的类型有: 内连接:join,inner join 外连接:left join,left outer join,right join,right outer join,union 交叉连接

  • c++实现跳跃表(Skip List)的方法示例

    前言 Skip List是一种随机化的数据结构,基于并联的链表,其效率可比拟于二叉查找树(对于大多数操作需要O(log n)平均时间).基本上,跳跃列表是对有序的链表增加上附加的前进链接,增加是以随机化的方式进行的,所以在列表中的查找可以快速的跳过部分列表(因此得名).所有操作都以对数随机化的时间进行.Skip List可以很好解决有序链表查找特定值的困难. 跳表是平衡树的一种替代的数据结构,但是和红黑树不相同的是,跳表对于树的平衡的实现是基于一种随机化的算法的,跳跃表使用概率均衡技术而不是使用

  • Java实现跳跃表的示例详解

    跳表全称叫做跳跃表,简称跳表,是一个随机化的数据结构,实质就是一种可以进行二分查找的有序链表.跳表在原有的有序列表上面增加多级索引,通过索引来实现快速查找.跳表不仅能提高搜索性能,同时也提高插入和删除的性能,redis中的有序集合set就是用跳表实现的,面试时候也经常会问. 这里我们原始数据个数n=10,以间隔k=2建立索引,则第一层索引10/2=5个,第二层⌈10/2^2⌉=3个,第三层⌈10/2^3⌉=2个,第四层⌈10/2^4⌉=1个.根据上图我们来分析一下,跳表的结构是一棵树(除原始数据

  • 详解Java中跳跃表的原理和实现

    目录 一.跳跃表的引入 二.算法分析 1.时间复杂度 2.空间复杂度 三.跳跃表介绍 四.跳跃表的实现 1.数据结构定义 2.查找 3.插入 4.删除 五.实战 1.代码 2.测试结果 一.跳跃表的引入 对有序顺序表可以采用二分查找,查找的时间复杂度为O (logn),插入.删除的时间复杂度为 O(n ).但是对有序链表不可以采用二分查找,查找.插入和删除的时间复杂度均为O (n). 有序链表如下图所示,若查找 8,则必须从第 1 个节点开始,依次比较 8 次才能查找成功. 如何利用链表的有序性

随机推荐