C++面试：跳表

        

目录

跳表介绍 

跳表的特点：

跳表的应用场景：

C++ 代码示例：

跳表的特性

跳表示例 

总结

        跳表（Skip List）是一种支持快速搜索、插入和删除的数据结构，具有相对简单的实现和较高的查询性能。下面是跳表的详细介绍和一个简单的 C++ 代码示例：

跳表介绍 

跳表的特点：

  1. 有序结构： 跳表中的每个节点都包含一个元素，并且节点按照元素的大小有序排列。
  2. 多层索引： 跳表通过维护多层索引来实现快速搜索。每一层都是一个有序链表，最底层包含所有元素，而每上一层的节点是下一层节点的一部分。
  3. 跳跃式访问： 通过索引层，跳表允许在较高层直接跳过一些节点，从而提高搜索效率。

跳表的应用场景：

  1. 有序集合的实现： 用于需要频繁的插入、删除和搜索操作的有序数据集合，如 Redis 中的有序集合（Sorted Set）。
  2. 替代平衡树： 在某些场景下，跳表可以作为对平衡树的一种替代，具有更简单的实现和较好的性能。

C++ 代码示例：

#include <iostream>
#include <vector>
#include <cstdlib>const int MAX_LEVEL = 16;  // 最大层数// 跳表节点定义
struct Node {int value;std::vector<Node*> forward;  // 每层的指针数组Node(int val, int level) : value(val), forward(level, nullptr) {}
};// 跳表定义
class SkipList {
private:Node* header;  // 头节点int level;     // 当前跳表的最大层数public:SkipList() : level(1) {header = new Node(0, MAX_LEVEL);}// 随机生成一个层数int randomLevel() {int lvl = 1;while ((rand() % 2) && (lvl < MAX_LEVEL))lvl++;return lvl;}// 插入一个元素void insert(int val) {std::vector<Node*> update(MAX_LEVEL, nullptr);Node* current = header;// 从最高层到底层，找到每一层的插入位置for (int i = level - 1; i >= 0; i--) {while (current->forward[i] != nullptr && current->forward[i]->value < val) {current = current->forward[i];}update[i] = current;}// 随机生成一个层数int newLevel = randomLevel();// 如果新的层数比当前层数高，则更新 updateif (newLevel > level) {for (int i = level; i < newLevel; i++) {update[i] = header;}level = newLevel;}// 创建新节点Node* newNode = new Node(val, newLevel);// 更新每一层的指针for (int i = 0; i < newLevel; i++) {newNode->forward[i] = update[i]->forward[i];update[i]->forward[i] = newNode;}}// 搜索一个元素，返回是否存在bool search(int val) {Node* current = header;// 从最高层到底层，搜索每一层的节点for (int i = level - 1; i >= 0; i--) {while (current->forward[i] != nullptr && current->forward[i]->value < val) {current = current->forward[i];}}// 到达底层，判断是否找到目标元素if (current->forward[0] != nullptr && current->forward[0]->value == val) {return true;} else {return false;}}// 删除一个元素void remove(int val) {std::vector<Node*> update(MAX_LEVEL, nullptr);Node* current = header;// 从最高层到底层，找到每一层的删除位置for (int i = level - 1; i >= 0; i--) {while (current->forward[i] != nullptr && current->forward[i]->value < val) {current = current->forward[i];}update[i] = current;}// 到达底层，判断是否找到目标元素if (current->forward[0] != nullptr && current->forward[0]->value == val) {// 更新每一层的指针，删除目标节点for (int i = 0; i < level; i++) {if (update[i]->forward[i] != current->forward[i]) {break;}update[i]->forward[i] = current->forward[i]->forward[i];}// 如果删除的是最高层的节点，更新层数while (level > 1 && header->forward[level - 1] == nullptr) {level--;}// 释放节点内存delete current;}}// 打印跳表void printSkipList() {for (int i = level - 1; i >= 0; i--) {Node* current = header->forward[i];std::cout << "Level " << i << ": ";while (current != nullptr) {std::cout << current->value << " ";current = current->forward[i];}std::cout << std::endl;}std::cout << "-----------------------" << std::endl;}
};int main() {// 创建跳表SkipList skipList;// 插入一些元素skipList.insert(3);skipList.insert(6);skipList.insert(7);skipList.insert(9);skipList.insert(12);// 打印跳表skipList.printSkipList();// 搜索元素int searchValue = 7;if (skipList.search(searchValue)) {std::cout << "Element " << searchValue << " found in the skip list." << std::endl;} else {std::cout << "Element " << searchValue << " not found in the skip list." << std::endl;}// 删除元素int removeValue = 6;skipList.remove(removeValue);// 打印删除后的跳表skipList.printSkipList();return 0;
}

        这是一个简单的跳表实现，包括插入、搜索和删除操作。在实际应用中，跳表的层数、随机层数的方式以及其他细节可以根据具体需求进行调整。

跳表的特性

  1. 有序性： 跳表中的每个节点按照元素的大小有序排列。这使得在跳表中可以快速定位和搜索元素。

  2. 多层索引： 跳表通过维护多层索引来实现快速搜索。每一层都是一个有序链表，最底层包含所有元素，而每一层的节点是下一层节点的子集。这样的多层索引结构可以提高搜索效率。

  3. 跳跃式访问： 通过多层索引，跳表允许在较高层直接跳过一些节点，从而实现跳跃式的访问。这种设计类似于在二分查找中直接跳过一半的元素，从而提高了搜索的效率。

  4. 平衡性： 跳表的设计通过随机层数和灵活的插入策略，保持了跳表的平衡性。这有助于避免类似于二叉搜索树中的不平衡情况，使得操作的时间复杂度更加可控。

  5. 简单实现： 跳表相对于其他高效的数据结构，如平衡树，实现相对简单。它不需要像平衡树那样复杂的平衡维护，使得代码的实现和维护相对容易。

  6. 支持动态操作： 跳表天生适合动态操作，包括插入和删除。由于插入和删除操作只需要调整相邻节点的指针，而不需要进行全局的平衡调整，因此操作的效率较高。

  7. 适应范围广： 跳表可以应用于各种有序数据集合的场景，特别是在需要频繁插入、删除和搜索操作的场景中，其性能表现优异。

        跳表的这些特性使得它在一些应用场景中具有明显的优势，尤其在无法提前知道数据分布情况的情形下，跳表能够以较简单的方式维护有序性和高效操作。

跳表示例 

        下面是一个使用 C++ 实现的跳表例子，包含插入、搜索、删除和打印操作。在这个例子中，我使用了模板类以支持不同类型的元素。

#include <iostream>
#include <vector>
#include <cstdlib>// 跳表节点定义
template <typename T>
struct Node {T value;std::vector<Node*> forward;Node(T val, int level) : value(val), forward(level, nullptr) {}
};// 跳表定义
template <typename T>
class SkipList {
private:Node<T>* header;int level;public:SkipList() : level(1) {header = new Node<T>(T(), MAX_LEVEL);  // 初始值为 T() 的头节点}// 随机生成一个层数int randomLevel() {int lvl = 1;while ((rand() % 2) && (lvl < MAX_LEVEL))lvl++;return lvl;}// 插入一个元素void insert(const T& val) {std::vector<Node<T>*> update(MAX_LEVEL, nullptr);Node<T>* current = header;// 从最高层到底层，找到每一层的插入位置for (int i = level - 1; i >= 0; i--) {while (current->forward[i] != nullptr && current->forward[i]->value < val) {current = current->forward[i];}update[i] = current;}// 随机生成一个层数int newLevel = randomLevel();// 如果新的层数比当前层数高，则更新 updateif (newLevel > level) {for (int i = level; i < newLevel; i++) {update[i] = header;}level = newLevel;}// 创建新节点Node<T>* newNode = new Node<T>(val, newLevel);// 更新每一层的指针for (int i = 0; i < newLevel; i++) {newNode->forward[i] = update[i]->forward[i];update[i]->forward[i] = newNode;}}// 搜索一个元素，返回是否存在bool search(const T& val) const {Node<T>* current = header;// 从最高层到底层，搜索每一层的节点for (int i = level - 1; i >= 0; i--) {while (current->forward[i] != nullptr && current->forward[i]->value < val) {current = current->forward[i];}}// 到达底层，判断是否找到目标元素return (current->forward[0] != nullptr && current->forward[0]->value == val);}// 删除一个元素void remove(const T& val) {std::vector<Node<T>*> update(MAX_LEVEL, nullptr);Node<T>* current = header;// 从最高层到底层，找到每一层的删除位置for (int i = level - 1; i >= 0; i--) {while (current->forward[i] != nullptr && current->forward[i]->value < val) {current = current->forward[i];}update[i] = current;}// 到达底层，判断是否找到目标元素if (current->forward[0] != nullptr && current->forward[0]->value == val) {// 更新每一层的指针，删除目标节点for (int i = 0; i < level; i++) {if (update[i]->forward[i] != current->forward[i]) {break;}update[i]->forward[i] = current->forward[i]->forward[i];}// 如果删除的是最高层的节点，更新层数while (level > 1 && header->forward[level - 1] == nullptr) {level--;}// 释放节点内存delete current;}}// 打印跳表void printSkipList() const {for (int i = level - 1; i >= 0; i--) {Node<T>* current = header->forward[i];std::cout << "Level " << i << ": ";while (current != nullptr) {std::cout << current->value << " ";current = current->forward[i];}std::cout << std::endl;}std::cout << "-----------------------" << std::endl;}
};int main() {// 创建跳表SkipList<int> skipList;// 插入一些元素skipList.insert(3);skipList.insert(6);skipList.insert(7);skipList.insert(9);skipList.insert(12);// 打印跳表skipList.printSkipList();// 搜索元素int searchValue = 7;if (skipList.search(searchValue)) {std::cout << "Element " << searchValue << " found in the skip list." << std::endl;} else {std::cout << "Element " << searchValue << " not found in the skip list." << std::endl;}// 删除元素int removeValue = 6;skipList.remove(removeValue);// 打印删除后的跳表skipList.printSkipList();return 0;
}

在这个例子中，使用跳表有几个考虑因素：

  1. 高效的搜索操作： 跳表的搜索操作时间复杂度为 O(log n)，其中 n 是跳表中的元素个数。相较于普通链表的线性搜索，跳表提供了更快的搜索速度。

  2. 支持动态操作： 跳表天生适合动态操作，包括插入和删除。由于插入和删除操作只需要调整相邻节点的指针，而不需要进行全局的平衡调整，因此在元素的动态更新场景下，跳表相对于其他数据结构更具有优势。

  3. 简单实现： 跳表的实现相对简单，不需要像平衡树那样复杂的平衡维护。这使得它在实际应用中更容易实现和维护。

  4. 对比其他数据结构： 在这个示例中，使用跳表的主要目的是演示跳表的基本原理和操作，并不代表它是绝对优于其他数据结构的选择。具体选择数据结构的决策取决于实际应用场景、数据分布情况以及对不同操作的需求。

总结

特性:

  1. 有序性： 跳表中的每个节点按照元素的大小有序排列，使得在跳表中可以快速定位和搜索元素。
  2. 多层索引： 跳表通过维护多层索引来实现快速搜索，每一层都是一个有序链表，最底层包含所有元素。
  3. 跳跃式访问： 通过多层索引，跳表允许在较高层直接跳过一些节点，实现跳跃式的访问，提高搜索效率。
  4. 平衡性： 通过随机层数和灵活的插入策略，保持了跳表的平衡性，避免了类似于二叉搜索树中的不平衡情况。
  5. 支持动态操作： 跳表天生适合动态操作，包括插入和删除，操作的时间复杂度较低。

应用场景:

  1. 有序集合的实现： 适用于需要频繁插入、删除和搜索操作的有序数据集合，例如在 Redis 中的有序集合（Sorted Set）实现中使用了跳表。
  2. 替代平衡树： 在某些场景下，跳表可以作为对平衡树的一种替代，相对简单的实现和较好的性能表现使得它成为一种备选选择。
  3. 动态数据库索引： 在数据库中，跳表可以用作动态索引结构，适用于动态更新和频繁搜索的情况。
  4. 高效的动态排序： 在需要频繁的动态排序操作的场景下，跳表的性能可能优于传统的排序算法。

总体评价:

  • 优势: 跳表提供了一种在有序数据集合中实现高效的动态操作的方式，相较于平衡树结构实现较为简单，适用于需要频繁更新和搜索的场景。
  • 劣势: 跳表相对于其他数据结构可能占用更多内存，对于某些内存敏感的场景，可能不是最优选择。在一些特定的搜索密集型场景中，红黑树等平衡树结构也具有竞争力。

总体而言，跳表在一些动态、搜索密集的应用场景中表现出色，但在具体选择时，需要综合考虑数据分布、内存使用、实现难度等因素。

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

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

相关文章

常用芯片学习——HC244芯片

常用芯片学习——HC244芯片

HC573 三态输出八路缓冲器|线路驱动器 使用说明 SNx4HC244 八路缓冲器和线路驱动器专门设计用于提高三态存储器地址驱动器、时钟驱动器以及总线导向接收器和发送器的性能和密度。SNx4HC244 器件配备两个具有独立输出使能 (OE) 输入的 4 位缓冲器和驱动器。当 OE 为低电平时&a…
阅读更多...
【AI视野·今日NLP 自然语言处理论文速览 第七十五期】Thu, 11 Jan 2024

【AI视野·今日NLP 自然语言处理论文速览 第七十五期】Thu, 11 Jan 2024

AI视野今日CS.NLP 自然语言处理论文速览 Thu, 11 Jan 2024 Totally 36 papers &#x1f449;上期速览✈更多精彩请移步主页 Daily Computation and Language Papers Leveraging Print Debugging to Improve Code Generation in Large Language Models Authors Xueyu Hu, Kun K…
阅读更多...
php基础学习之代码框架

php基础学习之代码框架

一&#xff0c;标记 脚本标记&#xff08;已弃用&#xff09;&#xff1a;<script language"php"> php代码 </script> 标准标记&#xff1a;<?php php代码 ?> 二&#xff0c;基础输出语句 不是函数&#xff0c;…
阅读更多...
行业分析|中国人工智能发展的优势与差距

行业分析|中国人工智能发展的优势与差距

​人工智能&#xff0c;被誉为第四次工业革命的催化剂&#xff0c;吸引着发达国家和众多科技公司大举投入研发。我国积极构筑人工智能发展的先发优势&#xff0c;党的二十大报告提出推动战略性新兴产业集群&#xff0c;构建一系列新的增长引擎&#xff0c;包括信息技术、人工智…
阅读更多...
QT发送request请求

QT发送request请求

时间记录&#xff1a;2024/1/23 一、使用步骤 &#xff08;1&#xff09;pro文件中添加network模块 &#xff08;2&#xff09;创建QNetworkAccessManager网络管理类对象 &#xff08;3&#xff09;创建QNetworkRequest网络请求对象&#xff0c;使用setUrl方法设置请求url&am…
阅读更多...
MySQL 8.3 发布, 它带来哪些新变化？

MySQL 8.3 发布, 它带来哪些新变化？

1月16号 MySQL 官方发布 8.3 创新版 和 8.0.36 长期支持版本 (该版本 没有新增功能&#xff0c;更多是修复bug )&#xff0c;本文基于 官方文档 说一下 8.3 版本带来的变化。 一 增加的特性 1.1 GTID_NEXT 支持增加 TAG 选项。 之前的版本中 GTID_NEXTUUID:number &#xff…
阅读更多...
scrapy框架核心知识Spider,Middleware,Item Pipeline,scrapy项目创建与启动,Scrapy-redis与分布式

scrapy框架核心知识Spider,Middleware,Item Pipeline,scrapy项目创建与启动,Scrapy-redis与分布式

scrapy项目创建与启动 创建项目 在你的工作目录下直接使用命令: scrapy startproject scrapytutorial运行后创建了一个名为scrapytutorial的爬虫工程 创建spider 在爬虫工程文件内&#xff0c;运行以下命令&#xff1a; scrapy genspider quotes创建了名为quotes的爬虫 …
阅读更多...
超融合系统疑难故障定位与解决实践 3 例（含信创技术栈）

超融合系统疑难故障定位与解决实践 3 例（含信创技术栈）

当 IT 系统出现故障&#xff0c;问题定位往往是运维人员最头疼的环节。尤其是超融合系统&#xff0c;由于整体涉及的技术栈比较复杂&#xff0c;且有越来越多的用户基于信创环境进行部署&#xff0c;非常考验厂商和技术人员的专业能力&#xff1a;厂商研发和售后工程师不仅应能…
阅读更多...
【C/C++】C/C++编程——C++ 开发环境搭建

【C/C++】C/C++编程——C++ 开发环境搭建

C的开发环境种类繁多&#xff0c;以下是一些常见的C 集成开发环境&#xff1a; AppCode &#xff1a;构建与JetBrains’ IntelliJ IDEA 平台上的用于Objective-C&#xff0c;C,C&#xff0c;Java和Java开发的集成开发环境CLion&#xff1a;来自JetBrains的跨平台的C/C的集成开…
阅读更多...
天津大数据培训班推荐，数据分析过程的常见错误

天津大数据培训班推荐，数据分析过程的常见错误

大数据”是近年来IT行业的热词&#xff0c;目前已经广泛应用在各个行业。大数据&#xff0c;又称海量信息&#xff0c;特点是数据量大、种类多、实时性强、数据蕴藏的价值大。大数据是对大量、动态、能持续的数据&#xff0c;通过运用分析、挖掘和整理&#xff0c;实现数据信息…
阅读更多...
keil5 查看stm32 寄存器的值

keil5 查看stm32 寄存器的值

1 查看芯片内部寄存器的值&#xff0c;首先是在仿真状态下&#xff0c;首先仿真&#xff0c;程序运行。 2 点击菜单栏的 View -> System viewer &#xff0c;右侧便会出现芯片的所有寄存器(如果没有&#xff0c;需要添加)&#xff0c;点击要查看的寄存器&#xff0c;便会出…
阅读更多...
ARM安装与项目结构

ARM安装与项目结构

1. 安装环境 参考E:\peixunQianrushi\arm\ziliao\FS4412新版&#xff08;学生资料&#xff09;\环境相关资料 这边建议全部默认路径 安装注意事项&#xff1a; 1、在接下来的安装过程中&#xff0c;对于使用win10、win8的操作系统的用户&#xff0c;所有的安装请均以管理员身份…
阅读更多...
014-信息打点-JS架构框架识别泄漏提取API接口枚举FUZZ爬虫插件项目

014-信息打点-JS架构框架识别泄漏提取API接口枚举FUZZ爬虫插件项目

014-信息打点-JS架构&框架识别&泄漏提取&API接口枚举&FUZZ爬虫&插件项目 #知识点&#xff1a; 1、JS前端架构-识别&分析 2、JS前端架构-开发框架分析 3、JS前端架构-打包器分析 4、JS前端架构-提取&FUZZ 解决&#xff1a; 1、如何从表现中的JS提取…
阅读更多...
pytorch（二）梯度下降算法

pytorch（二）梯度下降算法

文章目录 优化问题梯度下降随机梯度下降 在线性模型训练的时候&#xff0c;一开始并不知道w的最优值是什么&#xff0c;可以使用一个随机值来作为w的初始值&#xff0c;使用一定的算法来对w进行更新 优化问题 寻找使得目标函数最优的权重组合的问题就是优化问题 梯度下降 通…
阅读更多...
Canvas-Editor 实现类似 Word 协同编辑

Canvas-Editor 实现类似 Word 协同编辑

前言 对于word的协同编辑&#xff0c;已经构思很久了&#xff0c;但是没有找到合适的插件。今天推荐基于canvas/svg 的富文本编辑器 canvas-editor&#xff0c;能实现类似word的基础功能&#xff0c;如果后续有更好的&#xff0c;也会及时更新。 Canvas-Editor 效果图 官方文…
阅读更多...
终极解决Flutter项目运行ios项目报错Without CocoaPods, plugins will not work on iOS or macOS.

终极解决Flutter项目运行ios项目报错Without CocoaPods, plugins will not work on iOS or macOS.

前言 最近在开发Flutter项目&#xff0c;运行ios环境的时候报错没有CocoaPods&#xff0c;安卓环境可以正常运行&#xff0c;当时一脸懵逼&#xff0c;网上搜索了一下&#xff0c;有给我讲原理的&#xff0c;还有让我安装这插件那插件的&#xff0c;最终把电脑搞得卡死&#x…
阅读更多...
【spring】代码生成器

【spring】代码生成器

&#x1f4dd;个人主页&#xff1a;五敷有你 &#x1f525;系列专栏&#xff1a;spring ⛺️稳中求进&#xff0c;晒太阳 代码生成器&#xff08;本质IO流&#xff09; 在mybatis的逆向工程生成model和mapper接口和xml文件后&#xff0c;还需要反复的写Service的接口和…
阅读更多...
UE5 C++学习笔记 FString FName FText相互转换

UE5 C++学习笔记 FString FName FText相互转换

1.FString 是UE里的String。最接近std::string, 唯一可以修改的字符串类型。性能更低 TEXT(string) TEXT宏&#xff0c;作用是将字符串转换成Unicode&#xff0c;切记UE中使用字符串输出要使用该宏 2. FName 是UE里特有的类型。它更注重于表示名称不区分大小写&#xff0c;不…
阅读更多...
元数据管理在数据仓库中的实践应用

元数据管理在数据仓库中的实践应用

一、什么是数据仓库的元数据管理？ 1、什么是元数据？ 元数据（Metadata），又称中介数据、中继数据，为描述数据的数据（data about data）。 抽象的描述：一组用于描述数据的数据组，该数据组的一切信息都描述了该数据的某方面特征，则该数据组即可被称为元数据。 举几个…
阅读更多...
MyBatis的逆向工程的创建，generator插件的使用和可能出现的一些问题，生成的实体类多出.java 1 .java 2这种拓展文件的处理方案

MyBatis的逆向工程的创建，generator插件的使用和可能出现的一些问题，生成的实体类多出.java 1 .java 2这种拓展文件的处理方案

目录 创建逆向工程的步骤 ①添加依赖和插件 ②创建MyBatis的核心配置文件 ③创建逆向工程的配置文件 ④执行MBG插件的generate目标 数据库版本8有可能出现的问题&#xff1a; 1、生成的实体类多了.java 1 .java 2的拓展文件... 2、生成的属性与表中字段不匹配&#xff…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023