using a struct in pset5 misspelling

Question

I tried using the struct shown as described in the lecture but it come up with a problem.

    typedef struct node
    {
        bool is_word;
            struct node* address[27];
    }
    node;

using this struct if you have two word in a files such as vu and vo but vu is the only one in the dictionary it will say both are in the dictionary because when you load vu it will change is_word to true so when you check vu it says that is ok as well. or have I totally mis_understood the use of the struct

Answer 1

Not really. If you have allocate memory for a node that represents the letter 'v' as the first letter of a word, then according to the implementation, this node has an array of node children each of which represents a letter that comes right after 'v' in that word. For example:

#define SIZE 26

typdef struct node
{
    bool isWord;
    struct node *children[SIZE];
} node;

// the starting letters
node *root[SIZE] = {0};

// calculate the index of the node that represents the 'v'
int vIndex = 'v' - 'a';
// allocate memory for node that represents 'v' as the first letter of a word
root[vIndex] = malloc(sizeof(node));

Now allocating memory for any of the following nodes would correspond having the corresponding letter as a second letter in a word that follows a 'v'. So allocating memory for

root[vIndex]->children['a' - 'a']; // corresponds the 'a' in "va"
root[vIndex]->children['b' - 'a']; // corresponds the 'b' in "vb"
...
root[vIndex]->children['z' - 'a']; // corresponds the 'z' in "vz"

So if I want to have the word "van" loaded, assuming root[vIndex] have memory allocated for it (as I did above), I could do

// calculate the index for the 'a'
int aIndex = 'a' - 'a';
root[vIndex]->children[aIndex] = malloc(sizeof(node));
// calculate the index for the 'n'
int nIndex = 'n' - 'a';
root[vIndex]->children[aIndex]->children[nIndex] = malloc(sizeof(node));

// mark the end of the word
root[vIndex]->children[aIndex]->children[nIndex]->isWord = true;

And there you have the word "van" loaded into the try except that the code above looks awful. So is there a more elegant way we could do that? Certainly.

First, we could use a loop to iterate over each character in our word. We may use a loop for that. Then we may use a single variable to calculate the index inside the loop (i.e., the index of the current character) and we could use a temporary node to keep track of the current node. Here's some pseudocode:

1. declare a string called word and set it to "van"

2. declare a variable called index and set it to word[0] - 'a'
// ensure memory is allocated only once for any root node
3. if root[index] doesn't have memory allocated for it
    4. allocate memory for root[index]
5. declare a variable called current and set it to root[index]
6. for each character in word starting with the second character
    7. calculate the index of the current character and assign it to index
    // ensure memory is allocated only once for the same node
    8. if current->children[index] doesn't have memory allocated for it
        9. allocate memory for current->children[index]
      // update current
    10. set current to current->children[index]

// mark the end of the word
11. set current->isWord to true