SkipList插入末尾元素触发Segmentation Fault的问题求助

核心错误1：类型不匹配导致非法内存访问 #

你在insert_skiplist函数开头的初始化存在严重类型错误：

Node *x = list->heads;

list->heads的类型是Node**（指向指针数组的指针，存储每层的头节点指针），但你将其赋值给Node*类型的变量x。这会导致x指向heads数组的起始地址，而非有效的Node结构体。当后续执行x->next[0]时，程序会在错误的内存地址上解析Node的next字段，触发未定义行为——插入末尾元素时，遍历到链表尾部后访问无效内存，最终引发段错误。

修复方法：
重新设计遍历逻辑，使用Node*类型遍历每层节点，初始时从对应层的头节点（list->heads[i-1]，因heads是0索引数组，max_level从1开始计数）出发：

void insert_skiplist(SkipList *list, void *item) {
    Node **update = (Node **)malloc((list->max_height + 1) * sizeof(Node *));
    if (!update) {
        fprintf(stderr, "更新数组分配失败。\n");
        exit(EXIT_FAILURE);
    }

    // 从最高层开始记录每层的前驱节点
    Node *current;
    for (size_t i = list->max_level; i > 0; i--) {
        current = list->heads[i - 1];
        while (current != NULL && list->compare(current->item, item) <= 0) {
            current = current->next[i - 1];
        }
        update[i] = current;
    }

    // 检查最底层是否已存在该元素
    current = list->heads[0];
    while (current != NULL && list->compare(current->item, item) <= 0) {
        current = current->next[0];
    }

    if (current != NULL && list->compare(current->item, item) == 0) {
        free(update);
        return;
    }

    size_t level = random_level(list->max_height);

    if (level > list->max_level) {
        for (size_t i = list->max_level + 1; i <= level; i++) {
            update[i] = NULL;
        }
        list->max_level = level;
    }

    Node *new_node = create_node(item, level);
    for (size_t i = 1; i <= level; i++) {
        if (update[i] == NULL) {
            new_node->next[i-1] = list->heads[i-1];
            list->heads[i-1] = new_node;
        } else {
            new_node->next[i-1] = update[i]->next[i-1];
            update[i]->next[i-1] = new_node;
        }
    }

    free(update);
}

核心错误2：数据传递与比较逻辑错误 #

在main函数中，你直接将int值传递给insert_skiplist：

insert_skiplist(int_list, int_keys[i]);

Node的item字段是void*，应存储指向数据的指针而非数据本身。这导致compare_int函数错误地将指针地址当作int值比较：

int compare_int(const void *a, const void *b) {
 int x = (int *)a;
 int y = (int *)b;
 return (x - y);
}

这种错误会导致比较结果完全不符合预期，甚至可能间接引发内存访问错误。

修复方法：

1. 传递指向int的指针给插入函数：

for (size_t i = 0; i < sizeof(int_keys) / sizeof(int_keys[0]); i++) {
    insert_skiplist(int_list, &int_keys[i]);
}

2. 修正比较函数，正确解引用指针：

int compare_int(const void *a, const void *b) {
    int x = *(const int *)a;
    int y = *(const int *)b;
    return x - y;
}

辅助错误：搜索函数逻辑错误 #

search_skiplist函数同样存在类型不匹配和遍历逻辑错误，修复后的版本如下：

const void *search_skiplist(SkipList *list, const void *item) {
    if (list->max_level == 0) {
        return NULL;
    }

    Node *current = list->heads[list->max_level - 1];
    // 从最高层往下遍历
    for (int i = list->max_level - 1; i >= 0; i--) {
        while (current != NULL && list->compare(current->item, item) < 0) {
            current = current->next[i];
        }
        // 降到下一层
        if (i > 0) {
            current = (current == NULL) ? list->heads[i-1] : current->next[i-1];
        }
    }

    // 检查最底层节点
    while (current != NULL && list->compare(current->item, item) < 0) {
        current = current->next[0];
    }

    if (current != NULL && list->compare(current->item, item) == 0) {
        return current->item;
    }
    return NULL;
}

总结 #

最直接引发段错误的原因是insert_skiplist中list->heads（Node**）被错误赋值给Node*变量，导致非法内存访问。修复类型不匹配问题后，再修正数据传递和比较逻辑，即可解决插入末尾元素时的段错误。

内容的提问来源于stack exchange，提问作者Trammy