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++ 实现包含了以下主要部分:
randomLevel
方法。这段代码展示了如何用 C++ 实现跳跃表的插入和查找功能。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。