《跳表(skiplist)的代码实现.doc》由会员分享，可在线阅读，更多相关《跳表(skiplist)的代码实现.doc（8页珍藏版）》请在金锄头文库上搜索。
1、跳表（skiplist）的代码实现 跳表（skiplist）是一个非常优秀的数据结构，实现简单，插入、删除、查找的复杂度均为O(logN)。LevelDB的核心数据结构是用跳表实现的，redis的sorted set数据结构也是有跳表实现的。其结构如下所示：所有操作均从上向下逐层查找，越上层一次next操作跨度越大。其实现是典型的空间换时间。具体的细节，可参考维基百科http:/en.wikipedia.org/wiki/Skip_list本文作者将redis的sorted set代码进行整理，将跳表部分的实现抽取出来，供参考。skiplist.h 1 #ifndef _SKIPLIST_H
2、2 #define _SKIPLIST_H 3 4 #define SKIPLIST_MAXLEVEL 8 5 6 typedef struct skiplistNode 7 double score; 8 struct skiplistNode *backward; 9 struct skiplistLevel 10 struct skiplistNode *forward;11 level;12 skiplistNode;13 14 typedef struct skiplist 15 struct skiplistNode *header, *tail;16 unsigned long
3、length;17 int level;18 skiplist;19 20 #endifskiplist.c 1 #include skiplist.h 2 #include 3 #include 4 5 skiplistNode *slCreateNode(int level, double score) 6 skiplistNode * sn = malloc(sizeof(*sn) + level*sizeof(struct skiplistLevel); 7 sn-score = score; 8 return sn; 9 10 11 skiplist *slCreate(void)
4、12 int j; 13 skiplist *sl; 14 15 sl = malloc(sizeof(*sl); 16 sl-level = 1; 17 sl-length = 0; 18 sl-header = slCreateNode(SKIPLIST_MAXLEVEL, 0); 19 for(j = 0; j header-levelj.forward = NULL; 21 22 sl-header-backward = NULL; 23 sl-tail = NULL; 24 return sl; 25 26 27 void slFreeNode(skiplistNode *sn) 2
5、8 free(sn); 29 30 31 void slFree(skiplist *sl) 32 skiplistNode *node = sl-header-level0.forward, *next; 33 34 free(sl-header); 35 while(node) 36 next = node-level0.forward; 37 slFreeNode(node); 38 node = next; 39 40 free(sl); 41 42 43 int slRandomLevel(void) 44 int level = 1; 45 while(rand()&0xFFFF)
6、 (0.5 * 0xFFFF) 46 level += 1; 47 return (level header; 55 int i, level; 56 for ( i = sl-level-1; i = 0; i-) 57 while(node-leveli.forward & node-leveli.forward-score leveli.forward; 59 60 updatei = node; 61 62 level = slRandomLevel(); 63 if (level sl-level) 64 for (i = sl-level; iheader; 66 67 sl-le
7、vel = level; 68 69 node = slCreateNode(level, score); 70 for (i = 0; i leveli.forward = updatei-leveli.forward; 72 updatei-leveli.forward = node; 73 74 75 node-backward = (update0 = sl-header? NULL : update0); 76 if (node-level0.forward) 77 node-level0.forward-backward = node; 78 else 79 sl-tail = n
8、ode; 80 sl-length+; 81 return node; 82 83 84 void slDeleteNode(skiplist *sl, skiplistNode *x, skiplistNode *update) 85 int i; 86 for (i = 0; i level; i+) 87 if (updatei-leveli.forward = x) 88 updatei-leveli.forward = x-leveli.forward; 89 90 91 if (x-level0.forward) 92 x-level0.forward-backward = x-b
9、ackward; 93 else 94 sl-tail = x-backward; 95 96 while (sl-level 1 & sl-header-levelsl-level-1.forward = NULL) 97 sl-level-; 98 sl-length-; 99 100 101 int slDelete(skiplist *sl, double score) 102 skiplistNode *updateSKIPLIST_MAXLEVEL, *node;103 int i;104 105 node = sl-header;106 for(i = sl-level-1; i
10、 = 0; i-) 107 while (node-leveli.forward & node-leveli.forward-score leveli.forward;109 110 updatei = node;111 112 node = node-level0.forward;113 if (node & score = node-score) 114 slDeleteNode(sl, node, update);115 slFreeNode(node);116 return 1;117 else 118 return 0;119 120 return 0;121 122 123 int
11、 slSearch(skiplist *sl, double score) 124 skiplistNode *node;125 int i;126 127 node = sl-header;128 for (i = sl-level-1; i = 0 ;i-) 129 while(node-leveli.forward & node-leveli.forward-score leveli.forward;131 132 133 node = node-level0.forward;134 if (node & score = node-score) 135 printf(Found %dn,(int)node-score);136 return 1;137 else 138 printf(Not found %dn
