7.2 跳跃表（skiplist）—— C语言实现

🕗 发布于 2024-04-21 09:38 skiplist

文章目录

前言
一、跳跃表——查找操作
二、跳跃表——插入操作
三、代码演示
- 3.1 输出结果
- 3.2 代码细节
四、总结：
参考文献：

前言

本章内容参考海贼宝藏胡船长的数据结构与算法中的第七章——查找算法，侵权删。

查找的时间复杂度能从原来链表的 $O (n)$ 降到 $O (l o g n)$ ，典型的用空间复杂度换时间复杂度的例子。
在这里插入图片描述

直观上感受就是把原来的链表给拉升了，处于同一高度的节点被串联成了一个单独的链表，每个链表都有一个层高：
第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

插入和查找的过程图像要非常清晰，边写代码脑海里要有一个动态的图像。多练，无他唯手熟尔！

参考文献：

原文地址：https://blog.csdn.net/qq_43067403/article/details/137977749

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：【C++提高】常用容器
下一篇：nextjs getStaticProps 和 getServerSideProps 区别

【QT基础】创建项目&项目代码解释
本篇文章详细介绍了QT是如何创建项目的，并且解释了项目中各个默认文件代码的意思。内附大量图文。
阅读更多2024-09-20
什么品牌超声波清洗机质量好？四大绝佳超声波清洗机品牌推荐！
在关键部件——声波换能震动器的研发上，团队耗时两年，斥资逾百万，反复经历了上百轮的产品优化试验，深入探究了频率与真空冲击波能量对提升清洁效果及保护清洗物件免受损伤的细微作用。此超声波清洗器呈现出时尚的
阅读更多2024-09-20
基于eBPF的procstat软件追踪程序垃圾回收（GC）事件
procstat是一款基于eBPF的监控软件，运行在Linux平台，主要用于跟踪目标程序的运行状态，并报告异常指标，是分析程序性能问题的一大利器。procstat软件能够用于追踪golang及jvm程
阅读更多2024-09-20
VBA技术资料MF198：禁用下拉拖放
我给VBA的定义：VBA是个人小型自动化处理的有效工具。利用好了，可以大大提高自己的工作效率，而且可以提高数据的准确度。“VBA语言専攻”提供的教程一共九套，分为初级、中级、高级三大部分，教程是对VB
阅读更多2024-09-20
ISSTA 2024现场精彩：“杰出论文奖”超半数属于中国学者
开幕式还展示了一些有趣的统计，从1990年代至今的年录取率变化趋势，到每篇论文背后作者数量的分布图，再到年投稿量的变化趋势，每一个数字都见证了ISSTA的成长与辉煌，也映射出软件测试与分析领域日益蓬勃
阅读更多2024-09-20
解决selenium爬虫被浏览器检测问题
解决selenium爬虫被浏览器检测问题
阅读更多2024-09-20
极越联手百度这你受得了吗！SU7还能稳坐“7字辈”头把交椅？
方向盘采用了经典的圆形设计，其上的红色按键可轻松切换不同的驾驶模式，为驾驶者提供了更多的操控选择。尾部的扩散器和与车身同色的后保险杠装饰件，不仅提升了车辆的运动感，还让尾部看起来更加饱满和谐。座椅采用
阅读更多2024-09-20
【云安全】云服务安全攻防
本文主要介绍了场景的云服务攻击场景。
阅读更多2024-09-20
工程师 - .NET程序反编译器
它允许开发人员检查已编译的 .NET 应用程序、库和组件的底层代码，即使在无法获得原始源代码的情况下也是如此。.NET Reflector 可将已编译的 .NET 程序集（如`.dll`和`.exe`
阅读更多2024-09-20
【混淆矩阵】Confusion Matrix！定量评价的基础！如何计算全面、准确的定量指标去衡量模型分类的好坏？？
【混淆矩阵】Confusion Matrix！定量评价的基础！学习笔记
阅读更多2024-09-20