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;
}

总结

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

# c  # list  # skip  # skiplist实现排行榜  # c++容器list、vector、map、set区别与用法详解  # python调用c++ ctype list传数组或者返回数组的方法  # C++中list的使用方法及常用list操作总结  # C++中 STL list详解及简单实例  # C++ 关于MFC List Control 控件的总结  # C++模拟实现list功能  # 链表  # 数据结构  # 是一个  # 跳过  # 遍历  # 层数  # 下一层  # 随机化  # 所要  # 的是  # 都是  # 很好  # 是一种  # 第一个  # 就能  # 出现在  # 是从  # 有一定  # 以此类推  # 所需 

相关文章： 浅谈Javascript中的Label语句  简历在线制作网站免费,免费下载个人简历的网站是哪些？  广东专业制作网站有哪些,广东省能源集团有限公司官网？  如何快速搭建高效服务器建站系统？  如何正确下载安装西数主机建站助手？  制作网站公司那家好,网络公司是做什么的？  网页设计与网站制作内容,怎样注册网站？  建站主机是否等同于虚拟主机？  Avalonia如何实现跨窗口通信 Avalonia窗口间数据传递  如何在Golang中指定模块版本_使用go.mod控制版本号  非常酷的网站设计制作软件,酷培ai教育官方网站？  上海网站制作开发公司,上海买房比较好的网站有哪些？  极客网站有哪些,DoNews、36氪、爱范儿、虎嗅、雷锋网、极客公园这些互联网媒体网站有什么差异？  整人网站在线制作软件,整蛊网站退不出去必须要打我是白痴才能出去？  建站之星微信建站一键生成小程序+多端营销系统  建站之星会员如何解锁更多建站功能？  建站之星上传入口如何快速找到？  制作网站的基本流程,设计网站的软件是什么？  如何选择网络建站服务器？高效建站必看指南  小米网站链接制作教程,请问miui新增网页链接调用服务有什么用啊？  网站制作价目表怎么做,珍爱网婚介费用多少？  如何用VPS主机快速搭建个人网站？  学校免费自助建站系统：智能生成+拖拽设计+多端适配  高端企业智能建站程序：SEO优化与响应式模板定制开发  如何用5美元大硬盘VPS安全高效搭建个人网站？  建站主机选择指南：服务器配置与SEO优化实战技巧  c# Task.ConfigureAwait(true) 在什么场景下是必须的  做企业网站制作流程,企业网站制作基本流程有哪些？  山东网站制作公司有哪些,山东大源集团官网？  SAX解析器是什么，它与DOM在处理大型XML文件时有何不同？  相亲简历制作网站推荐大全,新相亲大会主持人小萍萍资料？  如何高效利用亚马逊云主机搭建企业网站？  c++23 std::expected怎么用 c++优雅处理函数错误返回【详解】  贸易公司网站制作流程,出口贸易网站设计怎么做？  建站主机与虚拟主机有何区别？如何选择最优方案？  c# 在高并发场景下，委托和接口调用的性能对比  南京做网站制作公司,南京哈发网络有限公司，公司怎么样，做网页美工DIV+CSS待遇怎么样？  如何使用Golang安装API文档生成工具_快速生成接口文档  如何在云主机上快速搭建网站？  独立制作一个网站多少钱,建立网站需要花多少钱？  css网站制作参考文献有哪些,易聊怎么注册？  如何构建满足综合性能需求的优质建站方案？  广州网站制作的公司,现在专门做网站的公司有没有哪几家是比较好的，性价比高，模板也多的？  如何通过服务器快速搭建网站？完整步骤解析  潍坊网站制作公司有哪些,潍坊哪家招聘网站好？  西安专业网站制作公司有哪些,陕西省建行官方网站？  建站之星后台管理如何实现高效配置？  大学网站设计制作软件有哪些,如何将网站制作成自己app？  如何基于云服务器快速搭建网站及云盘系统？  如何配置WinSCP新建站点的密钥验证步骤？