CS50 pset5 Speller

Question

That is my first post here, and I need help. Speller's output for lalaland.txt is 958 words, but should be 955. (3 x "i'd"). I have tried to hard-code "i'd", but then output was ~850. (program declined all of "i'd"). tolstoy.txt - 13117, but must be 13008, most words are two-letters (Ha, ha, ga, Ma, I'd, etc.). Same time other part of same word passing check. Same situation with all other texts. Program passing and declining same words with no reason. I have no idea what is happening.

Here is my load();

bool load(const char *dictionary)
{
    FILE *inputFile = fopen(dictionary, "r");
    if (inputFile == NULL)
    {
        return false;
    }

    while (true)
    {
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return 1;
        }
        n->next = NULL;
        int sc = fscanf(inputFile, "%s", n->word);
        if (sc == EOF)
        {
            free(n);
            break;
        }

        int bucket = hash(n->word);
        if (table[bucket] == NULL)
        {
            table[bucket] = n;
        }
        else
        {
            n->next = table[bucket]->next;
            table[bucket]->next = n;
        }
        sizeCount++;
    }
    fclose(inputFile);
    return true;
}

And check();

bool check(const char *word)
{
    int i = hash(word);
    if (table[i] == NULL)
    {
        return false;
    }
    struct node *checker = malloc(sizeof(node));
    checker = table[i];
    while (true)
    {
        if (strcasecmp(checker->word, word) == 0)
        {
            return true;
        }
        if (checker->next == NULL)
        {
            break;
        }
        checker = checker->next;
    }
    free(checker);
    return false;
}

Looks like a copy/paste accident; actual check function not posted. — DinoCoderSaurus

DinoCoderSaurus DinoCoderSaurus · Accepted Answer · 2020-05-22T21:54:07

Remember, table is an array of node pointers, not an array of nodes. Therefore, there is no memory allocated for a next or word element. These lines in load are accessing memory that does not belong to table[bucket]:

n->next = table[bucket]->next;
table[bucket]->next = n;

Since table is the head of the list, there is no need to allocate a node in check. If checker is a node pointer, initialized to table[bucket], the program will crawl the list just fine, and (should) only access allocated memory.

The memory violations are causing the unpredictable results. You could run valgrind -v to see the full report.

CS50 pset5 Speller

1 Answers