数据结构学习——skiplist跳表

//SkipList.h
#ifndef __SKIPLIST_H__
#define __SKIPLIST_H__
 
#include <climits>
#include <cstdlib>
#include <ctime>
#include <cmath>
 
class Skiplist {
private :
    struct Node {
        int key;
        Node * prev;
        Node * next;
        Node * down;
        Node * top;
        Node() : key(0), prev(nullptr), next(nullptr), down(nullptr), top(nullptr) {}
    };
private :
    Node * head;
    int level;
    int size;
private :
    void bindNewNode(Node * x, Node * p);
    void delNode(Node * x);
    Node * searchNode(int key);
public :
    Skiplist() : head(new Node), level(1),size(0)
        {head->key = INT_MIN; srand(static_cast<int>(time(0)));}
    ~Skiplist() {delete head;}
    void insert(int key);
    void remove(int key);
    bool search(int key) {return (searchNode(key) != nullptr);}
    void showSkiplist();
    int getLevel() {return level;}
    int getSize() {return size;}
};
 
#endif // __SKIPLIST_H__

//Skiplist.cpp
#include <iostream>
#include "SkipList.h"
using namespace std;
void Skiplist::bindNewNode(Node * x, Node * p) {
if (!x->next) {
x->next = p;
p->prev = x;
}
else {
p->next = x->next;
x->next->prev = p;
p->prev = x;
x->next = p;
}
}
void Skiplist::insert(int key) {
Node * p = new Node;
p->key = key;
Node * x = head;
while (1) { //find the prev node of p, which represents the right insert place
if (x->key <= key) {
if (x->next)
x = x->next;
else if (x->down)
x = x->down;
else break;
}
else if (x->prev->down)
x = x->prev->down;
else {
x = x->prev;
break;
}
}
bindNewNode(x, p);
while (rand() % 2) {  //throw the coin, then judge whether it needs to be higher according to the results
Node * highp = new Node;
highp->key = key;
while (!x->top && x->prev)
x = x->prev;
if (x->top) {
x = x->top;
bindNewNode(x, highp);
highp->down = p;
p->top = highp;
}
else { //already the top, add a sentry
Node * top = new Node;
x = top;
top->key = INT_MIN;
top->down = head;
head->top = top;
head = top;
bindNewNode(top, highp);
highp->down = p;
p->top = highp;
++level;
}
p = highp;
}
++size;
}
void Skiplist::delNode(Node * x) {
if (!x->next) { //node x is the last one
if (x->prev == head && head->down) { //x is not at the bottom and x is the last one of this level
head = head->down;
head->top = nullptr;
delete x->prev;
--level;
}
else
x->prev->next = nullptr;
}
else {
x->prev->next = x->next;
x->next->prev = x->prev;
}
delete x;
}
void Skiplist::remove(int key) {
Node * x = searchNode(key);
if (x) {
while (x->down) {
Node * y = x->down;
delNode(x);
x = y;
}
delNode(x);
--size;
}
}
Skiplist::Node * Skiplist::searchNode(int key) {
Node * x = head;
while (1) { //find the prev node of p, which represents the right insert place
if (x->key == key)
return x;
else if (x->key < key) {
if (x->next)
x = x->next;
else if (x->down)
x = x->down;
else
return nullptr;
}
else if (x->prev->down)
x = x->prev->down;
else {
return nullptr;
}
}
}
void Skiplist::showSkiplist() {
Node * x = head, * y = head;
while (y) {
x = y;
while (x) {
if (x->prev != nullptr)
cout << x->key << ' ';
x = x->next;
}
cout << endl;
y = y->down;
}
}

//main.cpp
#include "SkipList.h"
int main()
{
Skiplist* m_Skiplist = new Skiplist();
m_Skiplist->insert(7);
m_Skiplist->insert(14);
m_Skiplist->insert(21);
m_Skiplist->insert(32);
m_Skiplist->insert(37);
m_Skiplist->insert(71);
m_Skiplist->insert(85);
m_Skiplist->showSkiplist();
return 0;
}
————————————————————————————————————————————————————
使用方法，创建g++ -std=c++11 -o main main.cpp SkipList.cpp 生成main可执行文件
因为增加层数的方案用的是抛硬币，每次执行结果生成的level层数不一致，如下：
[root@192 skiplist1]# ./main
7 14 32
7 14 32 37
7 14 32 37 85
7 14 32 37 71 85
7 14 21 32 37 71 85
[root@192 skiplist1]# ./main
21
21
21
7 14 21 32 71
7 14 21 32 37 71 85
[root@192 skiplist1]# ./main
21
21
21
21
21
21 32
21 32 37
7 14 21 32 37 71 85