0

I know that there have been a lot of posts about this, but even after reading all of them, I can't seem to figure out why my code won't run properly — it still says that all 19190 words in austinpowers.txt are misspelled! Could someone help me? Below is dictionary.c.

 /**
 * Implements a dictionary's functionality.
 */

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

#include "dictionary.h"

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

int getIndex(const char c)  
{
    if (c == '\'') 
    {
        return 26;    
    }
    else 
    {
        return tolower(c) % 'a';
    }
}

unsigned int wordCount;
node *root;
struct node *nextNode;

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char *word)
{
    int length = strlen(word);
    node *ptr = root;

    for (int i=0; i<length; i++)
    {
        int index = getIndex(word[i]);

        nextNode = ptr->nodes[index];

        if (nextNode == NULL)
            return false;

        ptr = nextNode;
    }

    return ptr->is_word; 
}

/**
 * Loads dictionary into memory. Returns true if successful else false.
 */
bool load(const char *dictionary)
{
    FILE *fp = fopen(dictionary,"r");

    if (fp == NULL)
        return false;

    root = malloc(sizeof(node));
    node *ptr = root;

    //read dictionary letter by letter
    for (int c = fgetc(fp); c != EOF; c = fgetc(fp))
    {
        // If word has ended, increase word count and reset ptr
        if (c == '\n')
        {
            wordCount++;
            ptr->is_word = true;
            ptr = root;                
        }
        else
        {
            int index = getIndex(c);

            nextNode = ptr->nodes[index];

            if (nextNode == NULL)
                nextNode = malloc(sizeof(node));

            ptr = nextNode;
        }
    }

    fclose(fp);

    return true;
}

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

    else
        return 0;
}

/**
 * Unloads dictionary from memory. Returns true if successful else false.
 */

void clear(node* ptr)
{
    for (int i = 0; i < 27; i++)
    {
        if (ptr->nodes[i] != NULL)
        {
            clear(ptr->nodes[i]);
        }
    }

    free(ptr);
} 

bool unload(void)
{
    clear(root);
    return true;
}

1 Answer 1

1

The problem lies in the load() code:

else
    {
        int index = getIndex(c);

        nextNode = ptr->nodes[index];

        if (nextNode == NULL)
            nextNode = malloc(sizeof(node));

        ptr = nextNode;
    }

This code needs to be reworked. Simply put, it doesn't add any new nodes to the trie. The code assigns the address at ptr->nodes[index] to nextNode. If it is NULL, then it creates a new node, assigns it to nextNode and copies it back to ptr.

The problem with this is that it isn't assigning it to ptr->nodes[index], so the trie isn't getting any new nodes added to it. The new node gets assigned to ptr, which was pointing at root. So, there are a bunch of nodes allocated out there, but none are ever connected.

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

1
  • Thank you! I was finally able to fix my bug.
    – Ethan Teo
    Jan 16, 2017 at 3:10

You must log in to answer this question.

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