跳表C++实现

根据leetcode 1206题的需求进行实现。如下图

代码如下（层级算法参考redis的有序集合，投掷0-1.0的小数，以0-0.25小数为基准进行层数+1）：

#include <vector>
#include <random>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>#define _MAX_LEVEL_ (64) //层数上限64
using namespace std;//获取0-1.0随机值函数
double generateRandom() 
{// 使用 C++11 的随机数生成器std::random_device rd;  // 获取随机数种子std::mt19937 gen(rd());  // 使用梅森旋转算法生成随机数std::uniform_real_distribution<> dis(0.0, 1.0); // 定义范围return dis(gen); // 返回 0 到 1 之间的随机小数
}//跳表节点
class Node{
public:Node(){m_pNext = NULL;m_pDown = NULL;m_iKey = 0;m_iLevel = 0;};public:Node *m_pNext;  //同一行，下一节点指针Node *m_pDown;  //同一列，下一节点指针int m_iKey;     //key值int m_iLevel;   //当前所属层级
};//跳表类，包含方法：增、删、查
class Skiplist {
public:Skiplist() {m_pRoot = NULL;}bool search(int target) {bool bRet = false;Node *pCurr = m_pRoot;while(pCurr){if(pCurr->m_iKey == target){bRet = true;break;}if(pCurr->m_pNext == NULL)pCurr = pCurr->m_pDown;else if(pCurr->m_pNext->m_iKey > target)pCurr = pCurr->m_pDown;elsepCurr = pCurr->m_pNext;}return bRet;}void add(int num) {if(m_pRoot == NULL){m_pRoot = new Node();m_pRoot->m_iKey = num;m_pRoot->m_iLevel = 1;m_iLevelCount = 1;}else{//新增节点整列记录到vectorvector<Node *> vecNewList;if(search(num) == false) //不存在则进行插入{//新节点key比root的key值要小，则插在根节点前面if(num < m_pRoot->m_iKey){Node *pRootTmp = new Node();pRootTmp->m_iKey = num;pRootTmp->m_iLevel = m_pRoot->m_iLevel;pRootTmp->m_pNext = m_pRoot;vecNewList.push_back(pRootTmp);Node *pCurr = m_pRoot;while(pCurr->m_pDown != NULL){pCurr = pCurr->m_pDown;Node *pNew = new Node();pNew->m_iKey = num;pNew->m_iLevel = pCurr->m_iLevel;pNew->m_pNext = pCurr;vecNewList.push_back(pNew);}m_pRoot = pRootTmp;}else if(num > m_pRoot->m_iKey) //中间插入{int iLevel = GetRandomLevel();if(iLevel > m_iLevelCount) //提升根节点层级{for(int i = 0 ; i < (iLevel-m_iLevelCount) ; i++){Node *pNew = new Node();pNew->m_iKey = m_pRoot->m_iKey;pNew->m_iLevel = m_iLevelCount+(i+1);pNew->m_pDown = m_pRoot;m_pRoot = pNew;}m_iLevelCount = iLevel;}//插入的前一位节点整列记录到vectorvector<Node *> vecInsertList;//记录前一位Node *pCurr = m_pRoot;while(pCurr){while(pCurr->m_pNext != NULL && pCurr->m_pNext->m_iKey < num){pCurr = pCurr->m_pNext;}if(pCurr->m_iLevel <= iLevel)vecInsertList.push_back(pCurr);pCurr = pCurr->m_pDown;}//记录插入节点，并串联左右链for(vector<Node *>::iterator it = vecInsertList.begin() ; it != vecInsertList.end() ; it++){Node *pNew = new Node();pNew->m_iKey = num;pNew->m_iLevel = (*it)->m_iLevel;pNew->m_pNext = (*it)->m_pNext;(*it)->m_pNext = pNew;vecNewList.push_back(pNew);}}}else  //leetcode 1206的设计要求，可以插入相同key值(采用方案：复制一列){//已有列，复制Node *pCurr = m_pRoot;while(pCurr){if(pCurr->m_iKey == num){break;}if(pCurr->m_pNext == NULL)pCurr = pCurr->m_pDown;else if(pCurr->m_pNext->m_iKey > num)pCurr = pCurr->m_pDown;elsepCurr = pCurr->m_pNext;}//移动到最底层while(pCurr){Node *pNew = new Node();pNew->m_iKey = pCurr->m_iKey;pNew->m_pNext = pCurr->m_pNext;pNew->m_iLevel = pCurr->m_iLevel;pCurr->m_pNext = pNew;vecNewList.push_back(pNew);pCurr = pCurr->m_pDown;}}//串联上下层级for(unsigned int i = 0 ; i < (vecNewList.size()-1) ; i++){vecNewList[i]->m_pDown = vecNewList[i+1];}}}bool erase(int num) {bool bRet = false;Node *pCurr = m_pRoot;vector<Node *> vecLists;vector<Node *> vecNew;vector<Node *> vecLeft;vector<Node *> vecRight;if(m_pRoot->m_iKey == num){//记录整列需删除的节点到vectorpCurr = m_pRoot;bRet = true;while(pCurr){vecLists.push_back(pCurr);if(pCurr->m_pDown == NULL)break;pCurr = pCurr->m_pDown;}//记录第二列的key值和地址int iNewRootKey = pCurr->m_pNext->m_iKey;Node *pOrig = pCurr->m_pNext;//若第二列节点的层数不够，提升层数，记录新增层数的第二列节点到vectorpCurr = m_pRoot;while(pCurr){if(pCurr->m_pNext == NULL || pCurr->m_pNext->m_iKey != iNewRootKey){Node *pNew = new Node();pNew->m_iKey = iNewRootKey;pNew->m_iLevel = pCurr->m_iLevel;pNew->m_pNext = pCurr->m_pNext;vecNew.push_back(pNew);//printf("Create new root node [%d] on level[%d]\n" , iNewRootKey , pNew->m_iLevel);}if(pCurr->m_pDown == NULL)break;pCurr = pCurr->m_pDown;}if(vecNew.size() > 0){//修改根节点指向，串联新增的第二列节点m_pRoot = vecNew[0];for(unsigned int i = 0 ; i < (vecNew.size()-1) ; i++){vecNew[i]->m_pDown = vecNew[i+1];}vecNew[vecNew.size()-1]->m_pDown = pOrig; }else{//修改根节点指向m_pRoot = m_pRoot->m_pNext;}}else{//记录整列需删除的节点到vector，并串联其前后节点pCurr = m_pRoot;while(pCurr){//记录左侧列节点、待删除节点、右侧列节点if(pCurr->m_pNext && pCurr->m_pNext->m_iKey == num){//printf("-------------->delete[%d] on level[%d]\n" , pCurr->m_pNext->m_iKey , pCurr->m_pNext->m_iLevel);vecLeft.push_back(pCurr);vecLists.push_back(pCurr->m_pNext);vecRight.push_back(pCurr->m_pNext->m_pNext);bRet = true;}if(pCurr->m_pNext == NULL)pCurr = pCurr->m_pDown;else if(pCurr->m_pNext->m_iKey >= num)pCurr = pCurr->m_pDown;elsepCurr = pCurr->m_pNext;}for(unsigned int i = 0 ; i < vecLeft.size() && i < vecRight.size() ; i++){vecLeft[i]->m_pNext = vecRight[i];}}//执行删除动作for(vector<Node *>::iterator it = vecLists.begin() ; it != vecLists.end() ; it++){delete *it;}return bRet;}void PrintAll(){puts("------------------------------");vector<Node *> vecLists;Node *pCurr = m_pRoot;while(pCurr){vecLists.push_back(pCurr);if(pCurr->m_pDown == NULL)break;pCurr = pCurr->m_pDown;}for(vector<Node *>::iterator it = vecLists.begin() ; it != vecLists.end() ; it++){pCurr = *it;while(pCurr){printf("[%d] " , pCurr->m_iKey);pCurr = pCurr->m_pNext;}putchar('\n');}}private://获取随机层数函数，若每次掷出0-0.25的数则层数加1（仿redis有序集合的跳表实现）int GetRandomLevel(){int iRet = 1;double dNum = generateRandom();if(dNum <= 0.25){iRet += GetRandomLevel();}return (iRet < _MAX_LEVEL_) ? iRet : _MAX_LEVEL_;}private:Node *m_pRoot;      //指向最上层的头结点int m_iLevelCount;  //当前跳表总层数
};int main()
{Skiplist skiplist;//拷贝leetcode案例中的输入参数放进数组，遍历执行char aHandleArray[100][100] = {"add","add","add","add","add","add","add","add","add","erase","search","add","erase",\"erase","erase","add","search","search","search","erase","search","add","add","add","erase","search","add","search",\"erase","search","search","erase","erase","add","erase","search","erase","erase","search","add","add","erase","erase",\"erase","add","erase","add","erase","erase","add","add","add","search","search","add","erase","search","add","add",\"search","add","search","erase","erase","search","search","erase","search","add","erase","search","erase","search",\"erase","erase","search","search","add","add","add","add","search","search","search","search","search","search",\"search","search","search"};int iNumArray[] = {16,5,14,13,0,3,12,9,12,3,6,7,0,1,10,5,12,7,16,7,0,9,16,3,2,17,2,17,0,9,14,1,6,1,16,9,10,9,2,3,16,\15,12,7,4,3,2,1,14,13,12,3,6,17,2,3,14,11,0,13,2,1,10,17,0,5,8,9,8,11,10,11,10,9,8,15,14,1,6,17,16,13,4,5,4,17,16,7,14,1};for(unsigned int i = 0 ; i < sizeof(iNumArray)/sizeof(int) ; i++){if(strcmp(aHandleArray[i] , "add") == 0){skiplist.add(iNumArray[i]);printf("add[%d]null," , iNumArray[i]);}else if(strcmp(aHandleArray[i] , "search") == 0){printf("search[%d]%s," , iNumArray[i] , skiplist.search(iNumArray[i])==true?"true":"false");}else if(strcmp(aHandleArray[i] , "erase") == 0){printf("erase[%d]%s," , iNumArray[i] , skiplist.erase(iNumArray[i])==true?"true":"false");}}putchar('\n');skiplist.PrintAll();return 0;
}

案例运行结果：

可以看出，耗时这块还有优化空间，后续有时间再优化。