PSET 5 Check 50 errors

Question

I have implemented the four functions and although load is slow it seems to load all the words correctly, and spell checker seems to be working correctly. I think the problem could be at load or unload but I can't figure out what the problem is.

Here is the results from austinpower.txt

WORDS MISSPELLED: 644
WORDS IN DICTIONARY: 143091
WORDS IN TEXT: 19190
TIME IN load: 3.76
TIME IN check: 0.66
TIME IN size: 0.00
TIME IN unload: 0.00
TIME IN TOTAL: 4.42

/**************************************************************************** * dictionary.c * * Computer Science 50 * Problem Set 5 * * Implements a dictionary's functionality. ***************************************************************************/

#include <stdbool.h>
#include <stdio.h>
#include <cs50.h>
#include "dictionary.h"
#include <ctype.h>
#include <string.h>

//Prototypes
int hash_table(char *key);

//GLOBALS

typedef struct node {
        char word[LENGTH + 1];
        struct node *next;
    }node;

node *node_array[27] = {NULL};
unsigned int SIZE;

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char* word)
{
    //Copy const char word into temp_word for manipulation and to pass to hash key function
    char temp_word[sizeof(word + 1)];
    strcpy(temp_word, word);

    for(int i = 0, n = strlen(temp_word); i < n; i++)  // all caps are converted to lowercase
    {
        temp_word[i] = tolower(temp_word[i]);
    }

    int key = hash_table(temp_word);           
    node *crawler = malloc(sizeof(node));     //Set crawler to head to traverse list

    crawler = node_array[key];
    while(crawler->next != NULL)                     //traverse list comparing word with each word in list - return true if match is found.
    {
        int compare = strcmp(temp_word, crawler->word);
        if(compare == 0)
        {
            return true;
        }
        crawler = crawler->next;
    }
    printf("%s and %s\n", temp_word, crawler->word);
    return false;
}

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    //Open the file to be loaded for reading
    FILE *file = fopen(dictionary, "r");

    if(file == NULL)
    {
        printf("File does not exist or is corrupted\n");
        return false;
    }
    char temp_word[LENGTH + 1];
    node *crawler = malloc(sizeof(node));
    node *new_node = NULL;
    SIZE = 0;

    //Need to iterate through file until the end holding each string in a variable to be insterted into node_n->word
    while(fscanf(file, "%s", temp_word) !=EOF)
    {
       //printf("%s\n", temp_word);

        //Use temp_word as argument in hash function
        int key = hash_table(temp_word);

        //Use returned hash to input into array of structs if there is space in array
        if(node_array[key] == NULL)
        {
            node_array[key] = malloc(sizeof(node));
            strncpy(node_array[key]->word, temp_word, sizeof(temp_word));
            node_array[key]->next = NULL;
        }
        //If array location is used begin linked list
        else
        {
            crawler = node_array[key];          // <--- Searches through linked list until it reaches the end then adds node onto the end
            while(crawler->next != NULL)
            {
                crawler = crawler->next;
            }
            //Create new node and copy details
            new_node = malloc(sizeof(node));

            strncpy(new_node->word, temp_word, sizeof(temp_word));
            new_node->next = NULL;
            crawler->next = new_node;
        }
        SIZE++;  //Count words loaded to be passed to Size function
    }
            return true;
}

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

/**
 * Unloads dictionary from memory.  Returns true if successful else false.
 */
bool unload(void)
{
    node *crawler;
    node *node_free;
    //Loop through each element in array
    for(int i = 0, n = 26; i < n; i++)
    {
        crawler = node_array[i];     // <-- Set crawler to head
        while(crawler->next != NULL)   // <-- Crawl through linked list freeing nodes until we hit the end.
        {
            node_free = crawler;
            crawler = crawler->next;
            free(node_free);
        }
    }
    return true;
}

  //Create hash function which indexes words to an array of 26 linked lists - alphabet - Key will be 

int hash_table(char key[LENGTH + 1])
{
    int hash = toupper(key[0]) - 'A';
    return hash % 26;
}

Answer 1

Well, I looked at it anyways. First, your unload is seg faulting. You can work on that on your own.

Next, your check is failing because there is a logic error. Look at the following:

    while(crawler->next != NULL)  

This line will fail to check the last word in the linked list. The node for the last word will always have crawler->next == NULL, so the while loop will terminate before checking that word. That means up to 26 words (one for each hash) will never be found in the dictionary.

There are several memory leaks in the code, mostly because of this:

    node *crawler = malloc(sizeof(node));    
    crawler = node_array[key];

This creates a pointer, allocates memory to it, and then abandons that memory without freeing it. When a node (or any kind of pointer) is created, it does not have to have memory malloc'd to it. That is the separate operation of initializing it. You can set it to NULL or to some other memory that already exists. The following would be perfectly acceptable:

    node *crawler = node_array[key];   

As for the slow run time, that probably has a lot to do with the design of where you add each node. To add a node, the code walks each linked list to the end and adds a node there. You could more easily and more quickly add each new node to the beginning of each linked list. I'll leave it to you to figure out how.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)