本文將總結一種數據結構：跳躍表。前半部分跳躍表性質和操作的介紹直接摘自《讓算法的效率跳起來--淺談“跳躍表”的相關操作及其應用》上海市華東師范大學第二附屬中學 魏冉。之后將附上跳躍表的源代碼，以及本人對其的了解。難免有錯誤之處，希望指正，共同進步。謝謝。
跳躍表（Skip List）是1987年才誕生的一種嶄新的數據結構，它在進行查找、插入、刪除等操作時的期望時間復雜度均為O(logn),有著近乎替代平衡樹的本領。而且最重要的一點，就是它的編程復雜度較同類的AVL樹，紅黑樹等要低得多，這使得其無論是在理解還是在推廣性上，都有著十分明顯的優勢。
首先，我們來看一下跳躍表的結構
跳躍表由多條鏈構成（S0，S1，S2 ……，Sh），且滿足如下三個條件：
每條鏈必須包含兩個特殊元素：+∞ 和 -∞(其實不需要)
S0包含所有的元素，并且所有鏈中的元素按照升序排列。
每條鏈中的元素集合必須包含于序數較小的鏈的元素集合。
操作
一、查找
目的：在跳躍表中查找一個元素x
在跳躍表中查找一個元素x，按照如下幾個步驟進行：
1. 從最上層的鏈（Sh）的開頭開始
2. 假設當前位置為p，它向右指向的節點為q（p與q不一定相鄰），且q的值為y。將y與x作比較
(1) x=y 輸出查詢成功及相關信息
(2) x>y 從p向右移動到q的位置
(3) x<y 從p向下移動一格
3. 如果當前位置在最底層的鏈中（S0），且還要往下移動的話，則輸出查詢失敗
二、插入
目的：向跳躍表中插入一個元素x
首先明確，向跳躍表中插入一個元素，相當于在表中插入一列從S0中某一位置出發向上的連續一段元素。有兩個參數需要確定，即插入列的位置以及它的“高度”。
關于插入的位置，我們先利用跳躍表的查找功能，找到比x小的最大的數y。根據跳躍表中所有鏈均是遞增序列的原則，x必然就插在y的后面。
而插入列的“高度”較前者來說顯得更加重要，也更加難以確定。由于它的不確定性，使得不同的決策可能會導致截然不同的算法效率。為了使插入數據之后，保持該數據結構進行各種操作均為O(logn)復雜度的性質，我們引入隨機化算法（Randomized Algorithms）。
我們定義一個隨機決策模塊，它的大致內容如下：
產生一個0到1的隨機數r r ← random()
如果r小于一個常數p，則執行方案A， if r<p then do A
否則，執行方案B else do B
初始時列高為1。插入元素時，不停地執行隨機決策模塊。如果要求執行的是A操作，則將列的高度加1，并且繼續反復執行隨機決策模塊。直到第i次，模塊要求執行的是B操作，我們結束決策，并向跳躍表中插入一個高度為i的列。
我們來看一個例子：
假設當前我們要插入元素“40”，且在執行了隨機決策模塊后得到高度為4
步驟一：找到表中比40小的最大的數，確定插入位置
步驟二：插入高度為4的列，并維護跳躍表的結構
三、刪除
目的：從跳躍表中刪除一個元素x
刪除操作分為以下三個步驟：
在跳躍表中查找到這個元素的位置，如果未找到，則退出
將該元素所在整列從表中刪除
將多余的“空鏈”刪除
我們來看一下跳躍表的相關復雜度：
空間復雜度： O(n) （期望）
跳躍表高度： O(logn) （期望）
相關操作的時間復雜度：
查找： O(logn) （期望）
插入： O(logn) （期望）
刪除： O(logn) （期望）
之所以在每一項后面都加一個“期望”，是因為跳躍表的復雜度分析是基于概率論的。有可能會產生最壞情況，不過這種概率極其微小。
--------------------------------------------------------------------------------
以下是自己學習時碰到的一些問題
首先分配一個鏈表，用list.hdr指向，長度為跳躍表規定的最高層，說是鏈表，在以下代碼中只是分配了一段連續的空間，用來指向每一層的開始位置。我們看到結構體nodeType中，有一個key,一個rec(用戶數據)，還有一個指向結構體的指針數組。
一開始的那些圖容易給人誤解。如上圖所示，例如每個節點的forward[2]，就認為是跳躍表的第3層。List.hdr的forward[2]指向11，11的forward[2]指向30，30的forward[2]指向53。這就是跳躍表的第3層：11---30-----53。（準確的說每個forward都指向新節點，新節點的同層forward又指向另一個節點，從而構成一個鏈表，而數據只有一個，并不是像開始途中所畫的那樣有N個副本）。本人天資愚鈍，看了挺長時間才把它在內存里的結構看清楚了，呵呵。
以下是在網上搜到的一個實現代碼
代碼中主要注釋了insert函數，剩下的兩個函數差不多，就不一一注釋了
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，也就是說
后面沒有數據了，到頭了，并且這個值不再小于要插入的值。
記錄這個位置，留著向其后面插入數據*/
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指向第0層的X的后一個節點*/
x = x->forward[0];
/*如果相等就不用插入了*/
if (x != NIL && compEQ(x->key, key))
return STATUS_DUPLICATE_KEY;
/*隨機的計算要插入的值的最高level*/
for (
newLevel = 0;
rand() < RAND_MAX/2 && newLevel < MAXLEVEL;
newLevel++);
/*如果大于當前的level，則更新update數組并更新當前level*/
if (newLevel > list.listLevel) {
for (i = list.listLevel + 1; i <= newLevel; i++)
update[i] = NIL;
list.listLevel = newLevel;
}
/* 給新節點分配空間，分配newLevel個指針，則這個
節點的高度就固定了，只有newLevel。更高的層次將
不會再有這個值*/
if ((x = malloc(sizeof(nodeType) + newLevel*sizeof(nodeType *))) == 0)
return STATUS_MEM_EXHAUSTED;
x->key = key;
x->rec = *rec;
/* 給每層都加上這個值，相當于往鏈表中插入一個數*/
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;
}
本文來自CSDN博客，轉載請標明出處：http://blog.csdn.net/topcoder1234/archive/2010/08/26/5841119.aspx
posted on 2010-10-04 10:33
何克勤 閱讀(358)
評論(0) 編輯 收藏 所屬分類:
Algorithm and Data Structure