Answers to CS50x 2019 Problem Set 4: Data Structures.

Speller

// Implements a dictionary's functionality

//Using #'s for readability - should be <>
#include #ctype.h>
#include #stdbool.h>
#include #stdio.h>
#include #stdlib.h>
#include #string.h>
#include #strings.h>

#include "dictionary.h"


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

// Hashtable size
const int HASHTABLE_SIZE = 65536;

// initialize a hashtable that is a pointer
node *hashtable[HASHTABLE_SIZE];


//Returns integer hash value for a given a string
//https://www.reddit.com/r/cs50/comments/1x6vc8/pset6_trie_vs_hashtable/cf9nlkn/
int hash(const char *needs_hashing)
{
    unsigned int hash = 0;
    for (int i=0, n=strlen(needs_hashing); i<n; i++)
        hash = (hash << 2) ^ needs_hashing[i];
    return hash % HASHTABLE_SIZE;
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    
    // set cursor to point to beginning of appropriate linked list
    node *cursor = hashtable[hash(word)];

    // traverse dictionary
    while (cursor != NULL)
    {
        // compare word to dictionary
        if (strcasecmp(word, cursor->word) == 0)
        {
            return true;
        }
        cursor = cursor->next;

    }
    return false;
}

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

    // Open dictionary
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        unload();
        return false;
    }

    // Buffer for a word
    char word[LENGTH + 1];

    // Read each word from the dictionary one at a time
    while (fscanf(file, "%s", word) != EOF)
    {
        // create a new node for each word
        node *n = malloc(sizeof(node));
        if(n == NULL)
        {
            unload();
            return false;
        }


        // Copy word into node
        strcpy(n->word, word);
        n->next = NULL;


        // insert node into hash table
        // points to what hashtable points to, the first node
        int j = hash(n->word);
        n->next = hashtable[j];

        // hashtable points to n
        hashtable[j] = n;

    }

    // Close dictionary
    fclose(file);

    // Indicate success
    return true;

}

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

    for (int i = 0; i < HASHTABLE_SIZE; i++)
    {
        // sets to head of the list
        node *cursor = hashtable[i];

        // traverse list
        while (cursor != NULL)
        {
            counter++;
            cursor = cursor->next;
        }
    }
    return counter;
}


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

Dictionary.h

#define DICTIONARY_H

#include 

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

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


#endif // DICTIONARY_H
</PRE>