本文將總結(jié)一種數(shù)據(jù)結(jié)構(gòu)：跳躍表。前半部分跳躍表性質(zhì)和操作的介紹直接摘自《讓算法的效率跳起來(lái)--淺談“跳躍表”的相關(guān)操作及其應(yīng)用》上海市華東師范大學(xué)第二附屬中學(xué) 魏冉。之后將附上跳躍表的源代碼，以及本人對(duì)其的了解。難免有錯(cuò)誤之處，希望指正，共同進(jìn)步。謝謝。
跳躍表（Skip List）是1987年才誕生的一種嶄新的數(shù)據(jù)結(jié)構(gòu)，它在進(jìn)行查找、插入、刪除等操作時(shí)的期望時(shí)間復(fù)雜度均為O(logn),有著近乎替代平衡樹(shù)的本領(lǐng)。而且最重要的一點(diǎn)，就是它的編程復(fù)雜度較同類的AVL樹(shù)，紅黑樹(shù)等要低得多，這使得其無(wú)論是在理解還是在推廣性上，都有著十分明顯的優(yōu)勢(shì)。
首先，我們來(lái)看一下跳躍表的結(jié)構(gòu)
跳躍表由多條鏈構(gòu)成（S0，S1，S2 ……，Sh），且滿足如下三個(gè)條件：
每條鏈必須包含兩個(gè)特殊元素：+∞ 和 -∞(其實(shí)不需要)
S0包含所有的元素，并且所有鏈中的元素按照升序排列。
每條鏈中的元素集合必須包含于序數(shù)較小的鏈的元素集合。
操作
一、查找
目的：在跳躍表中查找一個(gè)元素x
在跳躍表中查找一個(gè)元素x，按照如下幾個(gè)步驟進(jìn)行：
1. 從最上層的鏈（Sh）的開(kāi)頭開(kāi)始
2. 假設(shè)當(dāng)前位置為p，它向右指向的節(jié)點(diǎn)為q（p與q不一定相鄰），且q的值為y。將y與x作比較
(1) x=y 輸出查詢成功及相關(guān)信息
(2) x>y 從p向右移動(dòng)到q的位置
(3) x<y 從p向下移動(dòng)一格
3. 如果當(dāng)前位置在最底層的鏈中（S0），且還要往下移動(dòng)的話，則輸出查詢失敗
二、插入
目的：向跳躍表中插入一個(gè)元素x
首先明確，向跳躍表中插入一個(gè)元素，相當(dāng)于在表中插入一列從S0中某一位置出發(fā)向上的連續(xù)一段元素。有兩個(gè)參數(shù)需要確定，即插入列的位置以及它的“高度”。
關(guān)于插入的位置，我們先利用跳躍表的查找功能，找到比x小的最大的數(shù)y。根據(jù)跳躍表中所有鏈均是遞增序列的原則，x必然就插在y的后面。
而插入列的“高度”較前者來(lái)說(shuō)顯得更加重要，也更加難以確定。由于它的不確定性，使得不同的決策可能會(huì)導(dǎo)致截然不同的算法效率。為了使插入數(shù)據(jù)之后，保持該數(shù)據(jù)結(jié)構(gòu)進(jìn)行各種操作均為O(logn)復(fù)雜度的性質(zhì)，我們引入隨機(jī)化算法（Randomized Algorithms）。
我們定義一個(gè)隨機(jī)決策模塊，它的大致內(nèi)容如下：
產(chǎn)生一個(gè)0到1的隨機(jī)數(shù)r r ← random()
如果r小于一個(gè)常數(shù)p，則執(zhí)行方案A， if r<p then do A
否則，執(zhí)行方案B else do B
初始時(shí)列高為1。插入元素時(shí)，不停地執(zhí)行隨機(jī)決策模塊。如果要求執(zhí)行的是A操作，則將列的高度加1，并且繼續(xù)反復(fù)執(zhí)行隨機(jī)決策模塊。直到第i次，模塊要求執(zhí)行的是B操作，我們結(jié)束決策，并向跳躍表中插入一個(gè)高度為i的列。
我們來(lái)看一個(gè)例子：
假設(shè)當(dāng)前我們要插入元素“40”，且在執(zhí)行了隨機(jī)決策模塊后得到高度為4
步驟一：找到表中比40小的最大的數(shù)，確定插入位置
步驟二：插入高度為4的列，并維護(hù)跳躍表的結(jié)構(gòu)
三、刪除
目的：從跳躍表中刪除一個(gè)元素x
刪除操作分為以下三個(gè)步驟：
在跳躍表中查找到這個(gè)元素的位置，如果未找到，則退出
將該元素所在整列從表中刪除
將多余的“空鏈”刪除
我們來(lái)看一下跳躍表的相關(guān)復(fù)雜度：
空間復(fù)雜度： O(n) （期望）
跳躍表高度： O(logn) （期望）
相關(guān)操作的時(shí)間復(fù)雜度：
查找： O(logn) （期望）
插入： O(logn) （期望）
刪除： O(logn) （期望）
之所以在每一項(xiàng)后面都加一個(gè)“期望”，是因?yàn)樘S表的復(fù)雜度分析是基于概率論的。有可能會(huì)產(chǎn)生最壞情況，不過(guò)這種概率極其微小。
--------------------------------------------------------------------------------
以下是自己學(xué)習(xí)時(shí)碰到的一些問(wèn)題
首先分配一個(gè)鏈表，用list.hdr指向，長(zhǎng)度為跳躍表規(guī)定的最高層，說(shuō)是鏈表，在以下代碼中只是分配了一段連續(xù)的空間，用來(lái)指向每一層的開(kāi)始位置。我們看到結(jié)構(gòu)體nodeType中，有一個(gè)key,一個(gè)rec(用戶數(shù)據(jù))，還有一個(gè)指向結(jié)構(gòu)體的指針數(shù)組。
一開(kāi)始的那些圖容易給人誤解。如上圖所示，例如每個(gè)節(jié)點(diǎn)的forward[2]，就認(rèn)為是跳躍表的第3層。List.hdr的forward[2]指向11，11的forward[2]指向30，30的forward[2]指向53。這就是跳躍表的第3層：11---30-----53。（準(zhǔn)確的說(shuō)每個(gè)forward都指向新節(jié)點(diǎn)，新節(jié)點(diǎn)的同層forward又指向另一個(gè)節(jié)點(diǎn)，從而構(gòu)成一個(gè)鏈表，而數(shù)據(jù)只有一個(gè)，并不是像開(kāi)始途中所畫(huà)的那樣有N個(gè)副本）。本人天資愚鈍，看了挺長(zhǎng)時(shí)間才把它在內(nèi)存里的結(jié)構(gòu)看清楚了，呵呵。
以下是在網(wǎng)上搜到的一個(gè)實(shí)現(xiàn)代碼
代碼中主要注釋了insert函數(shù)，剩下的兩個(gè)函數(shù)差不多，就不一一注釋了
view plaincopy to clipboardprint?
/* skip list */
#include <stdio.h>
#include <stdlib.h>
/* implementation dependent declarations */
typedef enum {
STATUS_OK,
STATUS_MEM_EXHAUSTED,
STATUS_DUPLICATE_KEY,
STATUS_KEY_NOT_FOUND
} statusEnum;
typedef int keyType; /* type of key */
/* user data stored in tree */
typedef struct {
int stuff; /* optional related data */
} recType;
#define compLT(a,b) (a < b)
#define compEQ(a,b) (a == b)
/* levels range from (0 .. MAXLEVEL) */
#define MAXLEVEL 15
typedef struct nodeTag {
keyType key; /* key used for searching */
recType rec; /* user data */
struct nodeTag *forward[1]; /* skip list forward pointer */
} nodeType;
/* implementation independent declarations */
typedef struct {
nodeType *hdr; /* list Header */
int listLevel; /* current level of list */
} SkipList;
SkipList list; /* skip list information */
#define NIL list.hdr
static int count = 0;
statusEnum insert(keyType key, recType *rec) {
int i, newLevel;
nodeType *update[MAXLEVEL+1];
nodeType *x;
count++;
/***********************************************
* allocate node for data and insert in list *
***********************************************/
/* find where key belongs */
/*從高層一直向下尋找，直到這層指針為NIL，也就是說(shuō)
后面沒(méi)有數(shù)據(jù)了，到頭了，并且這個(gè)值不再小于要插入的值。
記錄這個(gè)位置，留著向其后面插入數(shù)據(jù)*/
x = list.hdr;
for (i = list.listLevel; i >= 0; i--) {
while (x->forward[i] != NIL
&& compLT(x->forward[i]->key, key))
x = x->forward[i];
update[i] = x;
}
/*現(xiàn)在讓X指向第0層的X的后一個(gè)節(jié)點(diǎn)*/
x = x->forward[0];
/*如果相等就不用插入了*/
if (x != NIL && compEQ(x->key, key))
return STATUS_DUPLICATE_KEY;
/*隨機(jī)的計(jì)算要插入的值的最高level*/
for (
newLevel = 0;
rand() < RAND_MAX/2 && newLevel < MAXLEVEL;
newLevel++);
/*如果大于當(dāng)前的level，則更新update數(shù)組并更新當(dāng)前l(fā)evel*/
if (newLevel > list.listLevel) {
for (i = list.listLevel + 1; i <= newLevel; i++)
update[i] = NIL;
list.listLevel = newLevel;
}
/* 給新節(jié)點(diǎn)分配空間，分配newLevel個(gè)指針，則這個(gè)
節(jié)點(diǎn)的高度就固定了，只有newLevel。更高的層次將
不會(huì)再有這個(gè)值*/
if ((x = malloc(sizeof(nodeType) + newLevel*sizeof(nodeType *))) == 0)
return STATUS_MEM_EXHAUSTED;
x->key = key;
x->rec = *rec;
/* 給每層都加上這個(gè)值，相當(dāng)于往鏈表中插入一個(gè)數(shù)*/
for (i = 0; i <= newLevel; i++) {
x->forward[i] = update[i]->forward[i];
update[i]->forward[i] = x;
}
return STATUS_OK;
}
statusEnum delete(keyType key) {
int i;
nodeType *update[MAXLEVEL+1], *x;
/*******************************************
* delete node containing data from list *
*******************************************/
/* find where data belongs */
x = list.hdr;
for (i = list.listLevel; i >= 0; i--) {
while (x->forward[i] != NIL
&& compLT(x->forward[i]->key, key))
x = x->forward[i];
update[i] = x;
}
x = x->forward[0];
if (x == NIL || !compEQ(x->key, key)) return STATUS_KEY_NOT_FOUND;
/* adjust forward pointers */
for (i = 0; i <= list.listLevel; i++) {
if (update[i]->forward[i] != x) break;
update[i]->forward[i] = x->forward[i];
}
free (x);
/* adjust header level */
while ((list.listLevel > 0)
&& (list.hdr->forward[list.listLevel] == NIL))
list.listLevel--;
return STATUS_OK;
}
statusEnum find(keyType key, recType *rec) {
int i;
nodeType *x = list.hdr;
/*******************************
* find node containing data *
*******************************/
for (i = list.listLevel; i >= 0; i--) {
while (x->forward[i] != NIL
&& compLT(x->forward[i]->key, key))
x = x->forward[i];
}
x = x->forward[0];
if (x != NIL && compEQ(x->key, key)) {
*rec = x->rec;
return STATUS_OK;
}
return STATUS_KEY_NOT_FOUND;
}
void initList() {
int i;
/**************************
* initialize skip list *
**************************/
if ((list.hdr = malloc(
sizeof(nodeType) + MAXLEVEL*sizeof(nodeType *))) == 0) {
printf ("insufficient memory (initList)\n");
exit(1);
}
for (i = 0; i <= MAXLEVEL; i++)
list.hdr->forward[i] = NIL;
list.listLevel = 0;
}
int main(int argc, char **argv) {
int i, maxnum, random;
recType *rec;
keyType *key;
statusEnum status;
/* command-line:
*
* skl maxnum [random]
*
* skl 2000
* process 2000 sequential records
* skl 4000 r
* process 4000 random records
*
*/
maxnum = 20;
random = argc > 2;
initList();
if ((rec = malloc(maxnum * sizeof(recType))) == 0) {
fprintf (stderr, "insufficient memory (rec)\n");
exit(1);
}
if ((key = malloc(maxnum * sizeof(keyType))) == 0) {
fprintf (stderr, "insufficient memory (key)\n");
exit(1);
}
if (random) {
/* fill "a" with unique random numbers */
for (i = 0; i < maxnum; i++) key[i] = rand();
printf ("ran, %d items\n", maxnum);
} else {
for (i = 0; i < maxnum; i++) key[i] = i;
printf ("seq, %d items\n", maxnum);
}
for (i = 0; i < maxnum; i++) {
status = insert(key[i], &rec[i]);
if (status) printf("pt1: error = %d\n", status);
}
for (i = maxnum-1; i >= 0; i--) {
status = find(key[i], &rec[i]);
if (status) printf("pt2: error = %d\n", status);
}
for (i = maxnum-1; i >= 0; i--) {
status = delete(key[i]);
if (status) printf("pt3: error = %d\n", status);
}
return 0;
}
本文來(lái)自CSDN博客，轉(zhuǎn)載請(qǐng)標(biāo)明出處：http://blog.csdn.net/topcoder1234/archive/2010/08/26/5841119.aspx