Pset5 600 out 644 words misspelled. What am I missing?

Question

I can't seem to figure out what I'm doing wrong here... It loads the correct amount of words and checks them but its missing some when it comes to finding the misspellings. Can anyone spot what I'm doing that I shouldn't be? thanks!

int wordcount = 0;
int index2 = 0;
node* root = NULL;
void createTree(char word[index2]);
void freeme(node*tofree);

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char* word)
{
    /* Create pointer to search for value-------------------------------------*/
    node*current = root;
    // Iterate over new node pointer 
    for (int i = 0; i < strlen(word); i++)
    {
        /* Get value of character and if its poiner isnt NULL then move to the
        next one -------------------------------------------------------------*/
        int index = toupper(word[i]) - 65;
        if (current->children[index])
        {
            current = current->children[index];
            /* if end of word is reached tells us its the end and exit--------*/
            if (current->is_word == true && word[i + 1] == '\0')
            {
                return true;
            }
        }
    }
    return false;
}

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    /*------------------------------------------------------------------------*/
    char word[LENGTH+1];
    FILE* fp = fopen(dictionary, "r");
    if (fp == NULL)
    {
        printf("Could not open bleh.\n");
        return 1;
    }
    /* Initialize trie and create a Null root node----------------------------*/
    if (root == NULL)
    {
        root = malloc(sizeof(node));
        root->is_word = false;
    }
    /*Create word from text and load it into createTree-----------------------*/    
    for (int c = fgetc(fp); c != EOF; c = fgetc(fp))
    {
        // Check to see if char is a
        if (isalpha(c) || c == '\'')
        {
            word[index2] = c;
            index2++;
        }
        // Terminate word if the next char isnt a letter
        else if (isalpha(c) == 0)
        {
            word[index2] = '\0';
            createTree(word);
            index2 = 0;
            wordcount++;
        }
        else
            return true;
    }
    fclose(fp);
    return true;
}

Here's the function to store the words in case the error is in there... Seriously thanks!

void createTree(char word[index2])
{
    node*ptr = root;
    /* Iterate through word---------------------------------------------------*/
    for (int i = 0; i < strlen(word); i++)
    {
        /* Converts current character to index value--------------------------*/
        int index = toupper(word[i]) - 65;
        /* Check to see if the end of the word has been reached---------------*/
        if (word[i] != '\0')
        {
            /* Create a new node if still iterating through word--------------*/
            if (ptr->children[index] == NULL)
            {
                ptr->children[index] = malloc(sizeof(node));
            }
            /* Link the new node----------------------------------------------*/
            ptr = ptr->children[index];
            /* If end of word is reached set end of word to true--------------*/    
            if (word[i + 1] == '\0')
            {
                ptr->is_word = true;
            }
        }   
    }
}

Answer 1

There are two major problems with the code. First, neither load nor check are coded to handle apostrophes. Because of that, the value of index will be set at the ascii value of an apostrophe every time one is encountered. You should be able to figure out how to code for this, so I'll leave it at that.

The second problem is a subtle logic error and easily missed. Look at the following block of code:

for (int i = 0; i < strlen(word); i++)
{
    /* Get value of character and if its poiner isnt NULL then move to the
    next one -------------------------------------------------------------*/
    int index = toupper(word[i]) - 65;
    if (current->children[index])
    {
        current = current->children[index];
        /* if end of word is reached tells us its the end and exit--------*/
        if (current->is_word == true && word[i + 1] == '\0')
        {
            return true;
        }
    }
}

Specifically look at if (current->children[index]). It would be better to write this as if (current->children[index] !=NULL) to make its intent more clear. If this is true, all is well. But look what happens when it is null. The code will skip past the if statement's code block and loop. If it is null, that means that the word being tested doesn't exist in the dictionary, but the first part of it does (as another word.) The result is unpredictable and dependent on the contents of the trie and the word being checked. When this happens, you should immediately return false. Adding else return false; to the if block will cure this.

Also, when the code mallocs a node, it doesn't initialize the contents. Malloc only allocates the memory and returns the address of that memory. It doesn't initialize anything, so the nodes created contain garbage data. The code should initialize all 27 pointers to NULL and set is_word = FALSE every time a node is created.

This should take care of just about everything. Depending on how you code it, there may be more problems, but this will get you going.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)