跳表(skiplist)的代码实现.doc

跳表（skiplist）的代码实现 跳表（skiplist）是一个非常优秀的数据结构，实现简单，插入、删除、查找的复杂度均为O(logN)。LevelDB的核心数据结构是用跳表实现的，redis的sorted set数据结构也是有跳表实现的。其结构如下所示：所有操作均从上向下逐层查找，越上层一次next操作跨度越大。其实现是典型的空间换时间。具体的细节，可参考维基百科/wiki/Skip_list本文作者将redis的sorted set代码进行整理，将跳表部分的实现抽取出来，供参考。skiplist.h 1 #ifndef _SKIPLIST_H 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 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) 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) 28 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) (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-level = 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 = node; 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-backward; 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 = 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 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, (int)score);139 return 0;140 141 142 143 void slPrint(skiplist *sl) 144 skiplistNode *node;145 int i;146 for (i = 0; i header-leveli.forward;149 while(node) 150 printf(%d - , (int)(node-score);151 node = node-leveli.forward;152 153 printf(NULLn);154 155 156 157 #ifdef SKIP_LIST_TEST_MAIN158 int main() 159 srand(unsigned)time(0);160 int count = 20, i;161 162 printf(# Function Test #n);163 164 printf(= Init Skip List =n);165 skiplist * sl = slCreate();166 for ( i = 0; i count; i+) 167 slInsert(sl,i);168 169 printf(= Print Skip List =n);170 slPrint(sl);171 172 printf(= Search Skip List =n);173 for (i = 0; i count; i+) 174 int value = rand()%(count+10);175 slSearch(sl, value);176 177 printf(= Delete Skip List =n);178 for (i = 0; i 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 - 12 - 13 - 14 - 15 - 16 - 17 - 18 - 19 - NULL 5 LEVEL1: 0 - 2 - 4 - 7 - 9 - 10 - 11 - 12 - 14 - 15 - 17 - 18 - NULL 6 LEVEL2: 7 - 10 - 12 - 14 - 15 - NULL 7 LEVEL3: 10 - 14 - 15 - NULL 8 LEVEL4: 10 - 14 - NULL 9 LEVEL5: NULL10 LEVEL6: NULL11 LEVEL7: NULL12 = Search Skip List =13 Found 114 Found 1815 Not found 2116 Not found 2417 Found 1018 Not found 2019 Found 1420 Found 1021 Found 1922 Found 1823 Not found 2724 Found 525 Found 026 Found 027 Found 1828 Not found 2629 Found 1330 Not found 2831 Not found 2932 Not found 2333 = Delete Skip List =34 Delete0: SUCCESS35 Delete2: SUCCESS36 Delete4: SUCCESS37 Delete6: SUCCESS38 Delete8: SUCCESS39 Delete10: SUCCESS40 Delete12: SUCCESS41 Delete14: SUCCESS42 Delete16: SUCCESS43 Delete18: SUCCESS44 Delete20: NOT FOUND45 Delete22: NOT FOUND46 Delet