本文共 2869 字，大约阅读时间需要 9 分钟。

• 对单链表查找一个元素的时间复杂度是 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 
   
    #include 
    
     #include 
     
      using namespace std;typedef unsigned int UINT;template 
      
       class skipNode{
   public:    T data;    skipNode
       
         **next; //跳表节点的next是 skipNode
        
         * 类型的数组 skipNode(const UINT level) { next = new skipNode
         
          * [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
          
           * [level+1]; //索引级别从0（链表自身）开始 for(int i = 0; i < level+1; ++i) next[i] = NULL; } ~skipNode
           
            () { delete [] next; }};template 
            
             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
             
               *head; skiplist
              
               (UINT level = 10):maxLevel(level) { head = new skipNode
               
                (level); } ~skiplist
                
                 () { skipNode
                 
                   *p = head, *q; while(p) { q = p; p = p->next[0]; delete q; } } void insert(const T& inputdata) { skipNode
                  
                   * newNode = new skipNode
                   
                    (maxLevel, inputdata); skipNode
                    
                     * temPos[maxLevel+1]; skipNode
                     
                       *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
                      
                       * temPos[maxLevel+1]; skipNode
                       
                         *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
                        
                          *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
   
     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;}
   

以上写的比较简单，删除多个节点后，索引重新合理重建没有写。应该还有很多需要改进的地方，先放一放，往后继续学，保持学习进度。

转载地址：https://michael.blog.csdn.net/article/details/89416539 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！