c++ 跳表详细讲解

c++ 跳表详细讲解

跳表建立在链表的基础之上，使用空间换时间，提高了链表的查询的效率。效果堪比BST，但是不够稳定，是redis的底层数据结构之一。

#pragma once
#pragma once
#include <vector>
#include <iostream>
#include <stdlib.h>
namespace yixiao{
class SkipList
{
public:
SkipList(size_t level = 4):level_(level)
{
head_ = new SkipNode(-1,level);
}
bool search(int key)
{
SkipNode* head = head_;
for(int i = level_-1;i>=0;--i)
{
while(head->forward_[i]!= nullptr && head->forward_[i]->key_ < key)
{
head = head->forward_[i];
}
if(head->forward_[i] != nullptr && head->forward_[i]->key_ == key)
{
return true;
}
}
return false;
}
bool add(int key)
{
if(search(key)) return false;
size_t level = RandomLevel();
SkipNode* node = new SkipNode(key,level);
SkipNode* head = head_;
for(int i = level_-1;i>=0;--i)
{
while(head->forward_[i]!= nullptr && head->forward_[i]->key_ < key)
{
head = head->forward_[i];
}
if(level > i)
{
node->forward_[i] = head->forward_[i];
head->forward_[i] = node;
}
}
return true;
}
bool erase(int key)
{
SkipNode* head = head_;
SkipNode* node = nullptr;
for(int i = level_-1;i>=0;--i)
{
while(head->forward_[i]!= nullptr && head->forward_[i]->key_ < key)
{
head = head->forward_[i];
}
if(head->forward_[i] != nullptr && head->forward_[i]->key_ == key)
{
node = head->forward_[i];
head->forward_[i] = node->forward_[i];
}
}
if(node == nullptr)
{
return false;
}else
{
delete node;
node = nullptr;
return true;
}
}
void printSkipList()
{
for(int i= level_-1;i>=0;--i)
{
SkipNode* head = head_;
while (head->forward_[0]!=nullptr)
{
if(head->forward_.size()>i)
{
std::cout<<head->forward_[0]->key_<<"t";
}
else
{
std::cout<<"t";
}
head = head->forward_[0];
}
std::cout<<std::endl;
}
}
private:
size_t RandomLevel()
{
size_t level = 1;
while(rand() % 2)
{
level++;
}
return
level>level_?level_:level;
}
struct SkipNode
{
int key_;
//val
std::vector<SkipNode*> forward_;
SkipNode(int key,size_t level):key_(key),forward_(level,nullptr){}
};
size_t level_;
SkipNode* head_;
};
}

该实现是自己对，跳表思想的一个理解，如果有问题，希望斧正！

最后

以上就是温暖雪碧为你收集整理的c++ 跳表详细讲解的全部内容，希望文章能够帮你解决c++ 跳表详细讲解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。