Siersan

Unlike a balanced skip list, a probabilistic skip list uses random numbers to determine the height of each node rather than deterministic logic. The only real advantage of using a linked structure instead of an array based structure is in code maintainability.

90 Views
``````#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct node {
int data;
struct node *right;
struct node *down;
};

struct list {
int level;
};

/*
Naive example function
Don't use in production code
*/

int rand_level(int limit)
{
int i = 1;

while (rand() < RAND_MAX / 2 && i < limit) {
++i;
}

return i;
}

struct node *make_node(int data, struct node *right, struct node *down)
{
struct node *node = malloc(sizeof *node);

if (node == NULL) {
return NULL;
}

node->data = data;
node->right = right;
node->down = down;

return node;
}

void destroy_node(struct node *node)
{
free(node);
}

int insert_node(struct list *list, int data)
{
struct node *x, *save = NULL;
int i, level = rand_level(list->level + 1);

while (level > list->level) {
++list->level;
}

for (i = list->level; x != NULL; i--) {
while (x->right != NULL && data > x->right->data) {
x = x->right;
}

if ( i <= level ) {
if (x->right == NULL || data != x->right->data) {
x->right = make_node(data, x->right, NULL);
}

if (save != NULL) {
save->down = x->right;
}

save = x->right;
}

x = x->down;
}

return 1;
}

int remove_node(struct list *list, int data)
{
int ret = 0;
struct node *x, *save;

while (x != NULL) {
while (x->right != NULL && data > x->right->data) {
x = x->right;
}

if (x->right != NULL && data == x->right->data) {
save = x->right;
x->right = save->right;
destroy_node(save);

ret = 1;
}

x = x->down;
}

destroy_node(save);
}

return ret;
}

void list_structure(struct list *list)
{
struct node *x, *y, *z;

for (x = list->head; x != NULL; x = x->down) {
for (z = list->head; z->down != NULL; z = z->down) {
}

for (y = x; y != NULL; y = y->right) {
for (; z != NULL && z->data != y->data; z = z->right) {
printf("-");

if (z->right != NULL && z->right->data != y->data) {
printf("--");
}
}

printf("%02d", y->data);
}

printf("\n");
}
}

int main(void)
{
struct list list = {0};
int i;

srand((unsigned int)time(NULL));

for (i = 0; i < 25; i++) {
insert_node(&list, rand() % 99 + 1);

list_structure(&list);
printf("\n=========================\n");

getchar();
}

return 0;
}``````
Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.19 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.