c语言实现跳表（skiplist）

发布时间：2024年01月12日

概述：

跳表（Skip List）是一种数据结构，用于在有序的序列中进行快速查找、插入和删除操作。跳表的设计灵感来自平衡树，但相比于平衡树，跳表的实现更加简单，同时在实际应用中也能提供较好的性能。

以下是跳表的主要特点和概述：

层级结构： 跳表采用多层次的结构，每一层都是一个有序的链表。最底层包含所有的元素，而每一层都是前一层的一个子集。
索引： 每个节点都包含多个指针，指向同一层中的其他节点。这些指针被称为索引，通过索引可以在不必遍历整个链表的情况下，快速定位到目标节点。
随机性： 在跳表中，每个节点的升级或降级过程是随机的，这有助于保持跳表的平衡性。
平均时间复杂度： 在跳表中，查找、插入和删除的平均时间复杂度都是 O(log n)，其中 n 是跳表中元素的数量。相比于平衡树的实现，跳表的实现更简单，但在一些情况下性能能够媲美平衡树。
空间复杂度： 跳表的空间复杂度相对较高，因为每个节点都包含多个指针。
实现简单： 相比于复杂的平衡树实现，跳表的实现相对简单，容易理解和调试。

跳表的设计使得它成为一种高效的数据结构，尤其适用于需要频繁插入和删除操作的情况。在某些场景下，跳表可以作为一种替代平衡树的选择。

第一步：定义跳表节点

// 定义跳表节点结构
typedef struct Node {
    int key;
    struct Node** forward; // 指向前方节点的指针数组
} Node;

注意：这里并没有定义下一层的指针，在插入节点时，需要手动更新每层的指针

第二步：定义跳表节点构造

// 定义跳表结构
typedef struct SkipList {
    int level; // 当前跳表的层数
    Node* header; // 头节点
} SkipList;

第三步：创建新节点

// 创建新节点
Node* createNode(int key, int level) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->forward = (Node**)malloc(sizeof(Node*) * (level + 1));
    return newNode;
}

第四步：创建跳表

// 创建跳表
SkipList* createSkipList() {
    SkipList* skipList = (SkipList*)malloc(sizeof(SkipList));
    skipList->level = 0;
    skipList->header = createNode(INT_MIN, MAX_LEVEL);
    for (int i = 0; i <= MAX_LEVEL; i++) {
        skipList->header->forward[i] = NULL;
    }
    return skipList;
}

第五步：生成一个随机层数算法

// 生成一个随机层数，控制跳表的平衡性
int randomLevel() {
    int level = 0;
    while (rand() % 2 == 0 && level < MAX_LEVEL) {
        level++;
    }
    return level;
}

int level = 0;: 首先，初始化一个变量 level 为 0，表示节点的层数。
while (rand() % 2 == 0 && level < MAX_LEVEL) {: 进入一个循环，条件是当前随机数除以2的余数为0且 level 小于预设的最大层数 MAX_LEVEL。
- rand() % 2 == 0: 这部分通过 rand() 函数生成一个随机数，然后对2取余。由于 rand() 返回的值在一定范围内是随机的，因此这个条件的目的是使得随机数为偶数时循环继续，为奇数时循环结束。
- level < MAX_LEVEL: 这个条件确保节点的层数不会超过预设的最大层数。
level++;: 如果满足条件，增加 level 的值，表示节点的层数增加一层。
最终 return level;: 返回生成的随机层数。

第六步：编写插入节点

// 插入节点
void insertNode(SkipList* skipList, int key) {
    Node* update[MAX_LEVEL + 1];
    Node* current = skipList->header;

    // 初始化update数组
    for (int i = 0; i <= MAX_LEVEL; i++) {
        update[i] = NULL;
    }

    // 从最高层开始，找到每层的插入位置
    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;
    }

    // 生成一个随机层数，作为新节点的层数
    int newLevel = randomLevel();

    // 如果新节点的层数比当前跳表的层数大，更新update数组
    if (newLevel > skipList->level) {
        for (int i = skipList->level + 1; i <= newLevel; i++) {
            update[i] = skipList->header;
        }
        skipList->level = newLevel;
    }

    // 创建新节点
    Node* newNode = createNode(key, newLevel);

    // 更新每层的指针
    for (int i = 0; i <= newLevel; i++) {
        newNode->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = newNode;
    }
}

Node* update[MAX_LEVEL + 1];: 定义一个数组 update 用于存储每层的插入位置。
Node* current = skipList->header;: 初始化 current 指针为跳表的头节点，从头节点开始查找插入位置。
初始化 update 数组，将每个元素都设置为 NULL。
进入一个循环，从跳表的最高层开始向下查找每层的插入位置。在每层中，通过 current->forward[i] 遍历节点，找到对应位置并更新 update[i]。
生成一个随机层数 newLevel 作为新节点的层数。
如果新节点的层数比当前跳表的层数大，更新 update 数组。将新层数之后的位置都设置为跳表的头节点，并更新跳表的层数。
创建新节点，使用 createNode 函数生成一个具有指定键值和层数的节点。
最后，通过循环更新每层的指针，将新节点插入到跳表中。在每层中，将新节点的 forward[i] 指向 update[i]->forward[i]，并将 update[i]->forward[i] 指向新节点，完成插入操作。

第七步：编写查找节点

// 查找节点
Node* searchNode(SkipList* skipList, int key) {
    Node* 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];
        }
    }

    // 在最底层找到节点后，检查是否为目标节点
    if (current->forward[0] != NULL && current->forward[0]->key == key) {
        return current->forward[0];
    }

    // 未找到目标节点
    return NULL;
}

Node* current = skipList->header;: 初始化 current 指针为跳表的头节点，从头节点开始查找。
进入一个循环，从跳表的最高层开始向下查找每层的查找位置。在每层中，通过 current->forward[i] 遍历节点，找到对应位置。
在最底层找到节点后，通过?current->forward[0]?检查是否为目标节点。如果找到了目标节点，返回该节点的指针。
如果在最底层未找到目标节点，函数返回?NULL?表示未找到。

第八步：打印跳表

// 打印跳表
void printSkipList(SkipList* skipList) {
    printf("Skip List (level %d):\n", skipList->level);

    for (int i = skipList->level; i >= 0; i--) {
        Node* current = skipList->header->forward[i];
        printf("Level %d: ", i);
        while (current != NULL) {
            printf("%d ", current->key);
            current = current->forward[i];
        }
        printf("\n");
    }

    printf("\n");
}

第九步：释放

// 释放节点
void freeNode(Node* node) {
    free(node->forward);
    free(node);
}

// 释放跳表
void freeSkipList(SkipList* skipList) {
    Node* current = skipList->header->forward[0];
    Node* next;

    while (current != NULL) {
        next = current->forward[0];
        freeNode(current);
        current = next;
    }

    free(skipList->header->forward);
    free(skipList->header);
    free(skipList);
}

完整代码

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

#define MAX_LEVEL 6 // 最大层数

// 定义跳表节点结构
typedef struct Node {
    int key;
    struct Node** forward; // 指向前方节点的指针数组
} Node;

// 定义跳表结构
typedef struct SkipList {
    int level; // 当前跳表的层数
    Node* header; // 头节点
} SkipList;

// 创建新节点
Node* createNode(int key, int level) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->forward = (Node**)malloc(sizeof(Node*) * (level + 1));
    return newNode;
}

// 创建跳表
SkipList* createSkipList() {
    SkipList* skipList = (SkipList*)malloc(sizeof(SkipList));
    skipList->level = 0;
    skipList->header = createNode(INT_MIN, MAX_LEVEL);
    for (int i = 0; i <= MAX_LEVEL; i++) {
        skipList->header->forward[i] = NULL;
    }
    return skipList;
}

// 生成一个随机层数，控制跳表的平衡性
int randomLevel() {
    int level = 0;
    while (rand() % 2 == 0 && level < MAX_LEVEL) {
        level++;
    }
    return level;
}

// 插入节点
void insertNode(SkipList* skipList, int key) {
    Node* update[MAX_LEVEL + 1];
    Node* current = skipList->header;

    // 初始化update数组
    for (int i = 0; i <= MAX_LEVEL; i++) {
        update[i] = NULL;
    }

    // 从最高层开始，找到每层的插入位置
    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;
    }

    // 生成一个随机层数，作为新节点的层数
    int newLevel = randomLevel();

    // 如果新节点的层数比当前跳表的层数大，更新update数组
    if (newLevel > skipList->level) {
        for (int i = skipList->level + 1; i <= newLevel; i++) {
            update[i] = skipList->header;
        }
        skipList->level = newLevel;
    }

    // 创建新节点
    Node* newNode = createNode(key, newLevel);

    // 更新每层的指针
    for (int i = 0; i <= newLevel; i++) {
        newNode->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = newNode;
    }
}

// 查找节点
Node* searchNode(SkipList* skipList, int key) {
    Node* 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];
        }
    }

    // 在最底层找到节点后，检查是否为目标节点
    if (current->forward[0] != NULL && current->forward[0]->key == key) {
        return current->forward[0];
    }

    // 未找到目标节点
    return NULL;
}

// 打印跳表
void printSkipList(SkipList* skipList) {
    printf("Skip List (level %d):\n", skipList->level);

    for (int i = skipList->level; i >= 0; i--) {
        Node* current = skipList->header->forward[i];
        printf("Level %d: ", i);
        while (current != NULL) {
            printf("%d ", current->key);
            current = current->forward[i];
        }
        printf("\n");
    }

    printf("\n");
}

// 释放节点
void freeNode(Node* node) {
    free(node->forward);
    free(node);
}

// 释放跳表
void freeSkipList(SkipList* skipList) {
    Node* current = skipList->header->forward[0];
    Node* next;

    while (current != NULL) {
        next = current->forward[0];
        freeNode(current);
        current = next;
    }

    free(skipList->header->forward);
    free(skipList->header);
    free(skipList);
}

int main() {
    SkipList* skipList = createSkipList();

    insertNode(skipList, 3);
    insertNode(skipList, 6);
    insertNode(skipList, 7);
    insertNode(skipList, 9);
    insertNode(skipList, 12);
    insertNode(skipList, 19);
    insertNode(skipList, 21);
    insertNode(skipList, 25);

    printSkipList(skipList);

    int keyToSearch = 9;
    Node* result = searchNode(skipList, keyToSearch);

    if (result != NULL) {
        printf("Node with key %d found in the skip list.\n", keyToSearch);
    } else {
        printf("Node with key %d not found in the skip list.\n", keyToSearch);
    }

    freeSkipList(skipList);

    return 0;
}

文章来源:https://blog.csdn.net/m0_63251896/article/details/135552854
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！