skip list跳表C語言代碼。

代碼：

#include 
#include 
#include 
#include 

#define SKIP_LIST_INIT_LEVEL  5

struct list_node_s;
struct list_s;
typedef struct list_node_s list_node_t;
typedef struct list_s list_t;

struct list_node_s {
	int key;
	void *value;
	int high;
	struct list_node_s **forward;
};

struct list_s {
	int level;
	struct list_node_s *header;
};


int random_level();
list_t *new_list(int init_level);
list_node_t *new_list_node(int high);
void *find(list_t *l, int key);
void insert(list_t *l, int key, void *value);
void *delete_node(list_t *l, int key);
void *destroy(list_t *l);

int random_level()
{
	int k = 0;
//	srand(time(NULL));
	while (rand() % 2) {
		k++;
	}

	return k;
}

list_t *new_list(int init_level) 
{
	list_t *l;
	l = malloc(sizeof(list_t));
	l->header = new_list_node(init_level);
	l->level = 0;
	l->header->key = -1;
	return l;
}

list_node_t *new_list_node(int high) 
{
	int i;
	list_node_t *n;
	n = malloc(sizeof(list_node_t));
	n->forward = malloc(high *sizeof(void *));
	n->high = high;
	
	for (i = 0; i < high; i++) {
		n->forward[i] = NULL;
	}
	
	return n;
}

void *find(list_t *l, int key)
{
	int k = l->level;
	list_node_t *n = l->header;
	
	while (n && k >= 0) {
		while(n->forward[k] && n->forward[k]->key <= key) {
			n = n->forward[k];
		}
		
		if (n->key == key) {
			return n->value;
		}
		k--;
	}

	return NULL;
}

void insert(list_t *l, int key, void *value)
{
	int insert_level;
	int k;
	size_t size;
	list_node_t *p, *q, *n;
	list_node_t **update;
	
	k = l->level;
	size = sizeof(void *) * (k + 1);
	update = malloc(size);
	p = q = l->header;

	while (q && k >= 0) {
		while (q->key < key) {
			p = q;
			if (q->forward[k]) {
				q = q->forward[k];
			}
			else {
				break;
			}
		}
		q = update[k] = p;
		//	printf(level:%d->%d ,k, p->key);
		k--;
	}

	insert_level = random_level();
	if (insert_level > l->level ) {

		k = l->level++;
		insert_level = l->level;
		n = new_list_node(insert_level + 1);
		n->key = key;
		n->value = value;
		if (insert_level >= l->header->high) {
			list_node_t **l1, **l2;
			l1 = malloc(sizeof(void *) * (insert_level + 1));
			l2 = l->header->forward;
			memcpy(l1, l2, sizeof(void *) * insert_level);
			l1[insert_level] = NULL;
			l->header->forward = l1;
			free(l2);
			l->header->high++;
			l->header->forward[insert_level] = n;
		}
		else {
			l->header->forward[insert_level] = n;
		}

	}
	else {
		k = insert_level;
		n = new_list_node(k + 1);
		n->value = value;
		n->key = key;
	}
//	printf(key: %d update: , key);
	
	while (k >= 0) {
		p = update[k];
//		printf(%d , p->key);
		q = p->forward[k];
		p->forward[k] = n;
		n->forward[k] = q;
		k--;
	}
//	printf(
);
	free(update);
}

void *delete(list_t *l, int key) 
{
	int k = l->level;
	list_node_t *p, *q, *n;
	p = q = l->header;
	n = NULL;
	list_node_t **update;
	
	update = malloc(sizeof(void *) * (k + 1));
	
	while (q && k >= 0) {
		while (q->key < key) {
			p = q;
			if (q->forward[k]) {
				q = q->forward[k];
			}
			else {
				break;
			}
		}
		
		q = update[k] = p;
	
		k--;
	}

	if (update[0]->forward[0] && update[0]->forward[0]->key == key) {
		n = update[0]->forward[0];
	}
	else {
		free(update);
		return NULL;
	}
	
	k = n->high - 1;
	while (k >= 0) {
		p = update[k];
		p->forward[k] = n->forward[k];
		k--;
	}

	free(update);
	return n->value;
}


void show_list(list_t *l) 
{
	int k = l->level;
	list_node_t *n;
	n = l->header;
	while (k >= 0) {
		n = l->header;
		while (n) {
			printf(%d , n->key);
			n = n->forward[k];
		}
		printf(
);
		k--;
	}
}

int main(int argc, char *argv[]) 
{
	int k, i;
	list_t *l;
	void *ptr = &k;
	l = new_list(10);
	k = atoi(argv[1]);
	
	srand(time(NULL));
	i = k;

	printf(---------------
);
	while (i > 0) {
		int key;
		key = rand() % k;
		insert(l, key, ptr);
		//	show_list(l);
		i--;
	}
	i = k ;
	show_list(l);
	while (i > 0) {
		int key;
		void *p;
		key = rand() % k;
		p = find(l, key);
		if (p == NULL) {
			printf(key %d not found
, key);
		}
		else {
			delete(l, key);
			printf(key %d found
, key);
		}
		i--;
	}
	printf(
--------------
);
	//show_list(l);
	return 0;
}