跳表概念以及跳表增删查规则
跳表比较好理解，但是实际用代码来表示，还是有点复杂的。
实现的方法不唯一
1. 什么是跳表 跳表是 链表 + 索引 的一种数据结构 ，是以空间换取时间的方式，关于跳表参考: https://baike.baidu.com/item/跳表/22819833?fr=aladdin
2. 跳表概念 跳表在原有链表的基础上，增加索引，从而可以进行二分查找，提高搜寻效率。
原始链表
head ——> 1 ——> 8 ——> 12 ——> 23 ——> 55 ——> null 新增了索引的链表(跳表)
head2 ————————> 8 ———————————————————————> null head1 ————————> 8 —————————> 23 —————————> null head0 ——> 1 ——> 8 ——> 12 ——> 23 ——> 55 ——> null head0 , head1 , head2 上都是真实的节点，这就是以空间换取时间
例如算上head, 元素数据一共有 6 个，而添加索引后，元素一共有 11 个
3. 跳表增删查规则 3.1 跳表数据节点
数据节点可以和链表节点一致 ，也可以定义如下节点，除了数据外，有指针指向 前一个/后一个/上一个/下一个 节点，以便后续查找操作。
typedef struct { int data; struct node *next; // 后一个节点 struct node *last; // 前一个节点 struct node *up; // 上一个节点 struct node *down; // 下一个节点} node; 3.2 跳表初始化
当跳表有多少层的时候，应当建立多少个头结点，例如: 跳表为3层
head2 ——> nullhead1 ——> nullhead0 ——> null 3.3 查找 删除/新增 都会进行查询才操作，无非是删除/新增索引而已。
例如有如下数据
head2 —————————————————————> 23 —————————> null head1 ————————> 8 —————————> 23 —————————> null head0 ——> 1 ——> 8 ——> 12 ——> 23 ——> 55 ——> null 要查找 13这个节点
去除无效层
例如: head2 后面第一个节点的数据 23 ， 而 23 大于 13 , 所以 head2 没有数据匹配查询，故需要跳到下面一层，至 head1 上进行查询。
查询至head0层
去除无效层后数据进入了 head1 , 在head1上进行匹配，当匹配到 23 时，23大于13，将23标记为 查询结束点，对23的上一个节点 8 进行 向下指针操作，进入 head0层的8节点。
查找实际数据
从head0层的8 进行查找，直至 查询结束标记点(head1 23), 查询的数据分别为 8 ， 12 ，23 查询结束，未找到数据。
3.4 新增
新增操作需要记录索引寻址过程，以便后续新增索引。
头结点插入
头结点插入一定是 去除无效层 至head0 , 且 head0的第一个节点都比插入节点要大的情况下
例如:
如下跳表，插入 2
head2 —————————————————————> 23 —————————> null head1 ————————> 8 —————————> 23 —————————> null head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> null 尾结点插入
头结点插入一定是 去除无效层 至head0 , 且 head0的第一个节点都比插入节点要小，直至null节点的情况下
例如:
如下跳表，插入 65
head2 —————————————————————> 23 —————————> null head1 ————————> 8 —————————> 23 —————————> null head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> null 中间节点插入
除开以上2种情况，其余情况为 中间节点插入
新增索引
抛硬币的方法，当数据量达到一定规模的时候，一定是趋近于 50%的。
所以跳表会越来越趋向于如下形式
3 3 71 3 5 7 91 2 3 4 5 6 7 8 9 判断是否需要新增索引，采取抛硬币的方法来判断，即: 随机数 取余 为 0 则需要新增，否则不需要。
例如如下跳表，插入 65
head2 —————————————————————> 23 —————————> null head1 ————————> 8 —————————> 23 —————————> null head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> null 寻址应该为
head2: 23
head1: 23
元素数据插入后为
head2 —————————————————————> 23 ———————————————> null head1 ————————> 8 —————————> 23 ———————————————> null head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> 65 —> null 当插入65节点后，若判断需要索引的时候，则先为 head1 添加索引，添加位置为 寻址地址之后，寄 head1: 23
head2 —————————————————————> 23 ———————————————> null head1 ————————> 8 —————————> 23 —————————> 65 —> null head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> 65 —> null 继续判断，若不需要添加索引，则插入结束
若还需要添加索引，则继续上述操作，直至 索引层 达到最高层
3.5 删除
删除首先是查找操作【3.3 查找】
若未找到该节点，则删除失败
若找到了该节点，则应当提到该数据最高索引层，再从高到低删除
例如:
如下跳表，删除 23
head2 —————————————————————> 23 ———————————————> null head1 ————————> 8 —————————> 23 —————————> 65 —> null head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> 65 —> null 找到 head0 23 后，应该向上找到 head2 23 ,然后从高向低删除，若删除后，该索引没有数据了，则索引层减1
则删除head2 23 后数据如下
head1 ————————> 8 —————————> 23 —————————> 65 —> null head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> 65 —> null 删除head1 23 后数据如下
head1 ————————> 8 ———————————————————————> 65 —> null head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> 65 —> null 删除head0 23后数据如下
head1 ————————> 8 ————————————————> 65 —> null head0 ——> 3 ——> 8 ——> 12 ——> 55 ——> 65 —> null 4. 代码 skiplist.c
# include # include # include int maxlevel = 8; // 最大层数int currlevel = 0; // 当前层数// 数据节点typedef struct { int data; struct node *next; struct node *last; struct node *up; struct node *down;} node;// 记录索引寻址过程typedef struct { int level; struct node *node;} skipstep;// 判断是否需要新增索引, 抛硬币bool randnum() { if(0 == (rand() % 2)) return true; return false;}// 新增节点bool add(node *sl[] , int data) { printf(新增节点: %d,data); int level = currlevel; node *head = null; node *tmp = null; node *last = null; // 初始化索引 数据为 head 地址 skipstep steps[maxlevel]; int i; for (i=0;i0; steps[i].node = sl[i]; node *ss = steps[i].node; } // 赛选无效层 head = sl[level]; tmp = head->next; while ((level > 0) && (data data)) { level--; head = sl[level]; tmp = head->next; } // 根据索引寻找head0数据节点 while ((level > 0)) { while (tmp != null) { if (data data) { steps[level].level = level; if (null != last) steps[level].node = last; tmp = last->down; level--; break; } last = tmp; tmp = tmp->next; } if (null == tmp) { steps[level].level = level; if (null != last) steps[level].node = last; tmp = last->down; level--; } } // head0 数据合适的节点 while (tmp != null) { if (data data) { break; } last = tmp; tmp = tmp->next; } // 新增节点 node *newdata = (node *)malloc(sizeof(node)); newdata->data = data; newdata->up = null; newdata->down = null; newdata->last = null; newdata->next = null; int k = 0; // head0 插入原始数据 if (null == last ) { // 头结点 head = sl[0]; node *headnext = head->next; if (null != headnext) { newdata->next = headnext; headnext->last = newdata; newdata->last = head; } head->next = newdata; newdata->last = head; } else if ( null == tmp) { // 尾节点 last->next = newdata; newdata->last = last; } else { // 中间节点 newdata->next = tmp; tmp->last = newdata; newdata->last = last; last->next = newdata; } // 构建索引 while (randnum()) { k++; if (k >= maxlevel) break; // 新增索引数据 node *newindex = (node *)malloc(sizeof(node)); newindex->data = data; newindex->up = null; newindex->down = null; newindex->next = null; newindex->last = null; // 建立上下级关系 newindex->down = newdata; newdata->up = newindex; node *node = steps[k].node; // node->next node *nextindex = node->next; node->next = newindex; newindex->last = node; newindex->next = nextindex; if (null != nextindex) nextindex->last = newindex; newdata = newindex; // 判断是否需要新增索引层数 if (k > currlevel) currlevel = k; }}// 初始化头结点node *initskiplist(node *skiplist[]) { int i; for (i=0;imalloc(sizeof(node)); if (null == newhead) { printf(%d 层 头结点申请失败); return null; } newhead->data = -1-i; newhead->down = null; newhead->up = null; newhead->next = null; newhead->last = null; skiplist[i] = newhead; } return skiplist;}// 打印跳表数据void printskiplist(node *sl[]) { if (null == sl) { return; }; int level = currlevel; //int level = maxlevel; int i; for (i=level;i>=0;i--) { node *head = sl[i]; node *tmp = head->next; printf(第%d层 ,i); while (null != tmp) { printf( %d ,tmp->data); tmp = tmp->next; } printf(); }}// 查询数据node *query(node *sl[] , int data) { printf(查询数据: %d,data); int level = currlevel; node *head = null; node *tmp = null; node *last = null; head = sl[level]; tmp = head->next; int endquery = -1; // 筛除无效层 while ((level > 0) && (data data)) { level--; endquery = tmp->data; head = sl[level]; tmp = head->next; } // 根据索引定位到head0层 while ((level > 0 )) { while (tmp != null) { if (data data)) { level--; endquery = tmp->data; tmp = last->down; break; } last = tmp; tmp = tmp->next; } if (null == tmp) { tmp = last->down; endquery = -1; level--; } } // 查询实际数据 while (null != tmp) { if (endquery != -1) if (tmp->data > endquery) { tmp = null; break; } if (tmp->data == data) { break; } tmp = tmp->next; } // 返回查询的数据节点，若没有查询到，应当返回null ,否则返回实际的地址 return tmp;}// 删除数据bool del(node *sl[],int data) { printf(删除数据: %d,data); // 找到节点地址 node *tmp = query(sl,data); if (null == tmp) { printf(未找到节点,删除失败); return false; } int level = 0; node *t_last = null; node *t_next = null; // 找到该数据最高索引 while (null != tmp->up) { level++; tmp = tmp->up; } // 由上至下删除索引/数据 while (tmp != null) { t_last = tmp->last; t_next = tmp->next; node *t_down = tmp->down; if (t_last == null) { printf(上一个节点不可能为空，删除失败,层数: %d,level); return false; } t_last->next = t_next; if (null != t_next) t_next->last = t_last; else t_last->next = null; if ((t_last == sl[level]) && (null == t_next)) { currlevel--; } free(tmp); tmp = t_down; level--; } return true;}int main() { node *sl[maxlevel]; node *skiplist = initskiplist(sl); if (null == sl) { printf(skiplist 申请失败); return -1; } // 测试新增 int num[] = {1,3,2,10,8,9,22,30,29,120,99,78,55,76,21}; int i; for (i=0;i 执行结果
带你了解设备振动监测常见术语
从电报到5G 从甚低频到太赫兹 带你深入：细数无线电频谱发展史
首批正式搭载钠电池的汽车来了！
失调电压与开环增益 他们是表亲戚关系
iQOO Neo5或将采用硬件级独立显示芯片
跳表概念以及跳表增删查规则
三极管和MOS管的异常现象与根本原因分析
贸泽电子祝贺董荷斌夺得亚洲勒芒系列赛冠军
哪个牌子的无线运动耳机好、运动达人力荐的六款运动耳机
VR体验系统能够提高体验者的消防意识与应急逃生能力
用友网络与软通动力共同助力客户数智化转型落地
动力电池未来发展形势仍有诸多变数
展锐助力中兴通讯发布5G工业模组ZM9010
罗德与施瓦茨2021 SAECCE完美收官
开启企业数字化转型新篇章，华为云 828 企业节来了
机器人智能化背后的力量：高可靠防水连接器承担无损高速传输
2022年BLDC市场行情分析及趋势
新推18W Type-c PD 3.0多协议快充充电器可提供更精准电压
从LCD电极读数的单片机接口技术分析
电池的内阻与容量，二者之间有着紧密的联系
实现的方法不唯一
1. 什么是跳表 跳表是 链表 + 索引 的一种数据结构 ，是以空间换取时间的方式，关于跳表参考: https://baike.baidu.com/item/跳表/22819833?fr=aladdin
2. 跳表概念 跳表在原有链表的基础上，增加索引，从而可以进行二分查找，提高搜寻效率。
原始链表
head ——> 1 ——> 8 ——> 12 ——> 23 ——> 55 ——> null 新增了索引的链表(跳表)
head2 ————————> 8 ———————————————————————> null head1 ————————> 8 —————————> 23 —————————> null head0 ——> 1 ——> 8 ——> 12 ——> 23 ——> 55 ——> null head0 , head1 , head2 上都是真实的节点，这就是以空间换取时间
例如算上head, 元素数据一共有 6 个，而添加索引后，元素一共有 11 个
3. 跳表增删查规则 3.1 跳表数据节点
数据节点可以和链表节点一致 ，也可以定义如下节点，除了数据外，有指针指向 前一个/后一个/上一个/下一个 节点，以便后续查找操作。
typedef struct { int data; struct node *next; // 后一个节点 struct node *last; // 前一个节点 struct node *up; // 上一个节点 struct node *down; // 下一个节点} node; 3.2 跳表初始化
当跳表有多少层的时候，应当建立多少个头结点，例如: 跳表为3层
head2 ——> nullhead1 ——> nullhead0 ——> null 3.3 查找 删除/新增 都会进行查询才操作，无非是删除/新增索引而已。
例如有如下数据
head2 —————————————————————> 23 —————————> null head1 ————————> 8 —————————> 23 —————————> null head0 ——> 1 ——> 8 ——> 12 ——> 23 ——> 55 ——> null 要查找 13这个节点
去除无效层
例如: head2 后面第一个节点的数据 23 ， 而 23 大于 13 , 所以 head2 没有数据匹配查询，故需要跳到下面一层，至 head1 上进行查询。
查询至head0层
去除无效层后数据进入了 head1 , 在head1上进行匹配，当匹配到 23 时，23大于13，将23标记为 查询结束点，对23的上一个节点 8 进行 向下指针操作，进入 head0层的8节点。
查找实际数据
从head0层的8 进行查找，直至 查询结束标记点(head1 23), 查询的数据分别为 8 ， 12 ，23 查询结束，未找到数据。
3.4 新增
新增操作需要记录索引寻址过程，以便后续新增索引。
头结点插入
头结点插入一定是 去除无效层 至head0 , 且 head0的第一个节点都比插入节点要大的情况下
例如:
如下跳表，插入 2
head2 —————————————————————> 23 —————————> null head1 ————————> 8 —————————> 23 —————————> null head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> null 尾结点插入
头结点插入一定是 去除无效层 至head0 , 且 head0的第一个节点都比插入节点要小，直至null节点的情况下
例如:
如下跳表，插入 65
head2 —————————————————————> 23 —————————> null head1 ————————> 8 —————————> 23 —————————> null head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> null 中间节点插入
除开以上2种情况，其余情况为 中间节点插入
新增索引
抛硬币的方法，当数据量达到一定规模的时候，一定是趋近于 50%的。
所以跳表会越来越趋向于如下形式
3 3 71 3 5 7 91 2 3 4 5 6 7 8 9 判断是否需要新增索引，采取抛硬币的方法来判断，即: 随机数 取余 为 0 则需要新增，否则不需要。
例如如下跳表，插入 65
head2 —————————————————————> 23 —————————> null head1 ————————> 8 —————————> 23 —————————> null head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> null 寻址应该为
head2: 23
head1: 23
元素数据插入后为
head2 —————————————————————> 23 ———————————————> null head1 ————————> 8 —————————> 23 ———————————————> null head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> 65 —> null 当插入65节点后，若判断需要索引的时候，则先为 head1 添加索引，添加位置为 寻址地址之后，寄 head1: 23
head2 —————————————————————> 23 ———————————————> null head1 ————————> 8 —————————> 23 —————————> 65 —> null head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> 65 —> null 继续判断，若不需要添加索引，则插入结束
若还需要添加索引，则继续上述操作，直至 索引层 达到最高层
3.5 删除
删除首先是查找操作【3.3 查找】
若未找到该节点，则删除失败
若找到了该节点，则应当提到该数据最高索引层，再从高到低删除
例如:
如下跳表，删除 23
head2 —————————————————————> 23 ———————————————> null head1 ————————> 8 —————————> 23 —————————> 65 —> null head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> 65 —> null 找到 head0 23 后，应该向上找到 head2 23 ,然后从高向低删除，若删除后，该索引没有数据了，则索引层减1
则删除head2 23 后数据如下
head1 ————————> 8 —————————> 23 —————————> 65 —> null head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> 65 —> null 删除head1 23 后数据如下
head1 ————————> 8 ———————————————————————> 65 —> null head0 ——> 3 ——> 8 ——> 12 ——> 23 ——> 55 ——> 65 —> null 删除head0 23后数据如下
head1 ————————> 8 ————————————————> 65 —> null head0 ——> 3 ——> 8 ——> 12 ——> 55 ——> 65 —> null 4. 代码 skiplist.c
# include # include # include int maxlevel = 8; // 最大层数int currlevel = 0; // 当前层数// 数据节点typedef struct { int data; struct node *next; struct node *last; struct node *up; struct node *down;} node;// 记录索引寻址过程typedef struct { int level; struct node *node;} skipstep;// 判断是否需要新增索引, 抛硬币bool randnum() { if(0 == (rand() % 2)) return true; return false;}// 新增节点bool add(node *sl[] , int data) { printf(新增节点: %d,data); int level = currlevel; node *head = null; node *tmp = null; node *last = null; // 初始化索引 数据为 head 地址 skipstep steps[maxlevel]; int i; for (i=0;i0; steps[i].node = sl[i]; node *ss = steps[i].node; } // 赛选无效层 head = sl[level]; tmp = head->next; while ((level > 0) && (data data)) { level--; head = sl[level]; tmp = head->next; } // 根据索引寻找head0数据节点 while ((level > 0)) { while (tmp != null) { if (data data) { steps[level].level = level; if (null != last) steps[level].node = last; tmp = last->down; level--; break; } last = tmp; tmp = tmp->next; } if (null == tmp) { steps[level].level = level; if (null != last) steps[level].node = last; tmp = last->down; level--; } } // head0 数据合适的节点 while (tmp != null) { if (data data) { break; } last = tmp; tmp = tmp->next; } // 新增节点 node *newdata = (node *)malloc(sizeof(node)); newdata->data = data; newdata->up = null; newdata->down = null; newdata->last = null; newdata->next = null; int k = 0; // head0 插入原始数据 if (null == last ) { // 头结点 head = sl[0]; node *headnext = head->next; if (null != headnext) { newdata->next = headnext; headnext->last = newdata; newdata->last = head; } head->next = newdata; newdata->last = head; } else if ( null == tmp) { // 尾节点 last->next = newdata; newdata->last = last; } else { // 中间节点 newdata->next = tmp; tmp->last = newdata; newdata->last = last; last->next = newdata; } // 构建索引 while (randnum()) { k++; if (k >= maxlevel) break; // 新增索引数据 node *newindex = (node *)malloc(sizeof(node)); newindex->data = data; newindex->up = null; newindex->down = null; newindex->next = null; newindex->last = null; // 建立上下级关系 newindex->down = newdata; newdata->up = newindex; node *node = steps[k].node; // node->next node *nextindex = node->next; node->next = newindex; newindex->last = node; newindex->next = nextindex; if (null != nextindex) nextindex->last = newindex; newdata = newindex; // 判断是否需要新增索引层数 if (k > currlevel) currlevel = k; }}// 初始化头结点node *initskiplist(node *skiplist[]) { int i; for (i=0;imalloc(sizeof(node)); if (null == newhead) { printf(%d 层 头结点申请失败); return null; } newhead->data = -1-i; newhead->down = null; newhead->up = null; newhead->next = null; newhead->last = null; skiplist[i] = newhead; } return skiplist;}// 打印跳表数据void printskiplist(node *sl[]) { if (null == sl) { return; }; int level = currlevel; //int level = maxlevel; int i; for (i=level;i>=0;i--) { node *head = sl[i]; node *tmp = head->next; printf(第%d层 ,i); while (null != tmp) { printf( %d ,tmp->data); tmp = tmp->next; } printf(); }}// 查询数据node *query(node *sl[] , int data) { printf(查询数据: %d,data); int level = currlevel; node *head = null; node *tmp = null; node *last = null; head = sl[level]; tmp = head->next; int endquery = -1; // 筛除无效层 while ((level > 0) && (data data)) { level--; endquery = tmp->data; head = sl[level]; tmp = head->next; } // 根据索引定位到head0层 while ((level > 0 )) { while (tmp != null) { if (data data)) { level--; endquery = tmp->data; tmp = last->down; break; } last = tmp; tmp = tmp->next; } if (null == tmp) { tmp = last->down; endquery = -1; level--; } } // 查询实际数据 while (null != tmp) { if (endquery != -1) if (tmp->data > endquery) { tmp = null; break; } if (tmp->data == data) { break; } tmp = tmp->next; } // 返回查询的数据节点，若没有查询到，应当返回null ,否则返回实际的地址 return tmp;}// 删除数据bool del(node *sl[],int data) { printf(删除数据: %d,data); // 找到节点地址 node *tmp = query(sl,data); if (null == tmp) { printf(未找到节点,删除失败); return false; } int level = 0; node *t_last = null; node *t_next = null; // 找到该数据最高索引 while (null != tmp->up) { level++; tmp = tmp->up; } // 由上至下删除索引/数据 while (tmp != null) { t_last = tmp->last; t_next = tmp->next; node *t_down = tmp->down; if (t_last == null) { printf(上一个节点不可能为空，删除失败,层数: %d,level); return false; } t_last->next = t_next; if (null != t_next) t_next->last = t_last; else t_last->next = null; if ((t_last == sl[level]) && (null == t_next)) { currlevel--; } free(tmp); tmp = t_down; level--; } return true;}int main() { node *sl[maxlevel]; node *skiplist = initskiplist(sl); if (null == sl) { printf(skiplist 申请失败); return -1; } // 测试新增 int num[] = {1,3,2,10,8,9,22,30,29,120,99,78,55,76,21}; int i; for (i=0;i
带你了解设备振动监测常见术语
从电报到5G 从甚低频到太赫兹 带你深入：细数无线电频谱发展史
首批正式搭载钠电池的汽车来了！
失调电压与开环增益 他们是表亲戚关系
iQOO Neo5或将采用硬件级独立显示芯片
跳表概念以及跳表增删查规则
三极管和MOS管的异常现象与根本原因分析
贸泽电子祝贺董荷斌夺得亚洲勒芒系列赛冠军
哪个牌子的无线运动耳机好、运动达人力荐的六款运动耳机
VR体验系统能够提高体验者的消防意识与应急逃生能力
用友网络与软通动力共同助力客户数智化转型落地
动力电池未来发展形势仍有诸多变数
展锐助力中兴通讯发布5G工业模组ZM9010
罗德与施瓦茨2021 SAECCE完美收官
开启企业数字化转型新篇章，华为云 828 企业节来了
机器人智能化背后的力量：高可靠防水连接器承担无损高速传输
2022年BLDC市场行情分析及趋势
新推18W Type-c PD 3.0多协议快充充电器可提供更精准电压
从LCD电极读数的单片机接口技术分析
电池的内阻与容量，二者之间有着紧密的联系