skiplist c++

跳表（Skiplist）是一种基于链表实现的数据结构，用于快速查找和插入有序序列中的元素。它是一种随机化数据结构，可以在O(log n)的时间内完成查找、插入和删除操作。

以下是一个简单的C++实现示例：

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

using namespace std;

const int MAX_LEVEL = 16; // 最大层数

class Node {
public:
    int key;
    Node **forward;

    Node(int level, int key) {
        forward = new Node*[level+1];
        memset(forward, 0, sizeof(Node*)*(level+1));
        this->key = key;
    }

    ~Node() {
        delete[] forward;
    }
};

class SkipList {
public:
    SkipList() {
        levelCount = 1;
        head = new Node(MAX_LEVEL, 0);
        srand(time(0));
    }

    ~SkipList() {
        delete head;
    }

    int randomLevel() {
        int level = 1;
        while (rand() % 2 == 1 && level < MAX_LEVEL)
            level++;
        return level;
    }

    void insert(int key) {
        Node *update[MAX_LEVEL+1];
        memset(update, 0, sizeof(Node*)*(MAX_LEVEL+1));
        Node *p = head;
        for (int i = levelCount; i >= 1; i--) {
            while (p->forward[i] != nullptr && p->forward[i]->key < key)
                p = p->forward[i];
            update[i] = p;
        }
        p = p->forward[1];
        if (p != nullptr && p->key == key)
            return;
        int level = randomLevel();
        if (level > levelCount) {
            for (int i = levelCount+1; i <= level; i++)
                update[i] = head;
            levelCount = level;
        }
        p = new Node(level, key);
        for (int i = 1; i <= level; i++) {
            p->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = p;
        }
    }

    void remove(int key) {
        Node *update[MAX_LEVEL+1];
        memset(update, 0, sizeof(Node*)*(MAX_LEVEL+1));
        Node *p = head;
        for (int i = levelCount; i >= 1; i--) {
            while (p->forward[i] != nullptr && p->forward[i]->key < key)
                p = p->forward[i];
            update[i] = p;
        }
        p = p->forward[1];
        if (p == nullptr || p->key != key)
            return;
        for (int i = 1; i <= levelCount; i++) {
            if (update[i]->forward[i] != p)
                break;
            update[i]->forward[i] = p->forward[i];
        }
        delete p;
        while (levelCount > 1 && head->forward[levelCount] == nullptr)
            levelCount--;
    }

    bool search(int key) {
        Node *p = head;
        for (int i = levelCount; i >= 1; i--) {
            while (p->forward[i] != nullptr && p->forward[i]->key < key)
                p = p->forward[i];
        }
        p = p->forward[1];
        if (p != nullptr && p->key == key)
            return true;
        return false;
    }

    void display() {
        for (int i = 1; i <= levelCount; i++) {
            Node *p = head->forward[i];
            cout << "Level " << i << ": ";
            while (p != nullptr) {
                cout << p->key << " ";
                p = p->forward[i];
            }
            cout << endl;
        }
    }

private:
    Node *head;
    int levelCount;
};

int main() {
    SkipList skiplist;

    skiplist.insert(1);
    skiplist.insert(3);
    skiplist.insert(2);
    skiplist.insert(4);
    skiplist.display();

    skiplist.remove(3);
    skiplist.display();

    cout << skiplist.search(2) << endl;
    cout << skiplist.search(3) << endl;

    return 0;
}

在这个示例中，我们使用了一个类`Node`作为跳表中的节点，`SkipList`类则封装了跳表的插入、删除、搜索和显示等操作。其中，`randomLevel()`函数用于随机生成节点的层数，`insert()`函数用于插入一个节点，`remove()`函数用于删除一个节点，`search()`函数用于查找一个节点，`display()`函数用于显示整个跳表。

跳表是一种比较高级的数据结构，它可以在很多场景中代替平衡树，以提高数据结构操作的效率。如果你对跳表感兴趣，可以尝试阅读一些更深入的资料来了解更多。