跳表（SkipList）整体删除触发段错误的问题排查与内存释放验证

我要实现跳表的删除功能，原本想利用跳表特性优化算法复杂度，调试时触发了段错误。
编辑补充：最初误实现了O(n log n)复杂度的算法，实际需求是O(log n)的实现。我已经更新了可行的解决方案，想确认这个方案能不能正确释放内存？

主函数代码 #

int main(int argc, char const *argv[])
{
    srand(time(NULL));
    SkipList *list = malloc(sizeof(SkipList));
    list->max_level = 0;
    list->compare = NULL;
    list->head = create_node(NULL,MAX_HEIGHT);
    insert_skip_list(list,(int*)5);
    insert_skip_list(list,(int*)4);
    insert_skip_list(list,(int*)3);
    insert_skip_list(list,(int*)1);
    insert_skip_list(list,(int*)0);
    list=delete_skip_list(list);
    read_skip_list(list);
    return 0;
}

删除功能代码 #

SkipList* delete_skip_list(SkipList *list){
    delete_node_array(list->head);
    free(list);
    list=NULL;
    return list;
}
void delete_node_array(Node* node){
   if(node == NULL) return; 
   delete_node_array(node->next[0]);
   free(node);
   node = NULL;
}

结构体定义 #

struct _SkipList {
    Node *head;
    unsigned int max_level;
    int (*compare)(void*, void*);
};
struct _Node {
    Node **next;
    unsigned int size;
    void *item;
};

编辑补充代码 #

Node* create_node(void* item, int level){
    Node *node = malloc(sizeof(Node));
    if(node == NULL){
        printf("error malloc node");
    }
    node->item = item;
    node->size = level;
    node->next = (Node**)malloc(level * sizeof(Node));
    for (int i = 0; i < node->size; i++)
        {
            node->next[i] = NULL;
        }
    if(node == NULL){
        printf("error malloc node->next");
    }
    return node;
}
float float_rand( float min, float max )
{
    float scale = rand() / (float) RAND_MAX; /* [0, 1.0] */
    return min + scale * ( max - min );      /* [min, max] */
}
int random_level(){
    int level = 1;
    
    while(level<MAX_HEIGHT && float_rand(0,1) < 0.5){
        level++;
    }
    return level;
}
void insert_skip_list(SkipList* list,void* item){
   
    Node* node = create_node(item,random_level());
    if(node == NULL){
        printf("\nisert_skip_list:error malloc node");
    }
    if (list == NULL)
    {
         printf("\nisert_skip_list:list null");
         exit(EXIT_FAILURE);
    }
    if(node->size > list->max_level){
        list->max_level = node->size;
    }
    
    Node *x = list->head;
    
    for (int k = list->max_level-1; k >= 0; k--)
    {
        if(x->next[k] == NULL || item < x->next[k]->item){
            if(k < node->size){
                node->next[k] = x->next[k];
                x->next[k] = node;
            }
        }else{
            x = x->next[k];
        }
    }
}

错误输出 #

node size: 1
node size: 1
node size: 1
node size: 1
node size: 12004376
Program received signal SIGSEGV, Segmentation fault.

看起来是节点为空，导致无法访问size字段。

问题分析与修正方案 #

1. 段错误直接原因
   主函数中执行list=delete_skip_list(list);后，list已被置为NULL，后续调用read_skip_list(list)会访问空指针，直接触发段错误。

2. 内存释放的问题
   当前删除逻辑能遍历到所有节点（通过最底层链表递归遍历），但存在两个缺陷：

   • 未释放节点内的next指针数组：每个节点的next是用malloc分配的，必须在free(node)前先free(node->next)，否则会造成内存泄漏。
   • 递归遍历如果节点数量过多，会触发栈溢出，建议改用迭代方式。

3. 修正后的删除逻辑

void delete_node_array(Node* node){
    while(node != NULL) {
        Node* temp = node;
        node = node->next[0];
        free(temp->next); // 先释放指针数组
        free(temp);
    }
}

SkipList* delete_skip_list(SkipList *list){
    if(list == NULL) return NULL;
    delete_node_array(list->head);
    free(list);
    return NULL;
}

4. 其他需修正的代码问题
   • create_node中node->next的分配与判空逻辑错误：应分配Node*类型数组，且要判断node->next是否为NULL，而非node：

     Node* create_node(void* item, int level){
         Node *node = malloc(sizeof(Node));
         if(node == NULL){
             printf("error malloc node");
             return NULL;
         }
         node->item = item;
         node->size = level;
         node->next = (Node**)malloc(level * sizeof(Node*));
         if(node->next == NULL){
             printf("error malloc node->next");
             free(node);
             return NULL;
         }
         for (int i = 0; i < node->size; i++){
             node->next[i] = NULL;
         }
         return node;
     }
     

   • insert_skip_list中直接用item < x->next[k]->item比较是错误的，void*类型直接比较是地址比较，而非值比较，应使用跳表的compare函数（或默认实现整数比较逻辑）。

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