C语言Trie树实现中NULL值运行时被覆写为垃圾值问题排查

核心问题定位 #

代码出现随机内存污染、指针被覆写为垃圾值的根本原因是内存分配大小错误，同时存在冗余的内存分配操作导致泄漏。

具体错误分析 #

• 内存分配尺寸错误：在make_node_data函数中，你用malloc(sizeof(struct trie_node*))分配节点内存，但struct trie_node*是指针类型（通常4/8字节），而实际需要分配的是整个trie_node结构体的大小（包含1个int和26个指针，远大于指针尺寸）。分配内存不足会导致后续写入nodes数组时越界，破坏堆内存结构，引发随机异常。
• 冗余且错误的内存分配：new_node->data = malloc(sizeof(TRIE_DATA_TYPE));完全多余，因为data是int类型，直接赋值即可。这行代码不仅会造成内存泄漏，还会把指针地址强制转换为int存入data，后续又被new_node->data = data覆盖，属于无效操作。

修复后的完整代码 #

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

#define TRIE_LIMIT 26
#define TRIE_DATA_TYPE int
#define TRIE_DATA_DEFAULT -1
#define TRIE_NODE_NULL NULL
#define TRIE_START_CHAR 'a' // 树的起始字符，若要支持数字可改为'0'

struct trie_node {
    TRIE_DATA_TYPE data;
    struct trie_node * nodes[TRIE_LIMIT];
};

struct trie_node * make_node_data(TRIE_DATA_TYPE data) {
    // 修正：分配整个结构体的大小，而非指针大小
    struct trie_node* new_node = (struct trie_node*)malloc(sizeof(struct trie_node));
    if (new_node != NULL) {
        // 移除冗余的malloc，直接赋值data
        new_node->data = data;
        for (int i = 0; i < TRIE_LIMIT; i++) {
            new_node->nodes[i] = NULL;
        }
    }
    return new_node;
}

struct trie_node * make_node_default() {
    return make_node_data(TRIE_DATA_DEFAULT);
}

void insert_trie(struct trie_node * root, const char * val, TRIE_DATA_TYPE data) {
    struct trie_node * current = root;
    int length = strlen(val);

    for (int i=0; i < length; i++) {
        int index = val[i] - TRIE_START_CHAR;
        if (current->nodes[index] == NULL) {
            current->nodes[index] = make_node_default();
        }
        current = current->nodes[index];
    }
    if (current->data == TRIE_DATA_DEFAULT) {
        current->data = data;
    }
}

TRIE_DATA_TYPE find_data(struct trie_node* root, const char* val) {
    struct trie_node* current = root;
    int length = strlen(val);
    for (int i = 0; i < length; i++) {
        int index = val[i] - TRIE_START_CHAR;
        if (current->nodes[index] == NULL) {
            return TRIE_DATA_DEFAULT;
        }
        current = current->nodes[index];
    }
    return current->data;
}

void print_find(struct trie_node* root, const char * val) {
    TRIE_DATA_TYPE trie_val = find_data(root, val);
    if (trie_val == TRIE_DATA_DEFAULT) {
        printf("'%s' not in trie!\n", val);
    }
    else {
        printf("Data at '%s': %d\n", val, trie_val);
    }
}

// 新增：递归销毁Trie树，避免内存泄漏
void destroy_trie(struct trie_node* node) {
    if (node == NULL) return;
    for (int i = 0; i < TRIE_LIMIT; i++) {
        destroy_trie(node->nodes[i]);
    }
    free(node);
}

int main() {
    struct trie_node* root = make_node_default();
    insert_trie(root, "abc", 5);
    insert_trie(root, "abcd", 6);
    print_find(root, "abc");  // 输出：Data at 'abc': 5
    print_find(root, "abcd"); // 输出：Data at 'abcd': 6
    print_find(root, "trie"); // 输出：'trie' not in trie!

    // 修正：销毁整个树，而非仅free root
    destroy_trie(root);

    return 0;
}

额外优化建议 #

• 使用calloc替代malloc+手动赋值NULL：calloc会自动将分配的内存初始化为0（即NULL），可以省去循环赋值节点指针的代码，比如struct trie_node* new_node = calloc(1, sizeof(struct trie_node));
• 增加边界检查：插入/查找时检查输入字符串是否包含超出TRIE_START_CHAR到TRIE_START_CHAR+TRIE_LIMIT-1范围的字符，避免数组越界
• 处理重复插入逻辑：当前代码重复插入同一键时会忽略新数据，可根据需求修改为覆盖或返回错误

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