0

The code is here:

// Implements a dictionary's functionality

#include <stdbool.h>
#include "string.h"
#include <strings.h>
#include <ctype.h>
#include <cs50.h>
#include <stdlib.h>
#include <stdio.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 = 1000;

// Hash table
node *table[N];

// Count number of nodes
int num_nodes = 0;

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    
    
    int len = strlen(word);

    char words[len + 1];
    
    // convert word to lowercase and store it in word_copy
    for (int i = 0; i < len; i++)
    {
      words[i] = tolower(word[i]);
    }
    
    // add null terminator to end of char array
    words[len] = '\0';
    int hashed = hash(words);
    node *current = table[hashed];

  while (current != NULL)
  {
      if (strcmp(current -> word, words) == 0)
      {
          return true;
      }
      else
      {
          current = current -> next;
      }
  }
  return false;
}

// Hashes word to a number
// From Peter Weinberger
unsigned int hash(const char *word)
{
    unsigned int hash = 0;
    for (int i=0, n=strlen(word); i<n; i++)
        hash = (hash << 2) ^ word[i];
    return hash % N;
}

//Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    FILE *file = fopen(dictionary, "r");
    
    if (file == NULL)
    {
        printf("error reading file\n");
        return false;
    }
    char cur_word[LENGTH + 1];
    
    for (int i = 0; i < N; i++)
    {
        table[i] = NULL;
    }
     while (fscanf(file, "%s", cur_word) != EOF)
    {
        num_nodes++;
        int hashed = hash(cur_word);
        
        node *place = malloc(sizeof(node));
        if (place == NULL)
        {
            printf("unable to allocate memory \n");
            return false;
        }
        strcpy(place -> word, cur_word);
        
        if (table[hashed] == NULL)
        {
            table[hashed] = place;
            place -> next = NULL;
        }
        else
        {
            node *holder = table[hashed];
            table[hashed] = place;
            place -> next = holder;
        }
    }
    fclose(file);
    return true;
}

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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    for (int i = 0; i < N; i++)
    {
        node *tracker = table[i] -> next;
        free(table[i]);
        while(true)
        {
            if (tracker->next == NULL)
            {
                free(tracker);
                break;
            }
            node *current = tracker;
            tracker = tracker->next;
            free(current);
        }
    }
    return true;
}

and the check50 outputs this, and doesn't pass any test cases broken CS50

1

Have you thoroughly tested your code? I found that when I ran it with a small dictionary, it produced a seg fault in the unload() function.

There are issues in unload that need to be thought through. Interestingly, the problem only shows up when running a small dictionary. The full large dictionary doesn't produce the seg fault. But, since check50 does extensive testing with small dictionaries, it's failing there.

3
  • I hadn't run it on small dictionaries, but this is definitely true... let me check it out Jun 24 '20 at 4:57
  • I hadn't checked for NULL in the hash table, and assumed there was a "next"... works good now :) Jun 24 '20 at 5:01
  • How is your valgrind result?
    – Cliff B
    Jun 24 '20 at 5:08

You must log in to answer this question.

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