21xrx.com
2025-03-26 11:51:49 Wednesday
文章检索 我的文章 写文章
C++ 实现跳表
2023-06-30 01:30:05 深夜i     --     --
C++ 跳表 数据结构 算法 实现

跳表是一种基于有序链表的数据结构，它可以提供快速的查找，插入和删除操作。它的优势在于它的时间复杂度比纯链表快，但它的实现比红黑树和 AVL 树要简单。

下面我们将介绍 C++ 实现跳表的过程。我们首先需要定义节点类和跳表类。

节点类表示跳表的每个节点，包含了节点值，以及每一层的前向和后向指针。相比于纯链表，跳表节点还新增了上下两个指针，用于跨越多层节点。

class skipnode {
public:
  skipnode() {}
  skipnode(int _value) : value(_value) {}
  int value;
  skipnode* left = nullptr;
  skipnode* right = nullptr;
  skipnode* up = nullptr;
  skipnode* down = nullptr;
};

随后我们需要定义跳表类。跳表类包含了跳表的头节点和尾节点，以及每一层的头节点和尾节点。

class skiplist {
public:
  skiplist() {}
  int size() const;
  void insert(const int value);
  void erase(const int value);
  bool find(const int value) const;
private:
  skipnode* head = nullptr;
  skipnode* tail = nullptr;
  std::vector<skipnode*> heads = {};
  std::vector<skipnode*> tails = {};
  const float p = 0.25;
  const int max_level = 16;
};

其中，私有成员中的 `p` 表示每一层节点被升高到上一层的概率，一般都是设为 1/4； `max_level` 表示跳表的最大层数； `heads` 和 `tails` 分别表示每一层的头节点和尾节点，我们可以将它们放在一个 vector 中，方便遍历和查找。

下面是构造函数的实现：

skiplist::skiplist() {
  head = new skipnode();
  tail = new skipnode(INT_MAX);
  head->right = tail;
  tail->left = head;
  heads.resize(max_level);
  tails.resize(max_level);
  heads[max_level - 1] = head;
  tails[max_level - 1] = tail;
  for (int i = max_level - 2; i >= 0; --i) {
    heads[i] = new skipnode();
    tails[i] = new skipnode(INT_MAX);
    heads[i]->down = heads[i + 1];
    heads[i]->right = tails[i];
    tails[i]->down = tails[i + 1];
    tails[i]->left = heads[i];
    heads[i + 1]->up = heads[i];
    tails[i + 1]->up = tails[i];
  }
}

在上面的构造函数中，我们首先创建了两个哨兵节点： `head` 和 `tail`。它们分别作为跳表的头节点和尾节点，不包含实际数据， `head->right` 和 `tail->left` 用于遍历节点；

我们然后根据最大层数 `max_level`，和每层节点的前向和后向指针，创建多级节点。我们将最高层的头节点 `heads[max_level - 1]` 设为 `head`，尾节点 `tails[max_level - 1]` 设为 `tail`。对于其余层，我们在每一层的头和尾节点之间插入哨兵节点。

接下来是查找、插入、删除和打印跳表的代码实现：

int skiplist::size() const {
  int count = 0;
  skipnode* iter = head;
  while (iter->down)
    iter = iter->down;
  
  iter = iter->right;
  while (iter) {
    if (iter == tail)
      return count;
    
    iter = iter->right;
    ++count;
  }
  return count;
}
bool skiplist::find(const int value) const {
  skipnode* iter = head;
  while (iter) {
    if (iter == tail || iter->value > value)
      iter = iter->down;
    
    else if (iter->value == value)
      return true;
    
    else
      iter = iter->right;
    
  }
  return false;
}
void skiplist::insert(const int value) {
  std::vector<skipnode*> predecessors(max_level);
  skipnode* iter = head;
  for (int i = max_level - 1; i >= 0; --i) {
    while (iter->right->value < value)
      iter = iter->right;
    
    predecessors[i] = iter;
    iter = iter->down;
  }
  if (predecessors[0]->right->value == value)
    return;
  
  skipnode* newNode = new skipnode(value);
  for (int i = 0; i < max_level; ++i) {
    newNode->left = predecessors[i]->right;
    newNode->right = predecessors[i]->right->right;
    predecessors[i]->right->left = newNode;
    predecessors[i]->right = newNode;
    if (i > 0) {
      if (rand() / (float)RAND_MAX < p) {
        newNode->up = predecessors[i - 1]->right;
        predecessors[i - 1]->right->down = newNode;
        newNode = newNode->up;
      }
      else
        break;
      
    }
  }
}
void skiplist::erase(const int value) {
  skipnode* iter = head;
  for (int i = max_level - 1; i >= 0; --i) {
    while (iter->right->value < value)
      iter = iter->right;
    
    if (iter->right->value == value) {
      skipnode* toBeDeleted = iter->right;
      iter->right = toBeDeleted->right;
      toBeDeleted->right->left = iter;
      delete toBeDeleted;
    }
    iter = iter->down;
  }
}
void skiplist::print() const {
  for (int i = max_level - 1; i >= 0; --i) {
    skipnode* iter = heads[i];
    while (iter)
      std::cout << iter->value << " ";
      iter = iter->right;
    
    std::cout << std::endl;
  }
}

在查找节点时，我们从跳表的最高层开始查找，如果当前节点指向的节点值大于目标值，往下一层走；如果当前节点指向的节点值等于目标值，返回 true；如果当前节点指向的节点值小于目标值，向右边走。

在插入节点时，我们从跳表的最高层和头节点分别开始查找，将每一层插入的位置（前驱节点和后继节点之间）存储在存储器向量中。此后按层遍历，插入节点，同时在插入后返回一个随机数，如果这个随机数小于 `p`，则将新节点提升到上一层，并在上一层的前驱节点和后继节点之间插入节点。

在删除节点时，我们也是从跳表的最高层和头节点分别开始查找，将每一层需要删除的节点删除即可。

打印跳表时，我们从最高层遍历至最底层，按从左到右的顺序输出每一个节点。

总结起来，我们使用 C++ 实现了一种高效的数据结构————跳表，它能够提供快速的查找、插入和删除操作，并且实现也比红黑树和 AVL 树要简单。

  
  
下一篇: C++代码全集

评论区