具体的实现如下：
定义数据结构
//
// skiplist_def.h
// test
//
// Created by 杜国超 on 17/9/24.
// Copyright © 2017年 杜国超. All rights reserved.
//
#ifndef skiplist_def_h
#define skiplist_def_h
#define MAX_LEVEL 8
typedef int KeyType;
typedef int ValueType;
//定义节点信息数据结构
template <typename K,typename V>
struct NodeStructure {
K key;
V value;
NodeStructure* forward[1];
};
//定义跳跃表数据结构
template <typename K,typename V>
struct SkipLisStructure{
int level;
NodeStructure<K,V>* header;
};
typedef struct NodeStructure<KeyType,ValueType> NodeType;
typedef struct SkipLisStructure<KeyType,ValueType> ListType;
typedef NodeType* Node;
typedef ListType* List;
#define NEW_LEVEL_NODE(level) (Node)malloc(sizeof(NodeType) + (level) * sizeof(Node))
#endif /* skiplist_def_h */
增删查操作实现
//
// skiplist.h
// test
//
// Created by 杜国超 on 17/9/24.
// Copyright © 2017年 杜国超. All rights reserved.
//
#ifndef skiplist_h
#define skiplist_h
#include "skiplist_def.h"
class CSkipList{
public:
CSkipList();
~CSkipList();
public:
ValueType* Search(const KeyType& key);
bool Insert(KeyType& key,ValueType& value);
bool Delete(const KeyType& key,ValueType& value);
void FreeList();
private:
int RandomLevel();
private:
List _skipList;
int _size;
};
#endif /* skiplist_h */
//
// skiplist.cpp
// test
//
// Created by 杜国超 on 17/9/24.
// Copyright © 2017年 杜国超. All rights reserved.
//
#include "skiplist_def.h"
#include "skiplist.h"
#include <stdlib.h>
CSkipList::CSkipList(){
_skipList = (List)malloc(sizeof(ListType));
// 设置跳表的层level，初始的层为0层（数组从0开始）
_skipList->level = 0;
_skipList->header = NEW_LEVEL_NODE(MAX_LEVEL);
// 将header的forward数组清空
for(int i = 0; i < MAX_LEVEL; ++i)
_skipList->header->forward[i] = NULL;
_size = 0;
}
CSkipList::~CSkipList()
{
FreeList();
}
ValueType* CSkipList::Search(const KeyType& key){
Node node = _skipList->header;
Node indexNode = NULL;
for(int i = _skipList->level - 1; i >= 0; --i){
while((indexNode = node->forward[i]) && (indexNode->forward[i]->key <= key))
{
if (indexNode->key == key)
{
return &(indexNode->value);
}
node = indexNode;
}
}
return NULL;
}
bool CSkipList::Insert(KeyType& key, ValueType& value)
{
Node update[MAX_LEVEL];
int i;
Node node = _skipList->header;
Node indexNode = NULL;
//寻找key所要插入的位置
for(i = _skipList->level - 1; i >= 0; --i){
while((indexNode = node->forward[i]) && (indexNode->forward[i]->key < key))
{
node = indexNode;
}
update[i] = node;
}
node = node->forward[0];
//如果key已经存在
if(node->key == key){
node->value = value;
return false;
}else{
//随机生成新结点的层数
int level = RandomLevel();
if(level > _skipList->level){
for (int i = _skipList->level;i < level;++i)
{
update[i] = _skipList->header;
}
_skipList->level = level;
}
//申请新的结点
Node newNode = NEW_LEVEL_NODE(level);
newNode->key = key;
newNode->value = value;
//调整forward指针
for(int i = level - 1; i >= 0; --i){
node = update[i];
newNode->forward[i] = node->forward[i];
node->forward[i] = newNode;
}
//更新元素数目
++_size;
return true;
}
}
bool CSkipList::Delete(const KeyType& key,ValueType& value){
Node update[MAX_LEVEL];
int i;
Node node = _skipList->header;
Node indexNode = NULL;
//寻找key所要插入的位置
for(i = _skipList->level - 1; i >= 0; --i){
while((indexNode = node->forward[i]) && (indexNode->forward[i]->key < key))
{
node = indexNode;
}
update[i] = node;
}
node = node->forward[0];
//结点不存在
if(node->key != key){
return false;
}else{
value = node->value;
//调整指针
for(i = 0; i < _skipList->level; ++i){
if(update[i]->forward[i] != node)
break;
update[i]->forward[i] = node->forward[i];
}
//删除结点
free(node);
for(int i = _skipList->level - 1; i >= 0; i--){
if(_skipList->header->forward[i]==NULL){
_skipList->level--;
}
}
//更新链表元素数目
--_size;
return true;
}
}
int CSkipList::RandomLevel()
{
int k = 1;
while (rand()%2)
{
k++;
}
k=(k<MAX_LEVEL)?k:MAX_LEVEL;
return k;
}
void CSkipList::FreeList(){
Node p = _skipList->header;
Node q;
while(p != NULL){
q = p->forward[0];
free(p);
p = q;
}
free(p);
free(_skipList);
_size = 0;
}
