c++怎么實(shí)現(xiàn)跳躍表的方法示

這篇文章主要介紹c++怎么實(shí)現(xiàn)跳躍表的方法示，文中介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們一定要看完！

前言

Skip List是一種隨機(jī)化的數(shù)據(jù)結(jié)構(gòu)，基于并聯(lián)的鏈表，其效率可比擬于二叉查找樹（對于大多數(shù)操作需要O(log n)平均時(shí)間）?；旧?，跳躍列表是對有序的鏈表增加上附加的前進(jìn)鏈接，增加是以隨機(jī)化的方式進(jìn)行的，所以在列表中的查找可以快速的跳過部分列表(因此得名)。所有操作都以對數(shù)隨機(jī)化的時(shí)間進(jìn)行。Skip List可以很好解決有序鏈表查找特定值的困難。

跳表是平衡樹的一種替代的數(shù)據(jù)結(jié)構(gòu)，但是和紅黑樹不相同的是，跳表對于樹的平衡的實(shí)現(xiàn)是基于一種隨機(jī)化的算法的，跳躍表使用概率均衡技術(shù)而不是使用強(qiáng)制性均衡，因此，對于插入和刪除結(jié)點(diǎn)比傳統(tǒng)上的平衡樹算法更為簡潔高效。

一個(gè)跳表具有以下特征：

      1.一個(gè)跳表應(yīng)該有幾個(gè)層（level）組成；

      2.跳表的第一層包含所有的元素；

      3.每一層都是一個(gè)有序的鏈表；

      4.如果元素x出現(xiàn)在第i層，則所有比i小的層都包含x；

      5.第i層的元素通過一個(gè)down指針指向下一層擁有相同值的元素；

      6.Top指針指向最高層的第一個(gè)元素。

下面來研究一下跳表的核心思想: 先從鏈表開始，如果是一個(gè)簡單的鏈表，那么我們知道在鏈表中查找一個(gè)元素I的話，需要將整個(gè)鏈表遍歷一次。

如果是說鏈表是排序的，并且節(jié)點(diǎn)中還存儲(chǔ)了指向前面第二個(gè)節(jié)點(diǎn)的指針的話，那么在查找一個(gè)節(jié)點(diǎn)時(shí)，僅僅需要遍歷N/2個(gè)節(jié)點(diǎn)即可。

如上圖所示，是一個(gè)即為簡單的跳躍表。傳統(tǒng)意義的單鏈表是一個(gè)線性結(jié)構(gòu)，向有序的鏈表中插入一個(gè)節(jié)點(diǎn)需要O(n)的時(shí)間，查找操作需要O(n)的時(shí)間。如果我們使用上圖的跳躍表，就可以減少查找所需時(shí)間為O(n/2)，因?yàn)槲覀兛梢韵韧ㄟ^每個(gè)節(jié)點(diǎn)的最上面的指針先進(jìn)行查找，這樣子就能跳過一半的節(jié)點(diǎn)。比如我們想查找19，首先和6比較，大于6之后，在和9進(jìn)行比較，然后在和12進(jìn)行比較......最后比較到21的時(shí)候，發(fā)現(xiàn)21大于19，說明查找的點(diǎn)在17和21之間，從這個(gè)過程中，我們可以看出，查找的時(shí)候跳過了3、7、12等點(diǎn)，因此查找的復(fù)雜度為O(n/2)。

當(dāng)然上面只是最簡單的就是跳躍表，真正的跳表每一個(gè)結(jié)點(diǎn)不單單只包含指向下一個(gè)結(jié)點(diǎn)的指針，可能包含很多個(gè)指向后續(xù)結(jié)點(diǎn)的指針，這樣就可以跳過一些不必要的結(jié)點(diǎn)，從而加快查找、刪除等操作。對于一個(gè)鏈表內(nèi)每一個(gè)結(jié)點(diǎn)包含多少個(gè)指向后續(xù)元素的指針，這個(gè)過程是通過一個(gè)隨機(jī)函數(shù)生成器得到，就是通過隨機(jī)生成一個(gè)結(jié)點(diǎn)中指向后續(xù)結(jié)點(diǎn)的指針數(shù)目。

通過上面的跳表的很容易設(shè)計(jì)這樣的數(shù)據(jù)結(jié)構(gòu)：

定義每個(gè)節(jié)點(diǎn)類型：

typedef struct nodeStructure *node;
typedef struct nodeStructure
{
 keyType key; // key值
 valueType value; // value值
 // 向前指針數(shù)組，根據(jù)該節(jié)點(diǎn)層數(shù)的
 // 不同指向不同大小的數(shù)組
 node forward[1]; 
};

上面的每個(gè)結(jié)構(gòu)體對應(yīng)著圖中的每個(gè)節(jié)點(diǎn)，如果一個(gè)節(jié)點(diǎn)是一層的節(jié)點(diǎn)的話（如7，12等節(jié)點(diǎn)），那么對應(yīng)的forward將指向一個(gè)只含一個(gè)元素的數(shù)組，以此類推。

定義跳表數(shù)據(jù)類型：

// 定義跳表數(shù)據(jù)類型
typedef struct listStructure{
 int level; 
 struct nodeStructure * header;
} * list;

先不看代碼先用圖來描述一下Skip List構(gòu)造，插入和刪除的過程：

構(gòu)造Skip List

       1、給定一個(gè)有序的鏈表。

       2、選擇連表中最大和最小的元素，然后從其他元素中按照一定算法（隨機(jī)）隨即選出一些元素，將這些元素組成有序鏈表。這個(gè)新的鏈表稱為一層，原鏈表稱為其下一層。

       3、為剛選出的每個(gè)元素添加一個(gè)指針域，這個(gè)指針指向下一層中值同自己相等的元素。Top指針指向該層首元素

       4、重復(fù)2、3步，直到不再能選擇出除最大最小元素以外的元素。

插入過程

例子：插入 119， level = 2

如果 K 大于鏈表的層數(shù)，則要添加新的層。

例子：插入 119， K = 4

刪除 21

看到這就很清楚了，上面已經(jīng)提到所謂的Skip List是每層從它的下一層按照某種規(guī)律抽出一些元素，它的操作也很簡單，它的操作其實(shí)按層來操作鏈表，基本上是從上往下來操作。

具體的實(shí)現(xiàn)如下：

定義數(shù)據(jù)結(jié)構(gòu)

//
// 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;

//定義節(jié)點(diǎn)信息數(shù)據(jù)結(jié)構(gòu)
template <typename K,typename V>
struct NodeStructure {
 K key;
 V value;
 NodeStructure* forward[1];
};

//定義跳躍表數(shù)據(jù)結(jié)構(gòu)
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 */

增刪查操作實(shí)現(xiàn)

//
// 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));
 // 設(shè)置跳表的層level，初始的層為0層（數(shù)組從0開始）
 _skipList->level = 0;
 _skipList->header = NEW_LEVEL_NODE(MAX_LEVEL);
 // 將header的forward數(shù)組清空
 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已經(jīng)存在
 if(node->key == key){
  node->value = value;
  return false;
 }else{
  //隨機(jī)生成新結(jié)點(diǎn)的層數(shù)
  int level = RandomLevel();
  if(level > _skipList->level){
   for (int i = _skipList->level;i < level;++i)
   {
    update[i] = _skipList->header;
   }
   _skipList->level = level;
  }
  
  //申請新的結(jié)點(diǎn)
  Node newNode = NEW_LEVEL_NODE(level);
  newNode->key = key;
  newNode->value = value;
 
  //調(diào)整forward指針
  for(int i = level - 1; i >= 0; --i){
   node = update[i];
   newNode->forward[i] = node->forward[i];
   node->forward[i] = newNode;
  }
 
  //更新元素?cái)?shù)目
  ++_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];
 //結(jié)點(diǎn)不存在
 if(node->key != key){
  return false;
 }else{
  value = node->value;
  //調(diào)整指針
  for(i = 0; i < _skipList->level; ++i){
   if(update[i]->forward[i] != node)
    break;
   update[i]->forward[i] = node->forward[i];
  }
  //刪除結(jié)點(diǎn)
  free(node);
  for(int i = _skipList->level - 1; i >= 0; i--){
   if(_skipList->header->forward[i]==NULL){
    _skipList->level--;
   }
  }
  //更新鏈表元素?cái)?shù)目
  --_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;
}

以上是“c++怎么實(shí)現(xiàn)跳躍表的方法示”這篇文章的所有內(nèi)容，感謝各位的閱讀！希望分享的內(nèi)容對大家有幫助，更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道！