当前位置: 首页 > 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…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别

UnsatisfiedLinkError 在对接硬件设备中&#xff0c;我们会遇到使用 java 调用 dll文件 的情况&#xff0c;此时大概率出现UnsatisfiedLinkError链接错误&#xff0c;原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用&#xff0c;结果 dll 未实现 JNI 协…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?

在工业自动化持续演进的今天&#xff0c;通信网络的角色正变得愈发关键。 2025年6月6日&#xff0c;为期三天的华南国际工业博览会在深圳国际会展中心&#xff08;宝安&#xff09;圆满落幕。作为国内工业通信领域的技术型企业&#xff0c;光路科技&#xff08;Fiberroad&…...

文件上传漏洞防御全攻略

要全面防范文件上传漏洞&#xff0c;需构建多层防御体系&#xff0c;结合技术验证、存储隔离与权限控制&#xff1a; &#x1f512; 一、基础防护层 前端校验&#xff08;仅辅助&#xff09; 通过JavaScript限制文件后缀名&#xff08;白名单&#xff09;和大小&#xff0c;提…...

Xcode 16 集成 cocoapods 报错

基于 Xcode 16 新建工程项目&#xff0c;集成 cocoapods 执行 pod init 报错 ### Error RuntimeError - PBXGroup attempted to initialize an object with unknown ISA PBXFileSystemSynchronizedRootGroup from attributes: {"isa">"PBXFileSystemSynchro…...

python基础语法Ⅰ

python基础语法Ⅰ 常量和表达式变量是什么变量的语法1.定义变量使用变量 变量的类型1.整数2.浮点数(小数)3.字符串4.布尔5.其他 动态类型特征注释注释是什么注释的语法1.行注释2.文档字符串 注释的规范 常量和表达式 我们可以把python当作一个计算器&#xff0c;来进行一些算术…...