插入最后一个元素时出现SkipList分段错误

Question

我开发了一个带有 void 指针的 SkipList，以及设置其最大级别的概率方法。

这些是我的结构：

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

typedef struct _Node{
    Node **next;
    size_t size; //number of pointer in the node
    void *item;
}Node;

typedef struct _SkipList{
    Node **heads;
    size_t max_level; //max height in a single node
    size_t max_height; //max possible height in the skiplist
    int (*compare)(const void *, const void *);
}SkipList;

double random_probability() {
    return (double)rand() / RAND_MAX;
}

size_t random_level(size_t max_height) {
    size_t level = 1;
    while (random_probability() < 0.5 && level < max_height) {
        level++;
    }
    return level;
}

Node *create_node(void *item, size_t level) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (!newNode) {
        fprintf(stderr, "Errore nell'allocazione del nodo.\n");
        exit(EXIT_FAILURE);
    }
    newNode->item = item;
    newNode->size = level;
    newNode->next = (Node **)malloc(level * sizeof(Node *));
    if (!newNode->next) {
        fprintf(stderr, "Errore nell'allocazione dei puntatori successivi.\n");
        exit(EXIT_FAILURE);
    }
    for (size_t i = 0; i < level; i++) {
        newNode->next[i] = NULL;
    }
    return newNode;
}

void new_skiplist(SkipList **list, size_t max_height, int (*compare)(const void *, const void *)) {
    *list = (SkipList *)malloc(sizeof(SkipList));
    if (!*list) {
        fprintf(stderr, "Errore nell'allocazione della SkipList.\n");
        exit(EXIT_FAILURE);
    }
    (*list)->heads = (Node **)calloc(max_height, sizeof(Node *));
    if (!(*list)->heads) {
        fprintf(stderr, "Errore nell'allocazione dei puntatori iniziali.\n");
        exit(EXIT_FAILURE);
    }
    (*list)->max_level = 0;
    (*list)->max_height = max_height;
    (*list)->compare = compare;
    srand((unsigned int)time(NULL));
}

这是插入功能

void insert_skiplist(SkipList *list, void *item) {
    Node **update = (Node **)malloc((list->max_height + 1) * sizeof(Node *));
    if (!update) {
        fprintf(stderr, "Errore nell'allocazione dell'array di aggiornamento.\n");
        exit(EXIT_FAILURE);
    }

    Node *x = list->heads;

    // loop invariant: x[i]->item <= item or item < first element of level i in list
    for (size_t i = list->max_level; i > 0; i--) {
        while (x->next[i - 1] != NULL && list->compare(x->next[i - 1]->item, item) <= 0) {
            x = x->next[i - 1];
        }
        update[i] = x;
    }

    // loop end: x[1]->item <= item or item < first element in list
    x = x->next[0];

    if (x != NULL && list->compare(x->item, item) == 0) {
        // Elemento già presente, aggiorna il valore o gestisci il caso a tuo piacimento
        // x->item = newValue;
        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] = list->heads;
        }
        list->max_level = level;
    }

    x = create_node(item, level);

    for (size_t i = 1; i <= level; i++) {
        x->next[i - 1] = update[i]->next[i - 1];
        update[i]->next[i - 1] = x;
    }

    free(update);
}
    const void *search_skiplist(SkipList *list, void *item) {
        Node **x = list->heads;
        for (size_t i = list->max_level; i > 0; i--) {
            while (x[i] != NULL && list->compare(x[i]->item, item) < 0) {
                x = x[i]->next;
            }
        }

        if (x[1] != NULL && list->compare(x[1]->item, item) == 0) {
            return x[1]->item;
        } else {
            return NULL;
        }
    }

现在，当我尝试从主数组上创建一个跳过列表时：

int compare_int(const void *a, const void *b) {
 int x = (int *)a;
 int y = (int *)b;
 return (x - y);
}
int main() {
 srand((unsigned)time(NULL));

 SkipList *int_list;
 new_skiplist(&int_list, 10, compare_int);

 int int_keys[] = {3, 6, 1, 8, 2, 7, 5, 4, 9};
 for (size_t i = 0; i < sizeof(int_keys) / sizeof(int_keys[0]); i++) {
     insert_skiplist(int_list, int_keys[i]);
 }
const void* found=search_skiplist(int_list,9);
 if(found!=NULL) printf("FOUNDED\n");
 clear_skiplist(int_list);
return 0;

一切顺利，直到我尝试插入8，问题似乎是如果我的插入必须将一个节点放在列表的末尾，它就会出现分段错误。

准确地说，当我尝试插入 8 个项目时，GDB 收到此错误：

Program received signal SIGSEGV, Segmentation fault. 
Inser into  SkipList int: 9

Program received signal SIGSEGV, Segmentation fault.
0x004017ff in insert_skiplist (list=0xad1800, item=0x3) at src/skiplist.c:104
104         x = x->next[0];
(gdb) bt
#0  0x004017ff in insert_skiplist (list=0xad1800, item=0x3) at src/skiplist.c:104
#1  0x00401af6 in main () at src/main_ex2.c:30
(gdb) print (int)item
$1 = 3
(gdb) print (int*)item
$2 = (int *) 0x3
(gdb) print (int)x->item
$3 = 0
(gdb) print x->item
$4 = (void *) 0x0
(gdb) print x->next[0]
Cannot access memory at address 0x0
(gdb)
(gdb)

所以它无法访问 k-1 节点中的前一项，我不明白为什么，因为它将 6 放在 3 和 1 之后，没有错误。

我遇到了这个错误，有人可以帮助我理解这个错误吗？

非常感谢！

Answer 1

问题出在寻址上，这一段是错误的 Node *x = list->heads; 它必须是 Node *x = &list->heads。

现在一切正常