1. 什么是跳跃表
在解释这个之前，首先要看看 链表 和 数组 的区别
1.1 数组
用一组地址连续的存储单元以此存储线性表的数据元素，所以可以通过下标来获取
在申明数组的时候，需要指定大小
例如: int nums[5] = {9,12,15,21,35};
例如如下所示
对于有序数组而言，查找可以进行二分查找，提高查找效率。
若要对数组进行增加/删除等操作，会引发问题，例如，增加一个 16
这意味着，15以后的元素，都需要往后移位，才能插入这个元素，非常麻烦，而链表能够规避数组这一点。
1.2 链表
链表节点由2部分组成，即: 数据域和指针域，所以数据元素之间的逻辑关系是由节点中的指针来指示的。
同样存储 9,12,15,21,35 ，存储如下
由于节点的逻辑关系由节点中的指针来完成的，所以添加/删除节点非常方便(就不画了)，但是没办法通过下标来定位节点，所以没办法做二分查询。
1.3 数组和链表的区别
1、 数组需要在使用前提前规划长度，而链表不用
2、 数组开辟的是连续内存地址空间，而链表是随机申请空间
3、 数组寻址方式是靠下标，而链表是靠节点指针
1.3 跳跃表
所有的索引，都是真实实际的节点
跳表是 链表 + 索引 的一种数据结构 ，是以空间换取时间的方式，可以对链表进行类似二分查找操作。
同样存储 9,12,15,21,35 ，跳跃表存储可能如下
在链表中要查询 15 这个节点
那么会遍历 9——12——15
在跳表中查询15这个节点
那么会遍历 12——15
当链表数据被无限拉大时，查询效果会逐渐提现出来
2. 如何构建跳跃表
跳表比较好理解，但是实际用代码来表示，还是有点复杂的。
实现的方法不唯一
1、 跳跃表的最大层数应当被提前定义
2、 应当提前构建出跳跃表的头结点
2.1 如何判断是否要建立索引
采用抛硬币的方式，建立一个随机函数，随机返回 true 或者 false
当一个数据节点被插入后，应当调用该随机函数，若 结果为 false 或者达到 跳表最大层数 则停止，否则应当在该层建立索引
2.2 新增节点
跳表需要新增有序的数据节点，否则不能进行索引查询
新增节点逻辑
- 找到当前跳跃表最高有效层
- 进行索引逻辑判断，至最底层元素数据层(节点寻址路线需要记住)
- 进行节点插入
- 建立索引
假设有如下跳表:
新增节点 13
建立索引
建设建立随机函数结果一直未 true
删除/查找 逻辑类似
3. 如何构建跳跃表
跳跃表插入
1、 初始化所有层的Head节点
2、 在插入的时候，找到原始数据层，插入完毕后，进行向上建立索引
跳跃表查找
1、 找到目前有效索引最高层
2、 进行索引判断，定位到原始数据层
3、 依序查找
跳跃表删除
1、 按照查找 找到原始数据层
2、 删除原始数据，并且判断该值是否有索引，若没有，则删除完毕，若有则删除索引
代码
# include <stdio.h> # include <stdlib.h> # include <stdbool.h> int MaxLevel = 8; // 最大层数 int currLevel = 0; // 当前层数 // 数据节点 typedef struct node { 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\n",data); int level = currLevel; Node *Head = NULL; Node *tmp = NULL; Node *last = NULL; // 初始化索引 数据为 Head 地址 skipStep steps[MaxLevel]; int i; for (i=0;i<MaxLevel;i++) { steps[i].level = 0; steps[i].node = SL[i]; Node *ss = steps[i].node; } // 赛选无效层 Head = SL[level]; tmp = Head->next; while ((level > 0) && (data < tmp->data)) { level--; Head = SL[level]; tmp = Head->next; } // 根据索引寻找Head0数据节点 while ((level > 0)) { while (tmp != NULL) { if (data < tmp->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 < tmp->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;i<MaxLevel;i++) { Node *newHead = (Node *)malloc(sizeof(Node)); if (NULL == newHead) { printf("%d 层 头结点申请失败\n",i); 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层\t\t",i); while (NULL != tmp) { printf(" %d\t",tmp->data); tmp = tmp->next; } printf("\n"); } } // 查询数据 Node *query(Node *SL[] , int data) { printf("查询数据: %d\n",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 < tmp->data)) { level--; endQuery = tmp->data; Head = SL[level]; tmp = Head->next; } // 根据索引定位到Head0层 while ((level > 0 )) { while (tmp != NULL) { if (data < (tmp->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\n",data); // 找到节点地址 Node *tmp = query(SL,data); if (NULL == tmp) { printf("未找到节点,删除失败\n"); 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\n",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 申请失败\n"); return -1; } // 测试新增 int num[] = {9,13,11,21,31,45,66,99,101,103,106,8}; int i; for (i=0;i<sizeof(num)/sizeof(int);i++) { // bool add(Node *SL[] , int data) { add(SL,num[i]); } printf("打印节点\n"); PrintSkipList(SL); printf("\n"); // 测试删除 int delNum[] = {99,21,11,32}; for (i=0;i<sizeof(delNum)/sizeof(int);i++) { del(SL,delNum[i]); } printf("打印节点\n"); PrintSkipList(SL); printf("\n"); return 0; }
执行结果
# gcc skipList.c # ./a.out 新增节点: 9 新增节点: 13 新增节点: 11 新增节点: 21 新增节点: 31 新增节点: 45 新增节点: 66 新增节点: 99 新增节点: 101 新增节点: 103 新增节点: 106 新增节点: 8 打印节点 第5层 106 第4层 106 第3层 106 第2层 45 106 第1层 8 13 45 99 101 106 第0层 8 9 11 13 21 31 45 66 99 101 103 106 删除数据: 99 查询数据: 99 删除数据: 21 查询数据: 21 删除数据: 11 查询数据: 11 删除数据: 32 查询数据: 32 未找到节点,删除失败 打印节点 第5层 106 第4层 106 第3层 106 第2层 45 106 第1层 8 13 45 101 106 第0层 8 9 13 31 45 66 101 103 106 #
