0

I'm having trouble with the implementation of the PSET5 spell check code. I've looked through a lot of CS50 Stack Exchange posts, but haven't found any help. The problem is either in the check or in the load function. For lalaland.txt my implementation returns 15085 misspelled words, against 955 for the staff solution.

Help is much appreciated! :)

// Implements a dictionary's functionality

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

// Hash table
node *table[N];
int wordsindict;

//function declarations
void FreeLinkedList (struct node *del);

// Returns true if word is in dictionary else false
bool check(const char *word) {

    char s[LENGTH + 1];
    unsigned int len = strlen(word);

    //convert to lowercase and load into s, nullify rest
    for (int i = 0; i < len; i++) {
        s[i] = tolower(word[i]);
    }
    for (int j = len; j < LENGTH + 1; j++) {
        s[j] = '\0';
    }

    // Get hash
    int abc = hash(s);

    // Set new node to hash table address.
    node *tracker = table[abc];

    // Check if word is correct, loop over linked list
    while (tracker != NULL) {
        if (strncasecmp(tracker->word, s, LENGTH + 1) == 0) {
            free(tracker);
            return true;
        } else {
            tracker = tracker->next;
        }
    }

    free(tracker);
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word) {

    // djb2 algorithm, Adapted from: http://www.cse.yorku.ca/~oz/hash.html
    unsigned int nhash = 5381;
    int c;

    // As long as c is not a null pointer, use following formula to get hash
    while ((c  = *word++)) {
        nhash = ((nhash << 5) + nhash) + c;
    }

    return nhash % N;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary) {

    FILE *file = fopen(dictionary, "r");

    if (file == NULL) return false;

    // Fill table with Null pointers
    for (int i = 0; i < N; i++) {
        table[i] = NULL;
    }

    char word[LENGTH + 1];

    //get word and loop up to EOF
    while (fscanf(file, "%s", word) != EOF) {
        int len = strlen(word);
        char s[LENGTH + 1];

        // to lowercase, nullify rest
        for (int i = 0; i < len; i++) {
            s[i] = tolower(word[i]);
        }
        for (int j = len; j < LENGTH + 1; j++) {
            s[j] = '\0';
        }

        // get hash
        unsigned int abc = hash(s);

        // create new node every iteration
        node *n = malloc(sizeof(struct node));
        if (n == NULL) return false;

        // put word in node
        strcpy(n->word, s);
        n->next = NULL;

        // Set word in table pointer or between table pointer and first element
        if (table[abc] == NULL) {
            table[abc] = n;
        } else {
            n->next = table[abc];
            table[abc] = n;
        }
        wordsindict++;
    }
    fclose(file);
    return true;
}

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

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

// recursive function to free memory
void FreeLinkedList (struct node *del) {
    if (del == NULL) {
        free(del);
    } else {
        FreeLinkedList(del->next);
    }
}
0

In check, don't free any nodes. You still need them.

Unrelated, your FreeLinkedList makes little sense. In this code, the only value free could be called with is NULL, and free(NULL) does nothing.

1
  • Thanks. This solved the issue. A rubber duck might've helped, but I'd stared at it for so long. I changed the FreeLinkedList as well and it works now! – YouriR Mar 22 '20 at 11:12

You must log in to answer this question.

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