c++怎么实现一个跳表_c++跳表实现方法-C++-PHP中文网

c++怎么实现一个跳表_c++跳表实现方法

冰火之心

发布： 2025-10-12 10:49:01

原创

527人浏览过

跳表通过多层链表实现高效查找，平均时间复杂度O(log n)；节点含多级指针，插入时随机生成层级，C++实现包含头节点、层级控制与概率参数。

c++怎么实现一个跳表_c++跳表实现方法

跳表（Skip List）是一种基于链表的数据结构，通过多层索引提升查找效率，平均时间复杂度为 O(log n)。它结合了链表的插入删除效率和二分查找的速度优势。在 C++ 中实现跳表，主要涉及节点设计、层级随机生成、查找、插入和删除操作。

跳表节点结构设计

每个节点包含多个向右的指针，层数在创建时随机决定。通常用一个最大层级限制来控制空间开销。

struct SkipListNode { int key; int value; std::vector forward; // 每一层的下一个节点指针

SkipListNode(int k, int v, int level) : key(k), value(v), forward(level, nullptr) {}

登录后复制

};

forward 数组保存每一层的后继指针，level 决定该节点参与的层数。

跳表类基本结构

定义跳表类，包含最大层级、当前最高层级、概率因子等参数。

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

class SkipList { private: static const int MAX_LEVEL = 16; int level; float p; SkipListNode* head;

int randomLevel();

登录后复制

public:
SkipList(float prob = 0.5);
~SkipList();

void insert(int key, int value);  
bool search(int key, int& value);  
bool remove(int key);  
void display();

登录后复制

};

head 是一个虚拟头节点，其 forward 数组长度为 MAX_LEVEL，初始所有层都指向 null。

随机层级生成

用于控制新节点的层数，避免退化成普通链表。

int SkipList::randomLevel() { int lvl = 1; while ((rand() % 2)

以概率 p 向上增加一层，通常 p 取 0.5，这样大约一半的节点出现在下一层。

查找操作

从最高层开始，向右向下查找目标键。

爱图表

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

查看详情

bool SkipList::search(int key, int& value) { SkipListNode* current = head;

for (int i = level; i >= 0; i--) {  
    while (current->forward[i] != nullptr && current->forward[i]->key < key) {  
        current = current->forward[i];  
    }  
}  

current = current->forward[0];  
if (current != nullptr && current->key == key) {  
    value = current->value;  
    return true;  
}  
return false;

登录后复制

}

利用高层快速跳跃，逐步逼近目标位置。

插入操作

先查找插入位置，记录每层最后一个节点，再创建新节点并更新指针。

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

for (int i = level; i >= 0; i--) {  
    while (current->forward[i] && current->forward[i]->key < key) {  
        current = current->forward[i];  
    }  
    update[i] = current;  
}  

current = current->forward[0];  

if (current && current->key == key) {  
    current->value = value;  // 已存在，更新值  
    return;  
}  

int newLevel = randomLevel();  

if (newLevel > level) {  
    for (int i = level + 1; i <= newLevel; i++) {  
        update[i] = head;  
    }  
    level = newLevel;  
}  

SkipListNode* newNode = new SkipListNode(key, value, newLevel);  

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

登录后复制

}

update 数组保存路径，便于后续指针调整。

删除操作

查找到节点后，逐层断开连接并释放内存。

bool SkipList::remove(int key) { std::vector update(MAX_LEVEL, nullptr); SkipListNode* current = head;

for (int i = level; i >= 0; i--) {  
    while (current->forward[i] && current->forward[i]->key < key) {  
        current = current->forward[i];  
    }  
    update[i] = current;  
}  

current = current->forward[0];  

if (current == nullptr || current->key != key) {  
    return false;  
}  

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

delete current;  

while (level > 0 && head->forward[level] == nullptr) {  
    level--;  
}  

return true;

登录后复制

}

清理无效高层，保持结构紧凑。