一个简单的跳表(SkipList)实现
跳表（skiplist） 是一个非常有趣的、简单的数据结构， 应用也非常广泛， 著名的NoSQL内存数据库Redis， 就用到了skiplist作为排序集合的基础数据结构。 跳表最大的特点就是插入、删除操作的性能均为O(logn) 。 关于它的原理网上有一大堆，如果不了解的话，可以先看看文章末尾的参考资料， 或者动手google一下。 需要指出的是，网上搜的一些的文章原理介绍的不错， 但是代码写的有点乱， 排版的时候也没有语法高亮， 所以我自己也参照着写了一份， 并且在这里简单的注释一下。 首先， 一个“跳表” 基本上长的是这个样子的： 再来看下抽象的数据结构： #define object int typedef struct _node { int key; object *obj; struct _node *forward[1]; } node; typedef struct _skiplist { int level; struct _node *head; } skiplist; 值得注意的是， 结构体 node 的 forward 指针数组长度为1， 而我们从 skiplist 的长相和定义来看， forward 数组大小是随机的， 在 1 – MAX_LEVEL 之间， 因此， 一个技巧就是这样： node *nd = (node *)malloc(sizeof(node) + level * sizeof(node *)); 每次创建新的节点的时候， 都必须用到上面这条语句。 ...