1

I'm getting pretty close to done with Speller but seem to have hit a snag. I can't really figure out why my load() function isn't working properly..it seems to skip over about 40,000 words in the large dictionary. The check() and unload() functions seem to be working ok. Could anybody take a look at my code and let me know where I may be going wrong in load(), or if load() is the problem? Below is my code:

    /**
 * Implements a dictionary's functionality.
 */
#include <stdbool.h>
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#include "dictionary.h"
//hashtable size is 2^16, should be enough buckets
#define HASHTABLE_SIZE 65536

//create struct type for node to hold length +1 for \0
typedef struct node{
    char word[LENGTH + 1];
    struct node *next;
}node;

//create the hashtable bucket array, set to null
node* hashtable[HASHTABLE_SIZE] = {NULL};

//create a hashing function, credit to delipity(staff) on cs50 reddit page
int hash_it(char* needs_hashing)
{
    unsigned int hash = 0;
    for (int i=0, n=strlen(needs_hashing); i<n; i++)
        hash = (hash << 2) ^ needs_hashing[i];
    return hash % HASHTABLE_SIZE;
};

//create an int to store word count
int word_count = 0;

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char *word)
{
    //find word length, make an arr to hold it, set last char to \0
    int word_len = strlen(word);
    char to_be_checked[word_len+1];
    to_be_checked[word_len] = '\0';

    //populate to-be_checked with lowercase word
    for(int i=0; i<word_len; i++){
        to_be_checked[i] = tolower(word[i]);
    }

    //use hash function to find index of str if in hashtable
    int index = hash_it(to_be_checked);
    node *n = hashtable[index];

    //while not pointing to null, compare words, return true if same, update n to next
    while(n != NULL){
        if(strcmp(to_be_checked, n->word) == 0){
            return true;
        }
        n = n -> next;
    }
    //return false if strcmp isnt same
    return false;
}

/**
 * Loads dictionary into memory. Returns true if successful else false.
 */
bool load(const char *dictionary)
{
    FILE* file = fopen(dictionary, "r");
    if(file == NULL){
        printf("Dictionary is null. try again.\n");
        return false;
    }

    //creates word array so words from dict have space to be stored in
    char word[LENGTH+1];

    //loop through all words in dict until end of file
    while(fscanf(file, "%s", word) != EOF){

        //for each word in dict, create a new node
        node* new_node = malloc(sizeof(node));

        //if node points to NULL, unload and return false
        if(new_node == NULL){
            unload();
            return false;
        }

        //copy word from dict into new node
        strcpy(new_node -> word, word);

        //create index for new word using hash function
        int word_index = hash_it(word);

        //if hashtable[word_index] is null, insert word at that index
        if(hashtable[word_index]==NULL){
            hashtable[word_index] = new_node;
            new_node -> next = NULL;
        }
        //else if hashtable[word_index] is taken, append newnode
        else{
            new_node->next = hashtable[word_index];
            hashtable[word_index] = new_node;
            word_count++;
        }
    }
    //close file and return true once loaded if succesful
    fclose(file);
    return true;
}

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

/**
 * Unloads dictionary from memory. Returns true if successful else false.
 */
bool unload(void)
{
    for(int i=0; i<HASHTABLE_SIZE; i++){
        //create pointer to first bucket
        node *cursor = hashtable[i];
        //traverse each bucket's linked list until NULL
        while(cursor != NULL){
            //create a temp pointer to cursor
            node *temp = cursor;
            //set cursor to point to next node in linked list
            cursor = cursor -> next;
            //free the memory allocated to temp pointer
            free(temp);
        }
    }
    return true;
    word_count = 0;
}

This is the output I get when running ./speller texts/austinpowers.txt:

WORDS MISSPELLED:     644
WORDS IN DICTIONARY:  103038
WORDS IN TEXT:        19190
TIME IN load:         0.03
TIME IN check:        0.01
TIME IN size:         0.00
TIME IN unload:       0.02
TIME IN TOTAL:        0.06

and this is the staff solution:

WORDS MISSPELLED:     644
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        19190
TIME IN load:         0.02
TIME IN check:        0.02
TIME IN size:         0.00
TIME IN unload:       0.02
TIME IN TOTAL:        0.05
1

You are only incrementing wordcount in your else statement, so you aren't counting all of the words.

1
  • Awesome thank you, I was looking at it so long I didn't see that mistake.. it passes all the tests now. – Michael Oct 3 '17 at 17:50

You must log in to answer this question.

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