在数据结构算法中，有一种算法犹如“时空穿梭机”，能在瞬间跨越层层障碍，直击目标——它就是跳表算法。下面，就让我们一起揭开跳表算法的神秘面纱，通过实例探究其高效与魅力。
目录
一、跳表算法是什么？
二、实例解析
1、跳表的构建
2、查找过程
三、跳表算法的优点
四、跳表——C语言实现
1、常规链表查找
2、跳表查找
一、跳表算法是什么？
跳表，顾名思义，是一种能够“跳过”某些节点进行搜索的链表。它通过再链表的基础上增加多级索引，实现了对数据的快速定位、插入与删除。想象一下，再一条长长的队伍中，你能直接跳到接近目标的位置，是不是能缩短搜索该目标的时间，从而大大提高代码运行效率。
二、实例解析
假设有一个有序的链表，存储了数字1到10。现在，需要查找数字7.在没有跳表的情况下，可能需要从头开始，一步步遍历到7。但是有了跳表，一切都将变得不同。
1、跳表的构建
首先，要为这个链表构建一个跳表。跳表分为多层，每一层都是下面一层的部分节点建立的索引。比如：
层3：4，8
层2：2，4，6，8，10
层1：1，2，3，4，5，6，7，8，9，10
2、查找过程
现在，开始查找数据7：
从层3开始查找，首先比较4和7。由于4比7小，就继续向右查找，直至比较到8，仍未找到7，于是便下降到层2。
在层2比较6和7。6仍然小于7，但接近查找目标。继续向右查找，发现8大于7，于是再次下降一层，到达层1。
在层1，直接定位到6，便可轻松查找到值7。
通过这个实例可以看到，跳表通过多级索引，实现了对数据的快速定位，大大减少了查找的时间复杂度。但代价是占用更多的空间。典型的空间换时间。
三、跳表算法的优点
高效性：跳表的查找、插入和删除操作的平均时间复杂度都是O(log n)，媲美平衡树结构。
简单性：相对于红黑树等复杂的数据结构，跳表的实现更为简单，易于理解和维护。
随机性：跳表的随机性保证了其性能的稳定性，避免了极端情况下的性能下降。
四、跳表——C语言实现
1、常规链表查找
#include <stdio.h>
#include <stdlib.h>// 跳表节点定义
typedef struct SkipListNode {int value;struct SkipListNode *next;struct SkipListNode *skip;
} SkipListNode;// 创建跳表节点
SkipListNode* createSkipListNode(int value) {SkipListNode* node = (SkipListNode*)malloc(sizeof(SkipListNode));node->value = value;node->next = NULL;node->skip = NULL;return node;
}// 插入节点到跳表
void insertSkipList(SkipListNode** head, int value) {SkipListNode* newNode = createSkipListNode(value);if (*head == NULL) {*head = newNode;return;}SkipListNode* current = *head;SkipListNode* skipPrev = NULL;// 寻找插入位置while (current != NULL && current->value < value) {skipPrev = current;current = current->next;}// 插入节点newNode->next = current;if (skipPrev != NULL) {skipPrev->next = newNode;} else {*head = newNode;}// 更新跳过指针if (skipPrev != NULL && skipPrev->skip != NULL && skipPrev->skip->value < value) {newNode->skip = skipPrev->skip->next;skipPrev->skip->next = newNode;}
}// 查找节点
SkipListNode* findSkipList(SkipListNode* head, int value) {SkipListNode* current = head;while (current != NULL) {if (current->value == value) {return current;} else if (current->skip != NULL && current->skip->value <= value) {current = current->skip;} else {current = current->next;}}return NULL;
}// 打印跳表
void printSkipList(SkipListNode* head) {SkipListNode* current = head;while (current != NULL) {printf("%d ", current->value);if (current->skip != NULL) {printf("(skip to %d) ", current->skip->value);}current = current->next;}printf("\n");
}// 主函数
int main() {SkipListNode* head = NULL;// 插入数据insertSkipList(&head, 3);insertSkipList(&head, 7);insertSkipList(&head, 6);insertSkipList(&head, 9);insertSkipList(&head, 12);insertSkipList(&head, 19);insertSkipList(&head, 25);insertSkipList(&head, 30);// 打印跳表printf("Skip List: ");printSkipList(head);// 查找数据int valueToFind = 19;SkipListNode* foundNode = findSkipList(head, valueToFind);if (foundNode != NULL) {printf("Value %d found in the skip list.\n", valueToFind);} else {printf("Value %d not found in the skip list.\n", valueToFind);}return 0;
}
2、跳表查找
#include <stdio.h>
#include <stdlib.h>
#include <time.h>#define MAXLEVEL 3 // 假设跳表的最大层级为3// 跳表节点定义
typedef struct SkipListNode {int value;struct SkipListNode *forward[MAXLEVEL]; // 指向不同层级的下一个节点
} SkipListNode;// 创建跳表节点
SkipListNode* createSkipListNode(int level, int value) {SkipListNode* newNode = (SkipListNode*)malloc(sizeof(SkipListNode));newNode->value = value;for (int i = 0; i < level; i++) {newNode->forward[i] = NULL;}return newNode;
}// 随机生成节点的层级
int randomLevel() {int level = 1;while ((rand() & 0xFFFF) < (0.5 * 0xFFFF)) {level++;if (level == MAXLEVEL) break;}return level;
}// 插入节点到跳表
void insertSkipList(SkipListNode **head, int value) {SkipListNode *update[MAXLEVEL];SkipListNode *current = *head;// 从最高层开始，找到每层中插入位置的前一个节点for (int i = MAXLEVEL - 1; i >= 0; i--) {while (current->forward[i] != NULL && current->forward[i]->value < value) {current = current->forward[i];}update[i] = current;}// 随机决定新节点的层级int level = randomLevel();// 创建新节点SkipListNode *newNode = createSkipListNode(level, value);// 将新节点插入到跳表中for (int i = 0; i < level; i++) {newNode->forward[i] = update[i]->forward[i];update[i]->forward[i] = newNode;}
}// 查找节点
int findSkipList(SkipListNode *head, int value) {SkipListNode *current = head;int count = 0;int ncount = 0;for (int i = MAXLEVEL - 1; i >= 0; i--) {count ++ ;while (current->forward[i] != NULL && current->forward[i]->value < value) {current = current->forward[i];ncount ++ ;printf("ncount %d .\n", ncount);}count += ncount;printf("count %d .\n", count);ncount = 0;if(current->forward[i] != NULL && current->forward[i]->value == value ){return count; // 找到值，返回查找次数}}return -1; // 未找到值
}// 打印跳表
void printSkipList(SkipListNode *head) {for (int i = MAXLEVEL - 1; i >= 0; i--) {SkipListNode *current = head->forward[i];printf("Level %d: ", i);while (current != NULL) {printf("%d ", current->value);current = current->forward[i];}printf("\n");}
}int main() {srand((unsigned)time(NULL)); // 初始化随机数生成器// 创建跳表头节点SkipListNode *head = createSkipListNode(MAXLEVEL, -1);// 插入数据insertSkipList(&head, 3);insertSkipList(&head, 6);insertSkipList(&head, 7);insertSkipList(&head, 9);insertSkipList(&head, 12);insertSkipList(&head, 19);insertSkipList(&head, 25);insertSkipList(&head, 29);// 打印跳表printSkipList(head);// 查找数据int valueToFind = 7;int searchCount = findSkipList(head, valueToFind);if (searchCount != -1) {printf("Number of steps taken to find the value %d: %d\n", valueToFind, searchCount);} else {printf("Value %d not found in the skip list.\n", valueToFind);}valueToFind = 29;searchCount = findSkipList(head, valueToFind);if (searchCount != -1) {printf("Number of steps taken to find the value %d: %d\n", valueToFind, searchCount);} else {printf("Value %d not found in the skip list.\n", valueToFind);}// TODO: 实现删除操作以及内存释放return 0;
}
