C语言复杂数据结构内存释放问题及Valgrind报错排查

数据结构定义 #

我实现的哈希表字典是链表数组结构，层级为：dictionary -> table -> array -> array[i] 为链表节点，数据结构定义如下：

// Data type for nodes in linked list
typedef struct list_node {
    char word[MAX_WORD_LEN]; // Word, as a null-terminated string
    struct list_node *next;  // next in chain     
} list_node_t;

// Data type for a hash table. Use chaining for collisions, so array of list_nodes
typedef struct {
    list_node_t **array; // base array for hash table
    unsigned int length; // Length of base array
} table_t;

// Data type for a dictionary
typedef struct {
    table_t *table;   // Hash table that stores words
    unsigned size;    // Number of words stored in the dictionary
} dictionary_t;

内存释放代码问题 #

我尝试按「链表节点→数组→哈希表→字典」的顺序释放内存，但Valgrind检测出内存泄漏，释放代码如下：

void table_free(table_t *table) {
        list_node_t *node;
        list_node_t *tempNode;
        for (int i = 0; i < table->length; i++) {
            if (table->array[i] != NULL) {
                if (table->array[i]->next == NULL) {//if only one node in array[i]'s linked list
                    free(table->array[i]);
                    continue;
                } else {
                    node = table->array[i];
                    while(node->next != NULL) {
                        tempNode = node->next;
                        free(node);
                        node = tempNode;
                    }
                }
            }
        }

        for (int i = 0; i < table->length; i++) {
            if (table->array[i] == NULL) { //free the spots I missed
                free(table->array[i]);
            }
        }
        free(table->array);
        free(table);
}

void dict_free(dictionary_t *dict) {
    table_free(dict->table);
    free(dict);
}

Valgrind泄漏报错 #

==4046703== HEAP SUMMARY:
==4046703==     in use at exit: 60,928 bytes in 448 blocks
==4046703==   total heap usage: 2,031 allocs, 1,583 frees, 306,448 bytes allocated
==4046703== 
==4046703== 60,928 bytes in 448 blocks are definitely lost in loss record 1 of 1
==4046703==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==4046703==    by 0x109C84: insert_word_into_table (dictionary.c:56)
==4046703==    by 0x109DD5: dict_insert (dictionary.c:95)
==4046703==    by 0x10A2B1: read_dict_from_text_file (dictionary.c:239)
==4046703==    by 0x1095E1: main (spell_check.c:105)

插入函数的尝试问题 #

我尝试在insert_word_into_table函数中释放内存，该函数代码如下：

int insert_word_into_table(table_t *table, const char *word){
    int hsh_code = hash_code(word);
    int duplicateWordFlag = 0;
    //initialize the new node for the word
    list_node_t *newNode = malloc(sizeof(list_node_t));

    if (table->array[hsh_code] == NULL) {//if nothing is in the array
        table->array[hsh_code] = newNode;
        table->array[hsh_code]->next = NULL;
        strcpy(table->array[hsh_code]->word, word);
    } else {//if there is a node there
        list_node_t* i = table->array[hsh_code];
        while (i->next != NULL) {
            if (strcmp(word, i->word) == 0){
                duplicateWordFlag = -1;
            }
            i = i->next;
        }
        i->next = newNode;//new way
        strcpy(i->next->word, word);
        i->next->next = NULL;

    }
    //free(newNode); //my attempt to free it
    return duplicateWordFlag;
}

• 当注释free(newNode)时，Valgrind显示无泄漏，但实际是因为后续table_free会释放这些节点；
• 取消注释后，出现重复释放错误，报错如下：

==4047436== Invalid free() / delete / delete[] / realloc()
==4047436==    at 0x484B27F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==4047436==    by 0x10A03A: table_free (dictionary.c:161)
==4047436==    by 0x10A0F9: dict_free (dictionary.c:187)
==4047436==    by 0x109AEB: main (spell_check.c:229)
==4047436==  Address 0x4add510 is 0 bytes inside a block of size 136 free'd
==4047436==    at 0x484B27F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==4047436==    by 0x109DB2: insert_word_into_table (dictionary.c:75)
==4047436==    by 0x109DE1: dict_insert (dictionary.c:95)
==4047436==    by 0x10A2BD: read_dict_from_text_file (dictionary.c:239)
==4047436==    by 0x1095E1: main (spell_check.c:105)
==4047436==  Block was alloc'd at
==4047436==    at 0x4848899: malloc (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==4047436==    by 0x109C84: insert_word_into_table (dictionary.c:56)
==4047436==    by 0x109DE1: dict_insert (dictionary.c:95)
==4047436==    by 0x10A2BD: read_dict_from_text_file (dictionary.c:239)
==4047436==    by 0x1095E1: main (spell_check.c:105)

核心疑问 #

1. 我的内存释放代码哪里有问题？如何修复？
2. C语言中，函数内分配的内存仅在程序结束时释放是否足够？

问题解答 #

1. 内存释放代码的问题与修复

你的table_free函数存在两个关键问题：

• 链表遍历遗漏最后一个节点：在处理多节点链表时，while(node->next != NULL)循环只释放到倒数第二个节点，最后一个节点node没有被释放；
• 错误释放NULL指针：第二个循环中free(table->array[i])当table->array[i]为NULL时，free(NULL)虽然安全，但属于无效操作，且完全没必要。

修复后的table_free代码：

void table_free(table_t *table) {
    list_node_t *node;
    list_node_t *tempNode;
    for (int i = 0; i < table->length; i++) {
        node = table->array[i];
        // 遍历并释放当前链表的所有节点
        while (node != NULL) {
            tempNode = node->next;
            free(node);
            node = tempNode;
        }
        // 将数组元素置空，避免悬空指针（可选但推荐）
        table->array[i] = NULL;
    }
    free(table->array);
    free(table);
}

这段代码统一处理单节点和多节点链表的情况，遍历每个链表的所有节点并释放，不会遗漏任何节点。

另外，insert_word_into_table函数中绝对不能在插入后立即free(newNode)，因为你已经把newNode的指针存入哈希表的链表中，后续table_free会释放它。提前释放会导致哈希表中存储悬空指针，后续table_free再次释放就会触发重复释放错误。

2. 程序结束时释放内存是否足够？

从操作系统的角度来说，程序退出后，操作系统会回收该进程占用的所有内存，所以即使不手动释放，也不会造成系统层面的内存泄漏。但从程序健壮性和规范来说：

• 如果是短生命周期的程序，不手动释放内存通常不会有问题；
• 如果是长期运行的服务类程序（如后台守护进程），内存泄漏会导致内存占用持续增长，最终耗尽系统内存，引发OOM；
• 手动释放内存是良好的编程习惯，能避免潜在的内存问题，也便于通过Valgrind等工具排查其他内存错误。

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