C++跳表实现，封装成Skiplist类

跳表 (Skip List) 是由 William Pugh 发明的一种查找数据结构，支持对数据的快速查找，插入和删除。

跳表的期望空间复杂度为O(n) ，跳表的查询，插入和删除操作的期望时间复杂度都为O(logn)。

算法讲解149【扩展】有序表专题2-跳表_哔哩哔哩_bilibili代码、资料：https://github.com/algorithmzuo, 视频播放量 5749、弹幕量 6、点赞数 264、投硬币枚数 156、收藏人数 219、转发人数 5, 视频作者 左程云, 作者简介 本人号，详解各种算法和数据结构，代码和资料：https://github.com/algorithmzuo，相关视频：国内算法大佬左程云VS清华大佬马士兵：Leetcode刷题200道，足以吊打字节面试官！，当你以为算法复习好了，边睡边学算法丨第一期，编程'省赛'惊现牢大！注释是What can I say，一周刷爆LeetCode，算法大神左神（左程云）耗时100天打造算法与数据结构基础到高级全家桶教程，直击BTAJ等一线大厂必问算法面试题真题详解（马士兵），【蓝桥杯比赛】视频教程（入门学习+算法辅导），算法讲解148【扩展】有序表专题1-AVL树，算法突击训练营，动画讲解-跳跃表原理，【蓝桥杯】算法入门精品课，高质量案例题解，全程干货，强烈推荐！（已完结）https://www.bilibili.com/video/BV1HZ1jYMEt3 建议大家先看看以上链接的讲解，对跳表讲的非常细致(我自愧不如，就不写详细的题解了，只贴出代码)，我就是根据这位up主的讲解来实现的，看完之后再参考我的代码就应该很容易懂了

力扣题目链接：1206. 设计跳表 - 力扣（LeetCode）

C++代码(已封装成Skiplist类，可直接使用)：

class Skiplist {
private:struct node {//定义链表节点int val;struct node* down, * right;//下指针和右指针node() {//默认构造函数val = -2e9;down = right = nullptr;}node(int val1) {//带参构造函数val = val1;down = right = nullptr;}};typedef node* Node;static const int max_level = 20;//最大层数,可以根据需要修改Node head[max_level];//每一层的头结点public:Skiplist() {srand(time(nullptr));//初始化随机数种子//初始化头结点head数组for (int i = 0;i < max_level;i++)head[i] = new node;for (int i = max_level - 1;i >= 1;i--)head[i]->down = head[i - 1];}void add(int num) {//增int level = get_level();Node now = head[max_level - 1];int now_level = max_level - 1;//现在到达的层数Node ahead = nullptr;//上一个(记录ahead为了给上一个down指针赋值)while (now) {while (now->right && now->right->val < num) {now = now->right;}if (now_level <= level) {//小于分配的层数就执行插入操作Node new_node = new node(num);new_node->right = now->right;now->right = new_node;if (ahead)ahead->down = new_node;ahead = new_node;}now = now->down;now_level--;}}bool erase(int num) {//删Node now = head[max_level - 1];int flag = 0;while (now) {while (now->right && now->right->val < num) {now = now->right;}if (now->right && now->right->val == num) {now->right = now->right->right;//删除now->right节点flag = 1;}now = now->down;}return flag;//返回是否删除成功}bool search(int target) {//查Node now = head[max_level - 1];//从最高层头指针开始找while (now != nullptr) {while (now->right && now->right->val < target) {now = now->right;}if (now->right && now->right->val == target) {return true;}now = now->down;}return false;}int get_level() {//随机分配层数int cnt = 0;while (cnt < max_level - 1) {if (rand() % 2)cnt++;else break;}return cnt;}};