• 對單鏈表查找一個元素的時間復雜度是 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; }

以上寫的比較簡單，刪除多個節點后，索引重新合理重建沒有寫。應該還有很多需要改進的地方，先放一放，往后繼續學，保持學習進度。
測試結果：

總結

以上是生活随笔為你收集整理的数据结构--跳表SkipList的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。