0

I need some help with problem. Below I have the check, load and size functions. When I run speller, it appears to load the entire dictionary, but the check function doesn't identify misspelled words.

Also size doesn't return number of misspelled words. Can anyone look at it and give me a guidance on where could possibly be the problem?

Thank you all in advance!

//structure for linked lists
typedef struct node
{
    char word[LENGTH +1];
    struct node *next;
}
node;

//hash function
int hash_function(const char *key, int M)
{
    unsigned long h;
    const char *us;
    us = (const char *) key; 

    h=0;
    while (*us !=0)
    {
        h=(h * BASE + *us)%M;
        us++;
    }

    return h; 
}

// initializing a hash table, head of the linked list and number of words
node *hash_table[27]; 
node *head=NULL; 
int words=0;

/**
 * Returns true if word is in dictionary else false.
 */

bool check(const char* word)
{    
    int a= strlen(word);
    char letters[a];
    strcpy(letters, word); 
    for (int f=0; f<a; ++f)
    {
        if (isupper(word[f]))
        {
            letters[f]=tolower(word[f]);
        }
    }
    letters[a]='\0';

    int b = hash_function(letters,strlen(letters));
    node *testing = malloc(sizeof(node));
    testing=hash_table[b];

    if (b>=0)
    {
        while (testing!=NULL)
        {
            if (strcmp(testing->word, letters)==0)
            {
                return true;
            }
            testing=testing->next;
        }
    } 

    return false;
}

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */

bool load(const char* dictionary)
{
    FILE *fp=fopen(dictionary, "r");

    if (fp==NULL)
    {
        printf("File dictionary could not be opened.\n");
        return false; 
    }

    while (!feof(fp))
    {
        node *new_node=malloc(sizeof(node));
        fscanf(fp, "%s", new_node->word);
        int h=hash_function(new_node->word, strlen(new_node->word));

        if (hash_table[h]==NULL)
        {
            hash_table[h]=new_node;
            head=hash_table[h];
            head->next=NULL;
            ++words;
        }
        else if (hash_table[h]!=NULL)
        {
            new_node->next=head->next;
            head->next=new_node;
            ++words;
        }
    }

    if(feof(fp))
    {
        return true;
        fclose(fp); 
    }

    return false;
    fclose(fp);
}

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

unsigned int size(void)
{
    return words;
}
1

There are a few small issues and one big one. Your load function has a severe flaw that is corrupting the construction of the tree. Look at the following code:

if (hash_table[h]==NULL)
{
    hash_table[h]=new_node;
    head=hash_table[h];
    head->next=NULL;
    ++words;
}
else if (hash_table[h]!=NULL)
{
    new_node->next=head->next;
    head->next=new_node;
    ++words;
}

This works fine if hash_table[h] == NULL, but if not, it is going to have problems. It's failing because head is not currently set to the active word. Instead, it is still pointing at whatever was assigned to it in a previous pass. Sometimes, it might be a word with the right hash, other times (and most often) not.

The use of head in this code is introducing opportunities for errors and is not necessary. All of the code can be implemented using hash_table[] and new_node, so why introduce another variable?

As for minor issues, you are processing one extra word (a blank word) when EOF is encountered before actually processing the EOF. This is throwing your dictionary word count off by 1. Next, in check() you assign letters[a] = '\0';, but it was created by char letters[a]; That means that letters[a] doesn't exist and you are overwriting the first byte of some other variable that is adjacent to it in memory. Remember, an array of length a, runs from 0 to a-1, not 1 to a.

I'll let you figure out how to fix both of these - can't deprive you of all the fun. ;-)

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

1
  • Thank you for coming back again. I did change the load function as follows if (hash_table[h]==NULL) { hash_table[h]=new_node; new_node->next=NULL; words++; } else { node *head=hash_table[h]; while (head->next!=NULL) { head=head->next; } head->next=new_node; new_node->next=NULL; words++; } the problem is it still loads the entire dictionary – dean.d Jan 24 '16 at 23:47

You must log in to answer this question.

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