前言
本章内容参考海贼宝藏胡船长的数据结构与算法中的第七章——查找算法，侵权删。
查找的时间复杂度能从原来链表的 O ( n ) O(n) O(n)降到 O ( l o g n ) O(logn) O(logn)，典型的用空间复杂度换时间复杂度的例子。
直观上感受就是把原来的链表给拉升了，处于同一高度的节点被串联成了一个单独的链表，每个链表都有一个层高：
第0层：1，6，15，30
第1层：1，6，15，30
第2层：1，15，30
第3层：1，15
第4层：15
跳跃表的特点：
- 有层高，每一层又是单独的链表
- 有两个特殊的节点，头节点代表极小值，尾节点代表极大值。也就是说不管插入什么样的值都是在头尾节点之中
- 跳跃表本身会维护这些元素的有序性（跳跃表中的元素是有大小顺序的）
跳跃表具体的操作：
- 插入
- 删除
- 查找
一、跳跃表——查找操作
- 首先从最左上方的节点开始找，以当前节点值的下一个节点值作为基准值
- 如果下一个当前节点值比待查找值要小，当前层高（本层）节点的下一个节点与待查找值作比较。
- 如果下一个当前节点值比待查找值要大，该节点的位置（而不是下一层的第一个节点）向下走。
- 如果下一个当前节点值等于待查找值，那就找到了！
- 重复步骤1。
如图展示：
举个例子：
二、跳跃表——插入操作
结合普通链表的插入操作：我们应该先查找待插入节点的前一个节点
如何找到呢？
首先插入节点要有一个高度（高度随机），找到初始节点中与待插入节点等高的节点作为头节点
规则和查找操作类似：从上往下找，以当前节点值的下一个节点值作为基准值。
- 如果下一个节点值比待查找值要小，前往本层中的下一个节点
- 如果下一个节点值比待查找值要大，前往当前节点的下一层
重复操作2，到达0层。至此，找到了每一层需要连接插入节点的对应节点
三、代码演示
- 初始化了一个具有n层结构的跳跃表中的节点
- 需要一个表示整个跳跃表的结构，因为在跳跃表中有几个比较特殊的信息，这几个特殊的信息，必须是由跳跃表去维护的：
- 头尾指针
- 当前跳跃表最高的层数
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include <inttypes.h>
#include<time.h>
typedef struct Node
{
int key, level;
struct Node *next, *down, *up;
} Node;
typedef struct Skiplist
{
Node *head, *tail;
int max_level;
} Skiplist;
//初始化了一个具有n层结构的跳跃表中的节点
Node *getNewNode(int key, int n){
Node *nodes = (Node*)malloc(sizeof(Node) * n);
for (int i = 0; i < n; i++){
nodes[i].key = key;
nodes[i].level = i;
nodes[i].next = NULL;
nodes[i].down = (i ? nodes + (i - 1) : NULL);
nodes[i].up = (i + 1 < n ? nodes + (i + 1) : NULL);
}
return nodes + n - 1;
}
//初始化跳跃表
Skiplist *getNewSkiplist(int n){
Skiplist *s = (Skiplist *)malloc(sizeof(Skiplist));
s->head = getNewNode(INT32_MIN, n);
s->tail = getNewNode(INT32_MAX, n);
s->max_level = n;
Node *p = s->head, *q = s->tail;
while (p){
p->next = q;
p = p->down, q = q->down;
}
//刚开始创建跳表时，跳跃表是空，应该让跳表的头指针应该指向第0层的头节点，随着插入新节点，这个层高才逐渐增高
while (s->head->level != 0) s->head = s->head->down;
return s;
}
//返回的是找到值所在节点的最上层的节点
Node *find(Skiplist *s, int x){
Node *p = s->head;
while (p && p->key !=x){
if (p->next->key <= x) p = p->next;
else p = p->down;
}
return p;
}
double randDouble(){
#define MAX_RAND_N 1000000
return (rand() % MAX_RAND_N) * 1.0 / MAX_RAND_N;
#undef MAX_RAND_N
}
//生成层数
int randLevel(Skiplist *s){
int level = 1;
double p = 1.0 / 2.0;
while (randDouble() < p) level += 1; //层数越高，生成该层数的概率越小，生成n层的概率是p^n
#define min(a, b) ((a) > (b) ? (b) : (a))
return min(s->max_level, level);
#undef min
}
void insert(Skiplist *s, int x){
int level = randLevel(s);
printf("rand level = %d\n", level);
while (s->head->level + 1 < level) s->head = s->head->up; //这里保证头指针的层数一定不小于生成的node节点的层数
Node *node = getNewNode(x, level);
Node *p = s->head;
printf("insert begin\n");
fflush(stdout);
while (p->level != node->level) p = p->down;// 头节点和node节点等高，二者对齐
while (p) {
while (p->next->key < node->key) p = p->next;
node->next = p->next;
p->next = node; //这里已经完成了本层的节点插入
//接着向下继续插入
p = p->down;
node = node->down; //Node节点也得往下走
}
return;
}
void clearNode(Node *p){
if(p == NULL) return;
free(p);
return;
}
void clearSkiplist(Skiplist *s){
Node *p = s->head, *q;
while(p->level != 0) p = p->down; // 从最下层开始遍历清除
while(p){
q = p->next;
clearNode(p);
p = q;
}
free(s);
return;
}
void output(Skiplist *s){
Node *p = s->head;
int len = 0;
for (int i = 0; i <= s->head->level; i++){
len += printf("%4d", i);
}
printf("\n"); //输出层号
for (int i = 0; i < len; i++) printf("-");
printf("\n");
while (p->level > 0) p = p->down; //先到第0层，也就是最底层
while (p){
bool flag = (p->key != INT32_MIN && p->key != INT32_MAX); //头和尾没有必要输出
for (Node *q = p; flag && q; q = q->up){
printf("%4d", q->key);
}
if (flag) printf("\n");
p = p->next;
}
return;
}
int main(){
srand(time(0));
int x;
#define MAX_LEVEL 32
Skiplist *s = getNewSkiplist(MAX_LEVEL);
#undef MAX_LEVEL
// insert
while (~scanf("%d", &x)){
if (x == -1) break;
insert(s, x);
output(s);
}
output(s);
// find
while (~scanf("%d", &x)){
Node *p = find(s,x);
printf("find result: ");
if(p){
printf("key = %d, level = %d\n", p->key, p->level);
}else{
printf("NULL\n");
}
}
clearSkiplist(s);
return 0;
}
3.1 输出结果
插入
查找
3.2 代码细节
- 释放内存的部分，其实clearNode()传入只能是多层节点的最底层（当然这里有风险，如果传入的不是最底层，那么free就会出错），看这个例子
#include<stdio.h>
#include<stdlib.h>
int *getNewArray(int n){
int *p = (int *)malloc(sizeof(int) * n);
for(int i = 0; i < n; i++){
p[i] = i;
}
return p + n - 1;
}
void clearArray(int *p){
if(!p) return;
free(p);
return;
}
int main(){
int num = 12;
int *a1 = getNewArray(num);
printf("%p\n", a1);
printf("%d\n", *a1); // 11
printf("%d\n", *(a1 - num + 1)); // 0
// free a1
clearArray(a1);
printf("%d\n", *a1); // error
// free(): invalid pointer
//Aborted (core dumped)
printf("%d\n", *(a1 - num + 1)); // 0
// free a1 - num + 1
clearArray(a1-num+1);
printf("%d\n", *a1); // ?
printf("%d\n", *(a1 - num + 1)); // 0
return 0;
}
原因是：由于 getNewArray 返回了指向数组最后一个元素的指针，当你尝试在 clearArray 中释放这个指针时，会遇到 free(): invalid pointer 错误。因为 free 函数需要传入的指针必须是由 malloc, calloc 或 realloc 分配的原始指针。这里传入的是数组末尾的指针，而不是原始指针。
- 初始化跳跃表的时候：创建一个空的跳跃表（此时只有头尾两个具有max_level层的节点），此时的
s->head最好应该指向最底层，随着插入逐渐s->head升高。（不是必须，但这样方便维护）
四、总结：
有的版本跳跃表把Node中的
*next, *up, *down换成*next[]/*柔性数组,根据该节点层数的不同指向大小不同的数组 *next[0]表示该节点的第一层下一节点的索引地址 *next[1]表示该节点的第二层下一节点的索引地址 *next[n]表示该节点的第n层下一节点的索引地址 */这样做就没有up,down指针，这样处理也是一种可以借鉴的思路
关注
Node *getNewNode()函数，这个函数是申请（malloc）n层节点中底层的内存空间，而返回的则是顶层的内存地址，这个应当非常注意。封装结构：一个Node是一个封装，
getNewNode函数创建的是一个n层的具有高度的数组（其元素是Node类型），而跳表封装了这样的数组。如果把Node换成总结中的第一点*next[]，这个其实就是这样的一个具有n层的数组，不再把它抽象成单独的一个Node。这两种不同的定义，就看你怎么抽象了，到底哪个是最小的封装单元。
Node ——> 单个Node组成的高度（长度）为n的数组 ——> 跳表struct skip_list_node { /*key是唯一的*/ int key; /*存储的内容*/ int value; /*当前节点最大层数*/ int max_level; /*柔性数组,根据该节点层数的不同指向大小不同的数组 *next[0]表示该节点的第一层下一节点的索引地址 *next[1]表示该节点的第二层下一节点的索引地址 *next[n]表示该节点的第n层下一节点的索引地址 */ struct skip_list_node *next[]; }; 代码原文链接：https://blog.csdn.net/m0_37845735/article/details/103691814插入和查找的过程图像要非常清晰，边写代码脑海里要有一个动态的图像。多练，无他唯手熟尔！