跳表(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 *));

每次创建新的节点的时候, 都必须用到上面这条语句。

其实, 从数据结构的角度来看,上面这张图并没有很好的表示出整个skiplist结构, 我特地手绘了一个版本,见笑了,对照着我画得图, 看代码会更容易懂一些。

假设有 21, 32, 14 , 7 37被依次插入到链表中,并且level 随机生成如图所示, 则按照我的代码一步一步的插入,最后应该是这个样子的。

图中的0,1,2…表示 forward[0], forward[1] ,forward[2]等等,就这样。

所以, 创建一个 skiplist的过程用代码表示是这样的:

最重要的两个函数 : 插入 和 删除 。

首先是插入函数:

wordpress不用插件贴出来的代码实在是太恶心了, 乱七八糟的一坨!!!

每次写博客都要花大量的时间在排版代码上!       TM烦死了!

以后再也不会在博客里面贴代码了,直接放源码吧, 你大爷的!

代码  git clone git://github.com/run/skiplist.git

参考资料:

[1] http://en.wikipedia.org/wiki/Skip_list
[2] http://www.cnblogs.com/xuqiang/archive/2011/05/22/2053516.html
[3] 如果真的闲的蛋疼的话, 可以拜读一下William Pugh的论文,就是他发明了skiplist。

Tags: ,. 30,295 views
Home

30 Comments so far

Trackbacks/Pingbacks

Leave a comment

Name(required)
Mail (required),(will not be published)
Website(recommended)

Fields in bold are required. Email addresses are never published or distributed.

Some HTML code is allowed:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
URLs must be fully qualified (eg: http://blog.nlogn.cn),and all tags must be properly closed.

Line breaks and paragraphs are automatically converted.

Please keep comments relevant. Off-topic, offensive or inappropriate comments may be edited or removed.