0

I did ask this on Ed Forums so my apologies if you're sick of seeing it - but I'm still so stuck!!!

I get almost the right number of misspelled words on whatever text I use but it's off by the first 70-90 words which are all seen as misspelled (mind you, it's not the first 70-90 in a row, some are checked correctly.

When I've outputted it to a txt file it shows the correct number of misspelled words identified (not sure if I am simply not understanding what doing this should do)

When I compare side by side my output and the answer keys, they match.

I'm so incredibly confused and I've been working on this for two weeks and really really want to work it out! Please point me in the right direction, thank you.

int word_count = 0;

// 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 = 46000;

// Hash table

node *table[N];

// Returns true if word is in dictionary, else false

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

// Hashes word to a number

unsigned int hash(const char *word)
{
    // DJB Hash Function

    unsigned long hash = 5381;
    int c;
    int wordlength = strlen(word);
    char *hashword = malloc(sizeof(char) * wordlength + 1);

    for (int i = 0; i < wordlength; i++)
    {
        hashword[i] = tolower(word[i]);
    }

    while ((c = *hashword++) != '\0')
    {
        hash = ((hash << 5) + hash) + c; // hash * 33 + c;
    }

    return (hash % N);
}

// Loads dictionary into memory, returning true if successful, else false

bool load(const char *dictionary)
{
    // Open the file.

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

    // Check for NULL.
    if (dict == NULL)
    {
        return false;
    }

    // Define array to read words into.
    char dicword[LENGTH + 1];

    // Read the file into memory
    while (fscanf(dict, "%s", dicword) != EOF)
    {
        node *n = malloc(sizeof(node));

        if (n == NULL)
        {
            return false;
        }

        strcpy(n->word, dicword);
        n->next = NULL;

        n->next = table[hash(n->word)];
        table[hash(n->word)] = n;
        word_count++;
    }

    fclose(dict);
    return true;
}

// Returns number of words in dictionary if loaded, else 0 if not yet loaded

unsigned int size(void)
{
    if (&load == false)
    {
        return 0;
    }

    else
    {
       return word_count;
    }
}

// Unloads dictionary from memory, returning true if successful, else false

bool unload(void)
{
    int i = 0;
    node* tmp = table[i];
    for (i = 0; i < N; i++)
    {
        while (tmp != NULL)
        {
            tmp = table[i]->next;
            free(table[i]);
            table[i] = tmp;
        }

        free(table[i]);
    }

    return true;
}
2
  • Please put 3 backticks above and below your code to format it as code. May 4 at 12:49
  • Or, just highlight the code and then click on the curly braces in the tool bar above.
    – Cliff B
    May 4 at 23:04
1

I didn't do a deep dive, but something jumped out at me early. If this doesn't fix it, leave a comment and I'll look again.

Given that you're getting mostly correct results, its reasonable to assume that most of the code is working. So I'm immediately suspicious of the hash function. Now, look at this section of it:

int wordlength = strlen(word);
char *hashword = malloc(sizeof(char) * wordlength + 1);

for (int i = 0; i < wordlength; i++)
{
    hashword[i] = tolower(word[i]);
}

while ((c = *hashword++) != '\0')

The while loop depends on finding '\0', the end of string marker. But I don't see anywhere in the code where the EOS marker is written to hashword[]. That means that the code will continue looping until it finds a random 0x00 in memory that follows. That means the results are unpredictable and based solely on what was in memory prior to each pass of the loop. Also, the same word can potentially produce a different hash.

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

2
  • 1
    Oh bless you. What a simple mistake when it's pointed out - I don't think I'd ever have spotted that! I will be sleeping far better tonight! Thank you so much!
    – 1598523
    May 6 at 14:25
  • Not to worry. This is a very common problem for new programmers. I remember doing it a lot myself! ;-) Functions like strcpy() automatically copy the \0, but when loading a string, ie, char array, one char at a time, it often gets overlooked.
    – Cliff B
    May 6 at 19:22

You must log in to answer this question.

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