今天有同学去面试，被问到了“跳表”这种数据结构，说实话我之前对它了解不多，于是上网查了跳表的资料，并在这里总结一下。

什么是跳表？要说清楚这个问题，我们就要先从普通的有序链表说起。一个普通有序列表的结构如下：

我们可以看到，上图所示的链表按照由小到大的顺序排列（-1表示最小值，1表示最大值，这是本文的一个约定），如果我们想要查找一个元素x，算法如下：

1
2
3

cell *p = head;
while (p->next->key < x)  p=p->next;
return p;