0

I create an instance of a struct, wordTree, at the base level of my dictionary.c file. When the load function is called, the intention is that this instance gets created, and "branches" are then added to it, to build it up into a dictionary.

Here's my code:

typedef struct tree {
    char *word;
    struct tree *left;
    struct tree *right;
} tree;

struct tree *wordTree = NULL;

void addWordToTree(char *word, tree *tree) {
    //If tree is null, create the tree
    if (tree == NULL) {
        struct tree *wordTree = &(struct tree) {};
        wordTree->word = word;
        tree = wordTree;
        return;
    }

    //Otherwise, keep iterating through the given tree,
    //eventually inserting the word on a branch
}

bool load(const char *dictionary)
{
    //Open dictionary, iterate through it to find the words
    //For each word found...
    addWordToTree(word, wordTree);

    return true;
}

What I'm seeing is that on the first run, wordTree is NULL, as I'd expect. After setting tree to a non-NULL value in the addWordToTree function, and then continuing within the load function, wordTree appears to continue to be NULL.

I would have expected that referencing a pointer when entering the addWordToTree function, and then setting it to a new value, would mean that the instance used at the base of the file and within the load function would point towards the new value.

1

Function parameters in C are usually passed by value, creating a variable that's initialised to the passed value. That means your assignment to tree changes the variable tree in addWordToTree, but that has no effect on global variable wordTree.

While there is a way to mark parameters as pass by reference using &, it's usually not recommended, since it's not overly explicit and might be overlooked.

The way I dealt with that was by passing the root node's address instead of the root node itself, like

void addWordToTree(char *word, tree **node)
{
    if (*node == NULL) {
        tree newNode = calloc(1, sizeof(tree));
        newNode.word = word;
        *node = newNode;
    }
    else if (strcmp(word, (*node)->word) < 0)
    {
        addWordToTree(word, &(*node)->left);
    }
    else if (strcmp(word, (*node)->word) > 0)
    {
        addWordToTree(word, &(*node)->right);
    }
}

and then

    addWordToTree(word, &wordTree);

Please note that this naive implementation of a tree will essentially lead to a single linked list if the input is already sorted, one would have to balance the tree in some way. For a dictionary, a trie (with "ie", pronounced like "tree" or "try") or hash map would be the better choice.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .