跳表（查找，插入，删除）的实现

跳表（查找，插入，删除）的实现

引用

CSDN

1.

https://blog.csdn.net/2301_80698540/article/details/139512842

跳表

1. 跳表的基本概念
   跳表全称为跳跃列表，它允许快速查询，插入和删除一个有序连续元素的数据链表。跳跃列表的平均查找和插入时间复杂度都是O(logn)。快速查询是通过维护一个多层次的链表，且每一层链表中的元素是前一层链表元素的子集。一开始时，算法在最稀疏的层次进行搜索，直至需要查找的元素在该层两个相邻的元素中间。这时，算法将跳转到下一个层次，重复刚才的搜索，直到找到需要查找的元素为止。
   1.1跳表的查询类似于二分查找，如下图示例
   
   在一个有序数组中，若我们想使用二分法去查找20这个元素，则我们需要找到中间这个值，然后与12比较大小，大的则在右边查找即可，小的在左边查找即可，很明显我们需要在右边查找20这个数，刚好找到了20这个，如果数组的长度为N，那么时间的复杂度则为O(logN)空间复杂度为O(1)。
   但是如果是一个有序链表的话，我们就不能使用二分法来查找，因为链表不支持随机访问，所以这时我们就需要用到跳表这个概念来解决这个问题。
   首先我们需要进行第一次索引，在每两个节点提取一个节点到上一级，得到第一个索引层
   
   这样在第一层的位置进行遍历我们就可以找到220这个数，但是还有一个更简单的方法，那就是再建立一层索引，如下图。
   这样我们的索引的元素就更少了，我们仅需要找到第二层中仅小于20的元素12，然后顺着12访问它的下一层也就是第一层，在这一层找到20这个元素，然后顺着20这个元素找到原始链表中的数，即是我们需要查找的数。这样我们的时间复杂度也变为了O(logN)。
   如果某一个节点有上层节点的话，则我们需要向上走，整个过程类似于楼梯的形状，每个节点第一被访问一定是位于最顶层
   *如果节点x有第i+1，那么我们需要向上走，这种概率为p。
   *如果节点没有第i+1层指针，那么我们需要向左走，这种概率为1-p。
   1.2 跳表的插入
   加入我们要插入一个10的元素，则我们需要先找到仅此于小于10的元素，也就是9。
   
   然后从最高层开始查找到仅次小于10的元素，并将10插入其中
   1.3 跳表的删除
   首先我们需要先判断当前节点是否存在，只有存在才能删除，然后找到前驱节点，删除节点和单链表的删除类似。假设我们要删除12，则我们需要从顶层开始查找，发现12就在顶层然后删除12，顺着12找到下一层把第一层的12也删除，最后删除原始链表中的12。
   
   这样我们就完成了删除操作。
   相关代码如下

#include<stdio.h>  
#include<stdlib.h>  
#include<time.h>  
#defineMAX_LEVEL6  
typedefstructSkipListNode{  
intkey;  
intvalue;  
structSkipListNode** forward;  
}SkipListNode;  
typedefstructSkipList{  
intmax_level;  
intlevel;  
SkipListNode* header;  
}SkipList;  
SkipListNode* skipListNodeInit(intlevel,intkey,intvalue) { //接受节点的层数level、键值key和值value作为参数，并动态分配内存来创建节点；  
SkipListNode* node = (SkipListNode*)malloc(sizeof(SkipListNode));  
node->key =key;  
node->value =value; // //将节点的键值和值设置为参数的值；  
node->forward = (SkipListNode**)malloc((level+ 1) *sizeof(SkipListNode*)); //为指针数组forward分配足够的内存；  
for(inti = 0; i <=level; i++) {  
node->forward[i] =NULL; //将指针数组中的所有元素初始化为NULL  
}  
returnnode; //返回创建的节点。  
}  
SkipList* skipListInit() { //初始化跳表  
SkipList* skipList = (SkipList*)malloc(sizeof(SkipList)); //动态分配内存来创建一个SkipList结构体  
skipList->max_level =MAX_LEVEL; //设置最大层数max_level为预定义的常量值MAX_LEVEL  
skipList->level = 0; //设置当前层数level为0  
skipList->header = skipListNodeInit(MAX_LEVEL, 0, 0); //调用上述skipListNodeInit函数创建一个头节点。  
for(inti = 0; i <=MAX_LEVEL; i++) {  
skipList->header->forward[i] =NULL; //将头节点的指针数组中的所有元素初始化为NULL  
}  
returnskipList; //返回创建的跳表。  
}  
intrandomLevel() {  
intlevel = 1;  
while(rand() <RAND_MAX/ 2 && level <MAX_LEVEL) {  
level++;  
}  
returnlevel;  
}  
voidskipListInsert(SkipList*skipList,intkey,intvalue) { //节点插入  
SkipListNode* update[MAX_LEVEL+ 1]; //创建一个更新数组update  
SkipListNode* current =skipList->header;  
for(inti =skipList->level; i >= 0; i--) {  
while(current->forward[i] !=NULL&& current->forward[i]->key <key) {  
current = current->forward[i];  
}  
update[i] = current;  
}  
current = current->forward[0];  
if(current !=NULL&& current->key ==key) { //如果新节点的层级大于当前跳表的层级  
current->value =value;  
}else{  
intnew_level = randomLevel();  
if(new_level >skipList->level) {  
for(inti =skipList->level + 1; i <= new_level; i++) {  
update[i] =skipList->header;  
}  
skipList->level = new_level; //更新对应层级的前进节点数组  
}  
SkipListNode* new_node = skipListNodeInit(new_level,key,value);  
for(inti = 0; i <= new_level; i++) {  
new_node->forward[i] = update[i]->forward[i];  
update[i]->forward[i] = new_node; //将新节点插入到跳表中  
}  
}  
}  
voidskipListDelete(SkipList*skipList,intkey) { //创建一个更新数组update  
SkipListNode* update[MAX_LEVEL+ 1];  
SkipListNode* current =skipList->header;  
for(inti =skipList->level; i >= 0; i--) {  
while(current->forward[i] !=NULL&& current->forward[i]->key <key) {  
current = current->forward[i];  
}  
update[i] = current;  
}  
current = current->forward[0];  
if(current !=NULL&& current->key ==key) {  
for(inti = 0; i <=skipList->level; i++) {  
if(update[i]->forward[i] != current) {  
break;  
}  
update[i]->forward[i] = current->forward[i];  
}  
free(current); //释放要删除的节点的内存。  
while(skipList->level > 0 &&skipList->header->forward[skipList->level] ==NULL) {  
skipList->level--;  
}  
}  
}  
SkipListNode* skipListSearch(SkipList*skipList,intkey) { //节点查找  
SkipListNode* current =skipList->header;  
for(inti =skipList->level; i >= 0; i--) {  
while(current->forward[i] !=NULL&& current->forward[i]->key <key) {  
current = current->forward[i];  
}  
}  
current = current->forward[0];  
if(current !=NULL&& current->key ==key) {  
returncurrent;  
}else{  
returnNULL;  
}  
}  
intmain() {  
srand(time(NULL)); //调用srand函数设置随机数种子  
SkipList* skipList = skipListInit(); //通过调用skipListInit函数初始化一个跳表  
skipListInsert(skipList, 3, 30); //使用skipListInsert函数插入一系列键值对  
skipListInsert(skipList, 1, 10);  
skipListInsert(skipList, 2, 20);  
skipListInsert(skipList, 4, 40);  
skipListInsert(skipList, 6, 60);  
skipListInsert(skipList, 5, 50);  
skipListInsert(skipList, 7, 70);  
SkipListNode* node = skipListSearch(skipList, 4); //使用skipListSearch函数搜索具有键值为4的节点，并打印出节点的键值和值。  
if(node !=NULL) {  
printf("Key: %d, Value: %d\n", node->key, node->value);  
}else{  
printf("Key not found.\n");  
}  
skipListDelete(skipList, 4); //使用skipListDelete函数删除具有键值为4的节点。  
node = skipListSearch(skipList, 4); //再次使用skipListSearch函数搜索具有键值为4的节点  
if(node !=NULL) {  
printf("Key: %d, Value: %d\n", node->key, node->value);  
}else{  
printf("Key not found.\n");  
}  
return0;  
}