2004或2005年寫的代碼。
skiplist：
skiplist.h
/*
* 随机性查找数据结构的一种重要方案。
* 在 1990 年由 W. Pugh 发明。
*/
typedef int typekey;
/*
* 跳跃表节点，包含到后继节点的指针数组，它的大小对应于节点的级别。
* 节点的级别在建立时随机分配，并且不用在节点中保存。
*/
typedef struct node{
typekey key;
char *value;
struct node *forward[1];
} node;
/*
* 跳跃表数据结构，包含当前的整体级别、节点数目和头部节点。
* 头部节点的指针数组大小是 MaxLevel。
*/
typedef struct {
int level;
int count;
node * header;
} listnode,* skiplist;
extern skiplist init(void); /* 跳跃表建立例程 */
extern void destroy(skiplist); /* 跳跃表清除例程 */
extern node* search(typekey, skiplist);
extern node* insert(typekey, skiplist);
extern void delete(typekey, skiplist);
|
skiplist.c
#include <stdio.h>
#include <stdlib.h>
#include "./skiplist.h"
skiplist init(void);
void destroy(skiplist);
node* search(typekey, skiplist);
node* insert(typekey, skiplist);
void delete(typekey,skiplist);
static node* makeNode(int,int);
static void freeNode(node *);
static void Error(void);
#define MaxLevel 16 /* 最大级别数 */
#define Probability RAND_MAX/2 /* 提升级别的概率，这里是有 1/2 的可能性提级 */
node* search(typekey key, skiplist list)
{
node * x;
int i;
x = list->header;
for (i = list->level-1; i>=0; i--) /* 从高到低查找各个级别的链表 */
/* 在这个链表上把当前指针定位到小于这个查找键值的最后的节点 */
while (x->forward[i] != NULL && x->forward[i]->key < key)
x = x->forward[i];
x = x->forward[0];
if (x != NULL && x->key == key)
return x;
else
return NULL;
}
node* insert(typekey key, skiplist list)
{
/* 要插入的节点在每个级别的链表上前面最近的节点 */
node * update[MaxLevel];
node *x;
int i;
int lvl = 1; /* 新建节点的级别 */
x = list->header;
/* 找到要插入节点在各个级别的链表上的位置 */
for (i = list->level-1; i>=0; i--) {
while (x->forward[i] != NULL && x->forward[i]->key < key)
x = x->forward[i];
update[i] = x;
}
x = x->forward[0];
if (x != NULL && x->key == key) {
Error();
return NULL;
} else {
while (rand() < Probability && lvl < MaxLevel) /* 随机生成新节点的级别 */
lvl++;
if (lvl > list->level) { /* 新节点的级别大于当前的整体级别 */
for (i = lvl-1; i >= list->level ; i--)
update[i] = list->header; /* 补充超出的级别上的前面最近的节点 */
list->level = lvl; /* 提升整体级别 */
}
x = makeNode(lvl,key);
/* 在各个级别的链表上插入新节点 */
for (i = lvl-1; i >= 0; i--) {
x->forward[i] = update[i]->forward[i];
update[i]->forward[i] = x;
}
list->count++;
return x;
}
}
void delete(typekey key,skiplist list)
{
/* 要删除的节点在每个级别的链表上前面最近的节点 */
node *update[MaxLevel];
node * x;
int i;
x = list->header;
/* 找到要删除的节点在各个级别的链表上的位置 */
for (i = list->level-1; i >= 0; i--) {
while (x->forward[i] != NULL && x->forward[i]->key < key)
x = x->forward[i];
update[i] = x;
}
x = x->forward[0];
/* 在各个级别的链表删除这个节点 */
if (x != NULL && x->key == key) {
for (i = 0; i < list->level; i++) {
if (update[i]->forward[i] != x) /* 这个节点未达到这个级别 */
break;
update[i]->forward[i] = x->forward[i];
}
freeNode(x);
list->count--;
/* 当要删除的这个节点是某个级别上唯一的节点时将导致整体的级别下降 */
while (list->level >1 && list->header->forward[list->level-1] == NULL)
list->level--;
}
else
Error();
}
skiplist init(void)
{
skiplist l;
node * t;
int i;
l = (skiplist)malloc(sizeof(listnode));
t = (node*)malloc(sizeof(node)+(MaxLevel-1)*sizeof(node *));
t->value = NULL;
for(i = MaxLevel-1; i >= 0; i--)
t->forward[i] = NULL;
l->header = t;
l->level = 1;
l->count = 0;
return l;
}
void destroy(skiplist list)
{
node *x, *p;
x = list->header;
while(x != NULL) {
p = x;
x = x->forward[0];
freeNode(p);
}
free(list);
}
node* makeNode(int level,typekey key)
{
node * t;
t = (node*)malloc(sizeof(node)+(level-1)*sizeof(node *));
t->value = NULL;
t->key = key;
return t;
}
void freeNode(node * t)
{
if (t->value != NULL)
free(t->value);
free(t);
}
void Error(void)
{
printf("Skip List error\n");
}
|
