0

My function returns this:

WORDS MISSPELLED:     375902
WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        376904
TIME IN load:         0.02
TIME IN check:        1.20
TIME IN size:         0.00
TIME IN unload:       0.00
TIME IN TOTAL:        1.22

I don't understand what's going on - I've been grinding my gears on this problem and cannot find the origin of this issue. Check seems fine, so the problem must be in load right? But counter prints the correct number and adding a printf below table[index]->word and tmp->word will "seemingly" print the entire dictionary. So I'm very confused here - what the hell is going on?

bool check(const char *word)
{
    unsigned int index = hash(word);
    node *cursor = table[index];
    if(table[index] == NULL)
    {
        return false;
    }
    while(cursor != NULL)
    {
        if(strcasecmp(word, cursor->word) == 0)
        {
            return true;
        }
        cursor = cursor->next;
    }
    return false;

}

// Hashes word to a number
unsigned int hash(const char *word)
{
    unsigned int hashcode;
    for(int i = 0; word[i] != '\0'; i++)
    {
        char c = word[i];
        sumstring += c;
    }

    hashcode = sumstring % 10;
    return hashcode;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    for(int i = 0; i < 10; i++)
    {
        table[i] = NULL;
    }

    FILE *dicfile = fopen(dictionary, "r");
    if(dicfile == NULL)
    {
        fclose(dicfile);
        return false;
    }
    buffer = malloc(sizeof(char) * LENGTH);

    while(fscanf(dicfile, "%s", buffer) != EOF)
    {
    unsigned int index = hash(buffer);


    if(table[index] == NULL)
    {
        table[index] = malloc(sizeof(node));
        strcpy(table[index]->word, buffer);
        table[index]->next = NULL;
    }
    else
    {
        node *tmp = table[index]->next;
        while(tmp != NULL)
        {
            tmp = tmp->next;
        }
        tmp = malloc(sizeof(node));
        strcpy(tmp->word, buffer);
        tmp->next = NULL;
    }
    counter++;
    }
    free(buffer);
    fclose(dicfile);
    return true;
}

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

// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
    for(int i = 0; i < N; i++)
    {
    node *tmp = table[i];
        while(tmp != NULL)
        {
            node *tmp_2 = tmp;
            tmp = tmp->next;
            free(tmp_2);
        }
    }
    return true;
}
2
  • Which text file is this?
    – Vsjain
    Mar 18 at 15:17
  • All text files get 99% misspelled, but I believe this one is aca.txt Mar 18 at 17:51
1

First, since the global declarations and other code that comes at the top of the file weren't included, I've had to guess at some things to test the code.

I suspect that sumstring, used in the hash function, is declared as a global. If so, that's a big problem here. Since it's not initialized inside of the hash function, it is also not reset between calls. The value stored in sumstring is preserved from each call to hash() through to the next call. Thus, the calculated value for any word is totally unpredictable and indeterminate. The same word can generate different hash values on each pass. This is one of the main reasons why global variables are so frowned upon. They should only be used when absolutely necessary, and well justified.

Your suspicion that there's a problem in load is correct. Testing with a small dictionary shows that for a given hash value, any word after the first one in the linked list will be shown as misspelled. That's because no words are being stored after the first in each of 10 linked lists.

The problem lies here:

else
{
    node *tmp = table[index]->next;
    while(tmp != NULL)
    {
        tmp = tmp->next;
    }
    tmp = malloc(sizeof(node));
    strcpy(tmp->word, buffer);
    tmp->next = NULL;
}

The logic is to use tmp to find the end of the linked list. As written, the result will always be the same. When the loop finishes, tmp = NULL. It doesn't save the last valid address at all.

But then, even if it did save the address of the last node, new memory is malloc'd and the address of that new memory is stored in tmp. This action overwrites the address that was just found. The new node's address is never actually added to the linked list.

A rewrite of this is in order. First, consider starting by creating a new node and populating it with the current word and setting the next pointer to NULL. THEN, and only then, add the new node to the tree.

When adding the new node, it's far more efficient to insert the new node at the beginning of the linked list than the end. (This because an ordered list is not needed here.)

This should get you going again. There may well be other issues though, and your new code may or may not add new issues. Happy coding! ;-)

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

2
  • To me the logic of my load function appears sound: the temporary node pointer points to the pointer after the first element of the table. If it is not NULL, iterate till NULL is reached. When it is reached, allocate memory to the temporary node and save the word in it. Finish by setting the end point (NULL) as the next pointer. I will, however, try out your solution, if it works I'll accept your answer. Thank you very much in advance! Mar 18 at 23:28
  • Finally! I passed the problem! Thank you very much, your elaborate answer helped alot! Also - I knew my hash function was a piece of dung, but not to the extent that it actually was! 125 seconds to run shakespeare hahaha! That terrible function surely wasn't doing any favours. Mar 19 at 14:17

You must log in to answer this question.

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