c++中如何实现跳表_c++跳表实现方法-C++-PHP中文网

c++中如何实现跳表_c++跳表实现方法

下次还敢

发布： 2025-10-04 18:35:01

原创

867人浏览过

跳表通过多层链表实现，每层为下一层的索引，查找从顶层开始逐层下降，平均时间复杂度O(log n)。节点包含值和多级指针，插入时随机生成层数并更新各级指针，删除时调整路径上指针并释放节点，支持高效增删查操作。

c++中如何实现跳表_c++跳表实现方法

跳表（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 v, int level) : value(v), forward(level, nullptr) {}

登录后复制

};

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

跳表类的实现

实现插入、删除、查找等核心操作。维护最大层数和当前层数。

爱图表

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

查看详情

class SkipList {
private:
    static const int MAX_LEVEL = 16;
    SkipListNode* head;
    int currentLevel;
<pre class='brush:php;toolbar:false;'>int randomLevel() {
    int level = 1;
    while (rand() % 2 == 0 && level < MAX_LEVEL) {
        level++;
    }
    return level;
}

登录后复制

public: SkipList() { srand(time(nullptr)); currentLevel = 1; head = new SkipListNode(-1, MAX_LEVEL); }

void insert(int value) {
    std::vector<SkipListNode*> update(MAX_LEVEL, nullptr);
    SkipListNode* current = head;

    // 从最高层开始查找插入位置
    for (int i = currentLevel - 1; i >= 0; i--) {
        while (current->forward[i] != nullptr &&
               current->forward[i]->value < value) {
            current = current->forward[i];
        }
        update[i] = current;
    }

    current = current->forward[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* newNode = new SkipListNode(value, newNodeLevel);

    // 调整每层指针
    for (int i = 0; i < newNodeLevel; i++) {
        newNode->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = newNode;
    }
}

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

void erase(int value) {
    std::vector<SkipListNode*> update(MAX_LEVEL, nullptr);
    SkipListNode* current = head;

    for (int i = currentLevel - 1; i >= 0; i--) {
        while (current->forward[i] != nullptr &&
               current->forward[i]->value < value) {
            current = current->forward[i];
        }
        update[i] = current;
    }

    current = current->forward[0];

    if (current == nullptr || current->value != value) {
        return; // 值不存在
    }

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

    delete current;

    // 更新当前最大层数
    while (currentLevel > 1 && head->forward[currentLevel - 1] == nullptr) {
        currentLevel--;
    }
}

void display() {
    for (int i = 0; i < currentLevel; i++) {
        SkipListNode* node = head->forward[i];
        std::cout << "Level " << i << ": ";
        while (node != nullptr) {
            std::cout << node->value << " ";
            node = node->forward[i];
        }
        std::cout << std::endl;
    }
}

登录后复制

};

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

使用示例

测试跳表的基本功能：

int main() {
    SkipList skiplist;
    skiplist.insert(3);
    skiplist.insert(6);
    skiplist.insert(7);
    skiplist.insert(9);
    skiplist.insert(2);
    skiplist.insert(4);
<pre class='brush:php;toolbar:false;'>skiplist.display();

std::cout << "Search 6: " << (skiplist.search(6) ? "Found" : "Not found") << std::endl;
std::cout << "Search 5: " << (skiplist.search(5) ? "Found" : "Not found") << std::endl;

skiplist.erase(6);
std::cout << "After deleting 6:" << std::endl;
skiplist.display();

return 0;

登录后复制

}

基本上就这些。这个实现涵盖了跳表的核心逻辑：随机生成层数、多层索引查找、插入时路径记录、删除时指针调整。适合学习和基础使用。实际应用中可根据需要扩展泛型支持、内存管理等。

以上就是c++++中如何实现跳表_c++跳表实现方法的详细内容，更多请关注php中文网其它相关文章！