【数据结构】线性表（五）跳表及其基本操作（定义、创建、查找、插入、删除）

前言

1. 单链表

链表中的结点用存储单元（若干个连续字节）来存放，存储单元之间既可以是（存储空间上）连续的，也可以是不连续的，甚至可以零散地分布在存储空间中的任何位置。换言之，链表中结点的逻辑次序和物理次序之间并无必然联系。最重要的是，链表可以在不移动结点位置的前提下根据需要随时添加删除结点，动态调整。

【数据结构】线性表（二）单链表及其基本操作（创建、插入、删除、修改、遍历打印）-CSDN博客

https://blog.csdn.net/m0_63834988/article/details/133914875

数据结构_QomolangmaH的博客-CSDN博客

https://blog.csdn.net/m0_63834988/category_12435965.html

跳表（Skip List）

0. 概念

增加了向前指针的链表叫作跳表。跳表全称叫做跳跃表，简称跳表。跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。

跳表是一个随机化的数据结构，可以被看做二叉树的一个变种，它的性能在某些情况下可以与平衡二叉树（如红黑树和AVL树）相媲美，它的查找、插入和删除操作的时间复杂度为O(log n)

跳表的原理相对简单，因此在一些具有内存限制或对插入和删除操作性能要求较高的场景下，跳表是一种常用的选择。例如，Redis和LevelDB等数据库系统中就广泛使用了跳表来实现有序集合的功能。

1. 数据结构

定义宏：

代码语言：javascript复制

#define MAX_LEVEL 6

a. 跳表节点结构SkipListNode

代码语言：javascript复制

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

SkipListNode表示跳表中的节点，包含一个整型的键值key和一个整型的值value，以及一个指向其他节点的指针数组forward

b. 跳表结构SkipList

代码语言：javascript复制

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

SkipList表示整个跳表，包含最大层数max_level、当前层数level和一个指向头节点的指针header。

2. 辅助函数

a. 初始化节点

代码语言：javascript复制

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;
}

• 接受节点的层数level、键值key和值value作为参数，并动态分配内存来创建节点；
• 将节点的键值和值设置为参数的值；
• 为指针数组forward分配足够的内存；
• 将指针数组中的所有元素初始化为NULL，并返回创建的节点。

b. 初始化跳表

代码语言：javascript复制

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;
}

• 动态分配内存来创建一个SkipList结构体
• 设置最大层数max_level为预定义的常量值MAX_LEVEL
• 设置当前层数level为0
• 调用上述skipListNodeInit函数创建一个头节点。
• 将头节点的指针数组中的所有元素初始化为NULL，并返回创建的跳表。

c. 生成随机层数

代码语言：javascript复制

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

• 使用rand函数生成一个伪随机数，并与RAND_MAX的一半进行比较。如果生成的数小于RAND_MAX的一半，并且层数小于最大层数MAX_LEVEL，则层数加1。
• 函数的目的是根据一定的概率生成一个合适的层数，用于插入节点时确定节点在每一层的高度。

3. 查找节点

代码语言：javascript复制

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;
    }
}

从跳表的最高层开始遍历节点，找到在每一层中键值小于给定键值的最大节点。然后，沿着最底层的指针找到当前节点，并检查是否存在具有相同键值的节点。如果存在，返回该节点的指针。否则，返回NULL表示未找到。

4. 插入节点

代码语言：javascript复制

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;
        }
    }
}

• 创建一个更新数组update，用于记录在每个层级上需要更新的节点
• 从最高层级开始逐层遍历，找到要插入位置的前一个节点，并将其记录在更新数组中。
• 通过比较当前节点的后继节点的键和要插入的键，确定新节点的插入位置，并更新前进节点数组。
  • 如果要插入的键已存在于跳表中，则更新对应的值。
  • 如果新节点的层级大于当前跳表的层级，需要更新跳表的层级，并更新对应层级的前进节点数组。最后，将新节点插入到跳表中。

5. 删除节点

代码语言：javascript复制

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--;
        }
    }
}

• 创建一个更新数组update，用于记录在每个层级上需要更新的节点。
• 从最高层级开始逐层遍历，找到要删除的节点的前一个节点，并将其记录在更新数组中。
• 通过比较当前节点的后继节点的键和要删除的键，确定要删除的节点，并更新前进节点数组。
• 释放要删除的节点的内存。
• 检查跳表的当前层数，如果有必要，将当前层数减少，以确保跳表的高度与节点数量相匹配。

6. 主函数

代码语言：javascript复制

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: %dn", node->key, node->value);
    } else {
        printf("Key not found.n");
    }

    skipListDelete(skipList, 4);

    node = skipListSearch(skipList, 4);
    if (node != NULL) {
        printf("Key: %d, Value: %dn", node->key, node->value);
    } else {
        printf("Key not found.n");
    }

    return 0;
}

• 调用srand函数设置随机数种子
• 通过调用skipListInit函数初始化一个跳表
• 使用skipListInsert函数插入一系列键值对
• 使用skipListSearch函数搜索具有键值为4的节点，并打印出节点的键值和值。
• 使用skipListDelete函数删除具有键值为4的节点。
• 再次使用skipListSearch函数搜索具有键值为4的节点，并打印出结果。

代码整合

代码语言：javascript复制

#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: %dn", node->key, node->value);
    } else {
        printf("Key not found.n");
    }

    skipListDelete(skipList, 4);

    node = skipListSearch(skipList, 4);
    if (node != NULL) {
        printf("Key: %d, Value: %dn", node->key, node->value);
    } else {
        printf("Key not found.n");
    }

    return 0;
}

数组 指针 数据结构 函数 链表

0 人点赞