版权声明:本文为博主原创文章,未经博主允许不得转载。有问题可以加微信:lp9628(注明CSDN)。 https://cloud.tencent.com/developer/article/1435842
当开始深入的研究数据结构和算法你会爱上它。
下面是python实现代码,后面要记得加注释啊啊啊
from typing import Optional
import random
class ListNode:
def __init__(self, data: Optional[int] = None):
self._data = data
self._forwards = [] # Forward pointers
class SkipList:
_MAX_LEVEL = 16
def __init__(self):
self._level_count = 1
self._head = ListNode()
self._head._forwards = [None] * type(self)._MAX_LEVEL
def find(self, value: int) -> Optional[ListNode]:
p = self._head
for i in range(self._level_count - 1, -1, -1): # Move down a level
while p._forwards[i] and p._forwards[i]._data < value:
p = p._forwards[i] # Move along level
return p._forwards[0] if p._forwards[0] and p._forwards[0]._data == value else None
def insert(self, value: int):
level = self._random_level()
if self._level_count < level: self._level_count = level
new_node = ListNode(value)
new_node._forwards = [None] * level
update = [self._head] * level # update is like a list of prevs
p = self._head
for i in range(level - 1, -1, -1):
while p._forwards[i] and p._forwards[i]._data < value:
p = p._forwards[i]
update[i] = p # Found a prev
for i in range(level):
new_node._forwards[i] = update[i]._forwards[i] # new_node.next = prev.next
update[i]._forwards[i] = new_node # prev.next = new_node
def delete(self, value):
update = [None] * self._level_count
p = self._head
for i in range(self._level_count - 1, -1, -1):
while p._forwards[i] and p._forwards[i]._data < value:
p = p._forwards[i]
update[i] = p
if p._forwards[0] and p._forwards[0]._data == value:
for i in range(self._level_count - 1, -1, -1):
if update[i]._forwards[i] and update[i]._forwards[i]._data == value:
update[i]._forwards[i] = update[i]._forwards[i]._forwards[i] # Similar to prev.next = prev.next.next
def _random_level(self, p: float = 0.5) -> int:
level = 1
while random.random() < p and level < type(self)._MAX_LEVEL:
level += 1
return level
def __repr__(self) -> str:
values = []
p = self._head
while p._forwards[0]:
values.append(str(p._forwards[0]._data))
p = p._forwards[0]
return "->".join(values)
if __name__ == "__main__":
l = SkipList()
for i in range(10):
l.insert(i)
print(l)
p = l.find(7)
print(p._data)
l.delete(3)
print(l)
java实现:
package skiplist;
import java.util.Random;
/**
* 跳表的一种实现方法。
* 跳表中存储的是正整数,并且存储的是不重复的。
*
* Author:ZHENG
*/
public class SkipList {
private static final int MAX_LEVEL = 16;
private int levelCount = 1;
private Node head = new Node(); // 带头链表
private Random r = new Random();
public Node find(int value) {
Node p = head;
for (int i = levelCount - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
}
if (p.forwards[0] != null && p.forwards[0].data == value) {
return p.forwards[0];
} else {
return null;
}
}
public void insert(int value) {
int level = randomLevel();
Node newNode = new Node();
newNode.data = value;
newNode.maxLevel = level;
Node update[] = new Node[level];
for (int i = 0; i < level; ++i) {
update[i] = head;
}
Node p = head;
for (int i = level - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
update[i] = p;
}
for (int i = 0; i < level; ++i) {
newNode.forwards[i] = update[i].forwards[i];
update[i].forwards[i] = newNode;
}
if (levelCount < level) levelCount = level;
}
public void delete(int value) {
Node[] update = new Node[levelCount];
Node p = head;
for (int i = levelCount - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
update[i] = p;
}
if (p.forwards[0] != null && p.forwards[0].data == value) {
for (int i = levelCount - 1; i >= 0; --i) {
if (update[i].forwards[i] != null && update[i].forwards[i].data == value) {
update[i].forwards[i] = update[i].forwards[i].forwards[i];
}
}
}
}
private int randomLevel() {
int level = 1;
for (int i = 1; i < MAX_LEVEL; ++i) {
if (r.nextInt() % 2 == 1) {
level++;
}
}
return level;
}
public void printAll() {
Node p = head;
while (p.forwards[0] != null) {
System.out.print(p.forwards[0] + " ");
p = p.forwards[0];
}
System.out.println();
}
public class Node {
private int data = -1;
private Node forwards[] = new Node[MAX_LEVEL];
private int maxLevel = 0;
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("{ data: ");
builder.append(data);
builder.append("; levels: ");
builder.append(maxLevel);
builder.append(" }");
return builder.toString();
}
}
}
c实现:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <time.h>
// https://www.youtube.com/watch?v=2g9OSRKJuzM&t=17s
#define MAX_LEVEL 15
struct node {
int val;
int max_level;
struct node *forward[MAX_LEVEL];
};
struct skip_list {
struct node head;
int max_level;
int max_level_nodes;
};
void node_init(struct node* node)
{
memset(node, 0, sizeof(struct node));
}
void skip_list_init(struct skip_list* sl)
{
node_init(&sl->head);
sl->max_level = 0;
sl->max_level_nodes = 0;
}
void random_init()
{
static bool done = false;
if (done)
return;
srandom(time(NULL));
done = true;
}
int random_level(void)
{
int i, level = 1;
random_init();
for (i = 1; i < MAX_LEVEL; i++)
if (random() % 2 == 1)
level++;
return level;
}
void random_level_test()
{
printf("random level %d\n", random_level());
printf("random level %d\n", random_level());
printf("random level %d\n", random_level());
printf("random level %d\n", random_level());
printf("random level %d\n", random_level());
}
void insert(struct skip_list *sl, int val)
{
int level = random_level();
struct node *update[MAX_LEVEL];
struct node *new, *p;
int i;
new = (struct node*)malloc(sizeof(struct node));
if (!new)
return;
new->max_level = level;
new->val = val;
for (int i = 0; i < MAX_LEVEL; i++)
update[i] = &sl->head;
p = &sl->head;
for (i = level - 1; i >= 0; i--) {
while(p->forward[i] && p->forward[i]->val < val)
p = p->forward[i];
update[i] = p;
}
for (i = 0; i < level; i++) {
new->forward[i] = update[i]->forward[i];
update[i]->forward[i] = new;
}
if (sl->max_level < level) {
sl->max_level = level;
sl->max_level_nodes = 1;
} else if (sl->max_level == level)
sl->max_level_nodes++;
}
struct node *find(struct skip_list* sl, int val)
{
struct node *node = &sl->head;
int i;
for (i = sl->max_level - 1; i >= 0; i--) {
while (node->forward[i] && node->forward[i]->val < val)
node = node->forward[i];
}
if (node->forward[0] && node->forward[0]->val == val) {
return node->forward[0];
}
else
return NULL;
}
void delete(struct skip_list* sl, int val)
{
struct node *update[MAX_LEVEL];
struct node *p;
int i;
p = &sl->head;
for (i = sl->max_level; i >= 0; i--) {
while (p->forward[i] && p->forward[i]->val < val)
p = p->forward[i];
update[i] = p;
}
if (p->forward[0] == NULL || p->forward[0]->val != val)
return;
if (p->forward[0]->max_level == sl->max_level)
sl->max_level_nodes--;
for (i = sl->max_level-1; i >= 0; i--) {
if (update[i]->forward[i] && update[i]->forward[i]->val == val)
update[i]->forward[i] = update[i]->forward[i]->forward[i];
}
// fixup max_level and max_level_nodes
if (sl->max_level_nodes == 0) {
//sl->max_level--;
p = &sl->head;
// skip (max_level - 1), direct test (max_level - 2)
// since no nodes on (max_level - 1)
for (i = sl->max_level - 2; i >= 0; i--) {
while (p->forward[i]) {
sl->max_level_nodes++;
p = p->forward[i];
}
if (sl->max_level_nodes) {
sl->max_level = i + 1;
break;
} else
sl->max_level = i;
}
}
}
void print_sl(struct skip_list* sl)
{
struct node *node;
int level;
printf("%d level skip list with %d nodes on top\n",
sl->max_level, sl->max_level_nodes);
for (level = sl->max_level - 1; level >= 0; level--) {
node = &sl->head;
printf("Level[%02d]:", level);
while (node->forward[level]) {
printf("%4d", node->forward[level]->val);
node = node->forward[level];
}
printf("\n");
}
}
int main()
{
struct skip_list sl;
struct node *node = NULL;
int i;
skip_list_init(&sl);
print_sl(&sl);
for (i = 0; i < 10; i++)
insert(&sl, i);
print_sl(&sl);
node = find(&sl, 8);
if (node)
printf("find 8 in sl %d\n", node->val);
else
printf("8 not in sl\n");
for (i = 0; i < 10; i++) {
delete(&sl, i);
print_sl(&sl);
}
return 0;
}
c++实现:
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <cstring>
#include <random>
#include <ctime>
using namespace std;
/**
* 跳表的一种实现方法。
* 跳表中存储的是正整数,并且存储的是不重复的。
*
* 跳表的C++版本.
* 翻译JAVA版本 原作者 Author:ZHENG
*
* Author:puhuaqiang
*
* 跳表结构:
*
* 第K级 1 9
* 第K-1级 1 5 9
* 第K-2级 1 3 5 7 9
* ... ....
* 第0级(原始链表) 1 2 3 4 5 6 7 8 9
*/
const int MAX_LEVEL = 16;
/**
* @brief 节点
*/
class CNode
{
public:
CNode();
~CNode();
std::string toString();
/**
* @brief 获取索引链表
*/
CNode** GetIdxList();
/**
* @brief 设置数据
*/
void SetData(int v);
/**
* @brief 获取数据
*/
int GetData();
/**
* @brief 设置最大索引级别
*/
void SetLevel(int l);
private:
/**当前节点的值*/
int m_data;
/**
* 当前节点的每个等级的下一个节点.
* 第2级 N1 N2
* 第1级 N1 N2
* 如果N1是本节点,则 m_lpForwards[x] 保存的是N2
*
* [0] 就是原始链表.
*/
CNode* m_lpForwards[MAX_LEVEL];
/**当前节点的所在的最大索引级别*/
int m_iMaxLevel;
};
/**
* @brief 跳表
*/
class CSkipList
{
public:
CSkipList();
~CSkipList();
/**
* @brief 查找指定的值的节点
* @param v 正整数
*/
CNode* Find(int v);
/**
* @brief 插入指定的值
* @param v 正整数
*/
void Insert(int v);
/**
* @brief 删除指定的值的节点
* @param v 正整数
*/
int Delete(int v);
void PrintAll();
/**
* @brief 打印跳表结构
* @param l 等于-1时打印所有级别的结构 >=0时打印指定级别的结构
*/
void PrintAll(int l);
/**
* @brief 插入节点时,得到插入K级的随机函数
* @return K
*/
int RandomLevel();
private:
int levelCount;
/**
* 链表
* 带头/哨所(节点)
*/
CNode* m_lpHead;
};
int main()
{
CSkipList skipList;
/// 插入原始值
for(int i=1; i< 50; i++){
if((i%3) == 0){
skipList.Insert(i);
}
}
for(int i=1; i< 50; i++){
if((i%3) == 1){
skipList.Insert(i);
}
}
skipList.PrintAll();
std::cout<<std::endl;
/// 打印所有等级结构
skipList.PrintAll(-1);
/// 查找
std::cout<<std::endl;
CNode* lpNode = skipList.Find(27);
if(NULL != lpNode){
std::cout<<"查找值为27的节点,找到该节点,节点值:"<<lpNode->GetData()<<std::endl;
}else{
std::cout<<"查找值为27的节点,未找到该节点"<<std::endl;
}
/// 删除
std::cout<<std::endl;
int ret = skipList.Delete(46);
if(0 == ret){
std::cout<<"查找值为46的节点,找到该节点,并删除成功"<<std::endl;
}else{
std::cout<<"查找值为46的节点,找到该节点,删除失败"<<std::endl;
}
std::cout<<std::endl;
//打印所有等级结构
skipList.PrintAll(-1);
std::cin.ignore();
return 0;
}
CNode::CNode()
{
m_data = -1;
m_iMaxLevel = 0;
for(int i=0; i<MAX_LEVEL; i++){
m_lpForwards[i] = NULL;
}
}
CNode::~CNode()
{
}
CNode** CNode::GetIdxList()
{
return m_lpForwards;
}
void CNode::SetData(int v)
{
m_data = v;
}
int CNode::GetData()
{
return m_data;
}
void CNode::SetLevel(int l)
{
m_iMaxLevel = l;
}
std::string CNode::toString()
{
char tmp[32];
std::string ret;
ret.append("{ data: ");
sprintf(tmp, "%d", m_data);
ret.append(tmp);
ret.append("; levels: ");
sprintf(tmp, "%d", m_iMaxLevel);
ret.append(tmp);
ret.append(" }");
return ret;
}
CSkipList::CSkipList()
{
levelCount = 1;
m_lpHead = new CNode();
}
CSkipList::~CSkipList()
{
}
CNode* CSkipList::Find(int v)
{
CNode* lpNode = m_lpHead;
/**
* 从 最大级索引链表开始查找.
* K -> k-1 -> k-2 ...->0
*/
for(int i=levelCount-1; i>=0; --i){
/**
* 查找小于v的节点(lpNode).
*/
while((NULL != lpNode->GetIdxList()[i]) && (lpNode->GetIdxList()[i]->GetData() < v)){
lpNode = lpNode->GetIdxList()[i];
}
}
/**
* lpNode 是小于v的节点, lpNode的下一个节点就等于或大于v的节点
*/
if((NULL != lpNode->GetIdxList()[0]) && (lpNode->GetIdxList()[0]->GetData() == v)){
return lpNode->GetIdxList()[0];
}
return NULL;
}
void CSkipList::Insert(int v)
{
/// 新节点
CNode* lpNewNode = new CNode();
if(NULL == lpNewNode){
return;
}
/**
* 新节点最大分布在的索引链表的上限
* 如果返回 3,则 新的节点会在索引1、2、3上的链表都存在
*/
int level = RandomLevel();
lpNewNode->SetData(v);
lpNewNode->SetLevel(level);
/**
* 临时索引链表
* 主要是得到新的节点在每个索引链表上的位置
*/
CNode *lpUpdateNode[level];
for(int i=0; i<level; i++){
/// 每个索引链表的头节点
lpUpdateNode[i] =m_lpHead;
}
CNode* lpFind = m_lpHead;
for(int i= level-1; i >= 0; --i){
/**
* 查找位置
* eg. 第1级 1 7 10
* 如果插入的是 6
* lpFind->GetIdxList()[i]->GetData() : 表示节点lpFind在第1级索引的下一个节点的数据
* 当 "lpFind->GetIdxList()[i]->GetData() < v"不成立的时候,
* 新节点就要插入到 lpFind节点的后面, lpFind->GetIdxList()[i] 节点的前面
* 即在这里 lpFind就是1 lpFind->GetIdxList()[i] 就是7
*/
while((NULL != lpFind->GetIdxList()[i]) && (lpFind->GetIdxList()[i]->GetData() < v)){
lpFind = lpFind->GetIdxList()[i];
}
/// lpFind 是新节点在 第i级索引链表的后一个节点
lpUpdateNode[i] = lpFind;
}
for(int i=0; i<level; ++i){
/**
* 重新设置链表指针位置
* eg 第1级索引 1 7 10
* 插入6.
* lpUpdateNode[i] 节点是1; lpUpdateNode[i]->GetIdxList()[i]节点是7
*
* 这2句代码就是 把6放在 1和7之间
*/
lpNewNode->GetIdxList()[i] = lpUpdateNode[i]->GetIdxList()[i];
lpUpdateNode[i]->GetIdxList()[i] = lpNewNode;
}
if(levelCount < level){
levelCount = level;
}
}
int CSkipList::Delete(int v)
{
int ret = -1;
CNode *lpUpdateNode[levelCount];
CNode *lpFind = m_lpHead;
for(int i=levelCount-1; i>= 0; --i){
/**
* 查找小于v的节点(lpFind).
*/
while((NULL != lpFind->GetIdxList()[i]) && (lpFind->GetIdxList()[i]->GetData() < v)){
lpFind = lpFind->GetIdxList()[i];
}
lpUpdateNode[i] = lpFind;
}
/**
* lpFind 是小于v的节点, lpFind的下一个节点就等于或大于v的节点
*/
if((NULL != lpFind->GetIdxList()[0]) && (lpFind->GetIdxList()[0]->GetData() == v)){
for(int i=levelCount-1; i>=0; --i){
if((NULL != lpUpdateNode[i]->GetIdxList()[i]) && (v == lpUpdateNode[i]->GetIdxList()[i]->GetData())){
lpUpdateNode[i]->GetIdxList()[i] = lpUpdateNode[i]->GetIdxList()[i]->GetIdxList()[i];
ret = 0;
}
}
}
return ret;
}
void CSkipList::PrintAll()
{
CNode* lpNode = m_lpHead;
while(NULL != lpNode->GetIdxList()[0]){
std::cout<<lpNode->GetIdxList()[0]->toString().data()<<std::endl;
lpNode = lpNode->GetIdxList()[0];
}
}
void CSkipList::PrintAll(int l)
{
for(int i=MAX_LEVEL-1; i>=0;--i){
CNode* lpNode = m_lpHead;
std::cout<<"第"<<i<<"级:"<<std::endl;
if((l < 0) || ((l >= 0) && (l == i))){
while(NULL != lpNode->GetIdxList()[i]){
std::cout<<lpNode->GetIdxList()[i]->GetData()<<" ";
lpNode = lpNode->GetIdxList()[i];
}
std::cout<<std::endl;
if(l >= 0){
break;
}
}
}
}
int GetRandom()
{
static int _count = 1;
std::default_random_engine generator(time(0) + _count);
std::uniform_int_distribution<int> distribution(1,99999/*0x7FFFFFFF*/);
int dice_roll = distribution(generator);
_count += 100;
return dice_roll;
}
int CSkipList::RandomLevel()
{
int level = 1;
for(int i=1; i<MAX_LEVEL; ++i){
if(1 == (GetRandom()%3)){
level++;
}
}
return level;
}
参考:
(1)https://github.com/wangzheng0822/algo
(2)https://blog.csdn.net/liujiyong7/article/details/18079339