免费搭建淘宝客网站,期刊网站源码,制作网站需要哪些技术,百度云登录入口官网文章目录 1.跳表的基本概念2.跳表的结构3.跳表的增删改查4.完整代码 1.跳表的基本概念
跳表的本质是一种查找结构#xff0c;一般查找问题的解法分为两个大类#xff1a;一个是基于各种平衡树#xff0c;一个是基于哈希表#xff0c;跳表比较的特殊#xff0c;它独成一派… 文章目录 1.跳表的基本概念2.跳表的结构3.跳表的增删改查4.完整代码 1.跳表的基本概念
跳表的本质是一种查找结构一般查找问题的解法分为两个大类一个是基于各种平衡树一个是基于哈希表跳表比较的特殊它独成一派。跳表是基于有序链表的基础上发展而来的普通链表查找只能一个一个往下跳而跳表能一次跳过好几个结点这就是它查找效率高的原因。 例如 如果只有一层那么查找就是逐个遍历效率就是O(n)
如果为两个相邻结点添加第二层指向 甚至是添加第三层的指向 每层的结点个数呈现2:1的对应关系查找就是从最高层开始依次往下查找这个过程类型二分查找效率可以来到O(log n)。但是如果严格维持这种2:1的对应关系插入删除节点都需要重新调整插入删除效率直接就降到O(n)。所以跳表采用随机化结点的层数来控制查找插入删除的时间复杂度近似为O(log n)。怎么计算可以参考博客。
2.跳表的结构
跳表的结点有多层通过vectorSkiplistNode* 来存储下一个结点的指针。初始化跳表时是带头结点的它的层数要求是最高的它开始只有它自己默认给一层后面插入的时候如果有结点的层数高于它需要调整。
struct SkiplistNode
{ int _data;vectorSkiplistNode* _nextV;SkiplistNode(int data,int level):_data(data),_nextV(level,nullptr){}
};class Skiplist
{typedef SkiplistNode Node;
private:Node* _head;int _maxLevel 32;double _p 0.25;public:Skiplist(){_head new Node(-1,1);}
};int main()
{Skiplist list; return 0;
}3.跳表的增删改查
看看自己的代码有没有问题可以在leetcode上提交代码题目链接 1跳表的查找 跳表中的元素是有序的在理解跳表查找前先来看一下一个有序的单链表是如何查找元素的。 查找有序单链表cur表示当前结点如果cur的值data等于待查找的值target说明找到了。可如果cur 的下一个结点的值data大于target说明target目标值不在链表中或者是链表遍历到结尾还是找不到也说明target目标值不在链表中这就是有序单链表的查找过程。 有了有序单链表的查找的基础来看跳表的查找就简单了。 1、cur表示当前结点、next表示下一个结点、data表示结点的数据。 2、要从最高层找起直到遍历到最低的那一层。 3、如果target 等于 cur的 data说明找到了。 4、如果target 大于 next 的 data向右找。但是要保证next 不能为NULL。如找19而当前cur 的data是7它的next 是NULL。不代表找不到而是要到下一层找。 5、如果next的date 大于target 说明target可能在cur 和 next之间往下一层找。
bool search(int target)
{Node* cur _head;int level cur-_nextV.size() -1;while(level 0){if(cur-_nextV[level] cur-_nextV[level]-_data target){cur cur-_nextV[level];}else if(cur-_nextV[level] nullptr || cur-_nextV[level]-_data target){level--;}else {return true;}}return false;
}2跳表的插入 类比单链表的从中间的某个位置插入。需要找到前一个位置prev。跳表要找的是prevV前结点指针列表。 1、找到prevV 2、创建一个结点newNode先让newNode-_nextV[i] 逐个指向 prevV[i]-_nextV[i]指向的结点。再让prevV[i]-_nextV[i]指向newNode。 3、这里创建newNode层数是随机的需要根据概率计算。这里参照radis中给定的概率和最大层数。 4、如果插入节点的层数高于头结点需要调整头结点的层数。
vectorNode* findPervV(int num)
{Node* cur _head;int level _head-_nextV.size() -1;vectorNode* prevV(level 1,nullptr);while(level 0){ if(cur-_nextV[level] ! nullptr cur-_nextV[level]-_data num){cur cur-_nextV[level];}else if(cur-_nextV[level] nullptr || cur-_nextV[level]-_data num){prevV[level] cur;level--;}}return prevV;
}void add(int num)
{int n randomLevel();int level _head-_nextV.size() -1;vectorNode* prevV findPervV(num);// 调整头结点的层数if(n _head-_nextV.size()){_head-_nextV.resize(n,nullptr);prevV.resize(n,_head);}Node* newNode new Node(num,n); for(int i 0;i n;i){ newNode-_nextV[i] prevV[i]-_nextV[i];prevV[i]-_nextV[i] newNode;}
}int randomLevel()
{Node* cur _head;srand(time(NULL));int level 1;// rand的区间范围为[0,RAND_MAX]while(rand() RAND_MAX*_p level _maxLevel) { level;}return level;
}3跳表的删除 1、要到前结点列表prevV 2、根据当前结点的层数循环指向prevV[i]-_nextV[i] del-_nextV[i]
bool erase(int num)
{vectorNode* prevV findPervV(num);if(prevV[0]-_nextV[0] nullptr || prevV[0]-_nextV[0]-_data ! num){return false;}else{Node* del prevV[0]-_nextV[0];// 当前节点的层数for(int i 0;i del-_nextV.size();i){prevV[i]-_nextV[i] del-_nextV[i];}delete del;int index _head-_nextV.size() -1;// _head-_nextV[index] nullptr说明最高结点删除了调整头结点while (index 0) {if(_head-_nextV[index] nullptr) {index--;}else {break;} }return true;}
}4跳表的打印 这里按照单链表的思路打印如果只看第一层那么跳表就像是有序的单链表。注意跳表是带头指针的所以直接从_head-nextV[0]开始。
void print()
{Node* cur _head-_nextV[0];while(cur ! nullptr){ cout cur-_data -; cur cur-_nextV[0];}cout NULL endl;
}4.完整代码
#include vector
#include iostream
#include time.h
#include stdlib.husing namespace std;struct SkiplistNode
{ int _data;vectorSkiplistNode* _nextV;SkiplistNode(int data,int level):_data(data),_nextV(level,nullptr){}
};class Skiplist
{typedef SkiplistNode Node;
private:Node* _head;int _maxLevel 32;double _p 0.25;public:Skiplist(){_head new Node(-1,1);}bool search(int target){Node* cur _head;int level cur-_nextV.size() -1;while(level 0){if(cur-_nextV[level] cur-_nextV[level]-_data target){cur cur-_nextV[level];}else if(cur-_nextV[level] nullptr || cur-_nextV[level]-_data target){level--;}else {return true;}}return false;}vectorNode* findPervV(int num){Node* cur _head;int level _head-_nextV.size() -1;vectorNode* prevV(level 1,nullptr);while(level 0){ if(cur-_nextV[level] ! nullptr cur-_nextV[level]-_data num){cur cur-_nextV[level];}else if(cur-_nextV[level] nullptr || cur-_nextV[level]-_data num){prevV[level] cur;level--;}}return prevV; }void add(int num){int n randomLevel();int level _head-_nextV.size() -1;vectorNode* prevV findPervV(num);if(n _head-_nextV.size()){_head-_nextV.resize(n,nullptr);prevV.resize(n,_head);}Node* newNode new Node(num,n); for(int i 0;i n;i){ newNode-_nextV[i] prevV[i]-_nextV[i];prevV[i]-_nextV[i] newNode;}}int randomLevel(){Node* cur _head;srand(time(NULL));int level 1;while(rand() RAND_MAX*_p level _maxLevel) { level;}return level;}bool erase(int num){vectorNode* prevV findPervV(num);if(prevV[0]-_nextV[0] nullptr || prevV[0]-_nextV[0]-_data ! num){return false;}else{Node* del prevV[0]-_nextV[0];for(int i 0;i del-_nextV.size();i){prevV[i]-_nextV[i] del-_nextV[i];}delete del;int index _head-_nextV.size() -1;while (index 0) {if(_head-_nextV[index] nullptr) {index--;}else {break;} }return true;}}void print(){Node* cur _head-_nextV[0];while(cur ! nullptr){ cout cur-_data -; cur cur-_nextV[0];}cout NULL endl;}};int main()
{Skiplist list; list.add(1);list.add(3);list.add(6);cout list.search(6) endl;list.erase(9);list.erase(6);cout list.search(6) endl;list.print();return 0;
}
