无标题
#include <iostream>
#include <cstdlib>
#include <cstdint>
#include <cstring>
#include <ctime>#define SKIP_LIST_MAX_LEVEL 4// 跳表连接item
typedef struct skip_list_item
{struct skip_list_node *prev; // 上一个节点指针，指向头，&head[0]/headstruct skip_list_node *next; // 下一个节点指针
} skip_list_item_t;// 跳表节点
typedef struct skip_list_node
{skip_list_item_t item[SKIP_LIST_MAX_LEVEL]; // 跳表节点itemuint32_t key;                                // 用于排序的keyuint32_t level;                              // 节点当前所在层级
} skip_list_node_t;// 跳表结构
typedef struct skip_list
{skip_list_node_t head;  // 跳表每层的head，head.item[0]为原表uint64_t size;          // 跳表节点总数uint32_t level;         // 下次节点插入跳表层数uint32_t level_max;     // 跳表最大层数
} skip_list_t;/*******************************************************************************/
skip_list_t *skip_list_create()
{skip_list_t *skip_list = (skip_list_t *)calloc(1, sizeof(skip_list_t));skip_list->size = 0;skip_list->level = 0;skip_list->level_max = SKIP_LIST_MAX_LEVEL;return skip_list;
}void skip_list_destroy(skip_list_t *skip_list)
{skip_list_node_t *node = skip_list->head.item[0].next;while (node != NULL){skip_list_node_t *next = node->item[0].next;free(node);node = next;}free(skip_list);
}void skip_list_node_init(skip_list_node_t *node, uint32_t key, uint32_t level)
{memset(&node->item, 0, sizeof(node->item));node->key = key;node->level = level;
}void skip_list_update_level(skip_list_t *skip_list)
{uint32_t level = 1;while ((rand() & 65535) < 32768){level++;}level = level < SKIP_LIST_MAX_LEVEL ? level : SKIP_LIST_MAX_LEVEL;skip_list->level = level - 1;
}void skip_list_insert(skip_list_t *skip_list, skip_list_node_t *node)
{skip_list_update_level(skip_list);node->level = skip_list->level;skip_list_node_t *update[SKIP_LIST_MAX_LEVEL];skip_list_node_t *x = &skip_list->head;int i = SKIP_LIST_MAX_LEVEL - 1;// 找到每一层要插入的位置while (i >= 0){while (x->item[i].next != NULL && x->item[i].next->key < node->key){x = x->item[i].next;}update[i] = x;i--;}// 执行插入操作for (int i = 0; i <= (int)node->level; i++){node->item[i].next = update[i]->item[i].next;if (update[i]->item[i].next != NULL){update[i]->item[i].next->item[i].prev = node;}update[i]->item[i].next = node;node->item[i].prev = update[i];}skip_list->size++;
}skip_list_node_t *skip_list_find(skip_list_t *skip_list, uint32_t key)
{if (skip_list->size == 0)return NULL; // 空表skip_list_node_t *x = &skip_list->head;int i = SKIP_LIST_MAX_LEVEL - 1;// 先找到节点while (i >= 0){while (x->item[i].next != NULL && x->item[i].next->key < key){x = x->item[i].next;}i--;}x = x->item[0].next;if (x != NULL && x->key == key){return x;}return NULL;
}skip_list_node_t *skip_list_find_max(skip_list_t *skip_list)
{if (skip_list->size == 0)return NULL; // 空表skip_list_node_t *x = &skip_list->head;int i = SKIP_LIST_MAX_LEVEL - 1;// 找到最大节点while (i >= 0){while (x->item[i].next != NULL){x = x->item[i].next;}i--;}if (x == &skip_list->head)return NULL;return x;
}skip_list_node_t *skip_list_find_min(skip_list_t *skip_list)
{if (skip_list->size == 0)return NULL; // 空表skip_list_node_t *x = skip_list->head.item[0].next;if (x == NULL)return NULL;return x;
}void skip_list_print(skip_list_t *skip_list)
{for (int i = SKIP_LIST_MAX_LEVEL - 1; i >= 0; i--){skip_list_node_t *x = skip_list->head.item[i].next;std::cout << "Level " << i << ": ";while (x != NULL){std::cout << x->key << " ";x = x->item[i].next;}std::cout << std::endl;}
}int main()
{skip_list_t *skip_list = skip_list_create();srand(time(NULL));uint32_t keys[] = {3, 6, 7, 9, 12, 19, 17, 26, 21, 25};for (uint32_t key : keys){skip_list_node_t *node = (skip_list_node_t *)malloc(sizeof(skip_list_node_t));skip_list_node_init(node, key, 0);skip_list_insert(skip_list, node);}std::cout << "Skip List:" << std::endl;skip_list_print(skip_list);uint32_t search_key = 19;skip_list_node_t *found = skip_list_find(skip_list, search_key);std::cout << "Search for " << search_key << ": " << (found ? "Found" : "Not Found") << std::endl;search_key = 15;found = skip_list_find(skip_list, search_key);std::cout << "Search for " << search_key << ": " << (found ? "Found" : "Not Found") << std::endl;skip_list_destroy(skip_list);return 0;
} 

skip_list_insert 函数流程

随机决定新节点的层数

void skip_list_insert(skip_list_t *skip_list, skip_list_node_t *node)
{skip_list_update_level(skip_list);  // 随机更新跳表的层数node->level = skip_list->level;     // 设置新节点的层数
}

skip_list_update_level(skip_list) 会随机决定新节点需要占据的层数（根据概率，高层节点少，低层节点多，类似于抛硬币）。
新节点 node 的层数被设置为刚刚生成的随机层数 skip_list->level。

找到每一层要插入的位置

skip_list_node_t *update[SKIP_LIST_MAX_LEVEL];  // 保存插入位置的前驱节点
skip_list_node_t *x = &skip_list->head;         // 从跳表的头节点开始
int i = SKIP_LIST_MAX_LEVEL - 1;// 找到每一层要插入的位置
while (i >= 0)
{while (x->item[i].next != NULL && x->item[i].next->key < node->key){x = x->item[i].next;  // 在第 i 层向右移动，寻找插入位置}update[i] = x;  // 记录需要在第 i 层插入的位置的前一个节点i--;  // 进入下一层
}skip_list_node_t *update[SKIP_LIST_MAX_LEVEL];  // 保存插入位置的前驱节点
skip_list_node_t *x = &skip_list->head;         // 从跳表的头节点开始
int i = SKIP_LIST_MAX_LEVEL - 1;// 找到每一层要插入的位置
while (i >= 0)
{while (x->item[i].next != NULL && x->item[i].next->key < node->key){x = x->item[i].next;  // 在第 i 层向右移动，寻找插入位置}update[i] = x;  // 记录需要在第 i 层插入的位置的前一个节点i--;  // 进入下一层
}

​
初始化了一个 update 数组，用于保存插入位置前驱节点。
设置一个指针 x 指向跳表的头节点，从最高层 (i = SKIP_LIST_MAX_LEVEL - 1) 开始。
通过内层循环，在每一层查找当前节点 x 所需插入位置的前一个节点，并将该节点记录到 update 数组。
如果 x->item[i].next 不为空且 x->item[i].next->key 小于 node->key，则 x 继续向右移动。
一旦找到适合插入位置的节点，记录在 update[i] 中。
逐层向下（i–）重复上述步骤，直到最低层（层0）。
3. 执行插入操作
// 执行插入操作
for (int i = 0; i <= (int)node->level; i++)
{
node->item[i].next = update[i]->item[i].next; // 新节点的 next 指向前驱节点的 next
if (update[i]->item[i].next != NULL)
{
update[i]->item[i].next->item[i].prev = node; // 前驱节点的 next 指向新节点
}
update[i]->item[i].next = node; // 前驱节点的 next 指向新节点
node->item[i].prev = update[i]; // 新节点的 prev 指向前驱节点
}

skip_list->size++;  // 更新跳表中的节点数

}
复制
// 执行插入操作
for (int i = 0; i <= (int)node->level; i++)
{
node->item[i].next = update[i]->item[i].next; // 新节点的 next 指向前驱节点的 next
if (update[i]->item[i].next != NULL)
{
update[i]->item[i].next->item[i].prev = node; // 前驱节点的 next 指向新节点
}
update[i]->item[i].next = node; // 前驱节点的 next 指向新节点
node->item[i].prev = update[i]; // 新节点的 prev 指向前驱节点
}

skip_list->size++;  // 更新跳表中的节点数

}
​
遍历从第0层到新节点的最大层 node->level：
node->item[i].next = update[i]->item[i].next;：新节点 node 的下一个节点指向更新节点 update[i] 的下一个节点。
if (update[i]->item[i].next != NULL)：如果 update[i]->item[i].next 不是空，则更新下一个节点的 prev 指针指向新节点 node。
update[i]->item[i].next = node;：更新节点 update[i] 的下一个节点指向新节点 node。
node->item[i].prev = update[i];：新节点 node 的前一个节点指向更新节点 update[i]。
最后，更新跳表的节点总数 skip_list->size++。
插入过程示意图
假设跳表如下，准备插入节点 node（key为10）：

当前跳表：
Level 3: head -> 15 -> NULL
Level 2: head -> 9 -> 15 -> NULL
Level 1: head -> 7 -> 9 -> 15 -> NULL
Level 0: head -> 3 -> 7 -> 9 -> 15 -> NULL
复制
当前跳表：
Level 3: head -> 15 -> NULL
Level 2: head -> 9 -> 15 -> NULL
Level 1: head -> 7 -> 9 -> 15 -> NULL
Level 0: head -> 3 -> 7 -> 9 -> 15 -> NULL
​

1. 查找插入位置：
   在每一层中找到应插入位置前的节点。

update[] = { head, 7, 9, 9 };
复制
update[] = { head, 7, 9, 9 };
​
2. 执行插入：
假设新节点随机生成的层数为2（第三层也有节点）。

把新节点插入适当位置后：

插入 key=10 后的跳表：
Level 3: head -> 10 -> 15 -> NULL
Level 2: head -> 9 -> 10 -> 15 -> NULL
Level 1: head -> 7 -> 9 -> 10 -> 15 -> NULL
Level 0: head -> 3 -> 7 -> 9 -> 10 -> 15 -> NULL
复制
插入 key=10 后的跳表：
Level 3: head -> 10 -> 15 -> NULL
Level 2: head -> 9 -> 10 -> 15 -> NULL
Level 1: head -> 7 -> 9 -> 10 -> 15 -> NULL
Level 0: head -> 3 -> 7 -> 9 -> 10 -> 15 -> NULL