c++怎么实现一个跳表(Skip List)_C++高效数据结构与跳表实现指南

技术教程
2025-11-10 10:32:03

跳表通过多层链表实现快速查找，C++中以随机层级和指针数组构建，支持高效插入、删除与搜索，平均时间复杂度O(log n)，代码简洁但需注意线程安全。

c++怎么实现一个跳表(skip list)_c++高效数据结构与跳表实现指南

跳表（Skip List）是一种基于概率的动态数据结构，用来快速查找、插入和删除元素，平均时间复杂度为 O(log n)。相比平衡树，跳表实现更简单，同时具备良好的性能。在C++中实现跳表，需要理解其层级链表结构和随机层级生成机制。

跳表的基本原理

跳表通过多层链表实现快速跳跃访问：

底层是有序链表，包含所有元素
每一层都是下一层的“快照”，只包含部分节点
查找时从顶层开始，横向跳跃，遇到更大值则下降一层
每个节点有一定概率晋升到上一层（通常为50%）

定义跳表节点结构

每个节点包含多个向右指针，层数在创建时随机决定：

template <typename K, typename V>
class SkipListNode {
public:
    K key;
    V value;
    std::vector<SkipListNode*> forward;
<pre class='brush:php;toolbar:false;'>SkipListNode(K k, V v, int level)
    : key(k), value(v), forward(level, nullptr) {}

};

说明： forward 是一个指针数组，forward[i] 指向第 i 层的下一个节点。

跳表类的基本框架

实现核心操作：查找、插入、删除、层级生成等：

template <typename K, typename V>
class SkipList {
private:
    static const int MAX_LEVEL = 16;
    int currentLevel;
    SkipListNode<K, V>* header;
<pre class='brush:php;toolbar:false;'>int randomLevel();
void displayList();

public: SkipList(); ~SkipList();

SkipListNode<K,V>* search(K key);
void insert(K key, V value);
void remove(K key);
void display();

};

关键成员解释：

MAX_LEVEL： 最大层数限制，避免无限增长
currentLevel： 当前跳表最高非空层
header： 头节点，每层都有一个指向第一个有效节点的指针

随机生成节点层级

使用随机数决定新节点应有多少层：

template <typename K, typename V>
int SkipList<K, V>::randomLevel() {
    int level = 1;
    while (rand() % 2 && level < MAX_LEVEL) {
        level++;
    }
    return level;
}

说明： 每次有50%的概率继续向上加一层，直到达到最大限制。

Otter.ai

一个自动的会议记录和笔记工具，会议内容生成和实时转录

141 查看详情 Otter.ai

查找操作实现

从顶层开始，向右走到底再往下走：

template <typename K, typename V>
SkipListNode<K,V>* SkipList<K, V>::search(K key) {
    SkipListNode<K,V>* curr = header;
    for (int i = currentLevel; i >= 1; i--) {
        while (curr->forward[i] && curr->forward[i]->key < key) {
            curr = curr->forward[i];
        }
    }
    curr = curr->forward[1];
    if (curr && curr->key == key) {
        return curr;
    }
    return nullptr;
}

插入操作详解

先搜索路径记录每层最后到达的节点，再逐层更新指针：

template <typename K, typename V>
void SkipList<K, V>::insert(K key, V value) {
    std::vector<SkipListNode<K,V>*> update(MAX_LEVEL + 1, nullptr);
    SkipListNode<K,V>* curr = header;
<pre class='brush:php;toolbar:false;'>for (int i = currentLevel; i >= 1; i--) {
    while (curr->forward[i] && curr->forward[i]->key < key) {
        curr = curr->forward[i];
    }
    update[i] = curr;
}

curr = curr->forward[1];

if (curr && curr->key == key) {
    curr->value = value;
    return;
}

int newLevel = randomLevel();
if (newLevel > currentLevel) {
    for (int i = currentLevel + 1; i <= newLevel; i++) {
        update[i] = header;
    }
    currentLevel = newLevel;
}

SkipListNode<K,V>* newNode = new SkipListNode<;K,V>(key, value, newLevel);

for (int i = 1; i <= newLevel; i++) {
    newNode->forward[i] = update[i]->forward[i];
    update[i]->forward[i] = newNode;
}

}

删除节点操作

找到节点后，将其从各层链表中移除，并清理空层：

template <typename K, typename V>
void SkipList<K, V>::remove(K key) {
    std::vector<SkipListNode<K,V>*> update(MAX_LEVEL + 1, nullptr);
    SkipListNode<K,V>* curr = header;
<pre class='brush:php;toolbar:false;'>for (int i = currentLevel; i >= 1; i--) {
    while (curr->forward[i] && curr->forward[i]->key < key) {
        curr = curr->forward[i];
    }
    update[i] = curr;
}

curr = curr->forward[1];
if (!curr || curr->key != key) return;

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

delete curr;

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

}

构造与析构函数

初始化头节点并释放内存：

template <typename K, typename V>
SkipList<K, V>::SkipList() : currentLevel(1) {
    header = new SkipListNode<K,V>(K(), V(), MAX_LEVEL);
}
<p>template <typename K, typename V>
SkipList<K, V>::~SkipList() {
SkipListNode<K,V><em> curr = header->forward[1];
while (curr) {
SkipListNode<K,V></em> next = curr->forward[1];
delete curr;
curr = next;
}
delete header;
}</p>

打印跳表结构

便于调试，显示每层节点：

template <typename K, typename V>
void SkipList<K, V>::display() {
    for (int i = currentLevel; i >= 1; i--) {
        SkipListNode<K,V>* node = header->forward[i];
        std::cout << "Level " << i << ": ";
        while (node) {
            std::cout << node->key << "(" << node->value << ") ";
            node = node->forward[i];
        }
        std::cout << std::endl;
    }
}

基本上就这些。C++实现跳表的关键在于管理多级指针和维护搜索路径。虽然不如STL中的set/map底层高效（红黑树或B+树），但跳表代码清晰、易于扩展（如支持范围查询、计数等），适合学习和特定场景使用。注意线程安全问题，若需并发访问，应添加锁机制。

以上就是c++++怎么实现一个跳表(Skip List)_C++高效数据结构与跳表实现指南的详细内容，更多请关注其它相关文章！