AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

c语言实现跳表（skiplist）

2024-10-10 6
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 本文介绍了跳表（Skip List）的数据结构及其实现，包括节点定义、创建、随机层数生成、插入、查找、打印和释放操作，展示了跳表作为一种高效有序序列查找、插入和删除操作的数据结构。

概述：

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

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

  1. 层级结构： 跳表采用多层次的结构，每一层都是一个有序的链表。最底层包含所有的元素，而每一层都是前一层的一个子集。

  2. 索引： 每个节点都包含多个指针，指向同一层中的其他节点。这些指针被称为索引，通过索引可以在不必遍历整个链表的情况下，快速定位到目标节点。

  3. 随机性： 在跳表中，每个节点的升级或降级过程是随机的，这有助于保持跳表的平衡性。

  4. 平均时间复杂度： 在跳表中，查找、插入和删除的平均时间复杂度都是 O(log n)，其中 n 是跳表中元素的数量。相比于平衡树的实现，跳表的实现更简单，但在一些情况下性能能够媲美平衡树。

  5. 空间复杂度： 跳表的空间复杂度相对较高，因为每个节点都包含多个指针。

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

  1. int level = 0;: 首先，初始化一个变量 level 为 0，表示节点的层数。

  2. while (rand() % 2 == 0 && level < MAX_LEVEL) { : 进入一个循环，条件是当前随机数除以2的余数为0且 level 小于预设的最大层数 MAX_LEVEL。

    • rand() % 2 == 0: 这部分通过 rand() 函数生成一个随机数，然后对2取余。由于 rand() 返回的值在一定范围内是随机的，因此这个条件的目的是使得随机数为偶数时循环继续，为奇数时循环结束。

    • level < MAX_LEVEL: 这个条件确保节点的层数不会超过预设的最大层数。

  3. level++;: 如果满足条件，增加 level 的值，表示节点的层数增加一层。

  4. 最终 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;
    }
}

  1. Node* update[MAX_LEVEL + 1];: 定义一个数组 update 用于存储每层的插入位置。

  2. Node* current = skipList->header;: 初始化 current 指针为跳表的头节点，从头节点开始查找插入位置。

  3. 初始化 update 数组，将每个元素都设置为 NULL。

  4. 进入一个循环，从跳表的最高层开始向下查找每层的插入位置。在每层中，通过 current->forward[i] 遍历节点，找到对应位置并更新 update[i]。

  5. 生成一个随机层数 newLevel 作为新节点的层数。

  6. 如果新节点的层数比当前跳表的层数大，更新 update 数组。将新层数之后的位置都设置为跳表的头节点，并更新跳表的层数。

  7. 创建新节点，使用 createNode 函数生成一个具有指定键值和层数的节点。

  8. 最后，通过循环更新每层的指针，将新节点插入到跳表中。在每层中，将新节点的 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;
}

  1. Node* current = skipList->header;: 初始化 current 指针为跳表的头节点，从头节点开始查找。

  2. 进入一个循环，从跳表的最高层开始向下查找每层的查找位置。在每层中，通过 current->forward[i] 遍历节点，找到对应位置。

  3. 在最底层找到节点后，通过 current->forward[0] 检查是否为目标节点。如果找到了目标节点，返回该节点的指针。

  4. 如果在最底层未找到目标节点，函数返回 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;
}
文章标签：
C语言
索引
算法
存储
nanshaws
目录
相关文章
弹性计算-百晓生
|
22天前
|
弹性计算 人工智能 架构师
阿里云携手Altair共拓云上工业仿真新机遇
2024年9月12日，「2024 Altair 技术大会杭州站」成功召开，阿里云弹性计算产品运营与生态负责人何川，与Altair中国技术总监赵阳在会上联合发布了最新的“云上CAE一体机”。
弹性计算-百晓生
82278 20
阿里云携手Altair共拓云上工业仿真新机遇
Ganos全空间数据库
|
15天前
|
存储 关系型数据库 分布式数据库
GraphRAG：基于PolarDB+通义千问+LangChain的知识图谱+大模型最佳实践
本文介绍了如何使用PolarDB、通义千问和LangChain搭建GraphRAG系统，结合知识图谱和向量检索提升问答质量。通过实例展示了单独使用向量检索和图检索的局限性，并通过图+向量联合搜索增强了问答准确性。PolarDB支持AGE图引擎和pgvector插件，实现图数据和向量数据的统一存储与检索，提升了RAG系统的性能和效果。
Ganos全空间数据库
1069 50
BetterBench
|
19天前
|
机器学习/深度学习 算法 大数据
【BetterBench博士】2024 “华为杯”第二十一届中国研究生数学建模竞赛 选题分析
2024“华为杯”数学建模竞赛，对ABCDEF每个题进行详细的分析，涵盖风电场功率优化、WLAN网络吞吐量、磁性元件损耗建模、地理环境问题、高速公路应急车道启用和X射线脉冲星建模等多领域问题，解析了问题类型、专业和技能的需要。
BetterBench
2570 22
【BetterBench博士】2024 “华为杯”第二十一届中国研究生数学建模竞赛 选题分析
阿里云云原生
|
17天前
|
人工智能 IDE 程序员
期盼已久！通义灵码 AI 程序员开启邀测，全流程开发仅用几分钟
在云栖大会上，阿里云云原生应用平台负责人丁宇宣布，「通义灵码」完成全面升级，并正式发布 AI 程序员。
阿里云云原生
1110 1
瓴羊Dataphin
|
1天前
|
存储 人工智能 搜索推荐
数据治理，是时候打破刻板印象了
瓴羊智能数据建设与治理产品Datapin全面升级，可演进扩展的数据架构体系为企业数据治理预留发展空间，推出敏捷版用以解决企业数据量不大但需构建数据的场景问题，基于大模型打造的DataAgent更是为企业用好数据资产提供了便利。
瓴羊Dataphin
151 2
BetterBench
|
19天前
|
机器学习/深度学习 算法 数据可视化
【BetterBench博士】2024年中国研究生数学建模竞赛 C题：数据驱动下磁性元件的磁芯损耗建模 问题分析、数学模型、python 代码
2024年中国研究生数学建模竞赛C题聚焦磁性元件磁芯损耗建模。题目背景介绍了电能变换技术的发展与应用，强调磁性元件在功率变换器中的重要性。磁芯损耗受多种因素影响，现有模型难以精确预测。题目要求通过数据分析建立高精度磁芯损耗模型。具体任务包括励磁波形分类、修正斯坦麦茨方程、分析影响因素、构建预测模型及优化设计条件。涉及数据预处理、特征提取、机器学习及优化算法等技术。适合电气、材料、计算机等多个专业学生参与。
BetterBench
1565 16
【BetterBench博士】2024年中国研究生数学建模竞赛 C题：数据驱动下磁性元件的磁芯损耗建模 问题分析、数学模型、python 代码
大模型服务小助手
|
2天前
|
JSON 自然语言处理 数据管理
阿里云百炼产品月刊【2024年9月】
阿里云百炼产品月刊【2024年9月】，涵盖本月产品和功能发布、活动，应用实践等内容，帮助您快速了解阿里云百炼产品的最新动态。
大模型服务小助手
190 6
阿里云百炼产品月刊【2024年9月】
阿里云新鲜事
|
21天前
|
编解码 JSON 自然语言处理
通义千问重磅开源Qwen2.5，性能超越Llama
击败Meta，阿里Qwen2.5再登全球开源大模型王座
阿里云新鲜事
918 14
中间件小哥
|
16天前
|
人工智能 开发框架 Java
重磅发布！AI 驱动的 Java 开发框架：Spring AI Alibaba
随着生成式 AI 的快速发展，基于 AI 开发框架构建 AI 应用的诉求迅速增长，涌现出了包括 LangChain、LlamaIndex 等开发框架，但大部分框架只提供了 Python 语言的实现。但这些开发框架对于国内习惯了 Spring 开发范式的 Java 开发者而言，并非十分友好和丝滑。因此，我们基于 Spring AI 发布并快速演进 Spring AI Alibaba，通过提供一种方便的 API 抽象，帮助 Java 开发者简化 AI 应用的开发。同时，提供了完整的开源配套，包括可观测、网关、消息队列、配置中心等。
中间件小哥
683 9
阿里云专家技术服务助手
|
15天前
|
存储 监控 调度
云迁移中心CMH：助力企业高效上云实践全解析
随着云计算的发展，企业上云已成为创新发展的关键。然而，企业上云面临诸多挑战，如复杂的应用依赖梳理、成本效益分析等。阿里云推出的云迁移中心（CMH）旨在解决这些问题，提供自动化的系统调研、规划、迁移和割接等功能，简化上云过程。CMH通过评估、准备、迁移和割接四个阶段，帮助企业高效完成数字化转型。未来，CMH将继续提升智能化水平，支持更多行业和复杂环境，助力企业轻松上云。
阿里云专家技术服务助手
319 20