Sincerely, a confused CS50x student.
Sincerely, a confused CS50x student.
// Implements a dictionary's functionality
#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "dictionary.h"
// Represents a node in a hash table
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
} node;
// TODO: Choose number of buckets in hash table
const unsigned int N = 50492;
// Hash table
node *table[N];
// Returns true if word is in dictionary, else false
bool check(const char *word)
{
int j = strlen(word);
char nword[j];
nword[j] = '\0';
for (int i = 0; i < j; i++)
{
nword[i] = tolower(word[i]);
}
for (node *ptr = table[hash(word)]; ptr != NULL; ptr = ptr->next)
{
if (strcmp(nword, ptr->word) == 0)
{
return true;
}
}
return false;
}
// Hashes word to a number
unsigned int hash(const char *word)
{
// TODO: Improve this hash function
int hashArr[LENGTH + 1] = {139, 137, 127, 113, 109, 107, 103, 101, 97, 89, 83, 79, 73, 71, 67, 61, 59, 53, 47, 43, 41, 31, 29,
23, 19, 13, 7, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1};
int num = 0;
for (int i = 0; word[i] != '\0'; i++)
{
if (word[i] == '\'')
{
continue;
}
num += hashArr[i] * (tolower(word[i]) - 'a');
}
return num;
}
// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
for (int i = 0; i < N; i++)
{
table[i] = NULL;
}
FILE *dict = fopen(dictionary, "r");
if (dict == NULL)
{
return false;
}
node *ptr = NULL;
char c;
int idx = 0, h_idx = 0;
char nword[LENGTH + 1];
while (fread(&c, 1, 1, dict))
{
// end of line
if (c == '\n')
{
nword[idx] = '\0';
idx = 0;
ptr = malloc(sizeof(node));
if (ptr == NULL)
{
return false;
}
h_idx = hash(nword);
ptr->word[0] = nword[0];
for (int i = 1; nword[i - 1] != '\0'; i++)
{
ptr->word[i] = nword[i];
}
ptr->next = table[h_idx];
table[h_idx] = ptr;
}
// else append char into word buffer
else if (isalpha(c) || c == '\'')
{
nword[idx] = c;
idx++;
}
}
fclose(dict);
return true;
}
// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
// if cat hash not accessed, then dict not loaded
if (table[hash("cat")] == NULL)
{
return 0;
}
int count = 0;
for (int i = 0; i < N; i++)
{
for (node *ptr = table[i]; ptr != NULL; ptr = ptr->next)
{
count++;
}
}
return count;
}
// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
node *ptr;
for (int i = 0, lcount = 0; i < N; i++)
{
ptr = table[i];
while (ptr != NULL)
{
node *cursor = ptr;
ptr = ptr->next;
free(cursor);
}
}
return true;
}
