C 实现跳跃表查找(Skip List Search)算法

C++实现跳跃表查找(Skip List Search)算法

以下是用 C++ 实现跳跃表查找(Skip List Search)算法的示例代码:

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

class Node {
public:
    int value;
    std::vector<Node*> forward;

    Node(int value, int level) : value(value), forward(level + 1, nullptr) {}
};

class SkipList {
public:
    SkipList(int maxLevel) : maxLevel(maxLevel), level(0), head(new Node(-1, maxLevel)) {
        srand(time(0));
    }

    void insert(int value) {
        std::vector<Node*> update(maxLevel + 1, nullptr);
        Node* current = head;

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

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

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

    bool search(int value) const {
        Node* current = head;
        for (int i = level; 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;
    }

private:
    int maxLevel;
    int level;
    Node* head;

    int randomLevel() const {
        int lvl = 0;
        while (rand() % 2 == 0 && lvl < maxLevel) {
            ++lvl;
        }
        return lvl;
    }
};

// 测试 SkipList 实现
int main() {
    SkipList skipList(16);

    skipList.insert(1);
    skipList.insert(3);
    skipList.insert(7);
    skipList.insert(8);
    skipList.insert(9);

    std::cout << "Search for 3: " << (skipList.search(3) ? "Found" : "Not Found") << std::endl; // Output: Found
    std::cout << "Search for 6: " << (skipList.search(6) ? "Found" : "Not Found") << std::endl; // Output: Not Found

    return 0;
}

这个 C++ 实现包含了以下主要部分:

  1. Node 类:表示跳跃表中的节点,包含一个值和一个指针数组。
  2. SkipList 类:包含插入和查找方法,以及一个用于生成随机层级的 randomLevel 方法。
  3. randomLevel 方法:生成一个随机的层级,用于新节点。
  4. insert 方法:在跳跃表中插入一个值,更新相应的指针。
  5. search 方法:在跳跃表中查找一个值,返回一个布尔值表示是否找到。
  6. main 函数:测试插入和查找功能。

这段代码展示了如何用 C++ 实现跳跃表的插入和查找功能。

C++实现跳跃表查找(Skip List Search)算法

以下是用 C++ 实现跳跃表查找(Skip List Search)算法的示例代码:

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

class Node {
public:
    int value;
    std::vector<Node*> forward;

    Node(int value, int level) : value(value), forward(level + 1, nullptr) {}
};

class SkipList {
public:
    SkipList(int maxLevel) : maxLevel(maxLevel), level(0), head(new Node(-1, maxLevel)) {
        srand(time(0));
    }

    void insert(int value) {
        std::vector<Node*> update(maxLevel + 1, nullptr);
        Node* current = head;

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

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

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

    bool search(int value) const {
        Node* current = head;
        for (int i = level; 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;
    }

private:
    int maxLevel;
    int level;
    Node* head;

    int randomLevel() const {
        int lvl = 0;
        while (rand() % 2 == 0 && lvl < maxLevel) {
            ++lvl;
        }
        return lvl;
    }
};

// 测试 SkipList 实现
int main() {
    SkipList skipList(16);

    skipList.insert(1);
    skipList.insert(3);
    skipList.insert(7);
    skipList.insert(8);
    skipList.insert(9);

    std::cout << "Search for 3: " << (skipList.search(3) ? "Found" : "Not Found") << std::endl; // Output: Found
    std::cout << "Search for 6: " << (skipList.search(6) ? "Found" : "Not Found") << std::endl; // Output: Not Found

    return 0;
}

这个 C++ 实现包含了以下主要部分:

  1. Node 类:表示跳跃表中的节点,包含一个值和一个指针数组。
  2. SkipList 类:包含插入和查找方法,以及一个用于生成随机层级的 randomLevel 方法。
  3. randomLevel 方法:生成一个随机的层级,用于新节点。
  4. insert 方法:在跳跃表中插入一个值,更新相应的指针。
  5. search 方法:在跳跃表中查找一个值,返回一个布尔值表示是否找到。
  6. main 函数:测试插入和查找功能。

这段代码展示了如何用 C++ 实现跳跃表的插入和查找功能。

打赏

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,您说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

分享从这里开始,精彩与您同在