跳表 （Skip List） C++ 实现

本文主要是介绍跳表 （Skip List） C++ 实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

跳表 （Skip List） C++ 实现

跳表原理
跳表 c++ 实现
SkipNode
SkipList
随机层数
结点最大层数
基本操作
打印
主函数
输出结果
在学习 C++ 中的过程中，找个算法作为练习。
仅供参考。

跳表原理

跳表原理讲解请参考 https://lotabout.me/2018/skip-list/
为了节约时间，这里只是简单说明，原文如上。

跳表(skip list) 对标的是平衡树(AVL Tree)，是一种 插入/删除/搜索 都是 O ( l o g n ) O(log n)O(logn) 的数据结构。它最大的优势是原理简单、容易实现、方便扩展、效率更高。因此在一些热门的项目里用来替代平衡树，如 redis, leveldb 等。

跳表顾名思义就是跳跃的表格，理解起来其实就是跳着插入或者搜索。具体什么意思呢，其实就像是二分搜索一样，每次都将数组分成两点分，先定位搜索或者插入的数据在哪一部分，就可以节约搜索的时间。跳表其实是一样的原理，即建立多层索引（多层链表）。如果每次都是以二等分来建立索引的话，即如下图所示：

但是上述结构是“静态”的，即我们先拥有了一个链表，再在之上建了多层的索引。但是在实际使用中，我们的链表是通过多次插入/删除形成的，换句话说是“动态”的。上述的结构要求上层相邻节点与对应下层节点间的个数比是 1:2，随意插入/删除一个节点，这个要求就被被破坏了。

因此跳表（skip list）表示，我们就不强制要求 1:2 了，一个节点要不要被索引，建几层的索引，都在节点插入时由抛硬币决定。当然，虽然索引的节点、索引的层数是随机的，为了保证搜索的效率，要大致保证每层的节点数目与上节的结构相当。下面是一个随机生成的跳表：

对于上述随机跳表而言，每次插入一个新结点的时候，该结点的索引层数是抛硬币决定的，即由随机算法决定的。

当然为了防止运气太好，层数太高，我们一般会设置一个最大的层数 M a x L e v e l MaxLevelMaxLevel. 一般 M a x L e v e l = l o g 1 / p n MaxLevel=log_{1/p}nMaxLevel=log 
1/p
​    
 n。 p pp 为概率。

跳表 c++ 实现
思路：

首先创建一个结点的结构体，结构体里包含 一个键值对，key 用来建立索引，而 value 则用于存储真正的值；指向下一个结点的指针 next，以及标志每个结点索引层数的参数 level. next 指针是一个数组，用于存储结点在所有层数上的下一个结点。 例如， 上述图中结点6的next指针为{NIL, 25, 9, 7}.
创建class skipList, 包含头结点，尾结点，list 的最大层数，随机层数方法，以及一些列操作。
头结点和尾节点分别为整型的最小值和最大值，并在初始化时让所有层数上的头结点都指向尾节点。
操作包含插入，查找，删除。
SkipNode
为了可以适用于任何类型的value， 这里用了 template

template<typename T>
struct SkipNode
{int key;T value;vector<SkipNode*> next;    SkipNode(int k, T v, int level);
};

//构造函数，初始化

template<typename T> SkipNode<T>::SkipNode(int k, T v, int level) : key(k), value(v)
{for (int i = 0; i < level; i++){next.push_back(nullptr);}
}

SkipList

template<class T>
class SkipList
{public://头结点SkipNode<T>* head;//列表最大层数int maxLevel;//整型的最小值和最大值const int minInt = numeric_limits<int>::min();const int maxInt = numeric_limits<int>::max();public://构造函数SkipList(int maxLevel, T iniValue);//析构函数~SkipList();//随机层数方法int randomLevel();//插入, 查找， 删除SkipNode<T>* insert(int k, T v);SkipNode<T>* find(int k);SkipNode<T>* deleteNode(int k);//打印void printNode();private://尾节点SkipNode<T>* tail;//找到当前列表或者node的最大层数int nodeLevel(vector<SkipNode<T>*> p);
};//初始化
template<class T> SkipList<T>::SkipList(int maxLevel, T iniValue): maxLevel(maxLevel)
{//初始化头结点和尾节点为整型最小值和最大值head = new SkipNode<T>(minInt, iniValue, maxLevel);tail = new SkipNode<T>(maxInt, iniValue, maxLevel);//所有层数上的头结点指向尾节点for (int i = 0; i < maxLevel; i++){head->next[i] = tail;}
}template<class T> SkipList<T>::~SkipList()
{delete head;delete tail;
}

随机层数

用 time 作为种子来获取（0，1）的随机值。 level ++ 直到随机值为 0 或者超过最大层数。

template<class T> int SkipList<T>::randomLevel()
{int random_level = 1;int seed = time(NULL);static default_random_engine e(seed);static uniform_int_distribution<int> u(0, 1);while (u(e) && random_level < maxLevel){random_level++;}return random_level;
}

结点最大层数

返回当前node的最大层数，最小值为 1.

template<class T> int SkipList<T>::nodeLevel(vector<SkipNode<T>*> next)
{int node_level = 0;if (next[0]->key == maxInt){return node_level;}for (int i = 0; i < next.size(); i++){if (next[i] != nullptr && next[i]->key != maxInt){node_level++;}else{break;}}return node_level;
}

基本操作

/*插入：
1）首先用查找函数来判断该结点是否已经存在，如果存在，则更新该结点的值
2）获取新节点的随机层数
3）找到合适的插入位置
4）插入，并调整每层前后node的指针*/
template<class T> SkipNode<T>* SkipList<T>::insert(int k, T v)
{int x_level = randomLevel();SkipNode<T>* new_node = nullptr;SkipNode<T>* tmp = head;new_node = find(k);if (new_node) {new_node->value = v;cout << "\nThis node " << k << " has already existed. And its value has been updated to " << v << endl;return head;}cout << "key: " << k << ", randomLevel: " << x_level << endl;new_node = new SkipNode<T>(k, v, x_level);for (int i = (x_level - 1); i > -1; i--){while (tmp->next[i] != nullptr && tmp->next[i]->key < k){tmp = tmp->next[i];}new_node->next[i] = tmp->next[i];tmp->next[i] = new_node;}return head;
}/*查找：
由于列表有序，首先找到小于该结点的最近的结点，如果下一个结点等于目标结点，则返回该节点。
如果不是，则返回空*/
template<class T> SkipNode<T>* SkipList<T>::find(int x)
{SkipNode<T>* tmp = head;int current_level = nodeLevel(tmp->next);for (int i = (current_level - 1); i > -1; i--){while (tmp->next[i] != nullptr && tmp->next[i]->key < x){tmp = tmp->next[i];}}tmp = tmp->next[0];if (tmp->key == x){cout << "\nThis key " << x << " has been found\n";return tmp;}else{//cout << " \nThis key " << x << " doesn't exit\n";return nullptr;}
}/*删除：
1) 用 find(x) 方法判断该结点是否存在. 如果不存在，则返回当前list, 并告知该结点不存在。
2) 找到小于该结点的最近的结点。
3) 更改该节点每层的前面的结点的指针。*/
template<class T> SkipNode<T>* SkipList<T>::deleteNode(int x)
{SkipNode<T>* node = find(x);if (!node){cout << "\n This deleting node" << x << "doesn't exist" << endl;return head;}else{SkipNode<T>* tmp = head;int x_level = node->next.size();cout << "\nThe deleting node " << x << "'s level is " << x_level << endl;for (int i = (x_level - 1); i > -1; i--){while (tmp->next[i] != nullptr && tmp->next[i]->key < x){tmp = tmp->next[i];}tmp->next[i] = tmp->next[i]->next[i];cout << "This node " << x << " has been deleted from level " << i << endl;}return head;}
}

打印

// 分层打印
template<class T> void SkipList<T>::printNode()
{for (int i = 0; i < maxLevel; i++){SkipNode<T>* tmp = head;int lineLen = 1;if (tmp->next[i]->key != maxInt){cout << "\n";cout << "This is level " << i << ":" << endl;cout << "{";while (tmp->next[i] != nullptr && tmp->next[i]->key != maxInt){cout << "(" << "Key: " << tmp->next[i]->key << ", ";cout << "Value: " << tmp->next[i]->value << ")";tmp = tmp->next[i];if (tmp->next[i] != nullptr && tmp->next[i]->key != maxInt){cout << ", ";}                if (lineLen++ % 5 == 0) cout << "\n";}cout << "}" << "\n";}}
}

主函数

int main()
{int maxLevel = 6;SkipList<int> l(maxLevel, 0);for (size_t i = 0; i < 50; i++){l.insert(i, i);}    l.printNode();

输出结果

This is level 0:
{(Key: 0, Value: 0), (Key: 1, Value: 1), (Key: 2, Value: 2), (Key: 3, Value: 3), (Key: 4, Value: 4),
(Key: 5, Value: 5), (Key: 6, Value: 6), (Key: 7, Value: 7), (Key: 8, Value: 8), (Key: 9, Value: 9),
(Key: 10, Value: 10), (Key: 11, Value: 11), (Key: 12, Value: 12), (Key: 13, Value: 13), (Key: 14, Value: 14),
(Key: 15, Value: 15), (Key: 16, Value: 16), (Key: 17, Value: 17), (Key: 18, Value: 18), (Key: 19, Value: 19),
(Key: 20, Value: 20), (Key: 21, Value: 21), (Key: 22, Value: 22), (Key: 23, Value: 23), (Key: 24, Value: 24),
(Key: 25, Value: 25), (Key: 26, Value: 26), (Key: 27, Value: 27), (Key: 28, Value: 28), (Key: 29, Value: 29),
(Key: 30, Value: 30), (Key: 31, Value: 31), (Key: 32, Value: 32), (Key: 33, Value: 33), (Key: 34, Value: 34),
(Key: 35, Value: 35), (Key: 36, Value: 36), (Key: 37, Value: 37), (Key: 38, Value: 38), (Key: 39, Value: 39),
(Key: 40, Value: 40), (Key: 41, Value: 41), (Key: 42, Value: 42), (Key: 43, Value: 43), (Key: 44, Value: 44),
(Key: 45, Value: 45), (Key: 46, Value: 46), (Key: 47, Value: 47), (Key: 48, Value: 48), (Key: 49, Value: 49)
}This is level 1:
{(Key: 0, Value: 0), (Key: 4, Value: 4), (Key: 6, Value: 6), (Key: 10, Value: 10), (Key: 14, Value: 14),
(Key: 15, Value: 15), (Key: 17, Value: 17), (Key: 21, Value: 21), (Key: 22, Value: 22), (Key: 23, Value: 23),
(Key: 28, Value: 28), (Key: 30, Value: 30), (Key: 34, Value: 34), (Key: 35, Value: 35), (Key: 36, Value: 36),
(Key: 38, Value: 38), (Key: 39, Value: 39), (Key: 42, Value: 42), (Key: 46, Value: 46), (Key: 48, Value: 48),
(Key: 49, Value: 49)}This is level 2:
{(Key: 4, Value: 4), (Key: 21, Value: 21), (Key: 23, Value: 23), (Key: 34, Value: 34), (Key: 35, Value: 35),
(Key: 39, Value: 39), (Key: 42, Value: 42), (Key: 46, Value: 46)}This is level 3:
{(Key: 4, Value: 4), (Key: 46, Value: 46)}This is level 4:
{(Key: 46, Value: 46)}

————————————————
版权声明：本文为CSDN博主「啦啦啦啦啦~~」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_44387066/article/details/90766034

这篇关于跳表 （Skip List） C++ 实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---