c++怎么实现一个跳表(skip list)_c++跳表结构与查找算法实现-C++-PHP中文网

c++怎么实现一个跳表(skip list)_c++跳表结构与查找算法实现

穿越時空

发布： 2025-10-24 19:09:02

原创

202人浏览过

跳表通过多层链表实现，查找、插入、删除平均时间复杂度为O(log n)；其结构由带指针数组的节点组成，每层为上层快照，随机决定层数以控制索引密度；C++实现包含头节点、最大层数、当前层数及随机生成器；查找从顶层开始逐层下降定位目标；插入时记录路径并更新各层指针，新节点层数由randomLevel()按50%概率递增确定；若新节点层数超过当前层数，则补全更新数组并将当前层数提升；删除时先查找节点，断开其在各层连接，同时检查并降低空层的当前层数；整体实现简单高效，适合有序数据操作且优于平衡树的复杂性，但需注意边界处理与重复值判断。

c++怎么实现一个跳表(skip list)_c++跳表结构与查找算法实现

跳表（Skip List）是一种基于链表的数据结构，通过多层索引提升查找效率，平均时间复杂度为 O(log n)。相比平衡树，跳表实现更简单，且易于插入和删除。下面介绍 C++ 中跳表的结构设计与查找、插入、删除算法的实现。

跳表的基本结构

跳表由多层链表组成，底层是有序链表，每一层是上一层的“快照”，包含部分节点。每个节点有多个指针，指向同一层的下一个节点。

定义节点结构时，需要存储值和一个指针数组，用于指向每一层的下一个节点：

template <typename T>
struct SkipListNode {
    T value;
    std::vector<SkipListNode*> next;
<pre class='brush:php;toolbar:false;'>SkipListNode(T val, int level) : value(val), next(level, nullptr) {}

登录后复制

};

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

跳表类的设计与参数

跳表类包含最大层数、当前层数、头节点以及随机数生成器。插入时通过随机函数决定节点层数，控制索引密度。

template <typename T>
class SkipList {
private:
    int maxLevel;
    int currentLevel;
    SkipListNode<T>* head;
    std::default_random_engine generator;
    std::uniform_int_distribution<int> distribution;
<pre class='brush:php;toolbar:false;'>int randomLevel();

登录后复制

public: SkipList(int maxLvl = 16); ~SkipList();

void insert(T value);
bool search(T value);
bool remove(T value);

登录后复制

};

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

构造函数初始化头节点，其指针数组大小为最大层数：

template <typename T>
SkipList<T>::SkipList(int maxLvl)
    : maxLevel(maxLvl), currentLevel(1), 
      distribution(0, 1) {
    head = new SkipListNode<T>(T(), maxLevel);
}

登录后复制

查找操作实现

从最高层开始，向右移动直到下一个节点值大于目标，然后下降一层继续，直到找到目标或到达底层。

爱图表

AI驱动的智能化图表创作平台

查看详情

template <typename T>
bool SkipList<T>::search(T value) {
    SkipListNode<T>* current = head;
<pre class='brush:php;toolbar:false;'>for (int i = currentLevel - 1; i >= 0; i--) {
    while (current->next[i] != nullptr 
           && current->next[i]->value < value) {
        current = current->next[i];
    }
}

current = current->next[0];
return current != nullptr && current->value == value;

登录后复制

}

插入操作与随机层数

先查找插入位置，记录每层最后访问的节点，再创建新节点并链接到各层。

randomLevel() 函数以 50% 概率增加一层：

template <typename T>
int SkipList<T>::randomLevel() {
    int lvl = 1;
    while (distribution(generator) == 0 && lvl < maxLevel) {
        lvl++;
    }
    return lvl;
}

登录后复制

insert() 实现：

template <typename T>
void SkipList<T>::insert(T value) {
    std::vector<SkipListNode<T>*> update(maxLevel, nullptr);
    SkipListNode<T>* current = head;
<pre class='brush:php;toolbar:false;'>for (int i = currentLevel - 1; i >= 0; i--) {
    while (current->next[i] != nullptr 
           && current->next[i]->value < value) {
        current = current->next[i];
    }
    update[i] = current;
}

current = current->next[0];
if (current != nullptr && current->value == value) {
    return; // 已存在
}

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

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

登录后复制

}

删除操作

查找节点并断开其在每一层的连接，若某层无节点则降低当前层数。

template <typename T>
bool SkipList<T>::remove(T value) {
    std::vector<SkipListNode<T>*> update(maxLevel, nullptr);
    SkipListNode<T>* current = head;
<pre class='brush:php;toolbar:false;'>for (int i = currentLevel - 1; i >= 0; i--) {
    while (current->next[i] != nullptr 
           && current->next[i]->value < value) {
        current = current->next[i];
    }
    update[i] = current;
}

current = current->next[0];
if (current == nullptr || current->value != 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;

登录后复制

}

基本上就这些。跳表用空间换时间，实现比红黑树简单，适合需要有序数据但不想写复杂平衡逻辑的场景。注意随机层数策略影响性能稳定性，实际使用可调整概率。不复杂但容易忽略边界条件，比如空指针和重复值处理。

以上就是c++++怎么实现一个跳表(skip list)_c++跳表结构与查找算法实现的详细内容，更多请关注php中文网其它相关文章！