c++怎么实现一个跳表（Skip List）_C++实现高效有序结构Skip List教程-C++-PHP中文网

c++怎么实现一个跳表（Skip List）_C++实现高效有序结构Skip List教程

穿越時空

发布： 2025-11-10 06:29:27

原创

462人浏览过

跳表通过多层链表实现高效查找、插入和删除，平均时间复杂度为O(log n)。1. 定义节点结构包含值和各级指针；2. 实现随机层数生成；3. 查找从顶层开始逐层下降；4. 插入时记录路径并更新各级指针；5. 删除时断开各层连接并调整当前层数。C++实现包括节点类、跳表类及核心操作函数，支持基本有序集合操作，适用于替代平衡树，尤其在并发场景下具优势。

c++怎么实现一个跳表（skip list）_c++实现高效有序结构skip list教程

跳表（Skip List）是一种基于链表的有序数据结构，通过多层索引实现接近 O(log n) 的查找、插入和删除效率。相比平衡树，跳表实现更简单且易于理解。下面详细介绍如何用 C++ 实现一个支持插入、删除和查找操作的跳表。

跳表基本原理

跳表本质是带多级指针的链表。每一层都是下一层的“快速通道”。最底层包含所有元素，上层以一定概率（通常为 50%）索引下层节点。查找时从顶层开始，横向移动直到下一个节点大于目标值，再下降一层继续，类似二分查找的链式版本。

定义节点结构

每个节点包含一个值和一个指向不同层级的指针数组。

#include <vector>
#include <cstdlib>
#include <ctime>
#include <iostream>
<p>struct SkipListNode {
int value;
std::vector<SkipListNode*> forward; // 每一层的下一个节点</p><pre class='brush:php;toolbar:false;'>SkipListNode(int val, int level) : value(val), forward(level, nullptr) {}

登录后复制

};

立即学习“C++免费学习笔记（深入）”；

实现跳表类

跳表类需要维护最大层数、当前层数、头节点以及随机层数生成函数。

class SkipList {
private:
    static const int MAX_LEVEL = 16;  // 最大层数
    SkipListNode* head;
    int currentLevel;
<pre class='brush:php;toolbar:false;'>// 随机生成节点层数，概率为 1/2
int randomLevel() {
    int level = 1;
    while (rand() % 2 == 0 && level < MAX_LEVEL) {
        level++;
    }
    return level;
}

登录后复制

public: SkipList() { srand(time(nullptr)); // 初始化随机种子 head = new SkipListNode(-1, MAX_LEVEL); currentLevel = 1; }

~SkipList() {
    SkipListNode* curr = head;
    while (curr) {
        SkipListNode* next = curr->forward[0];
        delete curr;
        curr = next;
    }
}

登录后复制

接下来实现核心操作：查找、插入、删除。

查找操作

从最高层开始，向右走直到下一个节点大于目标，然后下降一层继续，直到第0层。

ViiTor实时翻译

AI实时多语言翻译专家！强大的语音识别、AR翻译功能。

116

查看详情

bool search(int target) {
    SkipListNode* curr = head;
    for (int i = currentLevel - 1; i >= 0; i--) {
        while (curr->forward[i] && curr->forward[i]->value < target) {
            curr = curr->forward[i];
        }
    }
    curr = curr->forward[0];
    return curr && curr->value == target;
}

登录后复制

插入操作

先查找每层最后一个小于目标的位置，记录路径。若节点已存在则不插入；否则创建新节点并按随机层数连接。

void insert(int value) {
    std::vector<SkipListNode*> update(MAX_LEVEL, nullptr);
    SkipListNode* curr = head;
<pre class='brush:php;toolbar:false;'>for (int i = currentLevel - 1; i >= 0; i--) {
    while (curr->forward[i] && curr->forward[i]->value < value) {
        curr = curr->forward[i];
    }
    update[i] = curr;
}

curr = curr->forward[0];

if (curr && curr->value == value) {
    return; // 已存在，不重复插入
}

int newNodeLevel = randomLevel();
if (newNodeLevel > currentLevel) {
    for (int i = currentLevel; i < newNodeLevel; i++) {
        update[i] = head;
    }
    currentLevel = newNodeLevel;
}

SkipListNode* newNode = new SkipListNode(value, newNodeLevel);
for (int i = 0; i < newNodeLevel; i++) {
    newNode->forward[i] = update[i]->forward[i];
    update[i]->forward[i] = newNode;
}

登录后复制

}

删除操作

查找节点，若存在则逐层断开连接，并释放内存。如果删除的是最高层节点，需更新 currentLevel。

bool erase(int value) {
    std::vector<SkipListNode*> update(MAX_LEVEL, nullptr);
    SkipListNode* curr = head;
<pre class='brush:php;toolbar:false;'>for (int i = currentLevel - 1; i >= 0; i--) {
    while (curr->forward[i] && curr->forward[i]->value < value) {
        curr = curr->forward[i];
    }
    update[i] = curr;
}

curr = curr->forward[0];
if (!curr || curr->value != value) {
    return false; // 未找到
}

for (int i = 0; i < currentLevel; i++) {
    if (update[i]->forward[i] != curr) break;
    update[i]->forward[i] = curr->forward[i];
}

delete curr;

while (currentLevel > 1 && head->forward[currentLevel - 1] == nullptr) {
    currentLevel--;
}

return true;

登录后复制

}

测试示例

使用 main 函数验证功能：

int main() {
    SkipList list;
    list.insert(3);
    list.insert(6);
    list.insert(7);
    list.insert(9);
    list.insert(12);
<pre class='brush:php;toolbar:false;'>std::cout << std::boolalpha;
std::cout << "查找 6: " << list.search(6) << "\n";     // true
std::cout << "查找 8: " << list.search(8) << "\n";     // false

list.erase(6);
std::cout << "删除后查找 6: " << list.search(6) << "\n"; // false

return 0;

登录后复制

}

基本上就这些。这个跳表实现了基本的有序集合操作，平均时间复杂度为 O(log n)，适合替代部分场景下的 set 或 map，尤其在并发环境下有更好表现潜力（可分层加锁）。注意控制 MAX_LEVEL 防止空间浪费，实际应用中可根据数据规模调整。不复杂但容易忽略细节，比如更新 update 数组和 currentLevel 的逻辑。

以上就是c++++怎么实现一个跳表（Skip List）_C++实现高效有序结构Skip List教程的详细内容，更多请关注php中文网其它相关文章！