高效查找利器：C语言跳表实现（从零开始掌握跳表数据结构）

如图所示，查找数字 17 时，可以从最高层开始，跳过大量无关节点，最终在底层精确定位，大大减少了比较次数。

跳表的核心思想

• 每个节点有多个指针，指向同层的下一个节点；
• 节点层数通过随机算法决定（通常使用抛硬币策略）；
• 最高层用于快速跳跃，最低层包含所有元素；
• 插入/删除时需维护各层的链接关系。

C语言跳表实现步骤

下面我们用 C 语言一步步实现跳表。首先定义节点结构和跳表结构。

1. 定义数据结构

#include <stdio.h>#include <stdlib.h>#include <time.h>#define MAX_LEVEL 16  // 最大层数#define PROBABILITY 0.5  // 升层概率typedef struct Node {    int key;    struct Node* forward[MAX_LEVEL];} Node;typedef struct SkipList {    Node* header;    int level;  // 当前最大层数} SkipList;

2. 创建新节点

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

3. 初始化跳表

SkipList* createSkipList() {    SkipList* list = (SkipList*)malloc(sizeof(SkipList));    list->level = 0;    list->header = createNode(-1, MAX_LEVEL - 1);    return list;}

4. 随机生成层数（抛硬币）

int randomLevel() {    int level = 0;    while ((rand() / (double)RAND_MAX) < PROBABILITY && level < MAX_LEVEL - 1) {        level++;    }    return level;}

5. 插入操作

void insert(SkipList* list, int key) {    Node* update[MAX_LEVEL];    Node* current = list->header;    // 从最高层开始查找插入位置    for (int i = list->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) {        return;    }    int newLevel = randomLevel();    // 如果新层数大于当前最大层数，更新高层指针    if (newLevel > list->level) {        for (int i = list->level + 1; i <= newLevel; i++) {            update[i] = list->header;        }        list->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;    }}

6. 查找操作

int search(SkipList* list, int key) {    Node* current = list->header;    for (int i = list->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 1; // 找到    }    return 0; // 未找到}

完整测试示例

int main() {    srand(time(NULL));    SkipList* list = createSkipList();    insert(list, 3);    insert(list, 6);    insert(list, 7);    insert(list, 9);    insert(list, 12);    printf("Search 6: %s\n", search(list, 6) ? "Found" : "Not Found");    printf("Search 10: %s\n", search(list, 10) ? "Found" : "Not Found");    return 0;}

总结

通过本教程，你已经掌握了如何用 C语言实现跳表。跳表是一种非常实用的跳表数据结构，在 Redis 等系统中被广泛使用。相比红黑树，它的代码更简洁，调试更容易。

如果你正在学习数据结构或准备面试，建议动手敲一遍上述C语言教程中的代码，并尝试扩展删除功能。完整的跳表源码可作为项目参考，助你深入理解其内部机制。

希望这篇教程对你有帮助！欢迎收藏并分享给其他 C 语言学习者。