C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之跳表詳解

大家好，今天分享一篇C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)相關(guān)的文章--跳表。

1. 什么是跳表

跳表是鏈表+索引的一種數(shù)據(jù)結(jié)構(gòu) ，是以空間換取時(shí)間的方式，關(guān)于跳表參考:

2. 跳表概念

跳表在原有鏈表的基礎(chǔ)上，增加索引，從而可以進(jìn)行二分查找，提高搜尋效率。

原始鏈表

Head ——> 1 ——> 8 ——> 12 ——> 23 ——> 55 ——> NULL

新增了索引的鏈表(跳表)

Head2 ————————> 8 ———————————————————————> NULL 
Head1 ————————> 8 —————————> 23 —————————> NULL 
Head0 ——> 1 ——> 8 ——> 12 ——> 23 ——> 55 ——> NULL

Head0 , Head1 , Head2 上都是真實(shí)的節(jié)點(diǎn)，這就是以空間換取時(shí)間

例如算上Head, 元素?cái)?shù)據(jù)一共有 6 個(gè)，而添加索引后，元素一共有 11 個(gè)

3. 跳表增刪查規(guī)則

3.1 跳表數(shù)據(jù)節(jié)點(diǎn)

數(shù)據(jù)節(jié)點(diǎn)可以和鏈表節(jié)點(diǎn)一致 ，也可以定義如下節(jié)點(diǎn)，除了數(shù)據(jù)外，有指針指向 前一個(gè)/后一個(gè)/上一個(gè)/下一個(gè) 節(jié)點(diǎn)，以便后續(xù)查找操作。

typedef struct {
        int data;
        struct Node *next; // 后一個(gè)節(jié)點(diǎn)
        struct Node *last; // 前一個(gè)節(jié)點(diǎn)
        struct Node *up; // 上一個(gè)節(jié)點(diǎn)
        struct Node *down; // 下一個(gè)節(jié)點(diǎn)
} Node;

3.2 跳表初始化

當(dāng)跳表有多少層的時(shí)候，應(yīng)當(dāng)建立多少個(gè)頭結(jié)點(diǎn)，例如: 跳表為3層

Head2 ——> NULL
Head1 ——> NULL
Head0 ——> NULL

3.3 查找

刪除/新增 都會(huì)進(jìn)行查詢(xún)才操作，無(wú)非是刪除/新增索引而已。

例如有如下數(shù)據(jù)

Head2 —————————————————————> 23 —————————> NULL 
Head1 ————————> 8 —————————> 23 —————————> NULL 
Head0 ——> 1 ——> 8 ——> 12 ——> 23 ——> 55 ——> NULL

要查找13這個(gè)節(jié)點(diǎn)

去除無(wú)效層 例如:Head2后面第一個(gè)節(jié)點(diǎn)的數(shù)據(jù)23， 而23大于13, 所以Head2沒(méi)有數(shù)據(jù)匹配查詢(xún)，故需要跳到下面一層，至Head1上進(jìn)行查詢(xún)。 查詢(xún)至Head0層 去除無(wú)效層后數(shù)據(jù)進(jìn)入了Head1, 在Head1上進(jìn)行匹配，當(dāng)匹配到23時(shí)，23大于13，將23標(biāo)記為 查詢(xún)結(jié)束點(diǎn)，對(duì)23的上一個(gè)節(jié)點(diǎn) 8 進(jìn)行 向下指針操作，進(jìn)入Head0層的8節(jié)點(diǎn)。 查找實(shí)際數(shù)據(jù) 從Head0層的8 進(jìn)行查找，直至查詢(xún)結(jié)束標(biāo)記點(diǎn)(head1 23), 查詢(xún)的數(shù)據(jù)分別為 8 ， 12 ，23 查詢(xún)結(jié)束，未找到數(shù)據(jù)。 3.4 新增

新增操作需要記錄索引尋址過(guò)程，以便后續(xù)新增索引。

頭結(jié)點(diǎn)插入 頭結(jié)點(diǎn)插入一定是去除無(wú)效層至Head0 , 且Head0的第一個(gè)節(jié)點(diǎn)都比插入節(jié)點(diǎn)要大的情況下 例如: 如下跳表，插入 2

Head2 —————————————————————> 23 —————————> NULL 
Head1 ————————> 8 —————————> 23 —————————> NULL 
Head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> NULL

尾結(jié)點(diǎn)插入

頭結(jié)點(diǎn)插入一定是去除無(wú)效層至Head0 , 且Head0的第一個(gè)節(jié)點(diǎn)都比插入節(jié)點(diǎn)要小，直至NULL節(jié)點(diǎn)的情況下

例如:

如下跳表，插入 65

Head2 —————————————————————> 23 —————————> NULL 
Head1 ————————> 8 —————————> 23 —————————> NULL 
Head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> NULL

中間節(jié)點(diǎn)插入

除開(kāi)以上2種情況，其余情況為 中間節(jié)點(diǎn)插入

新增索引

拋硬幣的方法，當(dāng)數(shù)據(jù)量達(dá)到一定規(guī)模的時(shí)候，一定是趨近于 50%的。

所以跳表會(huì)越來(lái)越趨向于如下形式

    3
    3       7
1   3   5   7   9
1 2 3 4 5 6 7 8 9

判斷是否需要新增索引，采取拋硬幣的方法來(lái)判斷，即: 隨機(jī)數(shù) 取余 為 0 則需要新增，否則不需要。

例如如下跳表，插入 65

Head2 —————————————————————> 23 —————————> NULL 
Head1 ————————> 8 —————————> 23 —————————> NULL 
Head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> NULL

尋址應(yīng)該為
Head2: 23
Head1: 23 元素?cái)?shù)據(jù)插入后為

Head2 —————————————————————> 23 ———————————————> NULL 
Head1 ————————> 8 —————————> 23 ———————————————> NULL 
Head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> 65 —> NULL  

當(dāng)插入65節(jié)點(diǎn)后，若判斷需要索引的時(shí)候，則先為 Head1 添加索引，添加位置為 尋址地址之后，寄 Head1: 23

Head2 —————————————————————> 23 ———————————————> NULL 
Head1 ————————> 8 —————————> 23 —————————> 65 —> NULL 
Head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> 65 —> NULL  

繼續(xù)判斷，若不需要添加索引，則插入結(jié)束

若還需要添加索引，則繼續(xù)上述操作，直至 索引層 達(dá)到最高層

3.5 刪除

刪除首先是查找操作【3.3 查找】

若未找到該節(jié)點(diǎn)，則刪除失敗

若找到了該節(jié)點(diǎn)，則應(yīng)當(dāng)提到該數(shù)據(jù)最高索引層，再?gòu)母叩降蛣h除

例如:

如下跳表，刪除 23

Head2 —————————————————————> 23 ———————————————> NULL 
Head1 ————————> 8 —————————> 23 —————————> 65 —> NULL 
Head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> 65 —> NULL  

找到 Head0 23 后，應(yīng)該向上找到 Head2 23 ,然后從高向低刪除，若刪除后，該索引沒(méi)有數(shù)據(jù)了，則索引層減1

則刪除Head2 23 后數(shù)據(jù)如下

Head1 ————————> 8 —————————> 23 —————————> 65 —> NULL 
Head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> 65 —> NULL  

刪除Head1 23 后數(shù)據(jù)如下

Head1 ————————> 8 ———————————————————————> 65 —> NULL 
Head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> 65 —> NULL 

刪除Head0 23后數(shù)據(jù)如下

Head1 ————————> 8 ————————————————> 65 —> NULL 
Head0 ——> 3 ——> 8 ——> 12 ——> 55 ——> 65 —> NULL 

4. 代碼

skipList.c

# include 
# include 
# include 

int MaxLevel = 8; // 最大層數(shù)
int currLevel = 0; // 當(dāng)前層數(shù)

// 數(shù)據(jù)節(jié)點(diǎn)
typedef struct {
        int data;
        struct Node *next;
        struct Node *last;
        struct Node *up;
        struct Node *down;
} Node;

// 記錄索引尋址過(guò)程
typedef struct {
        int level;
        struct Node *node;
} skipStep;

// 判斷是否需要新增索引, 拋硬幣
bool randNum() {
        if(0 == (rand() % 2))
                return true;

        return false;
}

// 新增節(jié)點(diǎn)
bool add(Node *SL[] , int data) {

        printf("新增節(jié)點(diǎn): %d
",data);
        int level = currLevel;

        Node *Head = NULL;
        Node *tmp = NULL;
        Node *last = NULL;

        // 初始化索引 數(shù)據(jù)為 Head 地址
        skipStep steps[MaxLevel];
        int i;
        for (i=0;inext;

        while ((level > 0) && (data < tmp->data)) {
                level--;
                Head = SL[level];
                tmp = Head->next;
        }

        // 根據(jù)索引尋找Head0數(shù)據(jù)節(jié)點(diǎn)
        while ((level > 0)) {

                while (tmp != NULL) {
                        if (data < tmp->data) {
                                steps[level].level = level;
                                if (NULL != last) 
                                        steps[level].node = last;
                                tmp = last->down;
                                level--;
                                break;
                        }

                        last = tmp;
                        tmp = tmp->next;
                }
                if (NULL == tmp) {
                        steps[level].level = level;
                        if (NULL != last) 
                                steps[level].node = last;
                        tmp = last->down;
                        level--;

                }
        }

        // Head0 數(shù)據(jù)合適的節(jié)點(diǎn)
        while (tmp != NULL) {
                if (data < tmp->data) {
                        break;
                }
                last = tmp;
                tmp = tmp->next;
        }

        // 新增節(jié)點(diǎn)
        Node *newData = (Node *)malloc(sizeof(Node));
        newData->data = data;
        newData->up = NULL;
        newData->down = NULL;
        newData->last = NULL;
        newData->next = NULL;

        int k = 0;

        // Head0 插入原始數(shù)據(jù)
        if (NULL == last ) {
                // 頭結(jié)點(diǎn)

                Head = SL[0];
                Node *headNext = Head->next;
                if (NULL != headNext) {
                        newData->next = headNext;
                        headNext->last = newData;

                        newData->last = Head;


                } 

                Head->next = newData;
                newData->last = Head;


        } else if ( NULL == tmp) {
                // 尾節(jié)點(diǎn)
                last->next = newData;
                newData->last = last;


        } else {
                // 中間節(jié)點(diǎn)
                newData->next = tmp;
                tmp->last = newData;

                newData->last = last;
                last->next = newData;
        }

        // 構(gòu)建索引
        while (randNum()) {
                k++;
                if (k >= MaxLevel) break;

                // 新增索引數(shù)據(jù)
                Node *newIndex = (Node *)malloc(sizeof(Node));
                newIndex->data = data;
                newIndex->up = NULL;
                newIndex->down = NULL;
                newIndex->next = NULL;
                newIndex->last = NULL;

                // 建立上下級(jí)關(guān)系
                newIndex->down = newData;
                newData->up = newIndex;

                Node *node = steps[k].node;

                // node->next
                Node *nextIndex = node->next;


                node->next = newIndex;
                newIndex->last = node;

                newIndex->next = nextIndex;
                if (NULL != nextIndex) 
                        nextIndex->last = newIndex;

                newData = newIndex;

                // 判斷是否需要新增索引層數(shù)
                if (k > currLevel) 
                        currLevel = k;
        }
}


// 初始化頭結(jié)點(diǎn)
Node *initSkipList(Node *skipList[]) {
        int i;
        for (i=0;idata = -1-i;
                newHead->down = NULL;
                newHead->up = NULL;
                newHead->next = NULL;
                newHead->last = NULL;

                skipList[i] = newHead;


        }
        return skipList;
}

// 打印跳表數(shù)據(jù)
void PrintSkipList(Node *SL[]) {
        if (NULL == SL) {
                return;
        };

        int level = currLevel;
        //int level = MaxLevel;

        int i;
        for (i=level;i>=0;i--) {
                Node *Head = SL[i];

                Node *tmp = Head->next;
                printf("第%d層		",i);
                while (NULL != tmp) {
                        printf(" %d	",tmp->data);

                        tmp = tmp->next;
                }
                printf("
");
        }
}

// 查詢(xún)數(shù)據(jù)
Node *query(Node *SL[] , int data) {
        printf("查詢(xún)數(shù)據(jù): %d
",data);

        int level = currLevel;

        Node *Head = NULL;
        Node *tmp = NULL;
        Node *last = NULL;

        Head = SL[level];
        tmp = Head->next;
        int endQuery = -1;

        // 篩除無(wú)效層
        while ((level > 0) && (data < tmp->data)) {
                level--;
                endQuery = tmp->data;
                Head = SL[level];
                tmp = Head->next;
        }

        // 根據(jù)索引定位到Head0層
        while ((level > 0 )) {

                while (tmp != NULL) {
                        if (data < (tmp->data)) {
                                level--;
                                endQuery = tmp->data;
                                tmp = last->down;
                                break;
                        }

                        last = tmp;
                        tmp = tmp->next;
                }
                if (NULL == tmp) {
                        tmp = last->down;
                        endQuery = -1;
                        level--;
                }

        }

        // 查詢(xún)實(shí)際數(shù)據(jù)
        while (NULL != tmp) {
                if (endQuery != -1)
                        if (tmp->data > endQuery) {
                                        tmp = NULL;
                                        break;
                        }
                if (tmp->data == data) {
                        break;
                }
                tmp = tmp->next;
        }
        // 返回查詢(xún)的數(shù)據(jù)節(jié)點(diǎn)，若沒(méi)有查詢(xún)到，應(yīng)當(dāng)返回NULL ,否則返回實(shí)際的地址
        return tmp;
}

// 刪除數(shù)據(jù)
bool del(Node *SL[],int data) {
        printf("刪除數(shù)據(jù): %d
",data);

        // 找到節(jié)點(diǎn)地址
        Node *tmp = query(SL,data);

        if (NULL == tmp) {
                printf("未找到節(jié)點(diǎn),刪除失敗
");
                return false;
        }
        int level = 0;
        Node *t_last = NULL;
        Node *t_next = NULL;


        // 找到該數(shù)據(jù)最高索引
        while (NULL != tmp->up) {
                level++;
                tmp = tmp->up;
        }

        // 由上至下刪除索引/數(shù)據(jù)
        while (tmp != NULL) {
                t_last = tmp->last;
                t_next = tmp->next;

                Node *t_down = tmp->down;

                if (t_last == NULL) {
                        printf("上一個(gè)節(jié)點(diǎn)不可能為空，刪除失敗,層數(shù): %d
",level);
                        return false;
                }

                t_last->next = t_next;

                if (NULL != t_next)
                        t_next->last = t_last;
                else
                        t_last->next = NULL;

                if ((t_last == SL[level]) && (NULL == t_next)) {
                        currLevel--;

                }
                free(tmp);

                tmp = t_down;
                level--;
        }

        return true;


}

int main() {

        Node *SL[MaxLevel];

        Node *skipList = initSkipList(SL);
        if (NULL == SL) {
                printf("skipList 申請(qǐng)失敗
");
                return -1;
        }

        // 測(cè)試新增
        int num[] = {1,3,2,10,8,9,22,30,29,120,99,78,55,76,21};
        int i;
        for (i=0;i

執(zhí)行結(jié)果

# gcc skipList.c -w -g
# ./a.out 
新增節(jié)點(diǎn): 1
新增節(jié)點(diǎn): 3
新增節(jié)點(diǎn): 2
新增節(jié)點(diǎn): 10
新增節(jié)點(diǎn): 8
新增節(jié)點(diǎn): 9
新增節(jié)點(diǎn): 22
新增節(jié)點(diǎn): 30
新增節(jié)點(diǎn): 29
新增節(jié)點(diǎn): 120
新增節(jié)點(diǎn): 99
新增節(jié)點(diǎn): 78
新增節(jié)點(diǎn): 55
新增節(jié)點(diǎn): 76
新增節(jié)點(diǎn): 21
第5層            99
第4層            99
第3層            76      99
第2層            9       76      99
第1層            3       9       29      30      76      78      99
第0層            1       2       3       8       9       10      21      22      29      30      55      76      78      99      120
刪除數(shù)據(jù): 99
查詢(xún)數(shù)據(jù): 99
刪除數(shù)據(jù): 9
查詢(xún)數(shù)據(jù): 9
刪除數(shù)據(jù): 78
查詢(xún)數(shù)據(jù): 78
刪除數(shù)據(jù): 55
查詢(xún)數(shù)據(jù): 55
刪除數(shù)據(jù): 3
查詢(xún)數(shù)據(jù): 3
刪除數(shù)據(jù): 1
查詢(xún)數(shù)據(jù): 1
刪除數(shù)據(jù): 28
查詢(xún)數(shù)據(jù): 28
未找到節(jié)點(diǎn),刪除失敗
刪除數(shù)據(jù): 78
查詢(xún)數(shù)據(jù): 78
未找到節(jié)點(diǎn),刪除失敗
第3層            76
第2層            76
第1層            29      30      76
第0層            2       8       10      21      22      29      30      76      120

#

審核編輯：湯梓紅

(num)>;i++)>;i++)>