跳跃表（skip list）基本原理及C/C++实现

1、基本原理

不想好好写字走的freestyle......其实可以直接看代码，我的注释还是很详细的，后面也有说明性的插图。

后面关于时间复杂度的分析证明没有贴（总之我们都知道它性能棒棒哒就行了）。

2、C/C++实现

比较符合MIT公开课的实现是这篇博文：跳跃表实现

而其他多数人都是抄袭这个实现：另一种实现

下面是自己的实现，因为最难的操作就是insert，所以目前只写了insert：

#include<stdlib.h>
#include<time.h>
#include<iostream>
#include<vector>

using namespace std;

#define Tail false // 表示抛硬币得到反面
#define Face true// 表示抛硬币得到正面
typedef int ElementType;// 定义存储元素类型

// 定义链表节点
typedef struct Node
{
	ElementType value;// 节点中存储的数据
	// 三个方向的指针，横向是单链表，纵向是双链表
	Node* next;	
	Node* up;
	Node* down;
}Node;

// 跳跃表结构定义
typedef struct SkipList
{
	int level;// 记录当前的跳跃表有几层
	vector<Node*> heads; // 管理头节点，便于以后从最高层往最底层查找
}SkipList;

// 建立一个只含头节点的表
SkipList* createSkipList()
{
	SkipList* ptrSkipList=new SkipList;
	ptrSkipList->level=1;
	// 创建第一个节点
	Node* head=new Node;
	head->value=INT_MIN;// 头节点的数据统一设置为-∞
	// 初始化三个指针为空
	head->next=nullptr;
	head->up=nullptr;
	head->down=nullptr;
	ptrSkipList->heads.emplace_back(head);// 将节点指针加入vector
	srand(time(0));// 播撒随机种子
	return ptrSkipList;
}

// 产生随机数，决定插入的元素要不要往上走
bool flipCoin()
{
	if(rand()%2==1)
		return Face;
	else
		return Tail;
}

// 跳跃表的插入
void insert(SkipList* ptrSkipList,ElementType value)
{
	// 首先插入最底层的链表，注意插入时要保证有序性
	Node* ptrNewNode=new Node;
	Node* p,*q;// 辅助指针
	ptrNewNode->value=value;
	ptrNewNode->next=nullptr;
	ptrNewNode->up=nullptr;
	ptrNewNode->down=nullptr;
	// 寻找插入的合适位置
	for(p=ptrSkipList->heads[0]->next,q=ptrSkipList->heads[0];(p!=nullptr)&&(value>p->value);p=p->next,q=q->next)
	{
		// 注意不要把p=p->next;写成p++;，会出事的
	}
	// 应该插在q后面
	q->next=ptrNewNode;
	ptrNewNode->next=p;
	// 抛硬币，如果是反面，结束，否则向上走
	int currentLevel=0;// 记录当前的层数，方便后面的连接，0在这里是一个没有意义的数，最小的level是1
	Node* move=ptrNewNode;// 辅助指针move，每次promote指向相同的节点
	// 开始抛硬币，如果是正面就上升(promote)
	while(flipCoin()!=Tail)
	{	
		cout<<"插入"<<value<<"时得到正面"<<endl;
		currentLevel++;
		// 新建一个节点包含这个元素
		Node* promote=new Node;
		promote->value=value;
		// 和下面含有相同元素的节点互连
		move->up=promote;
		promote->down=move;
		promote->next=nullptr;
		move=promote;// 更新move
		// 如果没有头节点，新建一个头节点，每次头节点也要promote
		if(ptrSkipList->heads.size()<currentLevel+1)
		{
			Node* head=new Node;
			head->value=INT_MIN;
			head->next=nullptr;
			// 连接两个头节点
			ptrSkipList->heads[currentLevel-1]->up=head;
			head->down=ptrSkipList->heads[currentLevel-1];		
			ptrSkipList->heads.emplace_back(head);// 加入新的头节点
			ptrSkipList->level++;// 更新层数
		}
		// 最后连接相同level的节点
		Node* r,*s;// 辅助指针
		for(r=ptrSkipList->heads[currentLevel]->next,s=ptrSkipList->heads[currentLevel];(r!=nullptr)&&(value>r->value);r=r->next,s=s->next)
		{
			// promote的时候也要保证元素之间的顺序，从小到大排列
		}
		s->next=move;
		move->next=r;
	}
	cout<<value<<"插入完毕"<<endl;
}

int main(int argc, char* argv[])
{
	SkipList* mylist=createSkipList();
	insert(mylist,4);
	insert(mylist,3);
	insert(mylist,0);
	insert(mylist,13);
	insert(mylist,2);
	insert(mylist,50);
	insert(mylist,7);
	cout<<"跳跃表层数："<<mylist->level<<endl;
	for(int i=mylist->level-1;i>=0;i--)
	{
		cout<<"第"<<i+1<<"层元素是：";
		for(Node* p=mylist->heads[i];p!=nullptr;p=p->next){
			cout<<p->value<<" ";
		}
		cout<<endl;
	}
}

写完以后才发现横向上其实也需要两个指针。。。这样查找算法就比较贴近公开课里讲的了，看起来更优雅，不过一个指针其实也是可以的，反正万变不离其宗，将就吧。。

这是测试结果：

做了一个可视化：

真美啊~