跳表的c++实现


从很早之前就从微信的技术文章中学到了跳表的知识,也大概了解了跳表是个什么结构。其实跳表就是有序链表的升级版,在第一层的有序链表之上,构建N层节点数更小的链表。但是一直没有静下心来自己写一下跳表的实现。

    跳表的实现,有使用数组的,也有使用单链表的。其中使用单链表的或许更容易理解一点。先放上跳表的示例图。

来自于 https://kenby.iteye.com/blog/1187303

                        图1-跳表结构图

上面的图片来自于博文:

                      https://kenby.iteye.com/blog/1187303

首先,引用该博文对跳表性质的介绍:

跳表具有如下性质:

(1) 由很多层结构组成

(2) 每一层都是一个有序的链表

(3) 最底层(Level 1)的链表包含所有元素

(4) 如果一个元素出现在 Level i 的链表中,则它在 Level i 之下的链表也都会出现。

(5) 每个节点包含两个指针,一个指向同一链表中的下一个元素,一个指向下面一层的元素。

--------------------- 
作者:swffsdgasdg 
来源:CSDN 
原文:https://blog.csdn.net/u013011841/article/details/39158585 
版权声明:本文为博主原创文章,转载请附上博文链接!

其中第5条。视具体实现而定。只有用链表实现的才有该性质。

    使用链表实现跳表,只要在节点上,增加一个向下的指针即可,指针指向该节点的下一层节点。

跳表的层级,是随机算法产生的,每插入一个节点时,都随机产生一个层级,然后将数据插入到跳表的每一层,跳表的最大层级就是插入的时候产生的层级的最大值。

    我们现在来看下如何用一维数组实现跳表。首先,看下数组实现的跳表的空间结构。

图片来自于博文: https://blog.csdn.net/u013011841/article/details/39158585

跳表的数组实现

可能看到这张图片会有点懵逼,不知道这几个指针是什么意思。那么,我们先看看跳表的节点数据结构

struct Node {
    int data = -1;
    int level = 0;
    Node *level_forward[MAX_LEVEL];
};
黄色和天蓝色的方框就是节点的结构,其中黄色的部分表示data,是节点的值,而天蓝色的方框,对应的是level_forward数组,表明的是节点各层级的下一个节点。例如

11节点中,level_forward[0]指向 L0中的15,level_forward[1]指向的是L1中的30,level_forward[2]指向的是L2中的30,level_forward[3]指向的是L3中的+∞(表示空)

,就是通过level_forward数组的指针传递,实现了跳表的功能。现在来看看跳表的数据结构。

class SkipList {
public:
    SkipList();
    void printAll();
    int randomLevel();
    
    int randomVal();

    void insert(int val);
    Node *find(int val);
    void remove(int val);

private:
    Node *head = nullptr;
    int levelCount = 0;
};

跳表的结构中,依靠跳表的头部指针,串联起整个跳表。首先,我们看下跳表的节点插入。

跳表的插入

以下内容,来自博文: https://blog.csdn.net/u013011841/article/details/39158585

 假设当前我们要插入元素“40”,且在执行了随机决策模块后得到高度为4

     步骤一:找到表中比40小的最大的数,确定插入位置


步骤二:插入高度为4的列,并维护跳跃表的结构



紫色的箭头表示更新过的指针

--------------------- 
作者:swffsdgasdg 
来源:CSDN 
原文:https://blog.csdn.net/u013011841/article/details/39158585 
版权声明:本文为博主原创文章,转载请附上博文链接!

    上面的博文很精彩,图片描述的很到位,且文字写的也好。从图中很容易就可以看出,在插入的时候,先会找插入的位置,插入的时候,更新插入位置的下一个节点指向,并且将插入位置的原来的下一个节点的值赋值给新插入的节点的下一个位置。具体的看代码

void SkipList::insert(int val) {
    int level = randomLevel();
    cout<<"begin insert val " << val <<" level " <<level<<endl;
    //将要值对应的下一个节点值存入临时数组中
    Node *update[level] = {0};

    Node *newnode = new Node;
    newnode->data = val;
    newnode->level = level;

    //默认先指向head
    for(int i = 0; i < level; ++i) {
        update[i]   = head;
    }

    Node *p = head;
    //从最顶层开始遍历,找出val插入的位置
    for(int i = level - 1; i >= 0; --i) {
        while(p->level_forward[i] != nullptr &&
                 p->level_forward[i]->data < val) {
             p = p->level_forward[i];
        }

        update[i] = p;
    }

    //依次更新update的下一个指向
    for(int i = 0; i < level; ++i) {
        //设置插入结点的下一个指向为原插入位置的forward
        newnode->level_forward[i] = update[i]->level_forward[i];
        //插入位置的下一个则为新节点
        update[i]->level_forward[i] = newnode;
    }

    if (levelCount < level) {
         levelCount = level;
    }
}

代码中与图中有一点不同的是,我们是以新节点随机产生的层级来进行插入位置的查找的。

跳表的查找

    跳表的查找与插入的时候的查找有很大程度上的相似。

跳跃链表查找操作
目的:在跳跃表中查找一个元素x

   在跳跃表中查找一个元素x,按照如下几个步骤进行:

      1. 从最上层的链(Lh)的开头开始

      2. 假设当前位置为p,它向右指向的节点为q(p与q不一定相邻),且q的值为y。将y与x作比较

          (1) x=y  输出查询成功及相关信息

          (2) x>y  从p向右移动到q的位置

          (3) x<y  从p向下移动一格 

      3. 如果当前位置在最底层的链中(L0),且还要往下移动的话,则输出查询失败


元素53的查找路径

--------------------- 
作者:swffsdgasdg 
来源:CSDN 
原文:https://blog.csdn.net/u013011841/article/details/39158585 
版权声明:本文为博主原创文章,转载请附上博文链接!

    首先从跳表头的最顶层开始遍历查找,一直到遇见p,p的下一个节点比查找值更大,则继续查找p的次一级,一直这样循环,直到查找完所有层级。具体看代码实现。


Node *SkipList::find(int val) {
    Node *p = head;

    //从最顶层开始查找
    for(int i = levelCount - 1; i >= 0; --i) {
        while(p->level_forward[i] != nullptr &&
                 p->level_forward[i]->data < val) {
            p = p->level_forward[i];
        }
    }

    //比较第0层的数据
    if ( p->level_forward[0] != nullptr &&
         p->level_forward[0]->data == val) {
         return p->level_forward[0];
    }

    return nullptr;
}

 跳表的删除

看完前面的跳表的插入和查找之后,我们再来看下跳表的删除。当删除跳表的某一个节点时,必须要删除所有层级上的该节点。所以实现上时,我们只要找出跳表中该节点的前驱,然后让前驱的下一个节点指向节点的后驱即可。查找跳表的前驱方法与跳表查找时的方法相同。具体我们看实现。


void SkipList::remove(int val) {
    //找出所有比当前删除值小的节点集合
    Node *update[levelCount] = {0};
    Node *p = head;

    for(int i = levelCount - 1; i >= 0; --i) {
        while(p->level_forward[i] != nullptr &&
                 p->level_forward[i]->data < val) {
             p = p->level_forward[i];
        }

        update[i] = p;
    }

    //修改删除节点的上一个节点的下一个节点指向
    if (p->level_forward[0] != nullptr && p->level_forward[0]->data == val) {
      for (int i = levelCount - 1; i >= 0; --i) {
        if (update[i]->level_forward[i] != nullptr &&
                update[i]->level_forward[i]->data == val) {
          update[i]->level_forward[i] = update[i]->level_forward[i]->level_forward[i];
        }
      }
    }
}



update中存放的就是删除节点的所有层的前驱节点,删除的时候,我们修改前驱节点每一层的level_forward指向。

  完整c++代码如下:


#include <iostream>
#include <list>
#include <string.h>
#include <cstdlib>
#include <vector>

using namespace std;

static const int MAX_LEVEL = 16;
struct Node {
    int data = -1;
    int level = 0;   
    Node *level_forward[MAX_LEVEL];

    Node():data(-1) {
        memset(level_forward, sizeof(level_forward), 0);
    }

    void print() {
        cout<<"data:" << data <<", level:"<< level <<endl;
    }
};

class SkipList {
public:
    SkipList();
    void printAll();

    int randomLevel();
    
    int randomVal();

    void insert(int val);
    Node *find(int val);
    void remove(int val);

private:
    Node *head = nullptr;
    int levelCount = 0;
};

SkipList::SkipList() {
     head = new Node;
}

int SkipList::randomLevel() {
    return abs(random())%MAX_LEVEL + 1;
}

int SkipList::randomVal() {
    return abs(random()) % 100;
}

void SkipList::printAll() {
     for(int i = levelCount - 1; i >= 0; --i) {
         Node *cur = head->level_forward[i];

         while(cur != nullptr) {
              if (cur == head->level_forward[i]) {
                cout<<cur->data;
              } else {
                  cout<<"->" << cur->data;
              }
          
              cur = cur->level_forward[i];
         }

         cout <<endl;
     }    
}

Node *SkipList::find(int val) {
    Node *p = head;

    //从最顶层开始查找
    for(int i = levelCount - 1; i >= 0; --i) {
        while(p->level_forward[i] != nullptr &&
                 p->level_forward[i]->data < val) {
            p = p->level_forward[i];
        }
    }

    //比较第0层的数据
    if ( p->level_forward[0] != nullptr && 
         p->level_forward[0]->data == val) {
         return p->level_forward[0];
    }

    return nullptr;
}

void SkipList::insert(int val) {
    int level = randomLevel();
    cout<<"begin insert val " << val <<" level " <<level<<endl;
    //将要值对应的下一个节点值存入临时数组中
    Node *update[level] = {0};

    Node *newnode = new Node;
    newnode->data = val;
    newnode->level = level;

    //默认先指向head
    for(int i = 0; i < level; ++i) {
        update[i]   = head;
    }

    Node *p = head;
    //从最顶层开始遍历,找出val插入的位置
    for(int i = level - 1; i >= 0; --i) {
        while(p->level_forward[i] != nullptr &&
                 p->level_forward[i]->data < val) {
             p = p->level_forward[i];
        }

        update[i] = p;
    }

    //依次更新update的下一个指向
    for(int i = 0; i < level; ++i) {
        //设置插入结点的下一个指向为原插入位置的forward
        newnode->level_forward[i] = update[i]->level_forward[i];
        //插入位置的下一个则为新节点
        update[i]->level_forward[i] = newnode;
    }

    if (levelCount < level) {
         levelCount = level;
    }
}

void SkipList::remove(int val) {
    //找出所有比当前删除值小的节点集合
    Node *update[levelCount] = {0};
    Node *p = head;

    for(int i = levelCount - 1; i >= 0; --i) {
        while(p->level_forward[i] != nullptr &&
                 p->level_forward[i]->data < val) {
             p = p->level_forward[i];
        }

        update[i] = p;
    }

    //修改删除节点的上一个节点的下一个节点指向
    if (p->level_forward[0] != nullptr && p->level_forward[0]->data == val) {
      for (int i = levelCount - 1; i >= 0; --i) {
        if (update[i]->level_forward[i] != nullptr && 
                update[i]->level_forward[i]->data == val) {
          update[i]->level_forward[i] = update[i]->level_forward[i]->level_forward[i];
        }
      }
    }
}

int main() {
    srandom(time(NULL));
    SkipList skip;
    int val = 0;
    vector<int> vals;

    for(int i = 0; i < 30; ++i) {
        val = skip.randomVal();
        vals.push_back(val);
        skip.insert(val);
    }
     
    skip.printAll();

    //查找
    int searchval = vals[5];
    Node *node = skip.find(searchval);

    if (nullptr != node) {
        cout<<"I got you"<<endl;
        node->print();
    } else {
        cout<<"I can't find you"<<endl;
    }

    skip.remove(searchval);
    cout<<"after remove node " << searchval<<endl;
    skip.printAll();
}
本版本的c++实现,参考的是王争老师在《数据结构与算法之美》的课程中的java实现。附上原java实现的代码地址:


     https://github.com/wangzheng0822/algo/blob/master/java/17_skiplist/SkipList.java


评论

发表评论