跳跃表原理及实现

一、跳表数据结构

         跳表是有序表的一种，其底层是通过链表实现的。链表的特点是插入删除效率高，但是查找节点效率很低，最坏的时间复杂度是O(N)，那么跳表就是解决这一痛点而生的。

        为了提高查询效率，我们可以给链表加上索引，利用二分查找的思路，每两个节点抽取一个索引，根据数据规模，提升索引的高度，索引的最高层级为logN,那么跳跃表支持平均0 (1ogN)，这样可以快读提高节点访问速度。由于在原始链表的基础上加索引，这些索引需要额外的存储空间，所以这是典型的通过空间换时间。下图简单描述跳跃表原理：

           如果要访问8这个歌节点元素，在没有索引的情况下，需要遍历链表8次才能找到目标节点，但是通过跳表访问(1 -> 5 -> 7-> 7->7 -> 8) ,只需要访问6次，数据规模越大优势越明显。

          对于提取索引，理论上每隔两个元素生成一个索引节点，但是在具体情况下，链表是动态的，删除和增加节点的时机很难确定，通过两个节点维护索引的方式开销成本很大。那么如何添加索引，一个新增节点要不要加索引，索引加到第几层，为了解决这个问题，可以通过投掷硬币的方式（随机数模2），连续投掷正面几次，那么这个次数就是索引的层级。

二、跳表代码实现

  1、跳表结构、操作函数声明

#ifndef SKIPLINKLIST_H__
#define SKIPLINKLIST_H__#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#include <math.h>
#include <unistd.h>#define MAX_LEVEL 8//定义数据域
typedef  int SkipLinkListData;typedef  struct skiplinklistnode
{int  level;SkipLinkListData  data;struct skiplinklistnode*  next;struct skiplinklistnode*  down;} SkipLinkListNode;/*** 创建链表节点
*/
SkipLinkListNode* create_skiplinklist_node(SkipLinkListData data,int level);/*** 插入节点
*/
void  insert_skiplinklist_node(SkipLinkListNode* head,SkipLinkListData data);/*** 维护索引
*/
void create_skiplinklist_index(SkipLinkListNode** index,SkipLinkListNode* node);/*** 随机数投硬币获取索引层高
*/
int   random_skiplinklistnode_level();/*** 遍历跳表
*/
void  show_skiplinglistnode_all(SkipLinkListNode* head);/*** 查询节点
*/
SkipLinkListNode*  search_skiplinklistnode(SkipLinkListNode* head,SkipLinkListData data);/*** 删除跳表元素 重组索引  s* 删除的过程其实也是查找
*/
void    delete_skiplinklistnode(SkipLinkListNode* head,SkipLinkListData data);#endif

2、跳表增删查操作定义

#include "./skiplinklist.h"SkipLinkListNode* create_skiplinklist_node(SkipLinkListData data,int level){SkipLinkListNode*  node = (SkipLinkListNode*) malloc(sizeof(SkipLinkListNode));if(node==NULL){perror("create node  fail");return NULL;}node->level = level;node->data =  data;node->next = NULL;node->down = NULL;return node;
}void insert_skiplinklist_node(SkipLinkListNode *head, SkipLinkListData data)
{SkipLinkListNode *down_ptr = head->down;if (down_ptr == NULL){head->down =  create_skiplinklist_node(data, 0);return;}int level = random_skiplinklistnode_level(); if(down_ptr->level<level){level = down_ptr->level +1;}SkipLinkListNode* index_node = NULL;/// 当前层级小于随机高度时候，需要升级索引if(down_ptr->level<level){/// 向上升级一层索引level = down_ptr->level +1;SkipLinkListNode* down_node = create_skiplinklist_node(down_ptr->data,level);index_node = create_skiplinklist_node(data,level);down_node->next = index_node;down_node->down = down_ptr;head->down = down_node;} /// 搜索节点while (down_ptr!= NULL && down_ptr->data<=data && down_ptr->level>0){SkipLinkListNode* next_ptr  = down_ptr->next;// 查找当前层级索引，定位到离当前数值的最大索引值while (next_ptr != NULL && next_ptr->data<=data && next_ptr->next!=NULL){next_ptr = next_ptr->next;}/// 维护索引if(down_ptr->level<=level){SkipLinkListNode* new_node = create_skiplinklist_node(data, down_ptr->level);if(next_ptr==NULL){/// 如果当前层索引到达最后一个值，则跳到下一层索引down_ptr->next=new_node;}else{new_node->next = next_ptr->next;next_ptr->next = new_node; }create_skiplinklist_index(&index_node,new_node);}///跳转下一层索引down_ptr = next_ptr != NULL?next_ptr->down:down_ptr->down;    }/// 遍历链表  数据插入链表while (down_ptr != NULL&&down_ptr->next!=NULL&&down_ptr->next->data<data){down_ptr = down_ptr->next;}SkipLinkListNode*  node = create_skiplinklist_node(data, 0);SkipLinkListNode*  next_node = down_ptr->next;down_ptr->next = node;node->next = next_node;if(index_node!=NULL){create_skiplinklist_index(&index_node,node);}
}void create_skiplinklist_index(SkipLinkListNode** index_node,SkipLinkListNode* new_node)
{if ((*index_node) == NULL){(*index_node) = new_node;}else{SkipLinkListNode* tmp_node = (*index_node);while (tmp_node != NULL){if (tmp_node->down == NULL){tmp_node->down = new_node;break;}tmp_node = tmp_node->down;}}
}int  random_skiplinklistnode_level()
{int level = 0;int mod = 2;while (rand() % mod == 0 ){level++;}return level>=MAX_LEVEL?MAX_LEVEL:level;
}void  show_skiplinglistnode_all(SkipLinkListNode* head)
{SkipLinkListNode*  down_ptr = head->down;while (down_ptr!=NULL){if(down_ptr->level==0){printf("原 始链表: %d ",down_ptr->data);}else{printf("第%d层索引: %d ",down_ptr->level,down_ptr->data);}SkipLinkListNode*  next_ptr = down_ptr->next;while (next_ptr!=NULL){printf("%d ",next_ptr->data);next_ptr = next_ptr->next;}down_ptr= down_ptr->down; printf("\n");}printf("\n");
}SkipLinkListNode*  search_skiplinklistnode(SkipLinkListNode* head,SkipLinkListData data)
{SkipLinkListNode* down_ptr =  head->down;/// 索引查找while (down_ptr!=NULL && down_ptr->data<=data && down_ptr->level>0){printf("遍历第%d层次节点:%d\n",down_ptr->level,down_ptr->data);if(down_ptr->next!=NULL && down_ptr->next->data>data){down_ptr = down_ptr->down;continue;}SkipLinkListNode* next_ptr  = down_ptr->next;while (next_ptr != NULL && next_ptr->data<=data && next_ptr->next!=NULL&& next_ptr->next->data<=data){next_ptr = next_ptr->next;printf("遍历第%d层次节点:%d\n",next_ptr->level,next_ptr->data);}///跳转下一层索引down_ptr = next_ptr != NULL?next_ptr->down:down_ptr->down;   }//到达底层链表 遍历目标值while (down_ptr!=NULL){if(down_ptr->data==data){printf("遍历第%d层次节点,命中目标%d\n",down_ptr->level,down_ptr->data);return down_ptr;}down_ptr =  down_ptr->next;}printf("遍历结束目标节点%d不存在\n",data);printf("\n");return NULL;
}void delete_skiplinklistnode(SkipLinkListNode *head, SkipLinkListData data)
{printf("删除元素开始\n");SkipLinkListNode *down_ptr = head->down;while (down_ptr != NULL && down_ptr->data < data && down_ptr->level > 0){printf("遍历第%d层次节点:%d\n", down_ptr->level, down_ptr->data);if (down_ptr->next != NULL && down_ptr->next->data>=data){/// 处理要删除的节点存在索引节点if(down_ptr->next->data==data){SkipLinkListNode* index_ptr = down_ptr->next;down_ptr->next = down_ptr->next->next;printf("删除第%d层索引%d\n",index_ptr->level,index_ptr->data);free(index_ptr);}down_ptr = down_ptr->down;continue;}SkipLinkListNode *next_ptr = down_ptr->next;while (next_ptr != NULL && next_ptr->data < data && next_ptr->next != NULL && next_ptr->next->data <= data){if(next_ptr->next->data==data){SkipLinkListNode*  index_node= next_ptr->next;next_ptr->next = next_ptr->next->next;free(index_node);continue;}next_ptr = next_ptr->next;printf("遍历第%d层次节点:%d\n", next_ptr->level, next_ptr->data);}/// 跳转下一层索引down_ptr = next_ptr != NULL ? next_ptr->down : down_ptr->down;}while (down_ptr!=NULL){if(down_ptr->next!=NULL && down_ptr->next->data==data){SkipLinkListNode* traget_node =  down_ptr->next;down_ptr->next =  down_ptr->next->next;free(traget_node);}down_ptr=down_ptr->next;}printf("删除元素结束\n");}

三、跳表测试

void  test_skiplinklist()
{SkipLinkListNode*  head = create_skiplinklist_node(0,0);SkipLinkListData  i;int c = 30;for(i=1;i<c;i++){insert_skiplinklist_node(head,i);   }show_skiplinglistnode_all(head);search_skiplinklistnode(head,28);delete_skiplinklistnode(head,15);show_skiplinglistnode_all(head);}