本文共 8397 字，大约阅读时间需要 27 分钟。

跳表 （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
   
    struct SkipNode{    int key;    T value;    vector
    
      next;    SkipNode(int k, T v, int level);};
    
   

//构造函数，初始化

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

随机层数

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

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

结点最大层数

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

template
   
     int SkipList
    
     ::nodeLevel(vector
     
      
       *> 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
   
     SkipNode
    
     * SkipList
     
      ::insert(int k, T v){	int x_level = randomLevel();	SkipNode
      
       * new_node = nullptr;	SkipNode
       
        * 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
        
         (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
         
           SkipNode
          
           * SkipList
           
            ::find(int x){ SkipNode
            
             * 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
             
               SkipNode
              
               * SkipList
               
                ::deleteNode(int x){ SkipNode
                
                 * node = find(x); if (!node) { cout << "\n This deleting node" << x << "doesn't exist" << endl; return head; } else { SkipNode
                 
                  * 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
   
     void SkipList
    
     ::printNode(){    for (int i = 0; i < maxLevel; i++)    {        SkipNode
     
      * 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
   
     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