跳表因為其結構簡單，對于一些高效的資料結構紅黑樹、B樹等來說相對簡單且容易實作，在應用方面也很廣泛，比如著名的中間件Redis里面的Zset就用到了跳表來實作高效查詢和排序
下面直接上代碼
定義結構體
forward[MaxLevel]是一個Node指標型別，用于當前節點指向的下一個節點的指標，為什么是指標陣列呢？因為當前節點可能會有好幾層索引，其中最頂層跨度最大，越往下跨度越小
struct Node{
int key;
Node* forward[MaxLevel];
};
查找演算法
大致思路就是：從上層往下找，當當前層的下一個節點比key大，則不能再往后遍歷了，需要跳到下一層去比較下一層的下一個節點的值了，直到跳到最底層
舉個簡單的例子【請叫我靈魂畫手_】：
1------------------->5------------------>9---------->11
1------->3-------->5------->7-------->9---------->11
1-->2-->3-->4-->5-->6-->7-->8-->9-->10--->11
-
當要尋找5，則可以直接1->5 在第一層索引找到
-
當要找8，則先在第一層跳到5這個位置，然后往下跳，找到7這個位置，再往下跳，找到8
-
找10，先第一層找到9這個位置，往下跳，找到10
Node* Search(Node* head,int key,int level){
Node* p = head;
for(int i=level;i>=0;i--){ //從最上層的索引開開始尋找 如果尋找的節點大于值 則跳到下一層尋找 否則遍歷下一個節點判斷
while(p->forward[i]!=NULL && p->forward[i]->key<key){ //當前層數小于要尋找的值 則繼續遍歷下一個節點
p = p->forward[i];
}
}
if(p==NULL)
return NULL;
if (p->key==key) //當前的節點==key 或者比key小 則沒有找到
return p;
else
return NULL;
}
下面看如何插入
插入就是要找到每層的鏈接點，并且保存連接點，和鏈表插入思想一樣，只是這里多了幾個節點而已
//確定高度的隨機化演算法
int randX(int &level){
t = rand()
for(int i=0,j=2;i<MaxLevel;i++,j+=j){
if (t>(2/j))
break
}
if(i>level){
level = i //更新最大高度
}
return i;
}
void Insert(Node* head,int key,int &level){
Node* p = head;
Node* update[MaxLevel]; //臨時變數
newLevel = randX(level);
for(int i=level;i>=0;i--){
while(p->forward[i]!=NULL && p->forward[i]->key<key) //尋找本層的最大節點
p = p->forward[i];
update[i] = p; //保存本層最大節點
}
p = (Node*)malloc(sizeof(Node));
p->key = key;
for(int i=0;i<=newLevel;i++){
p->forward[i] = update[i]->forward[i]; //插入操作
update[i]->forward[i] = p;
}
}
洗掉：就是插入的逆操作
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/73574.html
標籤：其他
上一篇：指標實作 Treap