My speller program (part of pset5) works well and the output exactly matches that of the staff's solution. However, when I run my program through check50, I still get several errors per their script:
:) dictionary.c, dictionary.h, and Makefile exist
:) speller compiles
:) handles most basic words properly
:( handles min length (1-char) words
expected "MISSPELLED WOR...", not "MISSPELLED WOR..."
:( handles max length (45-char) words
expected "MISSPELLED WOR...", not "MISSPELLED WOR..."
:( handles words with apostrophes properly
expected "MISSPELLED WOR...", not "MISSPELLED WOR..."
:( spell-checking is case-insensitive
expected "MISSPELLED WOR...", not "MISSPELLED WOR..."
:) handles substrings properly
:) program is free of memory errors
Link: https://submit.cs50.io/check50/721776e0e89e2336ee7ac371f4b7fe01f48daf77
These errors are strange. My program definitely recognizes one-character words such as "a" and "i," takes apostrophes correctly, etc. I know this since I ran the staff's solution next to mine and programmatically compared the misspelled words in Excel: They all matched.
Here is my code. I can't find what makes check50 trip. Thanks to any brave soul who answers!
// Implements a dictionary's functionality
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <strings.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;
// Number of buckets in hash table
const unsigned int N = 26;
// Hash table
node *table[N]; // This looks like just the beginning of the list
// Variable added by me: A counter for each word added into the dictionary
int wordLoadedCount = 0;
// Returns true if word is in dictionary else false
// This is where the actual dictionary is put to work.
// check will only be passed words that contain letters and possibly apostrophes
bool check(const char *word)
{
// CASE INSENSITIVE
// 0. Remove apostrophes from the word [???]
// 1. Hash word to obtain a hash value
int index = hash(word);
// 2. Access linked list at the index in the hash table
//Pointer to the first node: table[index]
// 3. Traverse linked list, looking for the word.
// CODE FROM WEEK 5 LECTURE
// Print List / Loop Through Linked List
for (node *tmp = table[index]; tmp != NULL; tmp = tmp->next)
{
if (strcasecmp(word, tmp->word) == 0)
{
return true;
}
}
return false;
}
// Hashes word to a number
unsigned int hash(const char *word)
{
//Objective: Return a number from 0 to 25 given the first letter of the word.
//Initialize index variable
int index = 26;
//Check the first letter of the word and convert it to an index from 0 to 25:
// Convert the first number to its ASCII-equivalent int
int firstLetter = (int)word[0];
// Case: Uppercase letters
if (firstLetter >= 65 && firstLetter <= 90)
{
// We want index = 0 when ASCII value = 65
index = firstLetter - 65;
}
// Case: /Lowercase letters
else if (firstLetter >= 97 && firstLetter <= 122)
{
//We want index = 0 when ASCII value = 97
index = firstLetter - 97;
}
//Check to make sure the return value is actually between 0 and 25 (that the value
//was actually changed
if (index == 26)
{
printf("We could not hash %s.\n", word);
return -1;
}
//Return index as intended
return index;
}
// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
// 1. Open dictionary file
FILE *file = fopen(dictionary, "r");
// Intermediate check to see if the file opened
if (file == NULL)
{
printf("Could not open %s.\n", dictionary);
unload();
return false;
}
//Initialize a buffer variable where we are storing each word
char storedWord[LENGTH + 1];
// 2. Read strings from the file one at the time
while(fscanf(file, "%s", storedWord) != EOF)
{
//3. Create a new node for each word
node *newNode = malloc(sizeof(node));
//Check if malloc() returns NULL
if (newNode == NULL)
{
printf("You program ran out of memory\n");
return false;
}
//Copy the word into the newly created node using strcpy()
strcpy(newNode->word, storedWord);
newNode->next = NULL;
// Update "word loaded" count.
wordLoadedCount++;
// 4. Hash word to obtain hash value / index
int index = hash(storedWord);
//5. Insert node into the hash table at that location
// If this bucket of the hash table is empty (not pointing at anything yet)
// I'm not sure if this step is necessary
if (table[index] == NULL)
{
table[index] = newNode;
newNode->next = NULL;
}
// If it is not empty:
else if (table[index] != NULL)
{
//a. Point new node to the existing first node
newNode->next = table[index];
//b. Point the list head to the new node
table[index] = newNode;
}
}
//Close the file to release memory
fclose(file);
return true;
}
// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
// If the dictionary was loaded...
if (wordLoadedCount > 1)
{
// Go through hash stucture created in load() and count the words stored
// I will do this inside the load function itself
return wordLoadedCount;
}
// Return 0 if the dictionary not loaded
return 0;
}
// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
// Loop through each bucket in the hash table
for (int i = 0; i < N; i++)
{
// COPIED FROM WEEK 5 LECTURE CODE
// "Free list
// Since we're freeing each node as we go along, we'll use a while loop
// and follow each node's next pointer before freeing it, but we'll see
// this in more detail in Problem Set 5."
while (table[i] != NULL)
{
node *tmp = table[i]->next;
free(table[i]);
table[i] = tmp;
}
//Check to see if we did in fact clear the memory allocated to the hash table.
if (table[i] != NULL)
{
printf("Something went wrong while freeing memory in unload() function.\n");
return false;
}
}
//Return true if sucessful
return true;
}
Apologies as I first posted this on stackoverflow.com before discovering there was a CS50-specific StackExchange page.
