0

I've been beating my head against a wall on this pset for 10 days now, watched all the videos, solved all the compiler errors, and just when I felt like I kind of understood this thing I ran the test and it failed on all counts other than the files existing and speller.c compiling. I'm sure this thing is so buggy it'll make your head spin if you know what you're looking at, but this is the first time in this course I've felt well and truly defeated.

Any help on any section of this would be appreciated.

#include <stdbool.h>
#include <stdio.h>
#include <ctype.h>
#include <strings.h>
#include <string.h>
#include <stdlib.h>
#include "dictionary.h"


// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

//initialize var for wordcount
int wordcount = 0;

// Number of buckets in hash table, or hashtable size
const unsigned int N = 26;

// Hash table
node *table[N];

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // TODO

    //hash the word to obtain the hash value using hash function
    int index = hash(word);

    //access linked list at that index in the table
    node* cursor = table[index];

    //iterate through the list looking for the word (strcasecmp)
    for (node* i = 0; i != NULL; i++)
    {
        cursor = cursor->next;
        char* compare = cursor->word;

        if (strcasecmp(word, compare) == 0)
            return true;
        else
            return false;
    }
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    //TODO

    //source: Deliberate Think on Youtube

    int hash = 0;
    int n;
    for (int i = 0; word[i] != '\0'; i++)
    {
        if (isalpha(word[i]))
            n = word[i] - 'a' + 1;
        else
            n = 27;

        hash = ((hash << 3) + n) % N;
    }
    return hash;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // TODO

    //open dictionary file
    FILE* dict = fopen(dictionary, "r");

    //if return value is NULL, return an error
    if (dict == NULL)
    {
        return false;
    }

    //iterate through each bucket in the hashtable and initialize to null?
    for (int i = 0; i < N; i++)
        table[i] = NULL;

    char word[LENGTH +1];

    //read the string from the file (fscanf(file, "%s", word)) until it reached EOF.  try while loop for this
    while (fscanf(dict, "%s", word) != EOF)
    {
        //create new node using malloc
        node *newnode = malloc(sizeof(node));

        //check if return value is NULL
        if (newnode == NULL)
        {
            free(newnode);
            return false;
        }

        //copy word into node using strcpy
        strcpy(newnode->word, word);

        //hash the word using the hash function above to determine which linked list the word should be placed in
        int index = hash(word);

        //insert the word into the hash table

            //add a new node to the linked list
            //set its pointer to the first element in the list
            //then reset the head's pointer to the new node

        newnode->next = table[index];
        table[index] = newnode;

        //increment wordcount for each word added
        wordcount++;


    }
    fclose(dict);

    return true;
}

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

    if (load(false))
        return 0;

    return wordcount;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // TODO


    //iterate through hash table
    for (int i = 0; i < N; i++)
    {
        //iterate through each list in table and free each node in list
        for (node* j = 0; j != NULL; j++)
        {
            //set cursor to the start of the list
            node* cursor = table[i];
            //set tmp to point to the same place as cursor
            node* tmp = cursor;

            cursor = cursor->next;
            free(tmp);
        }
    }
    return true;
}
2

First of all, get out of the mindset that code that compiles should work. All a successful compile means is that you've cleaned up mostly syntax errors. It has nothing to do with validating that a program works at all, or if it works correctly for all input. This is when you have to vigorously test code to make sure it executes correctly and to fix the logic flaws!

Take a careful look at the check() code, particularly the following and think about what it is doing.

node* cursor = table[index];

//iterate through the list looking for the word (strcasecmp)
for (node* i = 0; i != NULL; i++)
{
    cursor = cursor->next;
    char* compare = cursor->word;

    if (strcasecmp(word, compare) == 0)
        return true;
    else
        return false;
}

There are several issues here. First, consider the for loop setup. It's using a pointer to increment. Incrementing an address doesn't make any sense. Also, remember that the for loop will check the test condition on every loop, including the first. Since NULL is treated as 0, and the address stored in the pointer i is initialized to 0, or NULL, this loop simply never execute.

There are numerous ways to fix this for loop, but is a for loop appropriate here anyways? A for loop is best for executing a loop a well defined, fixed number of passes, usually based on an incrementing var with an upper fixed limit that is known or contained in another var at runtime.

Or, maybe a while loop is more appropriate. A while loop is more appropriate than a for loop when the number of passes isn't really known, but a test condition is really the controlling factor to terminate the loop. In this case, perhaps when cursor is NULL?

Next, look at the code inside the loop. It starts by moving the cursor pointer to the next node before checking the first node for a match! This means that the words in the first node in each linked list will never be found as correctly spelled. That can lead to up to N unique words being falsely called misspelled.

Finally, there's the else return false; statement. Because of this, only one word in the linked list will ever be checked. The loop needs to run until the entire linked list is scanned before returning false.

Figure out how to resolve all these issues and you'll be well on your way. THere may be other issues, but this was as far as I looked today. Can't deprive you of all the fun! ;-)

Programming note: There's no need to create an additional pointer var compare. It's a totally unneeded intermediate variable. Instead, just do this:

if (strcasecmp(word, cursor->word) == 0)

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 .