当前位置: 首页 > news >正文

c++实现跳表

原理

跳表(Skip List) 是一种随机化数据结构,用于高效查找、插入和删除,尤其适用于有序数据集合。相比链表,跳表通过多层索引结构加速查找,期望时间复杂度接近 O(log⁡n)。跳表的主要思想是:

  • 底层链表存储所有数据元素,保持有序。
  • 上层链表是稀疏索引,用于跳过部分节点,减少遍历的长度。

结构图

下面是一个跳表的结构示意:

Level 3:  [1] ----------------> [9]
Level 2:  [1] -----> [4] -----> [9]
Level 1:  [1] -----> [4] -----> [7] -----> [9]
Level 0:  [1] -> [2] -> [4] -> [5] -> [7] -> [8] -> [9]

如上图所示:

  1. 每一层都是一个有序链表。
  2. 每一层的节点是下一层的子集,存储重要的中间节点,形成分层索引
  3. 查找过程:从最高层开始,先向右移动,如果目标值超出范围,则向下移动到下一层。重复此过程直到找到目标节点。

优缺点

优点

  • 插入、删除和查找的期望时间复杂度为 O(log⁡n)。
  • 实现简单,比红黑树和AVL树更容易理解和维护。

缺点

  • 需要额外的空间存储索引层节点。

代码示例(c++)

下面是一段简单的 C++ 跳表实现,包括节点结构定义、插入、查找和显示功能。

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>
using namespace std;class Node {
public:int value;vector<Node*> forward;  // 每层的前向指针Node(int val, int level) : value(val), forward(level + 1, nullptr) {}
};class SkipList {
private:int maxLevel;  // 跳表的最大层数float probability;  // 晋升概率Node* header;  // 头节点int currentLevel;  // 当前跳表的层数public:SkipList(int maxLevel, float probability) : maxLevel(maxLevel), probability(probability), currentLevel(0) {header = new Node(-1, maxLevel);  // 头节点初始化为-1srand(time(nullptr));  // 初始化随机数种子}// 随机生成节点的层数int randomLevel() {int lvl = 0;while ((rand() / double(RAND_MAX)) < probability && lvl < maxLevel) {lvl++;}return lvl;}// 插入新节点void insert(int value) {vector<Node*> update(maxLevel + 1);Node* current = header;// 从最高层向下查找插入位置for (int i = currentLevel; i >= 0; i--) {while (current->forward[i] && current->forward[i]->value < value) {current = current->forward[i];}update[i] = current;}// 在底层插入节点的位置current = current->forward[0];// 如果节点不存在,则插入新节点if (!current || current->value != value) {int lvl = randomLevel();if (lvl > currentLevel) {for (int i = currentLevel + 1; i <= lvl; i++) {update[i] = header;}currentLevel = lvl;}Node* newNode = new Node(value, lvl);for (int i = 0; i <= lvl; i++) {newNode->forward[i] = update[i]->forward[i];update[i]->forward[i] = newNode;}cout << "Inserted value: " << value << " at level: " << lvl << endl;}}// 查找节点bool search(int value) {Node* current = header;for (int i = currentLevel; i >= 0; i--) {while (current->forward[i] && current->forward[i]->value < value) {current = current->forward[i];}}current = current->forward[0];return current && current->value == value;}// 打印跳表结构void display() {for (int i = currentLevel; i >= 0; i--) {Node* current = header->forward[i];cout << "Level " << i << ": ";while (current) {cout << current->value << " ";current = current->forward[i];}cout << endl;}}
};int main() {SkipList skipList(4, 0.5);  // 最大层数为4,晋升概率为0.5skipList.insert(3);skipList.insert(6);skipList.insert(7);skipList.insert(9);skipList.insert(12);skipList.insert(19);cout << "Skip List Structure:" << endl;skipList.display();cout << "Search 7: " << (skipList.search(7) ? "Found" : "Not Found") << endl;cout << "Search 4: " << (skipList.search(4) ? "Found" : "Not Found") << endl;return 0;
}

代码解析

  1. Node 类
    • 表示跳表中的节点,包含节点的值和指向不同层节点的指针向量 forward
  2. SkipList 类
    • 实现了跳表的主要功能,包括插入、查找和显示结构。
    • randomLevel:用于随机生成节点的层数,控制索引的稀疏程度。
    • insert:插入元素到跳表中,如果新节点的层数超过当前最大层数,则更新索引。
    • search:查找目标值是否存在。
  3. 主函数
    • 初始化跳表并插入若干元素,测试插入和查找功能。

运行结果

Inserted value: 3 at level: 0
Inserted value: 6 at level: 1
Inserted value: 7 at level: 2
Inserted value: 9 at level: 0
Inserted value: 12 at level: 1
Inserted value: 19 at level: 3
Skip List Structure:
Level 3: 19 
Level 2: 7 19 
Level 1: 6 12 19 
Level 0: 3 6 7 9 12 19 
Search 7: Found
Search 4: Not Found

总结

  • 时间复杂度:查找、插入、删除的期望时间复杂度为 O(log⁡n)O(\log n)O(logn)。
  • 空间复杂度:O(nlog⁡n)O(n \log n)O(nlogn),因为每个节点可能会出现在多层中。

跳表的实现简单且高效,常用于 Redis 等数据库的有序集合。

相关文章:

c++实现跳表

原理 跳表&#xff08;Skip List&#xff09; 是一种随机化数据结构&#xff0c;用于高效查找、插入和删除&#xff0c;尤其适用于有序数据集合。相比链表&#xff0c;跳表通过多层索引结构加速查找&#xff0c;期望时间复杂度接近 O(log⁡n)。跳表的主要思想是&#xff1a; …...

新探索研究生英语读写教程pdf答案(基础级)

《新探索研究生英语读写教程》的设计和编写充分考虑国内研究生人才培养目标和研究生公共英语的教学需求&#xff0c; 教学内容符合研究生认知水平&#xff0c; 学术特征突出&#xff1b;教学设计紧密围绕学术阅读、学术写作和学术研究能力培养&#xff1b;教学资源立体多元&…...

管道与共享内存

一&#xff0c;命名管道 管道的限制就是他只能在有血缘关系&#xff08;父子进程&#xff09;的进程中&#xff0c;允许互相访问&#xff0c;这是有局限性的&#xff0c;所以我们想在毫无关系的进程中允许他们相互访问&#xff0c;这就是命名管道的定义。 总结&#xff1a;命名…...

ES 自定义排序方式

es默认score是根据query的相关度进行打分的&#xff0c;具体打分机制可以参见&#xff1a;官方文档。如果召回时既希望有相关性又能根据其他信息进行排序。 例如小红书搜索的时候&#xff0c;可能既希望有召回相关度又能根据热度信息&#xff08;如果喜欢、收藏等等参数去进行召…...

在vue中,编写一个li标签同时使用v-for和v-if,谁的优先级更高

在 Vue 中&#xff0c;v-if 和 v-for 是两个常用的指令&#xff0c;但它们的优先级不同。当二者一起使用时&#xff0c;v-for 的优先级高于 v-if。这意味着&#xff0c;v-for 会先执行&#xff0c;即使列表中的某些元素不满足 v-if 条件&#xff0c;它们仍会被遍历和渲染。 由…...

Java 后端开发面试题及其答案

以下是一些常见的 Java 后端开发面试题及其答案&#xff0c;涵盖了 Java 基础、面向对象、并发、多线程、框架等多个方面&#xff1a; 1. Java 中的基本数据类型有哪些&#xff1f; 答案&#xff1a; Java 中的基本数据类型有 8 种&#xff1a; int&#xff1a;32 位整数lon…...

C++,STL 045(24.10.24)

内容 1.对set容器的大小进行操作。 2.set容器的交换操作。 运行代码 #include <iostream> #include <set>using namespace std;void printSet(set<int> &s) {for (set<int>::iterator it s.begin(); it ! s.end(); it){cout << *it <…...

二叉树习题其五【力扣】【算法学习day.12】

前言 书接上篇文章二叉树习题其四&#xff0c;这篇文章我们将基础拓展 ###我做这类文档一个重要的目的还是给正在学习的大家提供方向&#xff08;例如想要掌握基础用法&#xff0c;该刷哪些题&#xff1f;&#xff09;我的解析也不会做的非常详细&#xff0c;只会提供思路和一…...

【数据库】Mysql的锁类型

Mysql中的锁机制主要是为了保证数据的一致性和完整性&#xff0c;在并发的情况下起着至关重要的作用。其中锁的类型主要是分为以下几种&#xff1a; 按照粒度分类 全局锁&#xff1a;对于整个数据库实例进行枷锁&#xff0c;加锁后整个实例就处于只读的状态。局锁通常用于需要…...

自媒体短视频制作素材下载网站推荐,让创作更简单

随着自媒体行业的火爆&#xff0c;视频质量要求也越来越高。想要找到无版权的高清视频素材并不容易&#xff0c;但别担心&#xff01;今天为大家整理了5个国内外高质量的素材网站&#xff0c;让你轻松获取自媒体短视频素材&#xff0c;快收藏起来吧&#xff01; 蛙学网 蛙学网是…...

Altium Designer 入门基础教程(五)

本文章继续接着《Altium Designer 入门基础教程&#xff08;四&#xff09;》的内容往下介绍&#xff1a; 七、AD画板的整个流程步骤 I.集成库的制作 AD元件库有2种&#xff1a;1、原理图元件库SCH.LIB 2、印刷电路板&#xff08;PCB&#xff09;元件库 PCB.LIB 印刷电路…...

Java题集练习3

Java题集练习3 1 什么时候用instanceof instanceOf关键字主要用于判断一个对象是否为某个类的子类或是接口的实例&#xff0c;通常用于类型转换和运行时类型判断的场景&#xff0c;比如继承和多态中。比如&#xff0c;创建一个Animal类及其子类Cat和Cat子类Hat&#xff0c;可…...

【部署篇】Haproxy-01安装部署(源码方式安装)

‌一、HAProxy概述‌ HAProxy是一款免费、快速且可靠的代理软件&#xff0c;提供高可用性、负载均衡&#xff0c;支持TCP和HTTP应用代理&#xff0c;HAProxy凭借其卓越的性能和灵活性&#xff0c;成为众多知名网站和系统的首选代理软件。‌ ‌核心特点‌&#xff1a; ‌高性能…...

开拓鸿蒙测试新境界,龙测科技引领自动化测试未来

在当今科技舞台上&#xff0c;鸿蒙 OS 以非凡先进性强势登场&#xff0c;打破传统操作系统格局&#xff0c;为软件测试领域带来全新机遇与艰巨挑战。 一、鸿蒙 OS 的辉煌崛起 &#xff08;一&#xff09;壮丽发展历程与卓越市场地位 鸿蒙 OS 的发展如波澜壮阔的史诗。2023 年…...

Java项目-基于springboot框架的自习室预订系统项目实战(附源码+文档)

作者&#xff1a;计算机学长阿伟 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、ElementUI等&#xff0c;“文末源码”。 开发运行环境 开发语言&#xff1a;Java数据库&#xff1a;MySQL技术&#xff1a;SpringBoot、Vue、Mybaits Plus、ELementUI工具&#xff1a;IDEA/…...

调整数组奇偶数顺序

今天给大家分享一道题目&#xff0c;要求我们输入一个数组&#xff0c;将全部奇数放在偶数前面&#xff08;无需比较大小&#xff09;&#xff0c;下面是我写的代码 这个方法比使用三个数组进行数据传输要节省不少程序运行时间&#xff0c;缺点是使用了较多的while循环&#xf…...

Electron调用nodejs的cpp .node扩展【非安全】

Electron调用nodejs的cpp .node扩展【非安全】 环境&#xff1a; electron: 30.1.1 nodejs: 20.14.0前言 Electron中可以非常容易的调用nodejs的js代码&#xff0c;但是对于cpp .node扩展需要一定的配置才能调用&#xff0c;下面介绍一种最简单的cpp扩展的调用方法&#xff…...

一文了解AOSP是什么?

一文了解AOSP是什么&#xff1f; AOSP基本信息 基本定义 AOSP是Android Open Source Project的缩写&#xff0c;这是一个由Google维护的完全免费和开放的操作系统开发项目。它是Android系统的核心基础&#xff0c;提供了构建移动操作系统所需的基本组件。 主要特点 完全开源…...

ffmpeg视频边缘模糊,打造梦幻般的视觉效果!

在视频编辑的世界里&#xff0c;细节决定成败。边缘模糊效果是一种强大的工具&#xff0c;可以让你的作品瞬间提升质感。通过简单的命令&#xff0c;你可以轻松实现视频边缘的柔和化处理&#xff0c;创造出梦幻般的视觉效果。 想象一下&#xff0c;当你将一段普通的视频应用边…...

[Wireshark] 使用Wireshark抓包https数据包并显示为明文、配置SSLKEYLOGFILE变量(附下载链接)

前言 wireshark安装包 链接&#xff1a;https://pan.quark.cn/s/febb28f57c01 提取码&#xff1a;fUCQ 链接失效&#xff08;可能会被官方和谐&#xff09;可评论或私信我重发 chrome与firefox在访问https网站的时候会将密钥写入这个环境变量SSLKEYLOGFILE中&#xff0c;在wir…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

蓝桥杯 2024 15届国赛 A组 儿童节快乐

P10576 [蓝桥杯 2024 国 A] 儿童节快乐 题目描述 五彩斑斓的气球在蓝天下悠然飘荡&#xff0c;轻快的音乐在耳边持续回荡&#xff0c;小朋友们手牵着手一同畅快欢笑。在这样一片安乐祥和的氛围下&#xff0c;六一来了。 今天是六一儿童节&#xff0c;小蓝老师为了让大家在节…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

STM32F4基本定时器使用和原理详解

STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...