0

Something is wrong with my check(). It over-calculates the number of misspelled words. It seems that my code misses some conditions. Here is my code:

#include <stdbool.h>
#include <stdlib.h>
#include <ctype.h>    
#include <string.h>
#include <stdio.h>


#include "dictionary.h"

// Define a struct node to store words
typedef struct node
{
    bool is_word;
    struct node* children[27];
}
node;

// Set the root of tries
node root = {false, {NULL}};

I've updated the check(). Now it works.

/**
 * Returns true if word is in dictionary else false.
 */

bool check(const char* word)
{
    node* current_node = &root;
    for (int i = 0; i < LENGTH; i++)
    {   
        // Check if the letter is in the right order.
        if (word[i] != '\0')
        {
            // Calculate the index of the pointer of the corresponding trie. 
            int index = (isalpha(word[i])) ? (tolower(word[i]) - 'a'): 26; 
            // If the letter is in the loaded dictionary
            if (current_node -> children[index] != NULL)
            {
                current_node = current_node -> children[index];
            }
            // If the letter is not in the loaded dictionary
            else
            {
                return false;
            }            
        }
        // If reach the end of the word, check if it is indeed a word.
        else
        {
            if (current_node -> is_word == true)
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    }
    return false;
}

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */

EDIT 1: a new question.

current_node -> children[index] = malloc(sizeof(node));

current_node -> children[index] = {false, {NULL}}

After allocating memory for a new node, I tried to set the node to NULL, but my code reported error. Why my previous code node root = {false, {NULL}}; will work, but the code above won't? I think I'm still confused about the details of the usage of pointers.

EDIT 2: one more question.

node root = {false, {NULL}}

current_node -> children[index] = calloc(1, sizeof(node));

The first line create a node type in memory. How about the second one? Does it also create a node type or merely allocate the memory of the size of a node and set the data to zeroes? If it merely allocates memory, what operators should I use to assign values as current_node -> children[index] = {false, {NULL}} or current_node -> is_word = truewon't work?

int word_counter = 0;
bool load(const char* dictionary)
{
    // Read words from dictionary and store them in the tries
        // Read the first letter
        // Store it in the relevant children array (node -> children[x])
        // Read the next letter
        // Store it in the relevant children array (node -> children[x] -> children[x])
        // If a space is read, set is_word true. And contine the loop.  

    // Open the dictionary
    FILE* infile = fopen(dictionary, "r");
    if (infile == NULL)
    {
        printf("Could not open %s.\n", dictionary);
        return false;
    }

    node* current_node = &root;
    for (int c = fgetc(infile); c != EOF; c = fgetc(infile))
    {
        if (c != '\n') 
        {
            // Calculate the index of the children array if c is a letter or an apostrophe.
            int index = (isalpha(c)) ? (c - 'a'): 26;  
            // If children[index] is NULL, add another node to it to suggest that the word hasn't ended yet.
            if (current_node -> children[index] == NULL)
            {
                current_node -> children[index] = malloc(sizeof(node));
                if (current_node -> children[index] == NULL)
                {
                    printf("Memory allocation failed!");
                    return false;// Or return 1???
                }
                current_node = current_node -> children[index];    
            }
            else
            {
                current_node = current_node -> children[index];
            }

        }
        // If c is a '\n', mark the node as the end of the word. And reset the current_node to the root.
        else
        {
            current_node -> is_word = true;
            word_counter ++;
            current_node = &root;
        }
    }

    fclose(infile);
    return true;
}

/**
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */
unsigned int size(void)
{
    // TODO
    return word_counter;
}

/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
void free_node(node* cursor);
bool unload(void)
{
    // TODO
    //node* current_node = root;
    for (int i = 0; i < 27; i++)
    {
        if (root.children[i] != NULL)
        {
            free_node(root.children[i]);
        }

    }

    return true;
}

void free_node(node* cursor)
{
    for (int i = 0; i < 27; i++)
    {
        // If the child pointer do not point to Null, 
        // it suggests that the pointer points to another node.
        // So dive into the child node.
        if (cursor -> children[i] != NULL)
        {
            cursor = cursor -> children[i];
            // and return the for loop
            return free_node(cursor);
        }
    }
    // Continue the for loop
    // If reach the end of the loop, it suggests the pointer array all point to null.
    // Now you can free the current node.    
    free(cursor);
}

1 Answer 1

1

There are a few issues to be dealt with. First, in load(), when a node is created with a call to malloc, it is not then initialized, so it contains garbage data, not NULLs in all of the addresses. This will be a problem.

Next, the logic of check is flawed. It should NOT be checking whether is_word == true until the end of the word is reached. Say that cat is in the dictionary but cater is not. When t is reached, is_word would be true and you would get a false positive.

While traversing the trie to the end of the word, one of two things should happen. Either the next child is not null and the current pointer should be set to the child, or if the child is null, then return false.

This should get you going again.

If this answers your current question, please click on the check mark to accept. (Same goes for your previous question, hint hint. ;-) ) Let's keep up on forum maintenance. ;-)

4
  • Thank you, Cliff! Now the check() works. But I have a new question about how to set the allocated memory to NULL. I've updated the post. Thank you, Cliff!
    – Kevin King
    Sep 23, 2016 at 3:08
  • That technique only works when simultaneously creating/declaring and initializing a structure or array. Once it's been created, as is the case here, it doesn't work. You have two alternatives. Either populate each element of the struct using assignments and a for loop, or use calloc to allocate the memory. I'll leave it to you to read up on calloc. ;-) p.s. if your questions have been answered, please accept the answers by clicking on the check marks. Otherwise, they will stay in the unanswered question pool forever. :-(
    – Cliff B
    Sep 23, 2016 at 3:32
  • Thank you, Cliff! I also read a lot of posts about pointers, one of which suggested the usage of calloc(). I just wanted to know why mine won't work. Thank you for helping me clear up! :-)))
    – Kevin King
    Sep 23, 2016 at 5:50
  • Hi, Cliff I've come up with a relevant question about the usage of pointer again... and updated the post. Thank you!
    – Kevin King
    Sep 23, 2016 at 9:16

You must log in to answer this question.

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