I will add comments for any missing braces I add or indentation I change or for code I would change like so // NOTE blah blah blah
#include <ctype.h>
#include <stdbool.h>
#include <stdint.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;
// TODO: Choose number of buckets in hash table
const unsigned int N = 26;
// Hash table
node *table[N];
unsigned int wordss = 0;
// Returns true if word is in dictionary, else false
bool check(const char *word)
{
// TODO
int index1 = hash(word);
node *cursor = table[index1];
while (cursor != NULL)
{
if (strcasecmp(cursor->word, word) == 0)
{
return true;
}
cursor = cursor-> next;
}
return false;
}
// Hashes word to a number
unsigned int hash(const char *word)
{
// TODO: Improve this hash function
long sum = 0; // NOTE should probably make this unsigned
for (int i = 0; i < strlen(word); i++)
{
sum += tolower(word[i]);
}
return sum % N; // NOTE technically you should cast this result back to unsigned int.
}
// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
// TODO
FILE *input = fopen(dictionary, "r");
if (input == NULL)
{
printf("Could not open file.\n");
return false;
}
char word1[LENGTH+1];
while (fscanf(input, "%s", word1) != EOF)
{ // NOTE moved brace to new line for consistency
node *n = malloc(sizeof(node));
if (n == NULL)
{
printf("couldnt allocate memory \n");
return false; // NOTE you forgot to close the file before returning
}
strcpy(n->word, word1);
int index = hash(n->word);
if (table[index] != NULL)
{
n->next = table[index];
table[index] = n;
}
else
{
table[index] = n;
}
wordss = wordss + 1; // NOTE why not use words++ or wordss += 1??
} // NOTE moved this brace to proper indent level
// NOTE this now properly indented section is outside of the while loop
// NOTE this check is not needed, this failure is what got you out of the while loop in the first place
if (fscanf(input, "%s", word1) == EOF) // NOTE per above this should be removed.
{ // NOTE remove
fclose(input); // NOTE keep but unindent
return true; // NOTE keep but unindent
} // NOTE remove
fclose(input); // NOTE remove
return false; // NOTE remove
}
// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
// TODO
return wordss;
}
// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
// TODO
for (int i = 0; i < N; i++)
{
node *cursor = table[i];
while (cursor != NULL)
{
node *temp = cursor;
cursor = cursor->next;
free(temp);
}
return true; // NOTE this return should be outside the for loop!
}
}
Thoughts:
outside of the blatant error in unload where you are returning from the wrong spot which is absolutely going to prevent you from freeing all of the memory this code should pass the tests, and is functional. Not good, but should be functional.
You have a number of ways you could improve this, most notably would be considering keeping the node's in a given list in your table sorted in some fashion so that you don't have to search an entire 'basket' for each check every single time. That would help you regardless of your hash function, unless you are certain that your hash is so good that you have next to no hash collisions. With only 26 buckets, and more than 26 words you know that you will have significant hash collisions. But lets save that part for later. The focus is on you just getting some thing that functions basically and without memory errors.
Notes:
check(...): looks goodhash(...): looks good. A better hash function would be interesting but this should pass and works with your load and check functionload(...) : looks mostly good. Three points (two i mentioned above).
- you forget to close the file you were reading if you return false
- some really unneeded code at the end and I can't remember what the defined behavior is for that call since you already reached EOF to get out of the loop... but I don't think this is causing your memory errors or causing you to fail any tests.
- what should happen if they call
load after load without an unload? Or load, unload, load? which is the perfect segue to size
size() : looks good... only issue is you only ever increment it, never make use of it (and you really should), and it's incorrect after you unload a dictionary... what should size be after unload? what if you load, unload and load again?unload(): doesn't look good. You return early currently, on the first pass of the for loop. Secondly your return value is missing a very simple check you could make that would ensure consistency in your program and it's missing an assignment you should be making.. Think about this for a moment. What should size be after you call unload? If it were me I'd be decrementing wordss every time I free'd something, and making sure it was zero at the end, or I'd be incrementing a counter on each free and verifying that counter equaled size and then resetting size to zero before returning true. I dont know what I would do to size if they didn't match, but I kinda like my first idea because of this, in that it would tell me how many items I created but didn't free if you decrement it for each free. It would help perform a unit test that dictionary loads the right amount of words ( size check after load ) and definately unloaded everything ( size check inside of and after unload ), assuming they both returned true. And if one of them returns false, it gives me a clue about what went wrong. Also see my notes about size, what should size be after unload succeeds?
