- 对单链表查找一个元素的时间复杂度是 O(n)
- 通过对链表建立多级索引的结构，就是跳表，查找任意数据、插入数据、删除数据的时间复杂度均为 O(log n)
- 前提：建立了索引，用空间换时间的思路
- (每两个节点建立一个索引)索引节点总和 n/2+n/4+n/8+…+8+4+2 = n-2，空间复杂度 O(n)
- 插入和删除后，动态更新索引，避免局部链表元素过多或者过少，退化成单链表
skiplist.h
/**
* @description: 跳表
* @author: michael ming
* @date: 2019/4/22 22:21
* @modified by:
*/
#ifndef SKIPLIST_SKIPLIST_H
#define SKIPLIST_SKIPLIST_H
#include <ctime>
#include <cstdlib>
#include <iostream>
using namespace std;
typedef unsigned int UINT;
template <class T>
class skipNode
{
public:
T data;
skipNode<T> **next; //跳表节点的next是 skipNode<T>* 类型的数组
skipNode(const UINT level)
{
next = new skipNode<T>* [level+1]; //索引级别从0（链表自身）开始
for(int i = 0; i < level+1; ++i)
next[i] = NULL;
}
skipNode(const UINT level, const T& inputdata):data(inputdata)
{
next = new skipNode<T>* [level+1]; //索引级别从0（链表自身）开始
for(int i = 0; i < level+1; ++i)
next[i] = NULL;
}
~skipNode<T>()
{
delete [] next;
}
};
template <class T>
class skiplist
{
private:
UINT randomLevel()
{
// static bool flag = false;
// if(!flag)
// {
// srand(UINT(time(0)));
// flag = true;
// }
// else
// flag = false;
UINT lv = 0;
for(int i = 0; i < maxLevel; ++i)
{
if(rand()%2)
lv++;
}
return lv;
}
public:
UINT maxLevel;
skipNode<T> *head;
skiplist<T>(UINT level = 10):maxLevel(level)
{
head = new skipNode<T>(level);
}
~skiplist<T>()
{
skipNode<T> *p = head, *q;
while(p)
{
q = p;
p = p->next[0];
delete q;
}
}
void insert(const T& inputdata)
{
skipNode<T>* newNode = new skipNode<T>(maxLevel, inputdata);
skipNode<T>* temPos[maxLevel+1];
skipNode<T> *p = head, *q = NULL;
for(int i = maxLevel; i >= 0; i--) //记录插入点在每层的前一个位置
{
while((q = p->next[i]) && (q->data <= inputdata))
{
p = q;
}
temPos[i] = p;
}
UINT lv = randomLevel(); //新节点的随机索引级数
for(int i = 0; i <= lv; ++i) //将新节点依次连接进去
{
newNode->next[i] = temPos[i]->next[i];
temPos[i]->next[i] = newNode;
}
}
void delete_node(const T& inputdata)
{
skipNode<T>* temPos[maxLevel+1];
skipNode<T> *p = head, *q = NULL;
for(int i = maxLevel; i >= 0; i--)
{
while((q = p->next[i]) && (q->data < inputdata))
{
p = q;
}
temPos[i] = p;
}
if(q && q->data == inputdata)
{
for(int i = 0; i <= maxLevel; ++i)
{
if(temPos[i]->next[i] == q)
temPos[i]->next[i] = q->next[i];
}
delete q;
q = NULL;
}
}
void printSkipList()
{
skipNode<T> *p, *q;
for(int i = maxLevel; i >= 0; --i)
{
p = head;
while(q = p->next[i])
{
cout << q->data << " -> ";
p = q;
}
cout << endl;
}
}
};
#endif //SKIPLIST_SKIPLIST_H 复制
test_skiplist.cpp
/**
* @description: 测试跳表
* @author: michael ming
* @date: 2019/4/23 0:07
* @modified by:
*/
#include "skiplist.h"
int main()
{
skiplist<int> intSList;
for(int i = 0; i < 10; ++i)
{
intSList.insert(i);
}
intSList.printSkipList();
intSList.delete_node(9);
intSList.printSkipList();
intSList.delete_node(100);
intSList.printSkipList();
return 0;
} 复制
以上写的比较简单，删除多个节点后，索引重新合理重建没有写。应该还有很多需要改进的地方，先放一放，往后继续学，保持学习进度。
测试结果：
