跳表 （Skip List） C++ 实现

2024-04-12 01:58
文章标签 c++ 实现 list skip 跳表

本文主要是介绍跳表 （Skip List） C++ 实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

跳表 （Skip List） C++ 实现


跳表原理
跳表 c++ 实现
SkipNode
SkipList
随机层数
结点最大层数
基本操作
打印
主函数
输出结果
在学习 C++ 中的过程中，找个算法作为练习。
仅供参考。

跳表原理


跳表原理讲解请参考 https://lotabout.me/2018/skip-list/
为了节约时间，这里只是简单说明，原文如上。

跳表(skip list) 对标的是平衡树(AVL Tree)，是一种 插入/删除/搜索 都是 O ( l o g n ) O(log n)O(logn) 的数据结构。它最大的优势是原理简单、容易实现、方便扩展、效率更高。因此在一些热门的项目里用来替代平衡树，如 redis, leveldb 等。

跳表顾名思义就是跳跃的表格，理解起来其实就是跳着插入或者搜索。具体什么意思呢，其实就像是二分搜索一样，每次都将数组分成两点分，先定位搜索或者插入的数据在哪一部分，就可以节约搜索的时间。跳表其实是一样的原理，即建立多层索引（多层链表）。如果每次都是以二等分来建立索引的话，即如下图所示：

在这里插入图片描述

但是上述结构是“静态”的，即我们先拥有了一个链表，再在之上建了多层的索引。但是在实际使用中，我们的链表是通过多次插入/删除形成的，换句话说是“动态”的。上述的结构要求上层相邻节点与对应下层节点间的个数比是 1:2，随意插入/删除一个节点，这个要求就被被破坏了。

因此跳表（skip list）表示，我们就不强制要求 1:2 了，一个节点要不要被索引，建几层的索引，都在节点插入时由抛硬币决定。当然，虽然索引的节点、索引的层数是随机的，为了保证搜索的效率，要大致保证每层的节点数目与上节的结构相当。下面是一个随机生成的跳表：

在这里插入图片描述
对于上述随机跳表而言，每次插入一个新结点的时候，该结点的索引层数是抛硬币决定的，即由随机算法决定的。

当然为了防止运气太好，层数太高，我们一般会设置一个最大的层数 M a x L e v e l MaxLevelMaxLevel. 一般 M a x L e v e l = l o g 1 / p n MaxLevel=log_{1/p}nMaxLevel=log 
1/p
​    
 n。 p pp 为概率。

跳表 c++ 实现
思路：

首先创建一个结点的结构体，结构体里包含 一个键值对，key 用来建立索引，而 value 则用于存储真正的值；指向下一个结点的指针 next，以及标志每个结点索引层数的参数 level. next 指针是一个数组，用于存储结点在所有层数上的下一个结点。 例如， 上述图中结点6的next指针为{NIL, 25, 9, 7}.
创建class skipList, 包含头结点，尾结点，list 的最大层数，随机层数方法，以及一些列操作。
头结点和尾节点分别为整型的最小值和最大值，并在初始化时让所有层数上的头结点都指向尾节点。
操作包含插入，查找，删除。
SkipNode
为了可以适用于任何类型的value， 这里用了 template

template<typename T>
struct SkipNode
{int key;T value;vector<SkipNode*> next;    SkipNode(int k, T v, int level);
};



//构造函数，初始化

template<typename T> SkipNode<T>::SkipNode(int k, T v, int level) : key(k), value(v)
{for (int i = 0; i < level; i++){next.push_back(nullptr);}
}


SkipList

template<class T>
class SkipList
{public://头结点SkipNode<T>* head;//列表最大层数int maxLevel;//整型的最小值和最大值const int minInt = numeric_limits<int>::min();const int maxInt = numeric_limits<int>::max();public://构造函数SkipList(int maxLevel, T iniValue);//析构函数~SkipList();//随机层数方法int randomLevel();//插入, 查找， 删除SkipNode<T>* insert(int k, T v);SkipNode<T>* find(int k);SkipNode<T>* deleteNode(int k);//打印void printNode();private://尾节点SkipNode<T>* tail;//找到当前列表或者node的最大层数int nodeLevel(vector<SkipNode<T>*> p);
};//初始化
template<class T> SkipList<T>::SkipList(int maxLevel, T iniValue): maxLevel(maxLevel)
{//初始化头结点和尾节点为整型最小值和最大值head = new SkipNode<T>(minInt, iniValue, maxLevel);tail = new SkipNode<T>(maxInt, iniValue, maxLevel);//所有层数上的头结点指向尾节点for (int i = 0; i < maxLevel; i++){head->next[i] = tail;}
}template<class T> SkipList<T>::~SkipList()
{delete head;delete tail;
}

随机层数


用 time 作为种子来获取（0，1）的随机值。 level ++ 直到随机值为 0 或者超过最大层数。

template<class T> int SkipList<T>::randomLevel()
{int random_level = 1;int seed = time(NULL);static default_random_engine e(seed);static uniform_int_distribution<int> u(0, 1);while (u(e) && random_level < maxLevel){random_level++;}return random_level;
}


结点最大层数


返回当前node的最大层数，最小值为 1.

template<class T> int SkipList<T>::nodeLevel(vector<SkipNode<T>*> next)
{int node_level = 0;if (next[0]->key == maxInt){return node_level;}for (int i = 0; i < next.size(); i++){if (next[i] != nullptr && next[i]->key != maxInt){node_level++;}else{break;}}return node_level;
}



基本操作

/*插入：
1）首先用查找函数来判断该结点是否已经存在，如果存在，则更新该结点的值
2）获取新节点的随机层数
3）找到合适的插入位置
4）插入，并调整每层前后node的指针*/
template<class T> SkipNode<T>* SkipList<T>::insert(int k, T v)
{int x_level = randomLevel();SkipNode<T>* new_node = nullptr;SkipNode<T>* tmp = head;new_node = find(k);if (new_node) {new_node->value = v;cout << "\nThis node " << k << " has already existed. And its value has been updated to " << v << endl;return head;}cout << "key: " << k << ", randomLevel: " << x_level << endl;new_node = new SkipNode<T>(k, v, x_level);for (int i = (x_level - 1); i > -1; i--){while (tmp->next[i] != nullptr && tmp->next[i]->key < k){tmp = tmp->next[i];}new_node->next[i] = tmp->next[i];tmp->next[i] = new_node;}return head;
}/*查找：
由于列表有序，首先找到小于该结点的最近的结点，如果下一个结点等于目标结点，则返回该节点。
如果不是，则返回空*/
template<class T> SkipNode<T>* SkipList<T>::find(int x)
{SkipNode<T>* tmp = head;int current_level = nodeLevel(tmp->next);for (int i = (current_level - 1); i > -1; i--){while (tmp->next[i] != nullptr && tmp->next[i]->key < x){tmp = tmp->next[i];}}tmp = tmp->next[0];if (tmp->key == x){cout << "\nThis key " << x << " has been found\n";return tmp;}else{//cout << " \nThis key " << x << " doesn't exit\n";return nullptr;}
}/*删除：
1) 用 find(x) 方法判断该结点是否存在. 如果不存在，则返回当前list, 并告知该结点不存在。
2) 找到小于该结点的最近的结点。
3) 更改该节点每层的前面的结点的指针。*/
template<class T> SkipNode<T>* SkipList<T>::deleteNode(int x)
{SkipNode<T>* node = find(x);if (!node){cout << "\n This deleting node" << x << "doesn't exist" << endl;return head;}else{SkipNode<T>* tmp = head;int x_level = node->next.size();cout << "\nThe deleting node " << x << "'s level is " << x_level << endl;for (int i = (x_level - 1); i > -1; i--){while (tmp->next[i] != nullptr && tmp->next[i]->key < x){tmp = tmp->next[i];}tmp->next[i] = tmp->next[i]->next[i];cout << "This node " << x << " has been deleted from level " << i << endl;}return head;}
}


打印

// 分层打印
template<class T> void SkipList<T>::printNode()
{for (int i = 0; i < maxLevel; i++){SkipNode<T>* tmp = head;int lineLen = 1;if (tmp->next[i]->key != maxInt){cout << "\n";cout << "This is level " << i << ":" << endl;cout << "{";while (tmp->next[i] != nullptr && tmp->next[i]->key != maxInt){cout << "(" << "Key: " << tmp->next[i]->key << ", ";cout << "Value: " << tmp->next[i]->value << ")";tmp = tmp->next[i];if (tmp->next[i] != nullptr && tmp->next[i]->key != maxInt){cout << ", ";}                if (lineLen++ % 5 == 0) cout << "\n";}cout << "}" << "\n";}}
}


主函数

int main()
{int maxLevel = 6;SkipList<int> l(maxLevel, 0);for (size_t i = 0; i < 50; i++){l.insert(i, i);}    l.printNode();


输出结果

This is level 0:
{(Key: 0, Value: 0), (Key: 1, Value: 1), (Key: 2, Value: 2), (Key: 3, Value: 3), (Key: 4, Value: 4),
(Key: 5, Value: 5), (Key: 6, Value: 6), (Key: 7, Value: 7), (Key: 8, Value: 8), (Key: 9, Value: 9),
(Key: 10, Value: 10), (Key: 11, Value: 11), (Key: 12, Value: 12), (Key: 13, Value: 13), (Key: 14, Value: 14),
(Key: 15, Value: 15), (Key: 16, Value: 16), (Key: 17, Value: 17), (Key: 18, Value: 18), (Key: 19, Value: 19),
(Key: 20, Value: 20), (Key: 21, Value: 21), (Key: 22, Value: 22), (Key: 23, Value: 23), (Key: 24, Value: 24),
(Key: 25, Value: 25), (Key: 26, Value: 26), (Key: 27, Value: 27), (Key: 28, Value: 28), (Key: 29, Value: 29),
(Key: 30, Value: 30), (Key: 31, Value: 31), (Key: 32, Value: 32), (Key: 33, Value: 33), (Key: 34, Value: 34),
(Key: 35, Value: 35), (Key: 36, Value: 36), (Key: 37, Value: 37), (Key: 38, Value: 38), (Key: 39, Value: 39),
(Key: 40, Value: 40), (Key: 41, Value: 41), (Key: 42, Value: 42), (Key: 43, Value: 43), (Key: 44, Value: 44),
(Key: 45, Value: 45), (Key: 46, Value: 46), (Key: 47, Value: 47), (Key: 48, Value: 48), (Key: 49, Value: 49)
}This is level 1:
{(Key: 0, Value: 0), (Key: 4, Value: 4), (Key: 6, Value: 6), (Key: 10, Value: 10), (Key: 14, Value: 14),
(Key: 15, Value: 15), (Key: 17, Value: 17), (Key: 21, Value: 21), (Key: 22, Value: 22), (Key: 23, Value: 23),
(Key: 28, Value: 28), (Key: 30, Value: 30), (Key: 34, Value: 34), (Key: 35, Value: 35), (Key: 36, Value: 36),
(Key: 38, Value: 38), (Key: 39, Value: 39), (Key: 42, Value: 42), (Key: 46, Value: 46), (Key: 48, Value: 48),
(Key: 49, Value: 49)}This is level 2:
{(Key: 4, Value: 4), (Key: 21, Value: 21), (Key: 23, Value: 23), (Key: 34, Value: 34), (Key: 35, Value: 35),
(Key: 39, Value: 39), (Key: 42, Value: 42), (Key: 46, Value: 46)}This is level 3:
{(Key: 4, Value: 4), (Key: 46, Value: 46)}This is level 4:
{(Key: 46, Value: 46)}


————————————————
版权声明：本文为CSDN博主「啦啦啦啦啦~~」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_44387066/article/details/90766034

这篇关于跳表 （Skip List） C++ 实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/895795。

相关文章

关于C++中的虚拟继承的一些总结（虚拟继承，覆盖，派生，隐藏）

关于C++中的虚拟继承的一些总结（虚拟继承，覆盖，派生，隐藏）

1.为什么要引入虚拟继承 虚拟继承是多重继承中特有的概念。虚拟基类是为解决多重继承而出现的。如:类D继承自类B1、B2，而类B1、B2都继承自类A，因此在类D中两次出现类A中的变量和函数。为了节省内存空间，可以将B1、B2对A的继承定义为虚拟继承，而A就成了虚拟基类。实现的代码如下： class A class B1:public virtual A; class B2:pu
阅读更多...
C++对象布局及多态实现探索之内存布局（整理的很多链接）

C++对象布局及多态实现探索之内存布局（整理的很多链接）

本文通过观察对象的内存布局，跟踪函数调用的汇编代码。分析了C++对象内存的布局情况，虚函数的执行方式，以及虚继承，等等 文章链接：http://dev.yesky.com/254/2191254.shtml      论C/C++函数间动态内存的传递 (2005-07-30)   当你涉及到C/C++的核心编程的时候，你会无止境地与内存管理打交道。 文章链接：http://dev.yesky
阅读更多...
C++的模板(八)：子系统

C++的模板(八)：子系统

平常所见的大部分模板代码，模板所传的参数类型，到了模板里面，或实例化为对象，或嵌入模板内部结构中，或在模板内又派生了子类。不管怎样，最终他们在模板内，直接或间接，都实例化成对象了。 但这不是唯一的用法。试想一下。如果在模板内限制调用参数类型的构造函数会发生什么?参数类的对象在模板内无法构造。他们只能从模板的成员函数传入。模板不保存这些对象或者只保存他们的指针。因为构造函数被分离，这些指针在模板外
阅读更多...
C++工程编译链接错误汇总VisualStudio

C++工程编译链接错误汇总VisualStudio

目录 一些小的知识点 make工具 可以使用windows下的事件查看器崩溃的地方 dumpbin工具查看dll是32位还是64位的 _MSC_VER .cc 和.cpp 【VC++目录中的包含目录】 vs 【C/C++常规中的附加包含目录】——头文件所在目录如何怎么添加，添加了以后搜索头文件就会到这些个路径下搜索了 include<> 和 include"" WinMain 和
阅读更多...
C/C++的编译和链接过程

C/C++的编译和链接过程

目录 从源文件生成可执行文件（书中第2章） 1.Preprocessing预处理——预处理器cpp 2.Compilation编译——编译器cll ps：vs中优化选项设置 3.Assembly汇编——汇编器as ps：vs中汇编输出文件设置 4.Linking链接——链接器ld 符号 模块，库 链接过程——链接器 链接过程 1.简单链接的例子 2.链接过程 3.地址和
阅读更多...
C++必修：模版的入门到实践

C++必修：模版的入门到实践

✨✨ 欢迎大家来到贝蒂大讲堂✨✨ 🎈🎈养成好习惯，先赞后看哦~🎈🎈 所属专栏：C++学习 贝蒂的主页：Betty’s blog 1. 泛型编程 首先让我们来思考一个问题，如何实现一个交换函数？ void swap(int& x, int& y){int tmp = x;x = y;y = tmp;} 相信大家很快就能写出上面这段代码，但是如果要求这个交换函数支持字符型
阅读更多...
通过SSH隧道实现通过远程服务器上外网

通过SSH隧道实现通过远程服务器上外网

搭建隧道 autossh -M 0 -f -D 1080 -C -N user1@remotehost##验证隧道是否生效，查看1080端口是否启动netstat -tuln | grep 1080## 测试ssh 隧道是否生效curl -x socks5h://127.0.0.1:1080 -I http://www.github.com 将autossh 设置为服务，隧道开机启动
阅读更多...
时序预测 | MATLAB实现LSTM时间序列未来多步预测-递归预测

时序预测 | MATLAB实现LSTM时间序列未来多步预测-递归预测

时序预测 | MATLAB实现LSTM时间序列未来多步预测-递归预测 目录 时序预测 | MATLAB实现LSTM时间序列未来多步预测-递归预测基本介绍程序设计参考资料 基本介绍 MATLAB实现LSTM时间序列未来多步预测-递归预测。LSTM是一种含有LSTM区块（blocks）或其他的一种类神经网络，文献或其他资料中LSTM区块可能被描述成智能网络单元，因为
阅读更多...
C++入门01

C++入门01

1、.h和.cpp 源文件 (.cpp)源文件是C++程序的实际实现代码文件，其中包含了具体的函数和类的定义、实现以及其他相关的代码。主要特点如下：实现代码: 源文件中包含了函数、类的具体实现代码，用于实现程序的功能。编译单元: 源文件通常是一个编译单元，即单独编译的基本单位。每个源文件都会经过编译器的处理，生成对应的目标文件。包含头文件: 源文件可以通过#include指令引入头文件，以使
阅读更多...
vue项目集成CanvasEditor实现Word在线编辑器

vue项目集成CanvasEditor实现Word在线编辑器

CanvasEditor实现Word在线编辑器 官网文档：https://hufe.club/canvas-editor-docs/guide/schema.html 源码地址：https://github.com/Hufe921/canvas-editor 前提声明： 由于CanvasEditor目前不支持vue、react 等框架开箱即用版，所以需要我们去Git下载源码，拿到其中两个主
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2