跳表（查找，插入，删除）的实现

创作时间:

作者:

@小白创作中心

跳表（查找，插入，删除）的实现

引用

CSDN

https://blog.csdn.net/2301_80698540/article/details/139512842

跳表（Skip List）是一种随机化的数据结构，它通过在不同层级维护链表的子集，实现了快速的查找、插入和删除操作。本文将详细介绍跳表的基本概念、操作原理，并提供完整的C语言实现代码。

跳表的基本概念

跳表全称为跳跃列表，它允许快速查询、插入和删除一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是O(logn)。快速查询是通过维护一个多层次的链表，且每一层链表中的元素是前一层链表元素的子集。一开始时，算法在最稀疏的层次进行搜索，直至需要查找的元素在该层两个相邻的元素中间。这时，算法将跳转到下一个层次，重复刚才的搜索，直到找到需要查找的元素为止。

跳表的查询

跳表的查询类似于二分查找。在一个有序数组中，若我们想使用二分法去查找20这个元素，则我们需要找到中间这个值，然后与12比较大小，大的则在右边查找即可，小的在左边查找即可，很明显我们需要在右边查找20这个数，刚好找到了20这个，如果数组的长度为N，那么时间的复杂度则为O(logN)空间复杂度为O(1)。

但是，如果是一个有序链表的话，我们就不能使用二分法来查找，因为链表不支持随机访问，所以这时我们就需要用到跳表这个概念来解决这个问题。

首先我们需要进行第一次索引，在每两个节点提取一个节点到上一级，得到第一个索引层：

这样在第一层的位置进行遍历我们就可以找到22这个数，但是还有一个更简单的方法，那就是再建立一层索引，如下图。

这样我们的索引的元素就更少了，我们仅需要找到第二层中仅小于22的元素12，然后顺着12访问它的下一层也就是第一层，在这一层找到22这个元素，然后顺着22这个元素找到原始链表中的数，即是我们需要查找的数。这样我们的时间复杂度也变为了O(logN)。

如果某一个节点有上层节点的话，则我们需要向上走，整个过程类似于楼梯的形状，每个节点第一被访问一定是位于最顶层

*如果节点x有第i+1，那么我们需要向上走，这种概率为p。
*如果节点没有第i+1层指针，那么我们需要向左走，这种概率为1-p。

跳表的插入

加入我们要插入一个10的元素，则我们需要先找到仅此于小于10的元素，也就是9。

然后从最高层开始查找到仅次小于10的元素，并将10插入其中

跳表的删除

首先我们需要先判断当前节点是否存在，只有存在才能删除，然后找到前驱节点，删除节点和单链表的删除类似。假设我们要删除12，则我们需要从顶层开始查找，发现12就在顶层然后删除12，顺着12找到下一层把第一层的12也删除，最后删除原始链表中的12。

这样我们就完成了删除操作。

跳表的C语言实现

以下是跳表的完整C语言实现代码：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define MAX_LEVEL 6

typedef struct SkipListNode {
    int key;
    int value;
    struct SkipListNode** forward;
} SkipListNode;

typedef struct SkipList {
    int max_level;
    int level;
    SkipListNode* header;
} SkipList;

SkipListNode* skipListNodeInit(int level, int key, int value) {
    SkipListNode* node = (SkipListNode*)malloc(sizeof(SkipListNode));
    node->key = key;
    node->value = value;
    node->forward = (SkipListNode**)malloc((level + 1) * sizeof(SkipListNode*));
    for (int i = 0; i <= level; i++) {
        node->forward[i] = NULL;
    }
    return node;
}

SkipList* skipListInit() {
    SkipList* skipList = (SkipList*)malloc(sizeof(SkipList));
    skipList->max_level = MAX_LEVEL;
    skipList->level = 0;
    skipList->header = skipListNodeInit(MAX_LEVEL, 0, 0);
    for (int i = 0; i <= MAX_LEVEL; i++) {
        skipList->header->forward[i] = NULL;
    }
    return skipList;
}

int randomLevel() {
    int level = 1;
    while (rand() < RAND_MAX / 2 && level < MAX_LEVEL) {
        level++;
    }
    return level;
}

void skipListInsert(SkipList* skipList, int key, int value) {
    SkipListNode* update[MAX_LEVEL + 1];
    SkipListNode* current = skipList->header;
    for (int i = skipList->level; i >= 0; i--) {
        while (current->forward[i] != NULL && current->forward[i]->key < key) {
            current = current->forward[i];
        }
        update[i] = current;
    }
    current = current->forward[0];
    if (current != NULL && current->key == key) {
        current->value = value;
    } else {
        int new_level = randomLevel();
        if (new_level > skipList->level) {
            for (int i = skipList->level + 1; i <= new_level; i++) {
                update[i] = skipList->header;
            }
            skipList->level = new_level;
        }
        SkipListNode* new_node = skipListNodeInit(new_level, key, value);
        for (int i = 0; i <= new_level; i++) {
            new_node->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = new_node;
        }
    }
}

void skipListDelete(SkipList* skipList, int key) {
    SkipListNode* update[MAX_LEVEL + 1];
    SkipListNode* current = skipList->header;
    for (int i = skipList->level; i >= 0; i--) {
        while (current->forward[i] != NULL && current->forward[i]->key < key) {
            current = current->forward[i];
        }
        update[i] = current;
    }
    current = current->forward[0];
    if (current != NULL && current->key == key) {
        for (int i = 0; i <= skipList->level; i++) {
            if (update[i]->forward[i] != current) {
                break;
            }
            update[i]->forward[i] = current->forward[i];
        }
        free(current);
        while (skipList->level > 0 && skipList->header->forward[skipList->level] == NULL) {
            skipList->level--;
        }
    }
}

SkipListNode* skipListSearch(SkipList* skipList, int key) {
    SkipListNode* current = skipList->header;
    for (int i = skipList->level; i >= 0; i--) {
        while (current->forward[i] != NULL && current->forward[i]->key < key) {
            current = current->forward[i];
        }
    }
    current = current->forward[0];
    if (current != NULL && current->key == key) {
        return current;
    } else {
        return NULL;
    }
}

int main() {
    srand(time(NULL));
    SkipList* skipList = skipListInit();
    skipListInsert(skipList, 3, 30);
    skipListInsert(skipList, 1, 10);
    skipListInsert(skipList, 2, 20);
    skipListInsert(skipList, 4, 40);
    skipListInsert(skipList, 6, 60);
    skipListInsert(skipList, 5, 50);
    skipListInsert(skipList, 7, 70);
    SkipListNode* node = skipListSearch(skipList, 4);
    if (node != NULL) {
        printf("Key: %d, Value: %d\n", node->key, node->value);
    } else {
        printf("Key not found.\n");
    }
    skipListDelete(skipList, 4);
    node = skipListSearch(skipList, 4);
    if (node != NULL) {
        printf("Key: %d, Value: %d\n", node->key, node->value);
    } else {
        printf("Key not found.\n");
    }
    return 0;
}

通过以上代码，我们可以看到跳表的实现主要包括以下几个部分：