C++面试：跳表

2024-01-23 11:04
文章标签 c++ 面试 跳表

本文主要是介绍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. 高效的动态排序： 在需要频繁的动态排序操作的场景下，跳表的性能可能优于传统的排序算法。

总体评价:

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

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

这篇关于C++面试：跳表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


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

相关文章

字节面试 | 如何测试RocketMQ、RocketMQ？

字节面试 | 如何测试RocketMQ、RocketMQ？

字节面试：RocketMQ是怎么测试的呢？ 答： 首先保证消息的消费正确、设计逆向用例，在验证消息内容为空等情况时的消费正确性； 推送大批量MQ，通过Admin控制台查看MQ消费的情况，是否出现消费假死、TPS是否正常等等问题。（上述都是临场发挥，但是RocketMQ真正的测试点，还真的需要探讨） 01 先了解RocketMQ 作为测试也是要简单了解RocketMQ。简单来说，就是一个分
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
06 C++Lambda表达式

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获：包含零个或者多个捕获符的逗号分隔列表 模板形参：用于泛型lambda提供个模板形参的名
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
【C++高阶】C++类型转换全攻略：深入理解并高效应用

【C++高阶】C++类型转换全攻略：深入理解并高效应用

📝个人主页🌹：Eternity._ ⏩收录专栏⏪：C++ “ 登神长阶 ” 🤡往期回顾🤡：C++ 智能指针 🌹🌹期待您的关注 🌹🌹 ❀C++的类型转换 📒1. C语言中的类型转换📚2. C++强制类型转换⛰️static_cast🌞reinterpret_cast⭐const_cast🍁dynamic_cast 📜3. C++强制类型转换的原因📝
阅读更多...
C++——stack、queue的实现及deque的介绍

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2