0

G'day, I've been working away at pset5 and finally got it to compile with no memory leaks and runs fine, but does not pick up on all words. I've been using the debugger in combination with the cat.txt infile to debug it and have found, specifically to this text, that the problem arises when the second letter 'a' is checked in the word caterpillar. This is strange because it has no problem handling the previous 'a's that have come before it. If someone would be able to point me in the right direction that would be great.

Here is a sample of my code:

// Implements a dictionary's functionality

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

#include "dictionary.h"

#define max_word_size 45

// Struct Node definition
typedef struct node
{
    bool is_word;
    struct node *children[27];
}
node;

// Word Count
unsigned int counter = 0;

// Pointer to root
struct node *root = NULL;

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // Load Dictionary
    FILE *infile = fopen(dictionary, "r");
    if (infile == NULL)
    {
        printf("Could not open infile\n");
        return false;
    }

    // Allocate space in memory for root
    root = calloc(1, sizeof(node));

    // Pointer to root
    node *trav = root;

    // Load dictionary into memory by letters
    for (char c = fgetc(infile); c != EOF; c = fgetc(infile))
    {
        // Iterate through each word
        if (c != '\n')
        {
            // If apostrophe, assign to C[26]
            if (c == '\'')
            {
                c = 123;    // ASCII of 123 for apostrophe's
            }
            else if (isalpha(c))
            {
                c = tolower(c);
            }


            if (trav -> children[c - 97] == NULL)
            {
                trav -> children[c - 97] = calloc(1, sizeof(node));
            }
            else
            {
                trav = trav -> children[c - 'a'];
            }
        }

        // When c reaches end of word
        if (c == '\n')
        {
            trav -> is_word = true;
            trav = root;
            counter++;
        }
    }
    fclose(infile);
    return true;
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    node *trav = root;
    unsigned int index = 0;

    // Loop through letters in word
    for (int i = 0; i < strlen(word); i++)
    {

        // Check if character is apostrophe
        if (word[i] == '\'')
        {
            index = 26;
        }
        else
        {
            index = tolower(word[i]) - 'a';
        }

        // Go to corresponding element in children
        if (trav -> children[index] == NULL)        // If no letter
        {
            return false;
        }
        else if (trav -> children[index] != NULL)
        {
            trav = trav -> children[index];
        }

        if (i == strlen(word) - 1 && trav -> is_word == true)
        {
            return true;
        }
    }
    return false;
}

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

// Clear node function
void clear_node(node *trav)
{
    // for loop over 26
    for (int i = 0; i <= 26; i++)
    {
        if (trav -> children[i] != NULL)
        {
            clear_node(trav -> children[i]);
        }
    }
    free(trav);
    return;
}


// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    clear_node(root);
    return true;
}

Cheers!

1

The problem lies in this block of code:

        if (trav -> children[c - 97] == NULL)
        {
            trav -> children[c - 97] = calloc(1, sizeof(node));
        }
        else
        {
            trav = trav -> children[c - 'a'];
        }

Think about what's happening here. There are two cases - the next node exists or it doesn't exist. If it exists (the else clause), the code resets to that node - it steps one letter farther into the trie.

If, however, the node doesn't exist, life gets interesting. The if code block executes, creating the new node. Here's the problem though - it doesn't step to that node. Instead, the code just lets the current position pointer, trav, sit where it was.

I'll let you think about it, but here's a hint. The code is fixed by removing a single word. Happy coding! ;-)

You can test with a short dictionary with these words. Just use the dictionary as both the dictionary and the text to be checked:

cat
caterpillar
car
carry
car's
cars
gulf
hat

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

You must log in to answer this question.

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