C++跳表实现详解（从零开始构建高效有序集合）

什么是跳表？

跳表由 William Pugh 在 1989 年提出，其核心思想是“用空间换时间”。底层是一个普通的有序链表，上层则是“快速通道”，每一层都跳过若干元素，从而加速查找过程。

例如，在最底层（第0层），你可能有 1 → 3 → 4 → 7 → 9；而在第1层，可能是 1 → 4 → 9；第2层可能是 1 → 9。这样，查找 7 时，先在高层快速定位到 4 和 9 之间，再下降到低层精确查找。

跳表的核心操作

跳表支持三种基本操作：

• 查找（Search）
• 插入（Insert）
• 删除（Delete）

这些操作的平均时间复杂度均为 O(log n)，与平衡二叉搜索树相当。

C++ 跳表实现步骤

我们将围绕 C++有序集合 的需求，逐步构建跳表。

1. 定义节点结构

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

struct SkipListNode {    int val;    std::vector<SkipListNode*> next; // 每一层的下一个节点指针    SkipListNode(int value, int level) : val(value), next(level, nullptr) {}};

2. 跳表类定义

class SkipList {private:    static const double PROBABILITY; // 决定新层生成的概率    static const int MAX_LEVEL;      // 最大层数    SkipListNode* head;              // 头节点（哨兵）    int currentLevel;                // 当前实际最大层数    int randomLevel();               // 随机生成层数public:    SkipList();    ~SkipList();    bool search(int target);    void insert(int value);    bool erase(int value);};const double SkipList::PROBABILITY = 0.5;const int SkipList::MAX_LEVEL = 16;

3. 随机层数生成函数

使用抛硬币方式决定新节点的层数（每层以 50% 概率继续向上）。

int SkipList::randomLevel() {    int level = 1;    while ((rand() & 1) && level < MAX_LEVEL) {        level++;    }    return level;}

4. 查找操作

从最高层开始，逐层向右或向下移动。

bool SkipList::search(int target) {    SkipListNode* current = head;    for (int i = currentLevel - 1; i >= 0; i--) {        while (current->next[i] != nullptr && current->next[i]->val < target) {            current = current->next[i];        }    }    current = current->next[0];    return (current != nullptr && current->val == target);}

5. 插入操作

插入时需记录每层的前驱节点，以便更新指针。

void SkipList::insert(int value) {    std::vector<SkipListNode*> update(MAX_LEVEL, head);    SkipListNode* current = head;    // 从顶层向下查找插入位置    for (int i = currentLevel - 1; i >= 0; i--) {        while (current->next[i] != nullptr && current->next[i]->val < value) {            current = current->next[i];        }        update[i] = current;    }    // 若已存在，不重复插入    if (current->next[0] != nullptr && current->next[0]->val == value)        return;    int newLevel = randomLevel();    if (newLevel > currentLevel) {        for (int i = currentLevel; i < newLevel; i++) {            update[i] = head;        }        currentLevel = newLevel;    }    SkipListNode* newNode = new SkipListNode(value, newLevel);    for (int i = 0; i < newLevel; i++) {        newNode->next[i] = update[i]->next[i];        update[i]->next[i] = newNode;    }}

6. 删除操作

类似插入，先找到目标，再更新各层指针。

bool SkipList::erase(int value) {    std::vector<SkipListNode*> update(MAX_LEVEL, nullptr);    SkipListNode* current = head;    for (int i = currentLevel - 1; i >= 0; i--) {        while (current->next[i] != nullptr && current->next[i]->val < value) {            current = current->next[i];        }        update[i] = current;    }    current = current->next[0];    if (current == nullptr || current->val != value)        return false;    for (int i = 0; i < currentLevel; i++) {        if (update[i]->next[i] != current)            break;        update[i]->next[i] = current->next[i];    }    delete current;    // 降低当前层数（如果顶层为空）    while (currentLevel > 1 && head->next[currentLevel - 1] == nullptr) {        currentLevel--;    }    return true;}

完整初始化与析构

SkipList::SkipList() : currentLevel(1) {    head = new SkipListNode(0, MAX_LEVEL);    srand(time(nullptr)); // 初始化随机种子}SkipList::~SkipList() {    // 简单释放所有节点（可优化为逐层释放）    while (head->next[0] != nullptr) {        SkipListNode* temp = head->next[0];        head->next[0] = temp->next[0];        delete temp;    }    delete head;}

总结

通过以上步骤，我们完成了一个功能完整的 C++跳表实现。跳表不仅性能优秀，而且代码清晰易懂，非常适合用于实现 跳表插入删除 高频的场景，如 Redis 的有序集合（ZSET）就采用了跳表。

掌握 跳表数据结构 是提升 C++ 编程能力的重要一步。希望本教程能帮助你从零开始理解并实现跳表！