c++实现跳跃表(Skip List)的方法示例

时间:2021-05-20

前言

Skip List是一种随机化的数据结构,基于并联的链表,其效率可比拟于二叉查找树(对于大多数操作需要O(log n)平均时间)。基本上,跳跃列表是对有序的链表增加上附加的前进链接,增加是以随机化的方式进行的,所以在列表中的查找可以快速的跳过部分列表(因此得名)。所有操作都以对数随机化的时间进行。Skip List可以很好解决有序链表查找特定值的困难。

跳表是平衡树的一种替代的数据结构,但是和红黑树不相同的是,跳表对于树的平衡的实现是基于一种随机化的算法的,跳跃表使用概率均衡技术而不是使用强制性均衡,因此,对于插入和删除结点比传统上的平衡树算法更为简洁高效。

一个跳表具有以下特征:

1.一个跳表应该有几个层(level)组成;

2.跳表的第一层包含所有的元素;

3.每一层都是一个有序的链表;

4.如果元素x出现在第i层,则所有比i小的层都包含x;

5.第i层的元素通过一个down指针指向下一层拥有相同值的元素;

6.Top指针指向最高层的第一个元素。

下面来研究一下跳表的核心思想: 先从链表开始,如果是一个简单的链表,那么我们知道在链表中查找一个元素I的话,需要将整个链表遍历一次。

如果是说链表是排序的,并且节点中还存储了指向前面第二个节点的指针的话,那么在查找一个节点时,仅仅需要遍历N/2个节点即可。

如上图所示,是一个即为简单的跳跃表。传统意义的单链表是一个线性结构,向有序的链表中插入一个节点需要O(n)的时间,查找操作需要O(n)的时间。如果我们使用上图的跳跃表,就可以减少查找所需时间为O(n/2),因为我们可以先通过每个节点的最上面的指针先进行查找,这样子就能跳过一半的节点。比如我们想查找19,首先和6比较,大于6之后,在和9进行比较,然后在和12进行比较......最后比较到21的时候,发现21大于19,说明查找的点在17和21之间,从这个过程中,我们可以看出,查找的时候跳过了3、7、12等点,因此查找的复杂度为O(n/2)。

当然上面只是最简单的就是跳跃表,真正的跳表每一个结点不单单只包含指向下一个结点的指针,可能包含很多个指向后续结点的指针,这样就可以跳过一些不必要的结点,从而加快查找、删除等操作。对于一个链表内每一个结点包含多少个指向后续元素的指针,这个过程是通过一个随机函数生成器得到,就是通过随机生成一个结点中指向后续结点的指针数目。

通过上面的跳表的很容易设计这样的数据结构:

定义每个节点类型:

typedef struct nodeStructure *node;typedef struct nodeStructure{ keyType key; // key值 valueType value; // value值 // 向前指针数组,根据该节点层数的 // 不同指向不同大小的数组 node forward[1]; };

上面的每个结构体对应着图中的每个节点,如果一个节点是一层的节点的话(如7,12等节点),那么对应的forward将指向一个只含一个元素的数组,以此类推。

定义跳表数据类型:

// 定义跳表数据类型typedef struct listStructure{ int level; struct nodeStructure * header;} * list;

先不看代码先用图来描述一下Skip List构造,插入和删除的过程:

构造Skip List

1、给定一个有序的链表。

2、选择连表中最大和最小的元素,然后从其他元素中按照一定算法(随机)随即选出一些元素,将这些元素组成有序链表。这个新的链表称为一层,原链表称为其下一层。

3、为刚选出的每个元素添加一个指针域,这个指针指向下一层中值同自己相等的元素。Top指针指向该层首元素

4、重复2、3步,直到不再能选择出除最大最小元素以外的元素。

插入过程

例子:插入 119, level = 2

如果 K 大于链表的层数,则要添加新的层。

例子:插入 119, K = 4


删除 21

看到这就很清楚了,上面已经提到所谓的Skip List是每层从它的下一层按照某种规律抽出一些元素,它的操作也很简单,它的操作其实按层来操作链表,基本上是从上往下来操作。

具体的实现如下:

定义数据结构

//// 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 8typedef 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.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.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;}

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,如果有疑问大家可以留言交流,谢谢大家对的支持。

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章