跳表

跳表因为其结构简单，对于一些高效的数据结构红黑树、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; 
	}
}

删除：就是插入的逆操作