跳表的C语言实现

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

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

---

1. 跳表的基本概念

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

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

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

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

---

2. 跳表的关键操作

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

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

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

---

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. 代码说明

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

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

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

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

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

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

---

5. 运行结果

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

---

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