? ? ? ? 在數據結構算法中，有一種算法猶如“時空穿梭機”，能在瞬間跨越層層障礙，直擊目標——它就是跳表算法。下面，就讓我們一起揭開跳表算法的神秘面紗，通過實例探究其高效與魅力。

目錄

一、跳表算法是什么？

二、實例解析

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;
}