跳表的C语言实现

跳表（Skip List）是一种基于链表的动态数据结构，用于实现高效的查找、插入和删除操作。它通过引入多级索引来加速查找过程，类似于多级索引的有序链表。跳表的平均时间复杂度为 O(logn)，在某些场景下可以替代平衡树。

以下是跳表的基本实现思路和一个简单的 C 语言实现示例。

---

1. 跳表的基本概念

节点结构：每个节点包含一个值和多个指向不同层级的指针。

层级：每个节点的层级是随机的，通常通过抛硬币的方式决定。层级越高，索引的作用越强。

头节点：跳表的入口，包含指向各级索引的指针。

尾节点（可选）：用于快速判断是否到达链表末尾。

---

2. 跳表的关键操作

查找：从最高层开始，逐层向下查找，直到找到目标值或到达底层。

插入：找到插入位置后，随机生成节点的层级，并更新指针。

删除：找到目标节点后，更新相关指针，并释放节点。

---

3. C语言实现

以下是一个简单的跳表实现，支持查找、插入和删除操作：

#include <stdio.h> #include <stdlib.h> #include <time.h> #define MAX_LEVEL 16 // 最大层级 #define PROBABILITY 0.5 // 随机层级的概率 typedef struct SkipListNode { int value; struct SkipListNode* next[MAX_LEVEL]; } SkipListNode; typedef struct SkipList { SkipListNode* head; int level; } SkipList; // 创建新节点 SkipListNode* createNode(int value, int level) { SkipListNode* node = (SkipListNode*)malloc(sizeof(SkipListNode)); node->value = value; for (int i = 0; i < level; i++) { node->next[i] = NULL; } return node; } // 创建跳表 SkipList* createSkipList() { SkipList* list = (SkipList*)malloc(sizeof(SkipList)); list->head = createNode(-1, MAX_LEVEL); // 创建头节点 list->level = 0; return list; } // 随机生成层级 int randomLevel() { int level = 1; while (rand() / (double)RAND_MAX < PROBABILITY && level < MAX_LEVEL) { level++; } return level; } // 查找操作 SkipListNode* search(SkipList* list, int value) { SkipListNode* current = list->head; for (int i = list->level - 1; i >= 0; i--) { while (current->next[i] != NULL && current->next[i]->value < value) { current = current->next[i]; } } current = current->next[0]; if (current != NULL && current->value == value) { return current; } return NULL; } // 插入操作 void insert(SkipList* list, int value) { int level = randomLevel(); SkipListNode* newNode = createNode(value, level); SkipListNode* update[MAX_LEVEL] = {NULL}; SkipListNode* current = list->head; for (int i = list->level - 1; i >= 0; i--) { while (current->next[i] != NULL && current->next[i]->value < value) { current = current->next[i]; } update[i] = current; } for (int i = 0; i < level; i++) { newNode->next[i] = update[i]->next[i]; update[i]->next[i] = newNode; } if (level > list->level) { for (int i = list->level; i < level; i++) { list->head->next[i] = newNode; } list->level = level; } } // 删除操作 void deleteNode(SkipList* list, int value) { SkipListNode* update[MAX_LEVEL] = {NULL}; SkipListNode* current = list->head; for (int i = list->level - 1; i >= 0; i--) { while (current->next[i] != NULL && current->next[i]->value < value) { current = current->next[i]; } update[i] = current; } current = current->next[0]; if (current != NULL && current->value == value) { for (int i = 0; i < list->level; i++) { if (update[i]->next[i] != current) { break; } update[i]->next[i] = current->next[i]; } free(current); while (list->level > 1 && list->head->next[list->level - 1] == NULL) { list->level--; } } } // 打印跳表 void printSkipList(SkipList* list) { for (int i = list->level - 1; i >= 0; i--) { SkipListNode* current = list->head->next[i]; printf("Level %d: ", i); while (current != NULL) { printf("%d ", current->value); current = current->next[i]; } printf("\n"); } } int main() { srand(time(NULL)); SkipList* list = createSkipList(); insert(list, 3); insert(list, 6); insert(list, 7); insert(list, 9); insert(list, 12); insert(list, 19); insert(list, 17); insert(list, 26); insert(list, 21); insert(list, 25); printf("Skip List:\n"); printSkipList(list); SkipListNode* result = search(list, 19); if (result != NULL) { printf("Found %d in the skip list.\n", result->value); } else { printf("Value not found.\n"); } deleteNode(list, 19); printf("Skip List after deletion:\n"); printSkipList(list); return 0; } 4. 代码说明

节点结构：每个节点包含一个值和一个指向不同层级的指针数组。

随机层级：通过抛硬币的方式决定节点的层级。

查找：从最高层开始，逐层向下查找。

插入：找到插入位置后，随机生成节点的层级，并更新相关指针。

删除：找到目标节点后，更新相关指针，并释放节点。

打印：逐层打印跳表的内容，方便观察结构。

---

5. 运行结果

运行程序后，跳表的结构会以多级索引的形式打印出来，查找、插入和删除操作的结果也会显示。

---

跳表是一种非常灵活的数据结构，适用于需要高效查找和动态更新的场景。希望这个实现对你有所帮助！