CS50 Problem Set 5 - Mispellings

dictionary.c

/**
 * dictionary.c
 *
 * Computer Science 50
 * Problem Set 5
 *
 * Implements a dictionary's functionality.
 */

#include <stdbool.h>
#include "dictionary.h"

// global variables
struct node* hashtable[SIZE];
int dicSize = 0;
char word[LENGTH +1];

void Push(struct node** headRef, const char* word) {
    
    struct node* newNode = malloc(sizeof(struct node));
    strcpy(newNode->word, word);
    
    if (*headRef == NULL)
        *headRef = newNode;
    else
    {
        newNode->next = *headRef;
        *headRef = newNode;
    }      
}

void PrintList(struct node* head) {
    
    struct node* current = head;
    
    while (current != NULL) {
        printf("%s ", current->word);
        current = current->next;
    }
    printf("\n");
}

void DeleteList (struct node** headRef) {
    
    struct node* current = *headRef;
    struct node* next;
    
    while (current != NULL) {
        next = current->next;
        free(current);
        current = next;
    }
    
    *headRef = NULL;
}

/**
 * Hash function. 2nd one found here: https://www.reddit.com/r/cs50/comments/1x6vc8/pset6_trie_vs_hashtable/cf9nlkn
 * 
 * 1st one found here: http://codereview.stackexchange.com/questions/85556/simple-string-hashing-algorithm-implementation
 * 
 */

/** 
int hash(char* word) {
    unsigned int hash = 0;
    while (*word)
        hash = (hash * 10) + *word++ - '0';
    return hash % SIZE;
}
*/

int hash(char* word) {
    
    unsigned int hash = 0;
    for (int i = 0, n = strlen(word); i < n; i++)
        hash = (hash << 2) ^ word[i];
    return hash % SIZE;
}

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char* word)
{
    // convert word to lowercase since all words in dictionary are lowercase
    int len = strlen(word);
    char tempWord[len+1];
    strcpy(tempWord, word);
    
    for (int i = 0; i < strlen(tempWord); i++) {
        if (tempWord[i] != '\'')
            tempWord[i] = tolower(tempWord[i]);
    }
    
    // get the hash value of the passed in word
    int index = hash(tempWord);
    
    // go to that index and search for the word
    struct node* current = hashtable[index];
    
    // if word is found return true
    while (current != NULL) {
        if (strcmp(current->word, tempWord) != 0) {
            current = current->next;
        }
        else {
            return true;   
        }
    }
    return false;
}

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    // open the dictionary
    FILE* dic = fopen(dictionary, "r");
    if (dic == NULL)
        return false;
    
    // scan through the dictionary word by word
    while (fscanf(dic, "%s\n", word)!= EOF)
    {
        dicSize++;
        int index = hash(word);
        Push(&hashtable[index], word);
    }
    fclose(dic); // close the dictionary file
    
    return true;
}

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

/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
bool unload(void)
{
    // iterate through entire SIZE of the hashtable array
    for (int i = 0; i < SIZE; i++) {
        if (hashtable[i] != NULL) // if something is there then delete the entire list there
            DeleteList(&hashtable[i]);
    }
    return true;
}

Hash table implementation.