跳表是 链表 + 索引 的一种数据结构 ，是以空间换取时间的方式，关于跳表参考: https://baike.baidu.com/item/跳表/22819833?fr=aladdin,跳表在原有链表的基础上，增加索引，从而可以进行二分查找，提高搜寻效率。,原始链表,新增了索引的链表(跳表),Head0 , Head1 , Head2 上都是真实的节点，这就是以空间换取时间,例如算上Head, 元素数据一共有 6 个，而添加索引后，元素一共有 11 个,3.1 跳表数据节点,数据节点可以和链表节点一致 ，也可以定义如下节点，除了数据外，有指针指向 前一个/后一个/上一个/下一个 节点，以便后续查找操作。,3.2 跳表初始化,当跳表有多少层的时候，应当建立多少个头结点，例如: 跳表为3层,例如有如下数据,要查找 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,尾结点插入,头结点插入一定是 去除无效层 至Head0 , 且 Head0的第一个节点都比插入节点要小，直至NULL节点的情况下,例如:,如下跳表，插入 65,中间节点插入,除开以上2种情况，其余情况为 中间节点插入,新增索引,所以跳表会越来越趋向于如下形式,判断是否需要新增索引，采取抛硬币的方法来判断，即: 随机数 取余 为 0 则需要新增，否则不需要。,例如如下跳表，插入 65,寻址应该为
Head2: 23
Head1: 23,元素数据插入后为,当插入65节点后，若判断需要索引的时候，则先为 Head1 添加索引，添加位置为 寻址地址之后，寄 Head1: 23,继续判断，若不需要添加索引，则插入结束,若还需要添加索引，则继续上述操作，直至 索引层 达到最高层,3.5 删除,删除首先是查找操作【3.3 查找】,若未找到该节点，则删除失败,若找到了该节点，则应当提到该数据最高索引层，再从高到低删除,例如:,如下跳表，删除 23,找到 Head0 23 后，应该向上找到 Head2 23 ,然后从高向低删除，若删除后，该索引没有数据了，则索引层减1,则删除Head2 23 后数据如下,删除Head1 23 后数据如下,删除Head0 23后数据如下,skipList.c,执行结果
© 版权声明
文章版权归作者所有，未经允许请勿转载。
