1. 单链表
链表中的结点用存储单元（若干个连续字节）来存放，存储单元之间既可以是（存储空间上）连续的，也可以是不连续的，甚至可以零散地分布在存储空间中的任何位置。换言之，链表中结点的逻辑次序和物理次序之间并无必然联系。最重要的是，链表可以在不移动结点位置的前提下根据需要随时添加删除结点，动态调整。
0. 概念
增加了向前指针的链表叫作跳表。跳表全称叫做跳跃表，简称跳表。跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。
跳表是一个随机化的数据结构，可以被看做二叉树的一个变种，它的性能在某些情况下可以与平衡二叉树（如红黑树和AVL树）相媲美，它的查找、插入和删除操作的时间复杂度为O(log n)
跳表的原理相对简单，因此在一些具有内存限制或对插入和删除操作性能要求较高的场景下，跳表是一种常用的选择。例如，Redis和LevelDB等数据库系统中就广泛使用了跳表来实现有序集合的功能。
1. 数据结构
定义宏：
a. 跳表节点结构SkipListNode
SkipListNode表示跳表中的节点，包含一个整型的键值和一个整型的值，以及一个指向其他节点的指针数组
b. 跳表结构SkipList
表示整个跳表，包含最大层数、当前层数和一个指向头节点的指针。
2. 辅助函数
a. 初始化节点
b. 初始化跳表
c. 生成随机层数
3. 查找节点
从跳表的最高层开始遍历节点，找到在每一层中键值小于给定键值的最大节点。然后，沿着最底层的指针找到当前节点，并检查是否存在具有相同键值的节点。如果存在，返回该节点的指针。否则，返回NULL表示未找到。
4. 插入节点
5. 删除节点
6. 主函数
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/8064.html