0

I'm in a pickle here. I have followed walkthrough step by step for this part. But my code just keeps on refusing to load dictionary. (Sorry for the low quality code here)

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)
    {
        // TODO
        // Allocating memory for the new word
        node *n = malloc(sizeof(node));
        if (!n)
        {
            unload();
            return false;
        }
        //
        strcpy(n->word, word);
        n->next = NULL;
        //If the hash node isn't empty
        if (hashtable[hash(word)])
        {
            node *ptr = hashtable[hash(word)];
            n->next = ptr;
            hashtable[hash(word)] = n;
        }
        //If the hash node is empty
        else
        {
            hashtable[hash(word)] = n;
        }
    }

    // Close dictionary
    fclose(file);

    // Indicate success
    return true;
}

So here is the whole thing. I'm very new to this pointer and memory allocation business.

// Implements a dictionary's functionality

#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <cs50.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)
    {
        // TODO
        // Allocating memory for the new word
        node *n = malloc(sizeof(node));
        if (!n)
        {
            unload();
            return false;
        }
        //
        strcpy(n->word, word);
        n->next = NULL;
        //If the hash node isn't empty
        if (hashtable[hash(word)])
        {
            node *ptr = hashtable[hash(word)];
            n->next = ptr;
            hashtable[hash(word)] = n;
        }
        //If the hash node is empty
        else
        {
            hashtable[hash(word)] = n;
        }
    }

    // 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)
{
    // TODO
    unsigned int *size = malloc(sizeof(unsigned int));
    for (int i = 0; i < N; i++)
    {
        node *cursor = hashtable[i];
        while (cursor != NULL)
        {
            cursor = cursor->next;
            size++;

        }
    }

    return *size;
    free(size);
}

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // TODO
    // Determining which hashpointer should we use
    node *cursor = hashtable[hash(word)];
    // Converting uppercase to lowercase
    char *tmp = malloc((strlen(word) + 1) * sizeof(char));
    if (!tmp)
    {
        return 1;
    }
    for (int i=0; i < strlen(word); i++)
    {
        tmp[i] = tolower(word[i]);
    }

    while (cursor != NULL)
    {
        if (strcmp(cursor->word, tmp) == 0)
        {
            return true;
            free(cursor);
            break;
        }
        else
        {
            cursor = cursor -> next;
        }
    }
    free(cursor);
    return false;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // TODO
    // Iterate through all 26 hashtable head pointers
    for (int i = 0; i < N; i++)
    {
        node *cursor = hashtable[i];
        while (cursor != NULL)
        {
            node *temp = cursor;
            cursor = cursor -> next;
            free(temp);
        }
    }
    // Check if upload succeed
    for (int i = 0; i < N; i++)
    {
        if (hashtable[i] != NULL)
        return false;
        break;
    }
    return true;
}
  • So what do you mean by "keeps on refusing to load dictionary"? You seem to have some extra steps, but I don't see anything obviously wrong. Assuming hash to return a number between 0 and N-1, of course. Is there an error message? If so, which one? You could edit it into your question. – Blauelf Mar 22 '19 at 17:45
  • Thinking its the hash function. Not clear what you mean by "not loading dictionary." Is the program erroring out and saying "Dictionary not loaded" or does the program run but no words are found in the dictionary? IF it's the latter, the problem could be in check instead of load. Please edit the question and add the hash function, the declaration of the node structure and any other related code. Also, add a screenshot of the executing of the program including the command used to start it, the filenames used for input, and the output results (except the misspelled words if the list is long.) – Cliff B Mar 23 '19 at 0:52
  • To Cliff:Sorry for being so abstract earlier. will add hash function. I assume that dictionary didn't load, because all words from the text were marked as misspelled. and the size of the dictionary is zero. I tried again today today. Now I see words loaded into memory. Output shows as below: WORDS MISSPELLED: 17756 WORDS IN DICTIONARY: 253905384 WORDS IN TEXT: 17756 TIME IN load: 0.00 TIME IN check: 0.03 TIME IN size: 0.00 TIME IN unload: 0.00 TIME IN TOTAL: 0.03 Think now I will update the title to problem with "check" function. – jing wei Mar 23 '19 at 19:38
  • To Blauelf: Thanks for editing the file. it loads fine now. Would you mind taking a look of the Check function? – jing wei Mar 23 '19 at 19:46
1

First, you are correct in noting that if it is producing any kind of results other than an error message, the program is actually loading the files and running. (Perhaps you should review the speller.c file and understand it better? ;-) )

Next, you need to be more accurate in testing. Simply running one of the given files may not provide useful results. You'd need to know the results that SHOULD be produced in order to know more than whether the program runs. Run the program against two test files - a dictionary with a handful of words (say 5 or less) and a target file with a small number of words that you know will test conditions like spelled correctly, has an upper case but otherwise correct, incorrect spelling, has an apostrophe, etc. Then, you know what to expect and can compare the result to what is expected and know EXACTLY where to look for problems!

I will give you two big hints about pointers and malloc'd memory.

  1. When you allocate memory using malloc, it is neither initialized nor set to any given value. It contains garbage data left over from the last usage. ALWAYS INITIALIZE IT! This will fix a bunch of stuff!

  2. When incrementing or setting malloc'd memory using the pointer var, are you manipulating the contents of the memory location or are you manipulating the address of that location? Is it * or & ?

Kudos for walking the trie with independent code (assuming you get it to work) and for using mallocs and pointers to understand them. You should get the size function working with the existing code, for the practice if for no other reason.

However, there's a much simpler way to count the words in the dictionary. Count them as you go. That's my big hint on that.

Next, a best practice on when to use allocated memory at runtime. If the program needs an undefined amount of memory that will change with each run (or within each run), allocating memory at runtime is the choice. When a fixed amount of memory is needed, like a single int, then just allocate it as an int, or an array, or whatever.

There's overhead involved with allocating memory at runtime. If you need an int, use an int. It's the same size as the pointer and is far more efficient to directly access. Similar arguments can be made for other data types.

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

| improve this answer | |

You must log in to answer this question.

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