cs50 pset 5 speller (updated)

dictionary.c

// Implements a dictionary's functionality

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

#include "dictionary.h"

#define HASHTABLE_SIZE 10000

// Defines struct for a node
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

node *hashtable[HASHTABLE_SIZE];

// Hashes the word (hash function posted on reddit by delipity)
// The word you want to hash is contained within new node, arrow, word.
// Hashing that will give you the index. Then you insert word into linked list.
int hash_index(char *hash_this)
{
    unsigned int hash = 0;
    for (int i = 0, n = strlen(hash_this); i < n; i++)
    {
        hash = (hash << 2) ^ hash_this[i];
    }
    return hash % HASHTABLE_SIZE;
}

// Initializes counter for words in dictionary
int word_count = 0;

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // Opens dictionary
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        return false;
    }
    // Scans dictionary word by word (populating hash table with nodes containing words found in dictionary)
    char word[LENGTH + 1];
    while (fscanf(file, "%s", word) != EOF)
    {
        // Mallocs a node for each new word (i.e., creates node pointers)
        node *new_node = malloc(sizeof(node));
        // Checks if malloc succeeded, returns false if not
        if (new_node == NULL)
        {
            unload();
            return false;
        }
        // Copies word into node if malloc succeeds
        strcpy(new_node->word, word);

        // Initializes & calculates index of word for insertion into hashtable
        int h = hash_index(new_node->word);

        // Initializes head to point to hashtable index/bucket
        node *head = hashtable[h];

        // Inserts new nodes at beginning of lists
        if (head == NULL)
        {
            hashtable[h] = new_node;
            word_count++;
        }
        else
        {
            new_node->next = hashtable[h];
            hashtable[h] = new_node;
            word_count++;
        }
    }
    fclose(file);
    return true;
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // Creates copy of word on which hash function can be performed
    int n = strlen(word);
    char word_copy[LENGTH + 1];
    for (int i = 0; i < n; i++)
    {
        word_copy[i] = tolower(word[i]);
    }
    // Adds null terminator to end string
    word_copy[n] = '\0';
    // Initializes index for hashed word
    int h = hash_index(word_copy);
    // Sets cursor to point to same address as hashtable index/bucket
    node *cursor = hashtable[h];
    // Sets cursor to point to same location as head

    // If the word exists, you should be able to find in dictionary data structure.
    // Check for word by asking, which bucket would word be in? hashtable[hash(word)]
    // While cursor does not point to NULL, search dictionary for word.
    while (cursor != NULL)
    {
        // If strcasecmp returns true, then word has been found
        if (strcasecmp(cursor->word, word_copy) == 0)
        {
            return true;
        }
        // Else word has not yet been found, advance cursor
        else
        {
            cursor = cursor->next;
        }
    }
    // Cursor has reached end of list and word has not been found in dictionary so it must be misspelled
    return false;
}

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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    node *head = NULL;
    node *cursor = head;
    // freeing linked lists
    while (cursor != NULL)
    {
        node *temp = cursor;
        cursor = cursor->next;
        free(temp);
    }
    return true;
}

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

#define N 26
#define LENGTH 45
#define TABLE_SIZE 1000

typedef struct node
{
char word[LENGTH + 1];
struct node *left;
struct node *right;
}
node;

// Hash table declaration
node *hash_table[TABLE_SIZE];

// Define a function to compute the hash index of a word
unsigned int hash_index(const char *str)
{
unsigned int hash = 0;
int c;

while ((c = *str++) != '\0')
{
    hash = hash << 1;
    hash = hash + c;
}

return hash % TABLE_SIZE;

}

// Define a function to compare two strings in a case-insensitive manner
int strcasecmp(const char *s1, const char *s2)
{
char c1, c2;

while (*s1 && *s2)
{
    c1 = toupper(*s1);
    c2 = toupper(*s2);

    if (c1 != c2)
    {
        return c1 - c2;
    }

    s1++;
    s2++;
}

return *s1 - *s2;

}

node *insert(node *root, const char *word)
{
// Base case: empty tree
if (root == NULL)
{
// Allocate memory for new node
node *new_node = malloc(sizeof(node));
if (new_node == NULL)
{
return NULL;
}
// Copy word into node
strcpy(new_node->word, word);
// Set left and right children to NULL
new_node->left = new_node->right = NULL;
// Return the new node
return new_node;
}

// Compare word with node word
int cmp = strcasecmp(word, root->word);

// Insert node in left subtree if word is smaller than node word
if (cmp < 0)
{
    root->left = insert(root->left, word);
}
// Insert node in right subtree if word is greater than node word
else if (cmp > 0)
{
    root->right = insert(root->right, word);
}
// Return the root of the tree
return root;

}

// Calculate the hash index of the word
bool check(const char *word, node *hash_table_arr[])
{
// Calculate the hash index of the word
int h = hash_index(word);

// Find the correct entry in the hash table
for (node *entry = hash_table[h]; entry != NULL; entry = entry->right)
{
    // If the word is found, return true
    if (strcasecmp(word, entry->word) == 0)
    {
        return true;
    }
}

// Return false if the word is not found
return false;

}

int main()
{
// ... (rest of the code remains the same)
}

Thank you so much! This code was very useful, but I just have one question. Why do you need to make a copy of the word in the check function? I just want to know how it works. Thank you.