一、跳表数据结构

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

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

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

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

二、跳表代码实现

1、跳表结构、操作函数声明
#ifndef SKIPLINKLIST_H__#define SKIPLINKLIST_H__#include #include #include #include #include #include #define MAX_LEVEL 8//定义数据域typedefint SkipLinkListData;typedefstruct skiplinklistnode{intlevel;SkipLinkListDatadata;struct skiplinklistnode*next;struct skiplinklistnode*down;} SkipLinkListNode;/** * 创建链表节点*/SkipLinkListNode* create_skiplinklist_node(SkipLinkListData data,int level);/** * 插入节点*/voidinsert_skiplinklist_node(SkipLinkListNode* head,SkipLinkListData data);/** * 维护索引*/void create_skiplinklist_index(SkipLinkListNode** index,SkipLinkListNode* node);/** * 随机数投硬币获取索引层高*/int random_skiplinklistnode_level();/** * 遍历跳表*/voidshow_skiplinglistnode_all(SkipLinkListNode* head);/** * 查询节点*/SkipLinkListNode*search_skiplinklistnode(SkipLinkListNode* head,SkipLinkListData data);/** * 删除跳表元素 重组索引s * 删除的过程其实也是查找*/voiddelete_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 nodefail");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->levellevel +1;}SkipLinkListNode* index_node = NULL; /// 当前层级小于随机高度时候，需要升级索引if(down_ptr->levellevel +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->datalevel>0){SkipLinkListNode* next_ptr= down_ptr->next;// 查找当前层级索引，定位到离当前数值的最大索引值while (next_ptr != NULL && next_ptr->datanext!=NULL){ next_ptr = next_ptr->next;}/// 维护索引if(down_ptr->levellevel);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" />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->datalevel>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->datanext!=NULL&& next_ptr->next->datanext; 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 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 next != NULL && next_ptr->next->data 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");}

三、跳表测试

voidtest_skiplinklist(){ SkipLinkListNode*head = create_skiplinklist_node(0,0); SkipLinkListDatai; 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); }