Node类
用来存储键值对，每个节点有多个指针，用来指向不同层的下一个节点
层数是从1开始的，第0层其实是next指针，所以level层总共有level+1个指针
template<typename K, typename V>
class Node {
public:
Node() {} // 默认构造函数
Node(K k, V v, int); // 自定义构造函数
~Node(); // 析构函数
K get_key() const; // 获取key值
V get_value() const; // 获取value值
void set_value(V); // 设置value值
Node<K, V>** forward; // 指针数组，每个指针代表一层，指向下一个节点
int node_level; // 节点的层数
private:
K key;
V value;
};
template<typename K, typename V>
Node<K, V>::Node(K k, V v, int level) {
key = k;
value = v;
node_level = level;
forward = new Node<K, V>* [level + 1];
memset(forward, 0, sizeof(Node<K, V>*) * (level + 1));
}
template<typename K, typename V>
Node<K, V>::~Node() {
delete[] forward;
}
template<typename K, typename V>
K Node<K, V>::get_key() const {
return key;
}
template<typename K, typename V>
V Node<K, V>::get_value() const {
return value;
}
template<typename K, typename V>
void Node<K, V>::set_value(V v) {
value = v;
}SkipList类
用来对多个键值对进行管理，同时提供向外的接口，例如添加、查找、删除等操作
template<typename K, typename V>
class SkipList {
public:
SkipList(int); // 构造函数，初始化最大层数
~SkipList(); // 析构函数
int get_random_level(); // 随机获取一个节点的层数，有讲究
Node<K, V>* create_node(K, V, int); // 新建键值对
int insert_element(K, V); // 插入键值对
void display_list() const; // 输出跳表
bool search_element(K) const; // 查找键值对
void delete_element(K); // 删除键值对
int size() const; // 返回键值对个数
private:
int _max_level; // 最大层数，一开始就初始化
int _skip_list_level; // 当前最大层数，小于等于_max_level
Node<K, V>* _header; // 头结点
int _element_count; // 记录记录键值对个数
};构造函数和析构函数
template<typename K, typename V>
SkipList<K, V>::SkipList(int max_level) {
_max_level = max_level;
_skip_list_level = 0;
_element_count = 0;
K k;
V v;
_header = new Node<K, V>(k, v, _max_level); // 虚拟头结点
}
template<typename K, typename V>
SkipList<K, V>::~SkipList() {
delete _header; // 只释放了头结点
}// 创建一个节点
template<typename K, typename V>
Node<K, V>* SkipList<K, V>::create_node(K k, V v, int level) {
Node<K, V> *node = new Node<K, V>(k, v, level);
return node;
}
// 跳表大小
template<typename K, typename V>
int SkipList<K, V>::size() {
return _element_count;
}
// 随机获取一个层
template<typename K, typename V>
int SkipList<K, V>::get_random_level() {
int k = 1;
while (rand() % 2) {
k++;
}
k = (k < _max_level) ? k : _max_level;
return k;
}查找键值对
从当前最大层数开始找，如果要查找的键比cur的下一个节点的键大，cur就往后移
找到大于等于key的第一个节点，如果那个节点等于key，就说明找到了，否则没有该key
template<typename K, typename V>
bool SkipList<K, V>::search_element(K key) {
std::cout << "-----------search_element-----------" << std::endl;
Node<K, V> *cur = _header;
for (int i = _skip_list_level; i >= 0; i--) {
while (cur->forward[i] && cur->forward[i]->get_key() < key) {
cur = cur->forward[i];
}
}
cur = cur->forward[0];
if (cur && cur->get_key() == key) {
std::cout << "Found key: " << key << ", value: " << cur->get_value() << std::endl;
return true;
}
std::cout << "Not Found Key: " << key << std::endl;
return false;
}插入键值对
update指针数组记录要插入的节点的每一层的前继节点，这样节点插入的时候就可以设置好每一层的指针，每一层都要做一个链表插入时的动作
node->next = prev->next;
prev->next = node;
template<typename K, typename V>
int SkipList<K, V>::insert_element(K key, V value) {
Node<K, V> *cur = _header;
Node<K, V> *update[_max_level + 1];
memset(update, 0, sizeof(Node<K, V>*) * (_max_level + 1));
for (int i = _skip_list_level; i >= 0; i--) {
while (cur->forward[i] && cur->forward[i]->get_key() < key) {
cur = cur->forward[i];
}
update[i] = cur;
}
cur = cur->forward[0];
// 如果key已经存在，直接返回
if (cur != NULL && cur->get_key() == key) {
cout << "key: " << key << ", exists" << endl;
return 1;
}
// 如果key不存在，就创建
if (cur == NULL || cur->get_key() != key) {
int random_level = get_random_level();
if (random_level > _skip_list_level) {
for (int i = _skip_list_level + 1; i <= random_level; i++) {
update[i] = _header;
}
_skip_list_level = random_level;
}
Node<K, V> *insert_node = create_node(key, value, random_level);
for (int i = 0; i <= random_level; i++) {
insert_node->forward[i] = update[i]->forward[i];
update[i]->forward[i] = insert_node;
}
cout << "Successfully insert key: " << key << endl;
_element_count++; // 节点个数增加
}
return 0;
}删除键值对
跟插入节点一样的操作，先记录要删除节点的每一层的前继节点，然后每一层做一个链表删除节点的操作
prev->next = node->next;
delete node;
template<typename K, typename V>
void SkipList<K, V>::delete_element(K key) {
Node<K, V> *cur = _header;
Node<K, V> *update[_max_level + 1]; // 记录待删除节点不同层的前继节点
memset(update, 0, sizeof(Node<K, V>*) * (_max_level + 1));
for (int i = _skip_list_level; i >= 0; i--) {
while (cur->forward[i] && cur->forward[i]->get_key() < key) {
cur = cur->forward[i];
}
update[i] = cur;
}
cur = cur->forward[0];
if (cur != NULL && cur->get_key() == key) { // 找到对应节点，删除之
for (int i = 0; i <= _skip_list_level; i++) {
if (update[i]->forward[i] != cur) break;
update[i]->forward[i] = cur->forward[i]; // 处理前继节点的后继
}
while (_skip_list_level > 0 && _header->forward[_skip_list_level] == 0) {
_skip_list_level--;
}
delete cur; // 释放节点资源
std::cout << "Successfully deleted key " << key << std::endl;
_element_count--;
}
return;
}
