跳表 Skip List C 語言完整實現

編輯：關於C語言

資料結構定義


#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

#define SKIP_LIST_INIT_LEVEL 5

typedef struct list_node_s {
    int key;
    void *value;
    int height;                    // 節點層數
    struct list_node_s **forward;  // 每層前進指標陣列
} list_node_t;

typedef struct list_s {
    int level;                     // 當前最大層數
    list_node_t *header;           // 頭節點 (key = -1)
} list_t;

核心操作

隨機層數生成


int random_level() {
    int k = 0;
    while (rand() % 2) k++; // 50% 機率增加層數
    return k;
}

建立跳表


list_t *new_list(int init_level) {
    list_t *l = malloc(sizeof(list_t));
    l->header = malloc(sizeof(list_node_t));
    l->header->forward = calloc(init_level + 1, sizeof(list_node_t*));
    l->header->height = init_level + 1;
    l->header->key = -1;
    l->level = 0;
    return l;
}

查找


void *find(list_t *l, int key) {
    list_node_t *n = l->header;
    for (int k = l->level; k >= 0; --k) {
        while (n->forward[k] && n->forward[k]->key <= key)
            n = n->forward[k];
        if (n->key == key) return n->value;
    }
    return NULL;
}

插入


void insert(list_t *l, int key, void *value) {
    list_node_t *update[64]; // 假設最大層數 < 64
    list_node_t *n = l->header;

    // 1. 尋找每層插入位置
    for (int k = l->level; k >= 0; --k) {
        while (n->forward[k] && n->forward[k]->key < key)
            n = n->forward[k];
        update[k] = n;
    }

    // 2. 隨機新節點層數
    int new_level = random_level();
    if (new_level > l->level) {
        for (int k = l->level + 1; k <= new_level; ++k)
            update[k] = l->header;
        l->level = new_level;
    }

    // 3. 分配新節點
    list_node_t *new_node = malloc(sizeof(list_node_t));
    new_node->key = key;
    new_node->value = value;
    new_node->height = new_level + 1;
    new_node->forward = calloc(new_level + 1, sizeof(list_node_t*));

    // 4. 連接指標
    for (int k = 0; k <= new_level; ++k) {
        new_node->forward[k] = update[k]->forward[k];
        update[k]->forward[k] = new_node;
    }
}

刪除


void *delete(list_t *l, int key) {
    list_node_t *update[64];
    list_node_t *n = l->header;

    for (int k = l->level; k >= 0; --k) {
        while (n->forward[k] && n->forward[k]->key < key)
            n = n->forward[k];
        update[k] = n;
    }

    n = update[0]->forward[0];
    if (!n || n->key != key) return NULL;

    for (int k = 0; k <= l->level; ++k) {
        if (update[k]->forward[k] == n)
            update[k]->forward[k] = n->forward[k];
    }

    // 更新最大層數
    while (l->level > 0 && l->header->forward[l->level] == NULL)
        l->level--;

    void *val = n->value;
    free(n->forward);
    free(n);
    return val;
}

銷毀


void destroy(list_t *l) {
    list_node_t *n = l->header->forward[0];
    while (n) {
        list_node_t *next = n->forward[0];
        free(n->forward);
        free(n);
        n = next;
    }
    free(l->header->forward);
    free(l->header);
    free(l);
}

測試主程式


void show_list(list_t *l) {
    for (int k = l->level; k >= 0; --k) {
        list_node_t *n = l->header;
        printf("Level %d: ", k);
        while (n) {
            printf("%d ", n->key);
            n = n->forward[k];
        }
        printf("\n");
    }
}

int main(int argc, char *argv[]) {
    if (argc < 2) return 1;
    int n = atoi(argv[1]);
    srand(time(NULL));

    list_t *l = new_list(10);
    void *dummy = &n;

    // 插入 n 個隨機鍵
    for (int i = 0; i < n; ++i)
        insert(l, rand() % n, dummy);

    show_list(l);

    // 查找並刪除 n 個隨機鍵
    for (int i = 0; i < n; ++i) {
        int key = rand() % n;
        void *v = find(l, key);
        if (v) { delete(l, key); printf("Key %d found & deleted\n", key); }
        else printf("Key %d not found\n", key);
    }

    destroy(l);
    return 0;
}