跳表 完整 C 語言實作

跳表 簡介

跳表 是一種概率性資料結構，以多層鏈表實現有序集合，平均查詢/插入/刪除複雜度均為 O(log n)，實作比平衡樹簡單。本文提供完整可編譯的 C 實作。

資料結構定義

#define SKIP_LIST_INIT_LEVEL 5

typedef struct list_node_s {
    int key;
    void *value;
    int high;                 // 節點層高
    struct list_node_s **forward; // 各層前進指標陣列
} list_node_t;

typedef struct list_s {
    int level;                // 當前最高層
    struct list_node_s *header;   // 頭節點（key=-1）
} list_t;

核心操作實作

隨機層高產生

int random_level() {
    int k = 0;
    while (rand() % 2) k++;
    return k;  // 幾何分佈，期望高度 ≈ log₂ n
}

建立空跳表

list_t *new_list(int init_level) {
    list_t *l = malloc(sizeof(list_t));
    l->header = malloc(sizeof(list_node_t));
    l->header->forward = malloc(init_level * sizeof(void*));
    l->header->high = init_level;
    l->header->key = -1;
    for (int i=0; iheader->forward[i] = NULL;
    l->level = 0;
    return l;
}

查找

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

插入

void insert(list_t *l, int key, void *value) {
    int k = l->level;
    list_node_t *p = l->header, *q = l->header;
    list_node_t **update = malloc((k+1) * sizeof(void*));

    // 由高層至低層尋找插入位置，記錄 update[k]
    while (q && k >= 0) {
        while (q->key < key) {
            p = q;
            if (q->forward[k]) q = q->forward[k];
            else break;
        }
        q = update[k] = p;
        k--;
    }

    int insert_level = random_level();
    if (insert_level > l->level) {
        // 擴展頭節點 forward 陣列
        int new_level = ++l->level;
        insert_level = new_level;
        list_node_t *n = malloc(sizeof(list_node_t));
        n->forward = malloc((insert_level+1) * sizeof(void*));
        n->high = insert_level + 1;
        n->key = key; n->value = value;
        // 複製舊 forward 並擴展
        list_node_t **new_fwd = malloc((insert_level+1) * sizeof(void*));
        memcpy(new_fwd, l->header->forward, (l->level) * sizeof(void*));
        new_fwd[insert_level] = NULL;
        free(l->header->forward);
        l->header->forward = new_fwd;
        l->header->high++;
        l->header->forward[insert_level] = n;
    } else {
        list_node_t *n = malloc(sizeof(list_node_t));
        n->forward = malloc((insert_level+1) * sizeof(void*));
        n->high = insert_level + 1;
        n->key = key; n->value = value;
    }

    // 逐層插入
    for (int k = insert_level; k >= 0; k--) {
        list_node_t *p = update[k];
        list_node_t *q = p->forward[k];
        p->forward[k] = n;
        n->forward[k] = q;
    }
    free(update);
}

刪除

void *delete(list_t *l, int key) {
    int k = l->level;
    list_node_t *p = l->header, *q = l->header, *n = NULL;
    list_node_t **update = malloc((k+1) * sizeof(void*));

    while (q && k >= 0) {
        while (q->key < key) {
            p = q;
            if (q->forward[k]) q = q->forward[k];
            else break;
        }
        q = update[k] = p;
        k--;
    }

    if (update[0]->forward[0] && update[0]->forward[0]->key == key)
        n = update[0]->forward[0];
    else { free(update); return NULL; }

    for (int k = n->high - 1; k >= 0; k--) {
        update[k]->forward[k] = n->forward[k];
    }
    free(update);
    void *val = n->value;
    free(n->forward);
    free(n);
    return val;
}

顯示結構（除錯用）

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

主程式測試

int main(int argc, char *argv[]) {
    int k = atoi(argv[1]);
    list_t *l = new_list(10);
    srand(time(NULL));

    // 插入 k 個隨機鍵
    for (int i=k; i>0; i--) insert(l, rand()%k, &k);
    show_list(l);

    // 查找並刪除 k 次
    for (int i=k; i>0; i--) {
        int key = rand()%k;
        if (find(l, key)) { delete(l, key); printf("key %d found\n", key); }
        else printf("key %d not found\n", key);
    }
    return 0;
}

編譯執行

gcc skiplist.c -o skiplist
./skiplist 1000

複雜度分析

總結

• 跳表 以空間換時間，多層索引加速查找。
• 隨機層高保證期望平衡，無需複雜旋轉操作。
• 適合併發環境（可採用無鎖或細粒度鎖實現）。