本文主要是介绍redis核心数据结构——跳表项目设计与实现(跳表结构插入数据、删除数据、展示数据),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
数据的插入
首先来看需求
你的任务是实现 SkipList 类中搜索节点和插入节点的成员函数。
插入节点成员函数签名:int insert_element(const K key, const V value)
向跳表中插入一对数据,如果跳表中已存在该键值对,则不做任何操作,返回 1,如果不存在该键值对,则将该键值对插入到跳表中,返回 0。
参数说明: K key:键; V value:值。
搜索节点成员函数签名:bool search_element(K key)
在跳表中查询键值为 key 的键值对,如果跳表中已存在该键值对,则返回 true,否则返回 false。
参数说明: K key:键。
跳表的插入其实和链表插入差不多,不同之处就在于每一层都需要插入,查找也是一样,每一层都要进行查找。这两个操作其实不难,难的是数组越界问题的排查,主要是之前写的那篇文章里,节点构造函数中需要给forwards数组分配动态内存。
因为这个改了半天。
template <typename K, typename V>
Node<K, V>::Node(const K k, const V v, int level) {this->key = k;this->value = v;this->node_level = level;this->forward = new Node<K, V> *[level + 1];memset(this->forward, 0, sizeof(Node<K, V> *) * (level + 1));
};
另外就是每次创建新节点时需要随机分配层数,加上一开始用两个变量分别记录最大层数和当前层数,分配后该层数不能超过最大层数,且如果大于当前层数,需要将当前层数进行更新。
代码如下:
#include<stdlib.h>
#include <iostream>
#include <cstring>template<typename K, typename V>
class Node {
private:K key;V val;int node_level;public:Node** forwards;public:Node(K inkey, V value, int level): key(inkey), val(value), node_level(level),forwards(nullptr) {this->forwards = new Node<K, V>*[node_level+1];memset(this->forwards, 0, sizeof(Node<K,V>*)*(node_level+1));}~Node(){delete forwards;};K getKey() const {return key;}V get_value() const {return val;}int getLevel() const {return node_level;}void set_value(V value) {val = value;}};template<typename K, typename V>
class SkipList {
private:Node<K,V>* HeadNode = nullptr;int _maxlevel = 0;int temp_level = 0;
public:SkipList(int maxlevel = 500) {_maxlevel = maxlevel;HeadNode = new Node<K, V>(K(),V(),maxlevel);}~SkipList() { delete HeadNode; _maxlevel = 0; temp_level = 0; }int getRandomLevel() {srand((int)time(0));int k = 1;while (rand() % 2) {k++;}k = (k < _maxlevel) ? k : _maxlevel;return k;}int insert_element(const K key, const V value) {int flag = 0;Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode;while (cur) {if (cur->getKey() == key) {flag = 1;cur->set_value(value);}cur = cur->forwards[curlevel]; }curlevel--;}if (flag == 1) return 1;Node<K, V>* newNode = new Node<K,V>(key, value, getRandomLevel());if (temp_level < newNode->getLevel()) temp_level = newNode->getLevel();curlevel = newNode->getLevel();while (curlevel) {Node<K,V>* prev = HeadNode;cur = HeadNode->forwards[curlevel];while (cur) {if (cur->getKey() > newNode->getKey()) {prev->forwards[curlevel] = newNode;newNode->forwards[curlevel] = cur;break;} cur = cur->forwards[curlevel];prev = prev->forwards[curlevel];} if (!cur)prev->forwards[curlevel] = newNode;curlevel--;}return 0;}bool search_element(K key) {Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode->forwards[curlevel];while (cur) {if (cur->getKey() == key) return true;cur = cur->forwards[curlevel]; }curlevel--;}return false;}
};int main() {SkipList<int, int> mySkipList;int n, m;std::cin >> n >> m;while (n--) {int k, v, r;std::cin >> k >> v;r = mySkipList.insert_element(k,v);if (r == 0) std::cout << "Insert Success" << std::endl;else std::cout << "Insert Failed" << std::endl;}while (m--) {int k;std::cin >> k;if (mySkipList.search_element(k)) std::cout << "Search Success" << std::endl;else std::cout << "Search Failed" << std::endl;}
}
数据的删除
先来看下需求:
你的任务是实现 SkipList 类中删除节点成员函数。
成员函数签名:delete_element(K key)
此成员函数需要从跳表中删除键为 key 的节点。如果该键存在,则删除对应的节点;如果不存在,则不进行任何操作。
参数说明: K key:要删除的元素的键,其中 K 是键的类型。
思路和单纯的链表删除差不多
实现函数代码如下:
void delete_element(K key) {Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {Node<K,V>* prev = HeadNode;cur = HeadNode->forwards[curlevel];while (cur) {if (cur->getKey() == key) {prev->forwards[curlevel] = cur->forwards[curlevel];break;}cur = cur->forwards[curlevel];prev = prev->forwards[curlevel];}curlevel--;}}
数据的展示:
首先来看下需求:
你的任务是实现 SkipList 类中的打印跳表的成员函数。
成员函数签名:void display_list() 此成员函数专门负责按照层次结构将跳表的内容输出到控制台。
输出格式如下所述:
输出格式示例:
- 从最顶层开始,逐层向下打印跳表的索引链
- 每一层的打印输出首先标注该层的级别,接着依次打印该层上每个节点的键值对
- 每个键值对以键:值的形式表示,键值对之间使用;分隔,确保信息的清晰可读
- 每个层级的所有键值对信息占据一行,以便于视觉上的层次区分
Level 1: 1:3;3:5;
Level 0: 1:3;2:4;3:5;
三部分整合后代码如下:
#include<stdlib.h>
#include <iostream>
#include <cstring>template<typename K, typename V>
class Node {
private:K key;V val;int node_level;public:Node** forwards;public:Node(K inkey, V value, int level): key(inkey), val(value), node_level(level),forwards(nullptr) {this->forwards = new Node<K, V>*[node_level+1];memset(this->forwards, 0, sizeof(Node<K,V>*)*(node_level+1));}~Node(){delete forwards;};K getKey() const {return key;}V get_value() const {return val;}int getLevel() const {return node_level;}void set_value(V value) {val = value;}};template<typename K, typename V>
class SkipList {
private:Node<K,V>* HeadNode = nullptr;int _maxlevel = 0;int temp_level = 0;
public:SkipList(int maxlevel = 500) {_maxlevel = maxlevel;HeadNode = new Node<K, V>(K(),V(),maxlevel);}~SkipList() { delete HeadNode; _maxlevel = 0; temp_level = 0; }int getRandomLevel() {srand((int)time(0));int k = 1;while (rand() % 2) {k++;}k = (k < _maxlevel) ? k : _maxlevel;return k;}int insert_element(const K key, const V value) {int flag = 0;Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode;while (cur) {if (cur->getKey() == key) {flag = 1;cur->set_value(value);}cur = cur->forwards[curlevel]; }curlevel--;}if (flag == 1) return 1;Node<K, V>* newNode = new Node<K,V>(key, value, getRandomLevel());if (temp_level < newNode->getLevel()) temp_level = newNode->getLevel();curlevel = newNode->getLevel();while (curlevel) {Node<K,V>* prev = HeadNode;cur = HeadNode->forwards[curlevel];while (cur) {if (cur->getKey() > newNode->getKey()) {prev->forwards[curlevel] = newNode;newNode->forwards[curlevel] = cur;break;} cur = cur->forwards[curlevel];prev = prev->forwards[curlevel];} if (!cur)prev->forwards[curlevel] = newNode;curlevel--;}return 0;}bool search_element(K key) {Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode->forwards[curlevel];while (cur) {if (cur->getKey() == key) return true;cur = cur->forwards[curlevel]; }curlevel--;}return false;}void delete_element(K key) {Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {Node<K,V>* prev = HeadNode;cur = HeadNode->forwards[curlevel];while (cur) {if (cur->getKey() == key) {prev->forwards[curlevel] = cur->forwards[curlevel];break;}cur = cur->forwards[curlevel];prev = prev->forwards[curlevel];}curlevel--;}}void print() {Node<K,V>* cur = HeadNode;int curlevel = temp_level;while (curlevel) {cur = HeadNode->forwards[curlevel];std::cout << "Level " << curlevel-1 << ": ";while (cur) {std::cout << cur->getKey() << ":" << cur->get_value() << ';';cur = cur->forwards[curlevel];}std::cout << std::endl;curlevel--;}}
};int main() {SkipList<int, int> mySkipList;int n,k,m;std::cin >> n >> k >> m;while (n--) {int key, v, r;std::cin >> key >> v;r = mySkipList.insert_element(key,v);if (r == 0) std::cout << "Insert Success" << std::endl;else std::cout << "Insert Failed" << std::endl;}while (k--) {int key;std::cin >> key;mySkipList.delete_element(key);}while (m--) {int k;std::cin >> k;if (mySkipList.search_element(k)) std::cout << "Search Success" << std::endl;else std::cout << "Search Failed" << std::endl;}mySkipList.print();
}
这篇关于redis核心数据结构——跳表项目设计与实现(跳表结构插入数据、删除数据、展示数据)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!