SkipList的C语言完整实现
程序员文章站
2024-02-29 11:34:46
...
基于大数据日知录伪代码以及(http://dsqiu.iteye.com/blog/1705530)实现跳表
（等作业提交后再开放权限）
任务描述
根据大数据日知录课本上伪代码我们实现跳表的基本结构创建，对跳表内容进行查询，插入，删除。
为了方便测试我们假定最大层数为5（其实这个无所谓，你可以自己拟定）。
数据结构
1. 节点
//定义节点
struct Node
{
int value;
int key;
Node *forward[1];
};
2. 跳表
//定义跳跃表
struct List
{
int level;
Node *header;
};
核心代码块
1. 节点创建
//创建节点
Node* creatNode(int level,int key,int value)
{
//开辟空间
Node* node = (Node*)malloc(sizeof(Node) + level*sizeof(Node*));
node->key = key;
node->value = value;
return node;
}
2. 跳表初始化
//初始化跳表
List* creatList()
{
List* list = (List*)malloc(sizeof(List));
list->level = 0;
list->header = creatNode(MAX_LEVEL - 1, 0, 0);
for (int i = 0; i < MAX_LEVEL; i++)
{
list->header->forward[i] = NULL;
}
return list;
}
3. 随机数生成
int RandomLevel()
{
int v = 1;
while (rand() % 2)
v++;
return (v<MAX_LEVEL)?v:MAX_LEVEL;
}
4. 查询
注：我这里查询返回了数值，而不是真、假，只是为了后面测试用
int Search(int key, List* list) {
Node * x = list->header;
for (int i = list->level-1; i >= 0; i--)
{
while (x->forward[i]->key < key)
{
x = x->forward[i];
}
}
x = x->forward[1];
return (x->key == key) ? x->value : -1;
}
5. 插入
bool Insert(List *list,int key,int value) {
Node* update[MAX_LEVEL];
Node* x = list->header;
//寻找key所要插入的位置
//保存大于key的位置信息
for (int 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)
x->value = value;
else
{
int v = RandomLevel();
if (v > list->level)
{
for (int i = list->level; i < v; i++)
{
update[i] = list->header;
list->level = v;
}
}
x = creatNode(v, key, value);
for (int i = 0; i < list->level; i++)
{
x->forward[i] = update[i]->forward[i];
update[i]->forward[i] = x;
}
return true;
}
return false;
}
6. 删除
bool deleteNode(List* list,int key)
{
Node* update[MAX_LEVEL];
Node* x = list->header;
for (int 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 (int i = 0; i < list->level; i++)
{
if (update[i]->forward[i] != x)
break;
update[i]->forward[i] = x->forward[i];
}
free(x);
while (list->level > 1 && list->header->forward[list->level - 1] == NULL)
list->level--;
return true;
}
else
{
return false;
}
}
注：以上的查询、删除、插入是参考大数据日知录伪代码完成的
完整代码
#include<stdio.h>
#include<iostream>
#include<random>
#define MAX_LEVEL 5
using namespace std;
//定义节点
struct Node
{
int value;
int key;
Node *forward[1];
};
//定义跳跃表
struct List
{
int level;
Node *header;
};
//创建节点
Node* creatNode(int level,int key,int value)
{
//开辟空间
Node* node = (Node*)malloc(sizeof(Node) + level*sizeof(Node*));
node->key = key;
node->value = value;
return node;
}
//初始化跳表
List* creatList()
{
List* list = (List*)malloc(sizeof(List));
list->level = 0;
list->header = creatNode(MAX_LEVEL - 1, 0, 0);
for (int i = 0; i < MAX_LEVEL; i++)
{
list->header->forward[i] = NULL;
}
return list;
}
int RandomLevel()
{
int v = 1;
while (rand() % 2)
v++;
return (v<MAX_LEVEL)?v:MAX_LEVEL;
}
int Search(int key, List* list) {
Node * x = list->header;
for (int i = list->level-1; i >= 0; i--)
{
while (x->forward[i]->key < key)
{
x = x->forward[i];
}
}
x = x->forward[1];
return (x->key == key) ? x->value : -1;
}
bool Insert(List *list,int key,int value) {
Node* update[MAX_LEVEL];
Node* x = list->header;
//寻找key所要插入的位置
//保存大于key的位置信息
for (int 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)
x->value = value;
else
{
int v = RandomLevel();
if (v > list->level)
{
for (int i = list->level; i < v; i++)
{
update[i] = list->header;
list->level = v;
}
}
x = creatNode(v, key, value);
for (int i = 0; i < list->level; i++)
{
x->forward[i] = update[i]->forward[i];
update[i]->forward[i] = x;
}
return true;
}
return false;
}
bool deleteNode(List* list,int key)
{
Node* update[MAX_LEVEL];
Node* x = list->header;
for (int 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 (int i = 0; i < list->level; i++)
{
if (update[i]->forward[i] != x)
break;
update[i]->forward[i] = x->forward[i];
}
free(x);
while (list->level > 1 && list->header->forward[list->level - 1] == NULL)
list->level--;
return true;
}
else
{
return false;
}
}
void Result(List *list)
{
cout << "-----resut----" << endl;
Node *x = list->header;
while (x->forward[0] != NULL)
{
x = x->forward[0];
cout << "key: " << x->key << " value: " << x->value << endl;
}
}
int main()
{
List* list = creatList();
int n;
cout << "please intsert the number of the gather" << endl;
cin >> n;
for (int i = 0; i < n; i++)
{
int key, value;
cout << "please insert the " << i+1 << "th key and value:" << endl;
cin >> key >> value;
if (Insert(list, key, value))
cout <<"insert successfully!" << endl;
}
//打印结果
Result(list);
cout << "-----search-----" << endl;
cout << "please insert the key you want to search:" << endl;
int key_search;
cin >> key_search;
int re = Search(key_search, list);
if (re)
{
cout << "value: " << re << endl;
}
cout << "-----delete-----" << endl;
cout << "please insert the key you want to delete:" << endl;
int key_dele;
cin >> key_dele;
if (deleteNode(list,key_dele))
{
cout << "Delete successfully!" << endl;
}
else
{
cout << "No such a key!" << endl;
}
Result(list);
system("pause");
}
实验结果
以上就是所有代码，引用请注明出处https://editor.csdn.net/md?articleId=108707168
ps：如果你也是为了完成杜老师的作业，请自行理解添加自己的理解（无奈）