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();

        // 如果新的层数比当前层数高，则更新 update
        if (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();

        // 如果新的层数比当前层数高，则更新 update
        if (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. 高效的动态排序： 在需要频繁的动态排序操作的场景下，跳表的性能可能优于传统的排序算法。

总体评价:

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

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

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

排序（插入排序）

排序（插入排序）

现在&#xff0c;我们学习了之前数据结构的部分内容&#xff0c;即将进入一个重要的领域&#xff1a;排序&#xff0c;这是一个看起来简单&#xff0c;但是想要理清其中逻辑并不简单的内容&#xff0c;让我们一起加油把&#xff01; 排序的概念及其运用 排序的概念 排序&…
阅读更多...
激光雷达行业梳理1-概述、市场、技术路线

激光雷达行业梳理1-概述、市场、技术路线

激光雷达作为现代精确测距和感知技术的关键组成部分&#xff0c;在近几年里取得了令人瞩目的发展。作为自动驾驶感知层面的重要一环&#xff0c;相较摄像头、毫米波雷达等其他传感器具有“ 精准、快速、高效作业”的巨大优势&#xff0c;已成为自动驾驶的主传感器之一&#xff…
阅读更多...
CVHub|AI标注神器 X-AnyLabeling-v2.3.0 发布！支持YOLOv8旋转目标检测、EdgeSAM、RTMO等热门模型！

CVHub|AI标注神器 X-AnyLabeling-v2.3.0 发布！支持YOLOv8旋转目标检测、EdgeSAM、RTMO等热门模型！

本文来源公众号“CVHub”&#xff0c;仅用于学术分享&#xff0c;侵权删&#xff0c;干货满满。 原文链接&#xff1a;AI标注神器 X-AnyLabeling-v2.3.0 发布&#xff01;支持YOLOv8旋转目标检测、EdgeSAM、RTMO等热门模型&#xff01; 今天主要为大家详细介绍 X-AnyLabeling …
阅读更多...
NQA测试机制—UDP Jitter测试

NQA测试机制—UDP Jitter测试

概念 UDP Jitter是以UDP报文为承载&#xff0c;通过记录在报文中的时间戳信息来统计时延、抖动、丢包的一种测试方法。Jitter&#xff08;抖动时间&#xff09;是指相邻两个报文的接收时间间隔减去这两个报文的发送时间间隔。 UDP Jitter测试的过程如下&#xff1a; 1. 源端&a…
阅读更多...
【大数据处理技术实践】期末考查题目：集群搭建、合并文件与数据统计可视化

【大数据处理技术实践】期末考查题目：集群搭建、合并文件与数据统计可视化

集群搭建、合并文件与数据统计可视化 实验目的任务一&#xff1a;任务二&#xff1a; 实验平台实验内容及步骤任务一&#xff1a;搭建具有3个DataNode节点的HDFS集群集群环境配置克隆的方式创建 Slave 节点修改主机名编辑 hosts 文件生成密钥免认证登录修改 hadoop 的配置文件编…
阅读更多...
软件测试面试题（完整版）

软件测试面试题（完整版）

1、B/S架构和C/S架构区别 B/S 只需要有操作系统和浏览器就行&#xff0c;可以实现跨平台&#xff0c;客户端零维护&#xff0c;维护成本低&#xff0c;但是个性化能力低&#xff0c;响应速度较慢 C/S响应速度快&#xff0c;安全性强&#xff0c;一般应用于局域网中&#xff0c…
阅读更多...
DFT计算杂谈调查问卷

DFT计算杂谈调查问卷

为更好了解公众号受众对于DFT计算的了解情况以及目标需求&#xff0c;目的以更好更准确并实用地推送给公众号受众所需要的文章&#xff0c;所以本次推送发布调查问卷并收集填写者相关信息。 调查问卷调查内容仅与公众号运营和DFT计算相关&#xff0c;所收集信息仅用作公众号受众…
阅读更多...
== 和 equals：对象相等性比较的细微差别

== 和 equals：对象相等性比较的细微差别

和 equals&#xff1a;对象相等性比较的细微差别 既要脚踏实地于现实生活&#xff0c;又要不时跳出现实到理想的高台上张望一眼。在精神世界里建立起一套丰满的体系&#xff0c;引领我们不迷失不懈怠。待我们一觉醒来&#xff0c;跌落在现实中的时候&#xff0c;可以毫无怨言地…
阅读更多...
芋道--如何自定义业务表单，配置对应的工作流程(详细步骤)

芋道--如何自定义业务表单，配置对应的工作流程(详细步骤)

需求描述: 芋道的动态表单就不再介绍了&#xff0c;相对来讲比较简单,跟着官网文档就可以实现&#xff0c;本文将详细的介绍如何新建独立的业务表记录申请的信息&#xff0c;并设计对应的工作流。 这里表中的每一条记录&#xff0c;都将通过流程实例编号(process_instance_id )…
阅读更多...
HTML标题

HTML标题

我的HTML标题学习小记 HTML的标题功能真的非常实用&#xff01;它们就像是文章的大纲&#xff0c;帮助网页内容呈现出清晰的结构&#xff0c;也就是小题大作一番。 HTML标题的奥秘 在HTML中&#xff0c;我们使用<h1>至<h6>这些标签来定义标题。其中&#xff0c;…
阅读更多...
Java 设计者模式以及与Spring关系(六) 装饰和模版方法模式

Java 设计者模式以及与Spring关系(六) 装饰和模版方法模式

简介: 本文是个系列一次会出两个设计者模式作用&#xff0c;如果有关联就三个&#xff0c;除此外还会讲解在spring中作用。 23设计者模式以及重点模式 我们都知道设计者模式有3类23种设计模式&#xff0c;标红是特别重要的设计者模式建议都会&#xff0c;而且熟读于心&#…
阅读更多...
软件测试|SQL常用语法，你都会吗？

软件测试|SQL常用语法，你都会吗？

前言 SQL作为一门语言&#xff0c;和其他编程语言一样&#xff0c;都是需要遵循一些特定的规范和准则的&#xff0c;这也就是我们常说的语法&#xff08;Syntax&#xff09;。 下面是几个SQL的语法规则&#xff1a; 所有的 SQL 语法都必须以关键字&#xff08;也称命令&…
阅读更多...
图片有路人的部分怎么抠掉？看完你就会

图片有路人的部分怎么抠掉？看完你就会

在我们拍摄的照片中&#xff0c;常常会出现一些不想要的元素&#xff0c;比如路人、路边的垃圾桶、广告牌等等&#xff0c;有时候他们的出现可能会破坏照片的整体美感。那么&#xff0c;如何把图片中的路人部分抠掉呢&#xff1f;本文将为你详细介绍多种方法&#xff0c;帮助你…
阅读更多...
Java基础 - 09 Set之linkedHashSet , CopyOnWriteArraySet

Java基础 - 09 Set之linkedHashSet , CopyOnWriteArraySet

LinkedHashSet和CopyOnWriteArraySet都是Java集合框架提供的特殊集合类&#xff0c;他们在特定场景下有不同的用途和特点。 LinkedHashSet是Java集合框架中的一种实现类&#xff0c;它继承自HashSet并且保持插入顺序。它使用哈希表来存储元素&#xff0c;并使用链表来维护插入…
阅读更多...
让Mac与Windows合二为一：Microsoft Remote Desktop for Mac的魅力

让Mac与Windows合二为一：Microsoft Remote Desktop for Mac的魅力

在数字时代&#xff0c;远程连接已成为工作、学习和生活的必备工具。而Microsoft Remote Desktop for Mac正是这样一款能够让你随时随地&#xff0c;轻松连接到Windows系统的强大工具。 Microsoft Remote Desktop for Mac不仅提供了高效、稳定的远程访问体验&#xff0c;更凭借…
阅读更多...
aspose-cells-20.7.jar 去除水印及次数限制

aspose-cells-20.7.jar 去除水印及次数限制

1.使用 jd-gui.exe 反编译查看&#xff0c;直接搜索 License 1.修改 public static boolean isLicenseSet() {return (a ! null);}改成 public static boolean isLicenseSet() {return true;}2.修改 public void setLicense(InputStream stream) {Document document null;if (…
阅读更多...
Acwing-语法基础习题综合[难度：简单]

Acwing-语法基础习题综合[难度：简单]

目录 题目序号604&#xff1a; 圆的面积 题目序号605&#xff1a; 简单乘积 题目序号606&#xff1a; 平均数1 题目序号607&#xff1a; 平均数2 题目序号608&#xff1a; 差 题目序号609&#xff1a; 工资 题目序号611&#xff1a; 简单计算 题目序号612&#xff1a; …
阅读更多...
springboot 整合 ElasticSearch 方法 (一)

springboot 整合 ElasticSearch 方法 (一)

下载 ES 相当于安装 MySQL, 可以在官网上下载 (链接在后面). 要注意安装的 ES 的版本要和项目中用的 Springboot 的版本对应. 比如我用的 Springboot 版本是 2.6, 所以ES要下载7.15 版本的. 官网链接: https://www.elastic.co/cn/downloads/elasticsearch 点右边这个查看更多…
阅读更多...
Linux：动静态库的概念与制作使用

Linux：动静态库的概念与制作使用

文章目录 动静态库基础认知动静态库基本概念静态库的制作库的概念包的概念 静态库的使用第三方库小结 动态库的制作动态库的使用动态库如何找到内容&#xff1f;小结 本篇要谈论的内容是关于动静态库的问题&#xff0c;具体的逻辑框架是建立在库的制作&#xff0c;库的使用&…
阅读更多...
javaWebssh运动会管理系统myeclipse开发mysql数据库MVC模式java编程计算机网页设计

javaWebssh运动会管理系统myeclipse开发mysql数据库MVC模式java编程计算机网页设计

一、源码特点 java ssh运动会管理系统是一套完善的web设计系统&#xff08;系统采用ssh框架进行设计开发&#xff09;&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为TOMCAT7.0,M…
阅读更多...
最新文章

Copyright @ 2022~2023