0
// Implements a dictionary's functionality

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

#include "dictionary.h"

// Represents number of buckets in a hash table
#define N 26

// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;

// Represents a hash table
node *hashtable[N];
// Hashes word to a number between 0 and 25, inclusive, based on its first letter
unsigned int hash(const char *word)
{
    return tolower(word[0]) - 'a';
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    // Initialize hash table
    for (int i = 0; i < N; i++)
    {
        hashtable[i] = NULL;
    }

    // Open dictionary
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        unload();
        return false;
    }

    // Buffer for a word
    char word[LENGTH + 1];

    // Insert words into hash table
    while (fscanf(file, "%s", word) != EOF)
    {
        int index = hash(word);
        node * node1=malloc(sizeof(node));
        strcpy(node1->word,word);
        node1->next = NULL;
        if(hashtable[index]==NULL)
        {
            hashtable[index]=node1;
        }
        else
        {
            node1->next=hashtable[index];
            hashtable[index]=node1;
        }
    }

    // Close dictionary
    fclose(file);

    // Indicate success
    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size(void)
{
    unsigned int size=0;
    for (int i = 0; i < N; i++)
    {
        node* trav;
        for(trav = hashtable[i];trav !=NULL;trav=trav->next)
        {
            size+=1;
        }
    }
    return size;
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    int len = strlen(word);
    char new2[len+1];
    new2[len]='\0';
    for(int i = 0; i<len;i++)
    {
        if(word[i]!='\'')
        {
        new2[i]=tolower(word[i]);
        }
        else
        {
            new2[i]=word[i];
        }
    }
    for(node * right_list = hashtable[hash(word)];right_list!=NULL;right_list = right_list->next)
    {
        if(strcmp(right_list->word,new2)==0)
        {
            return true;
        }
    }
    return false;
}


void free_node(node*node1)
{
    if(node1->next == NULL)
    {
        free(node1);
    }
    else
    {
        free_node(node1->next);
        free(node1);
    }
}


// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    for(int i = 0;i<26;i++)
    {
        free_node(hashtable[i]);
    }
    return true;
}

For some reason my code executes perfectly fine and finds all of the misspelled words, but when I compare it to check50, it fails and I can't find out why. I used the diff -y thing and that worked also I didnt leak any memory.

1
  • Can you show as your sample output, what check50 says about your program. From just looking at your code how long did it take for it to finish checking a txt file?? It might be because time spent for the code.. Your N is only 26 which is so little for 140,000+ words, and your hash table is not really well designed. My advice would be to find a hash function online there are millions online that you could use and make you hash table bigger because 26 buckets for 140k words... That would mean that each bucket would have at least 5000 words which would be very inefficient to search through.
    – Ojou Nii
    May 18 '20 at 10:22
1

At a cursory read, it looks like free_node will fail if any hashtable[i] is NULL. That will happen with the small dictionary for example (and as one can see from the CS50 report, the tests are not using the large dictionary).

If hashtable[i] is null then this line if(node1->next == NULL) will fail, because NULL does not have a next member.

In my experience, this pset can and will pass with a 26 member hashtable.

1
  • you are a legend. For some reason that bug didn't cause valgrind to tell me that I leaked memory, I guess because I only tested it on large dictionaires. Also, on smaller dictionaries, the functions for checking the give words still worked perfectly since it came before the unload function, so this bug would have been nearly impossible for me to find, thank you so much. May 22 '20 at 9:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .