NULL 值在运行时被重新分配给垃圾

Question

我有一个 C 程序来实现 Trie，其中每个都不存储一些数据（见下文）。 trie 应该在其分支中使用字符串来在树中的每个终止点处使用整数数据来排列数据（即作为键）。

#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' // Defines the 'zero' of the tree, can use (e.g.) '0' for searches including numbers

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) {
        new_node->data = malloc(sizeof(TRIE_DATA_TYPE));
        new_node->data = data;
        for (int i = 0; i < TRIE_LIMIT; i++) {
            new_node->nodes[i] = NULL; // TRIE_NODE_NULL;
        }
    }
    return new_node;
}

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

void insert_trie(struct trie_node * root, char * val, TRIE_DATA_TYPE data) {
    // Based off of my solution to HackerRank "1 Week Preparation kit": "No Prefix Set"
    // Modified from:
    // https://www.digitalocean.com/community/tutorials/trie-data-structure-in-c-plus-plus
    // https://www.techiedelight.com/trie-implementation-insert-search-delete/
    struct trie_node * current = root;
    int length = strlen(val);

    for (int i=0; i < length; i++) { // Can replace with search for '\0'
        int index = val[i] - TRIE_START_CHAR;
        if (current->nodes[index] == NULL) {
            // Node does not yet exist in tree, append
            //printf("Making node for letter %s\n", val[i]);
            current->nodes[index] = make_node_default();
        }
        else {
            // Can do something else
        }
        current = current->nodes[index];
    }
    // Reached the final branch, can add our data here.
    if (current->data == TRIE_DATA_DEFAULT) {
        current->data = data;
    }
    else {
        // Handle case were data already exists at node;
    }
    current = root;
    return;
}

TRIE_DATA_TYPE find_data(struct trie_node* root, char* val) {
    // Searches a tree for val.
    // returns TRIE_DATA_TYPE if it doesn't exist
    // returns current->node
    // Modified from:
    // https://www.digitalocean.com/community/tutorials/trie-data-structure-in-c-plus-plus
    // https://www.techiedelight.com/trie-implementation-insert-search-delete/

    struct trie_node* current = root;
    int length = strlen(val);
    for (int i = 0; i < length; i++) { // Can replace with search for '\0'
        int index = val[i] - TRIE_START_CHAR;
        if (current->nodes[index] == NULL) {
            // Node does not yet exist in tree, return TRIE_DATA_DEFAULT
            //printf("Can't find val in root, i=%d returning...\n", i);
            current = root;
            return TRIE_DATA_DEFAULT;
        }
        else {
            // Node exists in tree, continue
            current = current->nodes[index];
        }
    }
    // Got to the end of the tree, returning value stored
    // Can check if there are daughter nodes, etc
    TRIE_DATA_TYPE data = current->data;
    current = root;
    return data;
}

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


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

    free(root);

    return 0;
}

使用调试器并在运行时检查“root”trie 中的值，我们看到树似乎正确初始化（数据为 -1，节点中的所有值为 NULL）。但最终（有时是第一个“插入”步骤，有时是第二个步骤，有时是在“print_find”期间），对于一些should 保持为 NULL 的值，这些值采用一些“无意义”值（下面的示例；[0]是正确的，其余的应该是 NULL；采取位于第一个“print_find”步骤的断点）。

*请注意，这是一个示例，每次我运行该应用程序时，我都会得到略有不同的结果，有时我会一直这样做，但通常我会遇到一些无意义的数据值，它声称“trie”的值'是-7600000之类的。

我试过清理和重建，以及不同的分配方式（malloc、vs calloc、vs nothing）。

我所期望的是，这些值在运行时将保持为 NULL，我可以使用 NULL 检查来推进 trie；相反，我经常以垃圾结束，因为它找到非 NULL 值并返回这些数据值。这看起来内存分配正确，但在运行时被其他进程或其他东西重用，但我不确定如何防止这种行为。

Answer 1

至少功能

make_node_data

是无效的，

对于初学者，您需要为节点而不是指向节点的指针分配内存

struct trie_node* new_node = (struct trie_node*)malloc(sizeof(struct trie_node*));
                                                       ^^^^^^^^^^^^^^^^^^^^^^^^

那就是你需要使用表达

sizeof( struct trie_node )

而不是

sizeof( struct trie_node * )

。

数据成员

data

的类型为

int

#define TRIE_DATA_TYPE int
//...
struct trie_node {
    TRIE_DATA_TYPE data;
    struct trie_node * nodes[TRIE_LIMIT];
};

因此内存分配

    new_node->data = malloc(sizeof(TRIE_DATA_TYPE));

没有意义并产生内存泄漏：

new_node->data = data;