跳表原理图
跳跃表（Skip List）是一种基于有序链表的数据结构，由William Pugh在论文《Skip lists: a probabilistic alternative to balanced trees》中提出。它是一种可以与平衡树媲美的层次化链表结构，能够在对数期望时间下完成查找、删除、添加等操作。
其原理是通过在链表中添加一些额外的指针，来提高查找、插入和删除元素的效率。 从概念上讲，跳跃表是一种查询结构，用于解决算法中的查找问题，即根据给定的`key`，快速查找到`key`所在的位置或者对应的`value`值。
2、跳跃表特点
跳跃表底部存储
有序性：跳跃表中的元素按照一定的顺序排列，可以是升序或降序。多层结构：跳跃表由多层链表组成，每一层都是一个有序链表。高层链表中的元素指向与其值相等的低层链表中的元素。快速查找：通过利用多层结构和指针的指引，可以在跳跃表中快速地查找元素。高效插入和删除：跳跃表支持高效的插入和删除操作，通过随机决定新节点是否提升到上一层，可以保持索引的平衡性和效率。3、跳跃表使用场景跳跃表在很多场景中都有应用，例如数据库索引、缓存系统、搜索引擎等。它的优势在于实现简单、效率高，并且具有良好的平衡性和扩展性。
4、C语言手撕跳跃表
C语言手撕跳跃表
#include <stdio.h>#include <stdlib.h>#include <time.h>#define MAX_LEVEL 6 // 最大层数// 跳跃表节点结构体typedef struct snode { int value; struct snode **forward; // 指向每一层的下一个节点} SNode;// 跳跃表结构体typedef struct skiplist { int level; // 当前最大层数 SNode *head; // 指向跳跃表头节点} SkipList;// 新建跳跃表节点SNode *createSNode(int value, int level) { SNode *node = (SNode *)malloc(sizeof(SNode)); node->value = value; node->forward = (SNode **)calloc(level, sizeof(SNode *)); return node;}// 新建跳跃表SkipList *createSkipList() { SkipList *skiplist = (SkipList *)malloc(sizeof(SkipList)); skiplist->level = 1; skiplist->head = createSNode(0, MAX_LEVEL); int i; for (i = 0; i < MAX_LEVEL; ++i) { skiplist->head->forward[i] = NULL; } return skiplist;}// 插入节点void insert(SkipList *skiplist, int value) { SNode *update[MAX_LEVEL]; // 记录每一层的前一节点 SNode *node = skiplist->head; int i; for (i = skiplist->level - 1; i >= 0; --i) { while (node->forward[i] != NULL && node->forward[i]->value < value) { node = node->forward[i]; } update[i] = node; } node = node->forward[0]; if (node == NULL || node->value != value) { int level = 1; while (rand() % 2 == 1 && level < MAX_LEVEL) { ++level; } if (level > skiplist->level) { for (i = skiplist->level; i < level; ++i) { update[i] = skiplist->head; } skiplist->level = level; } node = createSNode(value, level); for (i = 0; i < level; ++i) { node->forward[i] = update[i]->forward[i]; update[i]->forward[i] = node; } }}// 删除节点void delete(SkipList *skiplist, int value) { SNode *update[MAX_LEVEL]; SNode *node = skiplist->head; int i; for (i = skiplist->level - 1; i >= 0; --i) { while (node->forward[i] != NULL && node->forward[i]->value < value) { node = node->forward[i]; } update[i] = node; } node = node->forward[0]; if (node != NULL && node->value == value) { for (i = 0; i < skiplist->level; ++i) { if (update[i]->forward[i] != node) { break; } update[i]->forward[i] = node->forward[i]; } free(node); while (skiplist->level > 1 && skiplist->head->forward[skiplist->level - 1] == NULL) { --skiplist->level; } }}// 查找节点int search(SkipList *skiplist, int value) { SNode *node = skiplist->head; int i; for (i = skiplist->level - 1; i >= 0; --i) { while (node->forward[i] != NULL && node->forward[i]->value < value) { node = node->forward[i]; } } node = node->forward[0]; return node != NULL && node->value == value;}// 打印跳跃表void printSkipList(SkipList *skiplist) { int i; for (i = skiplist->level - 1; i >= 0; --i) { printf("Level %d: ", i); SNode *node = skiplist->head->forward[i]; while (node != NULL) { printf("%d->", node->value); node = node->forward[i]; } printf("NULL\n"); }}// 程序入口int main() { srand((unsigned)time(NULL)); // 初始化随机数种子 SkipList *skiplist = createSkipList(); insert(skiplist, 1); insert(skiplist, 2); insert(skiplist, 3); insert(skiplist, 4); insert(skiplist, 5); insert(skiplist, 6); insert(skiplist, 7); insert(skiplist, 8); printSkipList(skiplist); delete(skiplist, 3); printSkipList(skiplist); printf("search 3: %d\n", search(skiplist, 3)); printf("search 7: %d\n", search(skiplist, 7)); printf("search 9: %d\n", search(skiplist, 9)); free(skiplist); return 0;}
运行截图
