跳表

biningooginind 2020-03-17 原文

跳表因为其结构简单，对于一些高效的数据结构红黑树、B树等来说相对简单且容易实现。在应用方面也很广泛，比如著名的中间件Redis里面的Zset就用到了跳表来实现高效查询和排序

下面直接上代码

定义结构体

forward[MaxLevel]是一个Node指针类型，用于当前节点指向的下一个节点的指针，为什么是指针数组呢？因为当前节点可能会有好几层索引，其中最顶层跨度最大，越往下跨度越小

struct Node{
    int key;
    Node* forward[MaxLevel];
};

查找算法

大致思路就是：从上层往下找，当当前层的下一个节点比key大，则不能再往后遍历了，需要跳到下一层去比较下一层的下一个节点的值了，直到跳到最底层

举个简单的例子【**请叫我灵魂画手^_^**】：

1——————->5——————>9———->11

1——->3——–>5——->7——–>9———->11

1–>2–>3–>4–>5–>6–>7–>8–>9–>10—>11

当要寻找5，则可以直接1->5 在第一层索引找到
当要找8，则先在第一层跳到5这个位置，然后往下跳，找到7这个位置，再往下跳，找到8
找10，先第一层找到9这个位置，往下跳，找到10

Node* Search(Node* head,int key,int level){
    
    Node* p = head;
    for(int i=level;i>=0;i--){  //从最上层的索引开开始寻找  如果寻找的节点大于值 则跳到下一层寻找 否则遍历下一个节点判断 
        while(p->forward[i]!=NULL && p->forward[i]->key<key){  //当前层数小于要寻找的值 则继续遍历下一个节点 
            p = p->forward[i]; 
        }  
    }
    
    if(p==NULL)
        return NULL;
    if (p->key==key) //当前的节点==key 或者比key小 则没有找到 
        return p;
    else
        return NULL;    
}

下面看如何插入

插入就是要找到每层的链接点，并且保存连接点，和链表插入思想一样，只是这里多了几个节点而已

//确定高度的随机化算法 
int randX(int &level){
    t = rand()
    for(int i=0,j=2;i<MaxLevel;i++,j+=j){
        if (t>(2/j))
            break
    }
    
    if(i>level){
        level = i //更新最大高度 
    }   
    
    return i; 
} 


void Insert(Node* head,int key,int &level){
    
    Node* p  = head;
    Node* update[MaxLevel];  //临时变量
    
    newLevel = randX(level);
    
    for(int i=level;i>=0;i--){
        
        while(p->forward[i]!=NULL && p->forward[i]->key<key)  //寻找本层的最大节点 
            p = p->forward[i];
        update[i] = p;   //保存本层最大节点 
    }
    
    p = (Node*)malloc(sizeof(Node));
    p->key = key;
    for(int i=0;i<=newLevel;i++){
        p->forward[i] = update[i]->forward[i]; //插入操作
        update[i]->forward[i] = p; 
    }
}

删除：就是插入的逆操作