0

I unfortunately don't have a more specific title as I'm looking more for some overall guidance in pset5. I think I am very close to solving it, but some issues I am having are as listed below (hoping this can get me steered to where my problems lie). I have tried debugging, reading my code to myself (i.e. the duck...), but to no avail.

1) I get the correct # of misspelled words compared to staff solutions, but something is wrong with my size function (my words in dictionary are 143065 vs. 143091)

2) I fail basically all check50 requirements (other than files exist and compile)

3) I am leaking memory with node *new and can't figure out how to free it (if I free within the while loop, program gets stuck, and I can't free outside the while loop because it doesn't exist outside the loop).

dictionary.c

// Implements a dictionary's functionality

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

#include "dictionary.h"

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    //declare cursor pointer to traverse linked list determined by hash function
    node *cursor = hashtable[hash(word)];

    //traverse linked list
    while (cursor != NULL)
    {
        //if word match is found, return true
        if (strcasecmp(word, cursor->word) == 0)
        {
            return true;
        }
        //if no word match, go to the next node
        else
        {
            cursor = cursor->next;
        }
    }

    //if we have traversed linked list without any matches, return false
    return false;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    //set all initial hash table pointers to NULL
    for (int i = 0; i < HASH_SIZE; i++)
    {
        hashtable[i] = NULL;
    }

    //open dictionary
    FILE *dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        fprintf(stderr, "Could not open %s", dictionary);
        return false;
    }

    //set up tmp node pointer to read into from dictionary
    node *tmp = malloc(sizeof(node));

    //scan dictionary to populate hash table
    while (fscanf(dict, "%s", tmp->word) != EOF)
    {
        //malloc a node* for each new word, returning false if NULL
        node *new = malloc(sizeof(node));
        if (new == NULL)
        {
            unload();
            return false;
        }

        //copy dictionary word to memory
        strcpy(new->word, tmp->word);

        //insert new node into the hash table
        int i = hash(tmp->word);

        if (hashtable[i] == NULL)
        {
            hashtable[i] = new;
        }
        else
        {
            new->next = hashtable[i];
            hashtable[i] = new;
        }
    }

    //close dictionary and free nodes used above
    fclose(dict);
    free(tmp);

    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    int n = 0;
    for (int i = 0; i < HASH_SIZE; i++)
    {
        node *cursor = hashtable[i];
        while (cursor->next != NULL)
        {
            n++;
            cursor = cursor->next;
        }
    }
    return n;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    for (int i = 0; i < HASH_SIZE; i++)
    {
        node *cursor = hashtable[i];
        while (cursor->next != NULL)
        {
            node *tmp = cursor;
            cursor = cursor->next;
            free(tmp);
        }
    }
    return true;
}

// Hash function to return an integer based upon the first letter of the word
int hash(const char *key)
{
    return (toupper(key[0]) - 'A') % HASH_SIZE;
}

dictionary.h

// Declares a dictionary's functionality

#ifndef DICTIONARY_H
#define DICTIONARY_H

#include <stdbool.h>

// Maximum length for a word
// (e.g., pneumonoultramicroscopicsilicovolcanoconiosis)
#define LENGTH 45

// Prototypes
bool check(const char *word);
bool load(const char *dictionary);
unsigned int size(void);
bool unload(void);
int hash(const char *key);

#endif // DICTIONARY_H

//define size of hash array (one for each letter of the alphabet)
#define HASH_SIZE 26

//define "node" for usage in hash table / linked lists
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

//declaration of hash table for arrangement of dictionary
node *hashtable[HASH_SIZE];
1
  • The #endif // DICTIONARY_H should be the last line in that file. It is meant to protect you from accidentally including the same file twice. As the whole content of the file is skipped on a second inclusion, there won't be any name collisions. I would not place that much in the header file, as that's included in speller.c, which does not need to know implementation details (also, it now gets its own hashtable variable), but as long as you don't re-use names, it should not hurt. – Blauelf Nov 27 '18 at 16:32
1
  1. while (cursor != NULL), as you want to count the nodes, not the successor nodes (the difference in the numbers is exactly 26, the number of linked lists). Imagine what might happen if cursor did not point to a node, and you accessed cursor->next. (And if you want to "cheat", just count the words in load, store it in a global variable, and return that number!)
  2. Guessing here. new->next might not be set for the first node, causing segfaults if it doesn't contain NULL by coincidence. Always do the new->next = hashtable[i]; stuff, no if/else needed.
  3. See 1.
1
  • Thanks - I was originally trying to do the "cheat" method for the size function but I kept getting a "re-use of name" compilation error, which was because of having the extra information in dictionary.h that you mentioned in the comment earlier. By declaring the global variable in my .c file instead of the .h file I'm all set here now and can just return counter. I also updated my code for new->next and the while loop in unload and good to go! – Greh Nov 27 '18 at 19:22

You must log in to answer this question.

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