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

Question

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

#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 ''
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 %sn", 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 ''
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': %dn", 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;
}

使用调试器并在运行时检查'根'树中的值，我们看到的是树似乎初始化正确(数据为-1，节点中的所有值为NULL)。但最终(有时是第一个"插入")第一步，有时是第二步，有时是在print_find")中，值呈现一些';无意义';的值应该保持NULL(示例如下;[0]为正确，其余应为NULL;在第一个"print_find"一步)。

Null-nonsense

*请注意，这是一个例子，每次我运行应用程序，我得到的结果都略有不同，有时我一直运行，但通常我遇到一些无意义的数据值，它声称'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;

函数insert_trie中strlen的调用

int length = strlen(val);

是多余的。下面的for循环可以像

这样查找

for ( ; *val != ''; val++ )

for循环体中的这些语句

int index = val[i] - TRIE_START_CHAR;
if (current->nodes[index] == NULL) {

是不安全的，可能导致未定义的行为。

函数应该声明为

void insert_trie(struct trie_node * root, const char * val, TRIE_DATA_TYPE data);

还有这个语句

current = root;

通常在return语句之前出现在函数中是没有作用的。