卓越飞翔博客
我在这里分享我的跳跃列表实现。继续接受 c 语言培训是个好主意。
#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>
#define LOGLEVEL 3
// a skip list is made of a single linked where each element has an
// array of pointers to the next element of the same level.
// I will name `level_pointer` the array of pointers,
// for each element "e" in the list e.level_pointer[n] points to
// the next element "e1" at the same level.
// Every pointer with m smaller than n, the e.level_pointer[m] points
// to an element "e2" such that e =m such that
// e level_pointer = (struct skiplist**) calloc(1, sizeof(struct skiplist*));
slc->maxlevel = 1;
slc->level_pointer[0] = NULL;
slc->cmp = cmp;
return slc;
}
void logit(const char *restrict format, ...) {
va_list ap;
va_start( ap, format );
vprintf(format, ap);
}
void sklist_insert(struct sklist* slc, void *element) {
// create the new node
struct skiplist * sknode = (struct skiplist*) malloc(sizeof(struct skiplist*));
sknode->element = element;
sknode->maxlevel = 1;
// toss a coin to determine the element maxlevel
while ((rand() % 2) == 1) {
sknode->maxlevel++;
}
#if LOGLEVEL == 3
logit("INSERTING %d at LEVE %dn",*(int*)element, sknode->maxlevel);
#endif
sknode->level_pointer = (struct skiplist**) calloc(sknode->maxlevel, sizeof(struct skiplist*));
int from_level = sknode->maxlevel-1;
if (sknode->maxlevel > slc->maxlevel ) {
// if the new element has the tallest level_pointer
// it means all the pointers with higher level points to the new element
slc->level_pointer = (struct skiplist**) realloc(slc->level_pointer, sknode->maxlevel * sizeof(struct skiplist*));
int i;
for (i = slc->maxlevel; imaxlevel; i++) {
slc->level_pointer[i] = sknode;
sknode->level_pointer[i] = NULL;
}
from_level = slc->maxlevel - 1;
slc->maxlevel = sknode->maxlevel;
}
// starting from_level the insertion must be checked
struct skiplist ** left_p = slc->level_pointer;
for(;from_level>=0;from_level--) {
// peak the next element pointed, still staying a position before
// keeping in mind that head is smaller than anything,
// then left_p belong to something smaller than sknode
while( (left_p[from_level] != NULL) && slc->cmp(left_p[from_level]->element, sknode->element)level_pointer;
}
sknode->level_pointer[from_level] = left_p[from_level];
left_p[from_level] = sknode;
#if LOGLEVEL == 3
logit("Inserted %dn", *(int*) sknode->element);
#endif
//printf("left %dn", *(int*) left_p[from_level]->level_pointer[from_level]->element);
}
}
struct skiplist * sklist_exists(struct sklist* slc, void *element) {
// search for element and return it if it exists, return NULL otherwise
int maxlevel = slc->maxlevel-1;
struct skiplist ** lpoint = slc->level_pointer;
for (;maxlevel>=0; maxlevel--) {
struct skiplist ** prev;
while (lpoint[maxlevel]!=NULL && slc->cmp(lpoint[maxlevel]->element, element) element, maxlevel);
prev = lpoint;
lpoint = lpoint[maxlevel]->level_pointer;
}
if (lpoint[maxlevel]!=NULL && slc->cmp(lpoint[maxlevel]->element, element) == 0) {
return lpoint[maxlevel];
} else {
lpoint = prev;
}
}
return NULL;
}
struct skiplist * sklist_extract(struct sklist* slc, void *element) {
// search for element and return it if it exists, return NULL otherwise
int maxlevel = slc->maxlevel-1;
struct skiplist ** lpoint = slc->level_pointer;
struct skiplist * el_pile = NULL;
while (maxlevel>=0) {
struct skiplist ** prev = NULL;
while (lpoint[maxlevel]!=NULL && slc->cmp(lpoint[maxlevel]->element, element) element, maxlevel);
#endif
prev = lpoint;
lpoint = lpoint[maxlevel]->level_pointer;
}
if (lpoint[maxlevel]!=NULL && slc->cmp(lpoint[maxlevel]->element, element) == 0) {
#if LOGLEVEL == 3
logit("FOUND HHHHH l:%dn",lpoint[maxlevel]->maxlevel);
#endif
// remove everything from this level here to below:
if (el_pile == NULL && lpoint[maxlevel]->maxlevel == slc->maxlevel) {
el_pile = lpoint[maxlevel];
// it must resize the maxlevel of the main structure
// for this just inspect the main level_pointer and this element level_pointer
// until the second one is NULL and the first one is exactly this element
// reduce the maxlevel of the mail structure
int i = el_pile->maxlevel-1;
while(i>0 && (slc->level_pointer[i] == el_pile && el_pile->level_pointer[i] == NULL)) i--;
slc->maxlevel = i+1; // the level is the size
maxlevel = slc->maxlevel;
#if LOGLEVEL == 3
logit("shrink level %dn", maxlevel);
#endif
}
// eat one pos
lpoint[maxlevel] = lpoint[maxlevel]->level_pointer[maxlevel];
} else {
lpoint = prev;
}
maxlevel--;
}
return el_pile;
//return NULL;
}
int compare_ints(void *X, void *Y) {
int *x = (int*) X;
int *y = (int*) Y;
if(*xmaxlevel);
int l = slc->maxlevel;
for(int i=0;i<l struct skiplist head="slc-">level_pointer[i];
printf("nLEVEL: %dn",i);
while (head != NULL) {
printf("%dt-t", *(int*) (head->element));
head = head->level_pointer[i];
}
}
printf("n");
}
void pile_print_it(struct sklist* slc) {
printf("PILE staff: maxlevel: %dn", slc->maxlevel);
int l = slc->maxlevel;
for(int i=0;i<l printf struct skiplist head="slc-">level_pointer[i];
struct skiplist * head0 = slc->level_pointer[0];
while (head != NULL) {
while (head0!= head) {
printf("--t-t");
head0 = head0->level_pointer[0];
}
printf("%dt-t", *(int*) (head->element));
head = head->level_pointer[i];
head0 = head0->level_pointer[0];
}
}
printf("n");
}
int main() {
int *i;
*i = 190;
int j = 12;
printf("COMPARE %d vs %d : %dn", j, *i, compare_ints((void*) &j, (void *) i));
// *j = 12;
struct sklist *skipl = create_skip(compare_ints);
print_it(skipl);
sklist_insert(skipl, (void*)i);
print_it(skipl);
sklist_insert(skipl, (void*)&j);
print_it(skipl);
int k = 23;
sklist_insert(skipl, (void*)&k);
print_it(skipl);
int kk = 123;
sklist_insert(skipl, (void*)&kk);
pile_print_it(skipl);
int kk2 = 23;
struct skiplist *el = sklist_exists(skipl, (void*) &kk2);
if(el!=NULL) {
printf("FOUND!!!!!n");
} else {
printf("NOOOOT FOUND!!n");
}
for(;;) {
printf("command (I_nsert/L_ookup): n");
char command = (char) getchar();
//if (command == 'n') command = (char) getchar();
switch (command) {
case 'i':
case 'I':
{
printf("insert a num: ");
int *xx = malloc(sizeof(int));
scanf("%d", xx);
sklist_insert(skipl, (void*)xx);
pile_print_it(skipl);
}
break;
case 'l':
case 'L':
{
printf("lookup a num: ");
int *xx = malloc(sizeof(int));
scanf("%d", xx);
struct skiplist *el = sklist_exists(skipl, (void*) xx);
if(el!=NULL) {
printf("%d FOUND!!!!!n", *xx);
} else {
printf("%d NOOOOT FOUND!!n", *xx);
}
}
break;
case 'e':
case 'E':
{
printf("extract a num: ");
int *xx = malloc(sizeof(int));
scanf("%d", xx);
struct skiplist *el = sklist_extract(skipl, (void*) xx);
if(el!=NULL) {
printf("%d FOUND!!!!!n", *xx);
} else {
printf("%d NOOOOT FOUND!!n", *xx);
}
//free(el);
}
case 'p':
case 'P':
pile_print_it(skipl);
break;
case 'x':
return 0;
}
}
}
</l></l></stdarg.h></stdio.h></stdlib.h>其中存在一些错误，待修复
