node = sl->header;
for(i = sl->level-1; i >= 0; i--) {
while (node->level[i].forward && node->level[i].forward->score < score) {
node = node->level[i].forward;
}
update[i] = node;
}
node = node->level[0].forward;
if (node && score == node->score) {
slDeleteNode(sl, node, update);
slFreeNode(node);
return 1;
} else {
return 0;
}
return 0;
}
int slSearch(skiplist *sl, double score) {
skiplistNode *node;
int i;
node = sl->header;
for (i = sl->level-1; i >= 0 ;i--) {
while(node->level[i].forward && node->level[i].forward->score < score) {
node = node->level[i].forward;
}
}
node = node->level[0].forward;
if (node && score == node->score) {
printf("Found %d\n",(int)node->score);
return 1;
} else {
printf("Not found %d\n", (int)score);
return 0;
}
}
void slPrint(skiplist *sl) {
skiplistNode *node;
int i;
for (i = 0; i < SKIPLIST_MAXLEVEL; i++) {
printf("LEVEL[%d]: ", i);
node = sl->header->level[i].forward;
while(node) {
printf("%d -> ", (int)(node->score));
node = node->level[i].forward;
}
printf("NULL\n");
}
}
#ifdef SKIP_LIST_TEST_MAIN
int main() {
srand((unsigned)time(0));
int count = 20, i;
printf("### Function Test ###\n");
printf("=== Init Skip List ===\n");
skiplist * sl = slCreate();
for ( i = 0; i < count; i++) {
slInsert(sl,i);
}
printf("=== Print Skip List ===\n");
slPrint(sl);
printf("=== Search Skip List ===\n");
for (i = 0; i < count; i++) {
int value = rand()%(count+10);
slSearch(sl, value);
}
printf("=== Delete Skip List ===\n");
for (i = 0; i < count+10; i+=2) {
printf("Delete[%d]: %s\n", i, slDelete(sl, i)?"SUCCESS":"NOT FOUND");
}
slPrint(sl);
slFree(sl);
sl = NULL;
}
#endif
测试结果如下所示：
### Function Test ###
=== Init Skip List ===
=== Print Skip List ===
LEVEL[0]: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> 12 -> 13 -> 14 -> 15 -> 16 -> 17 -> 18 -> 19 -> NULL
LEVEL[1]: 0 -> 2 -> 4 -> 7 -> 9 -> 10 -> 11 -> 12 -> 14 -> 15 -> 17 -> 18 -> NULL
LEVEL[2]: 7 -> 10 -> 12 -> 14 -> 15 -> NULL
LEVEL[3]: 10 -> 14 -> 15 -> NULL
LEVEL[4]: 10 -> 14 -> NULL
LEVEL[5]: NULL
LEVEL[6]: NULL
LEVEL[7]: NULL
=== Search Skip List ===
Found 1
Found 18
Not found 21
Not found 24
Found 10
Not found 20
Found 14
Found 10
Found 19
Found 18
Not found 27
Found 5
Found 0
Found 0
Found 18
Not found 26
Found 13
Not found 28
Not found 29
Not found 23
=== Delete Skip List ===
Delete[0]: SUCCESS
Delete[2]: SUCCESS
Delete[4]: SUCCESS
Delete[6]: SUCCESS
Delete[8]: SUCCESS
Delete[10]: SUCCESS
Delete[12]: SUCCESS
Delete[14]: SUCCESS
Delete[16]: SUCCESS
Delete[18]: SUCCESS
Delete[20]: NOT FOUND
Delete[22]: NOT FOUND
Delete[24]: NOT FOUND
Delete[26]: NOT FOUND
Delete[28]: NOT FOUND
LEVEL[0]: 1 -> 3 -> 5 -> 7 -> 9 -> 11 -> 13 -> 15 -> 17 -> 19 -> NULL
LEVEL[1]: 7 -> 9 -> 11 -> 15 -> 17 -> NULL
LEVEL[2]: 7 -> 15 -> NULL
LEVEL[3]: 15 -> NULL
LEVEL[4]: NULL
LEVEL[5]: NULL
LEVEL[6]: NULL
LEVEL[7]: NULL