在 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 == '[=10=]')
    {
        // 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]);
    }
}

我是这样定义的 node:

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 原型中，您按值传递 tree，因此在 add 中对 tree 所做的任何更改都将在函数之后丢失returns。您首先需要更改 add 的原型以采用如下指针。

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]);
}

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

Creating new nodes in a trie data structure in C

c

trie