在 C 中的 trie 数据结构中创建新节点

Question

我正在尝试在 C 中实现 trie 数据结构，但无法弄清楚如何动态命名添加到字典中的新节点。请参阅我的 add 方法的最后几行，其中我尝试创建一个新节点并尝试指向它。

bool add(char *word, node tree)
{
    // Creates a variable to store the current char in the string
    char currChar = word[0];
    // Converts the current char to an index #
    int currCharIndex = ((int) toupper(currChar)) - 65;

    // Checks if we've reached the end of the word
    if (currChar == '\0')
    {
        // Sets current node word to true
        tree.word = true;
    }
    // Checks if next letter in word is not NULL
    else if (tree.children[currCharIndex] != NULL)
    {
        // Follows the pointer
        return add(&word[1], *tree.children[currCharIndex],);
    }
    else
    {
        //Creates a new node
        node; // TODO: name node
        // Points the current node to the new node
        tree.children[currCharIndex] = &// TODO: new node name
        return add(&word[1], *tree.children[currCharIndex]);
    }
}

这是我定义节点的方式:

typedef struct node
{
    bool word;
    struct node *children[26];
}
node;

bool search(char *word, node tree);
bool add(char *word, node tree);

int main(void)
{
    node dictionary;
}

Answer 1

在您拥有的 add 原型(prototype)中，您按值传递 tree ，因此对 add 内的 tree 所做的任何更改 函数返回后会丢失。您首先需要更改 add 的原型(prototype)以获取指针，如下所示。

bool add(char *word, node * tree)

然后您可以分配内存来添加节点，如下所示

...
else
{
    //Creates a new node
    node * newnode;
    newnode = malloc(sizeof(node));
    //TODO Initialize newnode i.e. set all children to NULL.
    tree->children[currCharIndex] = newnode;
    return add(&word[1], tree->children[currCharIndex]);
}

还修复了代码的其他部分以传递指针而不是值。

...
else if (tree->children[currCharIndex] != NULL)
{
    return add(&word[1], tree->children[currCharIndex]);
}