数据结构:跳表实现(C++)

在这里插入图片描述

个人主页 : 个人主页
个人专栏 : 《数据结构》 《C语言》《C++》《Linux》《网络》 《redis学习笔记》

文章目录

  • 前言
  • 跳表
    • 跳表的优化思路
    • skiplist,平衡搜索树,哈希表的对比
  • 实现思路
    • SkiplistNode
    • search 搜索
    • add 增加
    • earse 删除
  • 整体代码
  • 总结


前言

本文使用C++实现跳表的增删查。

铁蕾大佬关于跳表的博客


跳表

跳表(SkipList)是一种用于有序数据的高效数据结构,由 William Pugh 在1989年提出。
跳表本质是一个查找结构,通过在原有的有序链表上面增加多级索引来实现快速查找;跳表可以看作是一种可以进行二分查找的有序链表。

跳表的优化思路

  • 有序链表的问题:有序链表虽然保持了数据的顺序,但在查找特定元素时,需要从头节点开始顺序遍历,时间复杂度为O(N),其中N为链表中元素数量。这在数据量较大时,会导致查找效率较低

跳表的优化思路
假如我们每相邻两个节点增加一个指针,让这个指针指向下下个节点。
在这里插入图片描述

这样所有新增加的指针连成一个新链表,但它包含的节点个数只有原来的一半。此时,我们再查找特定元素时,需要比较的节点数量大概只有原来的一半。
跳表就是采用多层链表的思路。
在这里插入图片描述

在这里插入图片描述

skiplist,平衡搜索树,哈希表的对比

SkipList(跳表):
查找效率:跳表的平均时间复杂度为O(logN),其中N是节点的数量。这是因为跳表通过多层链表结构,使得查找过程能够跳过部分节点,从而加快查找速度;
特点:跳表是一种概率平衡的数据结构,其实现相对简单,且支持快速的插入,删除和查找操作。同时,跳表在内存中的占用也相对较低

平衡搜索树
查找效率:平衡搜索树的查找时间复杂度通常我O(logN),其中N是节点的数量。这是因为平衡搜索树通过旋转,分裂等操作来保持树的平衡性,从而确保每次查找都能快速定位到目标节点
特定:平衡搜索树具有严格的平衡性要求,使其插入,删除和查找操作都能保持较高的效率。同时,平衡搜索树还支持范围查询等复杂操作。然而,其实现相对复杂,且需要额外的空间来维护树的平衡性

哈希表
查找效率:哈希表的查找效率时间复杂度平均为O(1),但在最坏情况下可能退化为O(N)。因此,哈希表的查找效率取决于哈希函数的优劣和装填因子的设置
特点:哈希表具有极高的查找效率,特别适用于需要频繁查找的场景。同时,哈希表的插入和删除操作也相对简单。然而,哈希表不支持范围查询等复杂操作,且哈希冲突较多时,其性能可能会受到影响。此外,哈希表还需要额外的空间来存储哈希函数和链表等结构

实现思路

SkiplistNode

struct SkiplistNode {int _val;vector<SkiplistNode*> _nexts;SkiplistNode(int val, int level) :_val(val), _nexts(level, nullptr) {}
};

search 搜索

在这里插入图片描述
假如我们要查找 17 这个节点

先定义 cur 指向头节点,从最顶层开始查找;发现 9 小于 17(要查找元素在该元素后面),改变cur指向,使cur 指向 9节点。
在这里插入图片描述
再从9节点开始查找,发现 21 大于 17(要查找元素在该元素前面),去下面一层查找,发现 17 == 17,找到要查找的元素。
在这里插入图片描述

    bool search(int target) {int level = _head._nexts.size() - 1;SkiplistNode* cur = &_head;while (level >= 0) {if (cur->_nexts[level] && cur->_nexts[level]->_val < target) {// 向右走,更新 cur 和 level,target 只能在 cur->_nexts[level]->_val 后面cur = cur->_nexts[level];}else if (!cur->_nexts[level] || cur->_nexts[level]->_val > target) {// 向下走,target 只能在 cur->_nexts[level]->_val 前面level--;}else {// 找到了return true;}}return false;}

add 增加

在这里插入图片描述
假如我们要增加 18 。
那我们需要分三步完成,1.寻找到新增节点要插入的位置。2.构造新节点。3.链接节点;其实与单链表的新增节点相似,只不过寻找到新增节点要插入的位置由一点不同

寻找新增节点要插入的位置
我们需要一个数组(大小为最大层数),来记录新节点前面的节点。此时 cur 指向头结点,从顶层开始查找,发现 6 < 18(新增节点在6的后面),改变cur,使cur指向6
在这里插入图片描述
cur指向6,从顶层查找,发现6指向nullptr,向下走,prevs在第4层记录6(如果新增节点有4层,6可能是新增节点的前一个节点)。发现 25 > 18(新增节点在25之前),向下走,prevs在第三层记录6(如果新增节点有3层,6可能是新增节点的前一个节点)。发现 9 < 18(新增节点在9后面),cur 指向9。
在这里插入图片描述
cur指向9,从第二层查找,发现 17 < 18(新增节点在17之后),cur指向17。 在这里插入图片描述
cur指向17,从第二层查找,发现 25 > 18(新增节点在25前面),向下走,prevs在第二层记录17(如果新增节点有2层,17可能是新增节点的前一个节点)。从第一次查找,发现 19 > 18(新增节点在19前面),向下走,prevs在第一层记录19(如果新增节点有1层,19可能是新增节点的前一个节点)。此时层数 小于 0,查找结束。17的后面就是新增节点的位置。
在这里插入图片描述

在这里插入图片描述

    vector<SkiplistNode*> searchPrevs(int num) {vector<SkiplistNode*> prevs(_maxLevel, &_head);int level = _head._nexts.size() - 1;SkiplistNode* cur = &_head;while (level >= 0) {if (!cur->_nexts[level] || cur->_nexts[level]->_val >= num) {// 要插入节点,一定在cur->_nexts[level]的前面// 向下走,并更新节点prevs[level] = cur;level--;}else if (cur->_nexts[level] && cur->_nexts[level]->_val < num) {// 要插入节点,一定在cur->_nexts[level]的后面// 向右走cur = cur->_nexts[level];}}return prevs;}void add(int num) {// 寻找插入位置,并记录前面的节点vector<SkiplistNode*> prevs = searchPrevs(num);// 构造新节点,随机层数int newlevel = RandomLevel();SkiplistNode* newnode = new SkiplistNode(num, newlevel);// 连接节点newlevel--;while (newlevel >= 0) {newnode->_nexts[newlevel] = prevs[newlevel]->_nexts[newlevel];prevs[newlevel]->_nexts[newlevel] = newnode;newlevel--;}}

earse 删除

在这里插入图片描述
假如我们要删除 19。
我们需要4步完成,1.寻找删除节点,并记录前面节点。2.判断是否存在要删除的节点。3.链接节点。4.删除节点
与新增节点操作类似。

经过第一步寻找删除节点,并记录前面节点后,我们只需判断prevs数组中第0层节点的第0层指向的节点是否等于要删除节点即可。

在这里插入图片描述

    vector<SkiplistNode*> searchPrevs(int num) {vector<SkiplistNode*> prevs(_maxLevel, &_head);int level = _head._nexts.size() - 1;SkiplistNode* cur = &_head;while (level >= 0) {if (!cur->_nexts[level] || cur->_nexts[level]->_val >= num) {// 要插入节点,一定在cur->_nexts[level]的前面// 向下走,并更新节点prevs[level] = cur;level--;}else if (cur->_nexts[level] && cur->_nexts[level]->_val < num) {// 要插入节点,一定在cur->_nexts[level]的后面// 向右走cur = cur->_nexts[level];}}return prevs;}bool erase(int num) {// 寻找删除节点,并记录前面的节点vector<SkiplistNode*> prevs = searchPrevs(num);// 判断是否存在要删除的节点if (!prevs[0]->_nexts[0] || prevs[0]->_nexts[0]->_val != num)return false;// 连接节点SkiplistNode* del = prevs[0]->_nexts[0];int level = del->_nexts.size() - 1;while (level >= 0) {prevs[level]->_nexts[level] = del->_nexts[level];level--;}// 删除节点delete del;return true;}

整体代码

leetcode上设计跳表的题
1206.设计跳表

在这里插入图片描述

struct SkiplistNode {int _val;vector<SkiplistNode*> _nexts;SkiplistNode(int val, int level) :_val(val), _nexts(level, nullptr) {}
};class Skiplist {// 本质是一个有序链表
public:Skiplist() :_head(-1, _maxLevel) {srand((unsigned int)time(nullptr));}bool search(int target) {int level = _head._nexts.size() - 1;SkiplistNode* cur = &_head;while (level >= 0) {if (cur->_nexts[level] && cur->_nexts[level]->_val < target) {// 向右走,更新 cur 和 level,target 只能在 cur->_nexts[level]->_val 后面cur = cur->_nexts[level];}else if (!cur->_nexts[level] || cur->_nexts[level]->_val > target) {// 向下走,target 只能在 cur->_nexts[level]->_val 前面level--;}else {// 找到了return true;}}return false;}void add(int num) {// 寻找插入位置,并记录前面的节点vector<SkiplistNode*> prevs = searchPrevs(num);// 构造新节点,随机层数int newlevel = RandomLevel();SkiplistNode* newnode = new SkiplistNode(num, newlevel);// 连接节点newlevel--;while (newlevel >= 0) {newnode->_nexts[newlevel] = prevs[newlevel]->_nexts[newlevel];prevs[newlevel]->_nexts[newlevel] = newnode;newlevel--;}}bool erase(int num) {// 寻找删除节点,并记录前面的节点vector<SkiplistNode*> prevs = searchPrevs(num);// 判断是否存在要删除的节点if (!prevs[0]->_nexts[0] || prevs[0]->_nexts[0]->_val != num)return false;// 连接节点SkiplistNode* del = prevs[0]->_nexts[0];int level = del->_nexts.size() - 1;while (level >= 0) {prevs[level]->_nexts[level] = del->_nexts[level];level--;}// 删除节点delete del;return true;}private:int RandomLevel() {int level = 1;while (rand() <= RAND_MAX * _p && level < _maxLevel)level++;return level;}vector<SkiplistNode*> searchPrevs(int num) {vector<SkiplistNode*> prevs(_maxLevel, &_head);int level = _head._nexts.size() - 1;SkiplistNode* cur = &_head;while (level >= 0) {if (!cur->_nexts[level] || cur->_nexts[level]->_val >= num) {// 要插入节点,一定在cur->_nexts[level]的前面// 向下走,并更新节点prevs[level] = cur;level--;}else if (cur->_nexts[level] && cur->_nexts[level]->_val < num) {// 要插入节点,一定在cur->_nexts[level]的后面// 向右走cur = cur->_nexts[level];}}return prevs;}private:double _p = 0.5;int _maxLevel = 32;SkiplistNode _head;
};

总结

以上就是跳表的实现

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/468179.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

材质(二)——材质参数化,从源材质继承生成不同的材质实例

继承原材质&#xff0c;对外提供参数。 更改调制不同的参数&#xff0c;生成不同的材质实例。 类似于&#xff0c;类的继承。有一个基类Base.继承生成为子类 A_Base,B_Base,C_Base

Kotlin 协程使用及其详解

Kotlin协程&#xff0c;好用&#xff0c;但是上限挺高的&#xff0c;我一直感觉自己就处于会用&#xff0c;知其然不知其所以然的地步。 做点小总结&#xff0c;比较浅显。后面自己再继续补充吧。 一、什么是协程&#xff1f; Kotlin 协程是一种轻量级的并发编程方式&#x…

HDFS和HBase跨集群数据迁移 源码

HDFS集群间数据迁移&#xff08;hadoop distcp&#xff09; hadoop distcp \ -pb \ hdfs://XX.14.36.205:8020/user/hive/warehouse/dp_fk_tmp.db/ph_cash_order \ hdfs://XX.18.32.21:8020/user/hive/warehouse/dp_fksx_mart.db/HBase集群间数据&#xff08;hbase ExportSnap…

多态(c++)

一、概念 多态分为编译时多态&#xff08;静态多态&#xff09;和运行时多态&#xff08;动态多态&#xff09;&#xff0c;函数重载和函数模板就是编译时多态&#xff0c;它们传不同的类型的参数就可以调用不同的函数&#xff0c;通过参数不同达到多种形态&#xff0c;因为它们…

MySQL之索引(1)(索引概念与作用、红黑树、b树、b+树)(面试高频)

目录 一、索引的概念、作用。 &#xff08;1&#xff09;介绍。 &#xff08;2&#xff09;为啥索引能优化sql查询&#xff1f; 1、某张表(emp)结构以及数据如下。 2、假如执行的SQL语句为&#xff1a;select * from emp where empno7844; 3、对比与总结。 &#xff08;3&#…

element-plus的Tree 树形控件添加图标

该文章为本菜鸡学习记录&#xff0c;如有错误还请大佬指教 本人刚开始接触vue框架&#xff0c;在使用element-plus组件想实现树形控件&#xff0c;发现官网的组件示例没有图标区分显示 实现效果 代码 <temple 部分 <el-tree :data"data" node-click"hand…

libgdiplus在MacOS M1上问题:Unable to load shared library ‘libgdiplus‘

libgdiplus在MacOS M1上问题&#xff1a;Unable to load shared library libgdiplus 问题解决步骤1步骤2 问题 在mac上的pycharm中执行下面的代码时出现下面的错误 slide.get_thumbnail( RuntimeError: Proxy error(TypeInitializationException): The type initializer for…

在 WPF 中,绑定机制是如何工作的?WPF数据绑定机制解析

在WPF&#xff08;Windows Presentation Foundation&#xff09;中&#xff0c;数据绑定机制是其核心功能之一&#xff0c;广泛用于连接应用程序的UI&#xff08;用户界面&#xff09;和应用程序的业务逻辑层。数据绑定允许你将UI元素与数据源&#xff08;如对象、集合或其他数…

BEAGLE: Forensics of Deep Learning Backdoor Attack for Better Defense(论文阅读)

将论文中内容精简了一下&#xff0c;并做了下总结。 目录 摘要 背景介绍 Contribution&#xff1a; 提出的方法&#xff1a;BEAGLE的核心目标 简化的具体步骤&#xff1a; ThreatModel&#xff1a; 方法限制&#xff1a; 案例分析&#xff1a; EAGLE 自动生成的扫描…

EasyUI弹出框行编辑,通过下拉框实现内容联动

EasyUI弹出框行编辑&#xff0c;通过下拉框实现内容联动 需求 实现用户支付方式配置&#xff0c;当弹出框加载出来的时候&#xff0c;显示用户现有的支付方式&#xff0c;datagrid的第一列为conbobox,下来选择之后实现后面的数据直接填充&#xff1b; 点击新增&#xff1a;新…

Node.js 全栈开发进阶篇

​&#x1f308;个人主页&#xff1a;前端青山 &#x1f525;系列专栏&#xff1a;node.js篇 &#x1f516;人终将被年少不可得之物困其一生 依旧青山,本期给大家带来node.js篇专栏内容:node.js- 全栈开发进阶篇 前言 大家好&#xff0c;我是青山。在上一篇文章中&#xff0c;…

单双链表及其反转

一&#xff0c;空指针的补充 1. 空指针的定义 在 C 语言中&#xff0c;空指针通常被定义为 NULL&#xff0c;或者在 C 中为 nullptr。它的本质是一个指针&#xff0c;指向无效的地址&#xff0c;用来表示一个指针当前没有指向有效的内存空间。空指针并不指向实际的内存地址&am…

Scrapy框架:Python爬虫开发快速入门与初试

在众多编程语言中&#xff0c;Python以其简洁的语法和强大的库支持&#xff0c;成为了编写爬虫的首选语言。而在Python的爬虫库中&#xff0c;Scrapy框架无疑是其中的佼佼者。Scrapy是一个开源的、基于Python的爬虫框架&#xff0c;它提供了一套完整的工具和功能&#xff0c;使…

C语言 | Leetcode C语言题解之第543题二叉树的直径

题目&#xff1a; 题解&#xff1a; typedef struct TreeNode Node;int method (Node* root, int* max) {if (root NULL) return 0;int left method (root->left, max);int right method (root->right, max);*max *max > (left right) ? *max : (left right);…

探索Python视频处理的瑞士军刀:ffmpeg-python库

文章目录 **探索Python视频处理的瑞士军刀&#xff1a;ffmpeg-python库**第一部分&#xff1a;背景介绍第二部分&#xff1a;ffmpeg-python库是什么&#xff1f;第三部分&#xff1a;如何安装ffmpeg-python库&#xff1f;第四部分&#xff1a;简单库函数使用方法1. 视频转码2. …

King3399(ubuntu文件系统)wifi设备树分析

该文章仅供参考&#xff0c;编写人不对任何实验设备、人员及测量结果负责&#xff01;&#xff01;&#xff01; 0 引言 文章主要介绍King3399(ubuntu)wifi设备树&#xff0c;涉及king-rk3399.dts、rp-wifi-sdio.dtsi内容修改与介绍 在使用wifi前本人遇到了一个比较奇怪的问…

Elmo驱动器上位机软件的详细配置

续接上文,本文讲解Elmo驱动器上位机软件更详细的配置,重点关注,在电机的位置受到约束的情况下,完成驱动器的参数整定过程,以及一些调试方法 一 硬件介绍 本文使用的是另一套设备,假设电机的位置是受到约束的 1 编码器规格书 编码器已知信息是 :读数头是26位的,通讯…

【Python】爬虫使用代理IP

1、代理池 IP 代理池可以理解为一个池子&#xff0c;里面装了很多代理IP。 池子里的IP是有生命周期的&#xff0c;它们将被定期验证&#xff0c;其中失效的将被从池子里面剔除池子里的ip是有补充渠道的&#xff0c;会有新的代理ip不断被加入池子中池子中的代理ip是可以被随机…

Ascend Extension for PyTorch是个what?

1 Ascend Extension for PyTorch Ascend Extension for PyTorch 插件是基于昇腾的深度学习适配框架&#xff0c;使昇腾NPU可以支持PyTorch框架&#xff0c;为PyTorch框架的使用者提供昇腾AI处理器的超强算力。 项目源码地址请参见Ascend/Pytorch。 昇腾为基于昇腾处理器和软…

【HarmonyOS Next】数据本地存储:@ohos.data.preferences

【HarmonyOS Next】数据本地存储&#xff1a;ohos.data.preferences 在开发现代应用程序时&#xff0c;数据存储是一个至关重要的过程。应用程序为了保持某些用户设置、应用状态以及其他小量数据信息通常需要一个可靠的本地存储解决方案。在 HarmonyOS Next 环境下&#xff0c…