探索跳表：一种高效的数据结构

在数据结构的世界里，跳表（Skip List）是一种非常独特且实用的数据结构，它能够在很多场景下高效地实现数据的查找、插入和删除操作，同时又有着相对简单的实现逻辑。今天，就让我们一起深入了解跳表，并附上用 C++ 实现的代码示例，方便大家更好地掌握这一有趣的数据结构。

阿贾克斯ajax0322

883人浏览 · 2024-12-23 23:38:43

阿贾克斯ajax0322 · 2024-12-23 23:38:43 发布

一、跳表的基本概念

跳表本质上是对有序链表的一种优化升级。我们都知道，普通的有序链表在进行查找操作时，时间复杂度往往是 O (n)，因为需要依次遍历链表节点来查找目标元素，这在数据量较大时效率会比较低下。而跳表通过 “跳跃” 的方式，构建了多层索引结构，使得查找操作能够快速地跳过一些不必要的节点，将查找的平均时间复杂度优化到了 O (log n)，极大地提高了效率。

想象一下，我们有一个很长的有序链表，跳表就像是在这个链表之上搭建了一些 “高架桥”，让我们可以快速地在不同位置 “跳跃”，更快地抵达目标节点所在的大致区域，然后再通过底层链表进行精确查找。

二、跳表的结构组成

跳表主要由多个层级的链表组成，最底层的链表包含了所有的数据节点，就如同普通的有序链表一样，每个节点存储着数据以及指向下一个节点的指针。而往上的每一层链表都是对下一层链表的一种 “稀疏索引”，节点数量相对更少，它们通过特定的规则从下一层链表中选取部分节点构建而成。

通常，跳表的每一层节点都会有一个指针指向下一层对应位置的节点，这样方便我们在查找过程中可以灵活地在各层之间 “穿梭”。而且，跳表中每个节点包含多个指针（一般有一个指向下一个同层节点的指针，还有一个或多个指向下一层对应节点的指针，取决于跳表的实现细节）。

三、跳表的操作原理

查找操作

当我们要查找一个元素时，首先从最顶层的链表开始，按照节点中的指针，快速向前 “跳跃”，一旦发现当前节点的下一个节点的值大于要查找的目标值时，就会下降到下一层链表继续查找，如此反复，直到在最底层链表中找到目标元素或者确定目标元素不存在为止。这种分层查找的方式，避免了对链表的全量遍历，大大加快了查找速度。

插入操作

插入操作稍微复杂一些。首先，需要通过查找操作找到要插入的位置，这个过程和前面说的查找类似，确定了合适的插入位置后，在最底层链表插入新的节点。然后，以一定的概率（这个概率通常是固定的，比如 1/2，不同的实现可以有所不同）决定是否将这个新节点 “提拔” 到上一层链表中，若决定提拔，就在上一层链表对应的位置也插入该节点，并且重复这个提拔的过程，直到不再需要提拔为止。

删除操作

删除操作同样要先通过查找确定要删除的节点是否存在。如果存在，就在每一层链表中找到对应的节点并删除，删除时要注意维护好各层链表的指针关系，确保整个跳表的结构依然正确且有序。

四、C++ 实现跳表示例代码

以下是一个简单的 C++ 跳表实现代码示例，这里为了简化，做了一些功能上的简化和特定的设计假设，主要是为了展示跳表的核心结构和操作实现思路。

#include <iostream>
#include <cstdlib>
#include <ctime>

// 定义跳表节点结构体
template<typename T>
struct SkipListNode {
    T data;
    SkipListNode** next;  // 指针数组，用于指向下一层节点
    SkipListNode(T value, int level) : data(value) {
        next = new SkipListNode*[level + 1];
        for (int i = 0; i <= level; ++i) {
            next[i] = nullptr;
        }
    }
};

// 跳表类定义
template<typename T>
class SkipList {
public:
    SkipList(int maxLevel = 16);
    ~SkipList();
    bool insert(T value);
    bool search(T value);
    bool remove(T value);

private:
    int randomLevel();
    int level;  // 当前跳表最大层级
    SkipListNode<T>* header;  // 头节点
};

// 跳表构造函数，初始化头节点和层级等
template<typename T>
SkipList<T>::SkipList(int maxLevel) : level(1), header(new SkipListNode<T>(T(), maxLevel)) {}

// 跳表析构函数，释放所有节点内存
template<typename T>
SkipList<T>::~SkipList() {
    SkipListNode<T>* current = header;
    SkipListNode<T>* next;
    while (current) {
        next = current->next[0];
        delete current;
        current = next;
    }
}

// 随机生成节点的层级，这里简单模拟以1/2概率提升层级
template<typename T>
int SkipList<T>::randomLevel() {
    int lvl = 1;
    while (rand() % 2 == 0 && lvl < level) {
        lvl++;
    }
    return lvl;
}

// 插入元素操作
template<typename T>
bool SkipList<T>::insert(T value) {
    SkipListNode<T>** update = new SkipListNode<T>*[level + 1];
    SkipListNode<T>* current = header;

    // 从顶层开始查找合适的插入位置
    for (int i = level; i >= 0; --i) {
        while (current->next[i] && current->next[i]->data < value) {
            current = current->next[i];
        }
        update[i] = current;
    }

    current = current->next[0];

    // 如果节点已存在，插入失败
    if (current && current->data == value) {
        delete[] update;
        return false;
    }

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

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

    delete[] update;
    return true;
}

// 查找元素操作
template<typename T>
bool SkipList<T>::search(T value) {
    SkipListNode<T>* current = header;
    for (int i = level; i >= 0; --i) {
        while (current->next[i] && current->next[i]->data < value) {
            current = current->next[i];
        }
    }
    current = current->next[0];
    return current && current->data == value;
}

// 删除元素操作
template<typename T>
bool SkipList<T>::remove(T value) {
    SkipListNode<T>** update = new SkipListNode<T>*[level + 1];
    SkipListNode<T>* current = header;

    // 查找要删除的节点位置
    for (int i = level; i >= 0; --i) {
        while (current->next[i] && current->next[i]->data < value) {
                current = current->next[i];
            }
            update[i] = current;
    }

    current = current->next[0];
    if (!current || current->data!= value) {
        delete[] update;
        return false;
    }

    // 从各层链表中删除节点
    for (int i = 0; i <= level && update[i]->next[i] == current; ++i) {
        update[i]->next[i] = current->next[i];
    }

    delete current;

    // 检查是否需要降低最大层级
    while (level > 0 && header->next[level] == nullptr) {
        level--;
    }

    delete[] update;
    return true;
}

你可以使用以下方式来测试这个跳表的功能：

int main() {
    srand(static_cast<unsigned int>(time(nullptr)));
    SkipList<int> skipList;
    skipList.insert(5);
    skipList.insert(3);
    skipList.insert(7);
    std::cout << "Search for 5: " << (skipList.search(5)? "Found" : "Not Found") << std::endl;
    std::cout << "Search for 4: " << (skipList.search(4)? "Found" : "Not Found") << std::endl;
    skipList.remove(5);
    std::cout << "Search for 5 after removal: " << (skipList.search(5)? "Found" : "Not Found") << std::endl;
    return 0;
}

在上述代码中：