1

I just can't get my speller program to work. I have been troubleshooting for several days with gdb, valgrind, testing different options etc. but I still have two basic problems.

  1. All words are misspelled. I believe this is caused by an error in the check function. Valgrind tells me "Conditional jump or move depends on uninitialised value(s)" for the strcmp function.

  2. The last word of the key text file is skipped which causes a seg fault. I thought the problem would be that I'm using eof as a loop condition in the load function. I tried using fgets instead but it didn't help.

I hope I'm not breaking any rules with this but below are my check and load functions. Any help will be very much appreciated. Thank you.

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

unsigned int counter = 0;
node* hashtable[26];

//Hash function
int hash_function(const char* key)
{
    int hash = tolower(key[0])-'a';
    return hash % 26;
}

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char* word)
{
    int len = strlen(word);
    char low[len+1];

    for (int i = 0; word[i] != '\0'; i++)
    {
        low[i] = tolower(word[i]);
    }
    low[len] = '\0';

    int b = hash_function(low);

    node* cursor = hashtable[b];

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

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
    //Initialize hash table
    for (int i = 0; i < 26; i++)
    {
        hashtable[i] = NULL;
    }

    //Open the dictionary
    FILE* inptr = fopen(dictionary, "r");

    //Check if dictionary contains words
    if (inptr == NULL)
    {
        printf("File does not exist.\n");
        return false;
    }

    //Check if end of dictionary is reached
    char buf[LENGTH+1];
    while(fgets(buf, sizeof(buf), inptr) != NULL)
    {
        //Assign space for a new word
        node* new_node = malloc(sizeof(node));

        //Copy word from buffer into new node
        strcpy(new_node->word, buf);

        new_node -> next = NULL;

        //Hash the word
        int a = hash_function(new_node->word);

        //Insert at beginning of linked list
        new_node->next = hashtable[a];
        hashtable[a] = new_node;
        counter++;
    }
    fclose(inptr);
    return true;
}

2 Answers 2

1

Meanwhile I was able to make the program work, it runs nicely now and passes check50 and valgrind. The problem was fgets and eof. I replaced fgets with fscanf which solved the problem with the misspelled words. I am not very sure why but apparently this is because fgets ignores whitespace. The segfault problem was solved by adding another feof loop condition after mallocing the new_node. feof only returns true once it tries to read past the last word. Thanks for taking a look at my code.

0

I recommend using gdb to step through your hash table after loading the dictionary. I have a hunch that you are not loading as many words as you think you are.

I don't want to give too much away, but have you considered what happens if the second item in the linked list of one of your hash table's indexes is also not NULL?

5
  • Hi Matt, thanks for the advice. I chose the easiest way by just inserting the word in the beginning of the linked list like this: new_node->next = hashtable[a]; hashtable[a] = new_node; counter++; I think the load functions works fine now. But I still get all words as misspelled and a seg fault in the end when using the large dictionary (there is no seg fault wth the small dictionary). Any idea what else might cause this problem?
    – Nic
    Jul 30, 2016 at 9:38
  • You will need to think about this more carefully. Jul 30, 2016 at 22:38
  • Let's say you add a word beginning with 'a' to your hashtable. You check to see if hashtable[0] is NULL. Since it is your first word beginning with 'a', the test returns TRUE (since it is NULL) and you can safely assign hashtable[a] = new_node;. All's right with the world. What happens with the second word beginning with 'a'? Your test for NULL will return FALSE, and you will execute new_node->next = hashtable[a]; So far, so good. What happens when you enter a third word beginning with 'a'? If this helps, be sure to upvote my answer above! Jul 30, 2016 at 22:48
  • I am no longer checking if hashtable[ ] is NULL, I decided to just add the words in the beginning of each linked list, I hope this is ok. According to gdb my load function works fine. Valgrind is also happy. I did a few other changes as well, please see above for my updated code. Unfortunately I still have both of my problems. With gdb's help I could figure out that there is a problem in the while loop inside the check function. The hashtable is built correctly, the loop runs through all words in the linked list but it doesn't detect whether a word is spelled correctly or not.
    – Nic
    Jul 31, 2016 at 9:35
  • Does anyone have an idea what's wrong with my code? Please, I'm really stuck. Thanks in advance.
    – Nic
    Aug 4, 2016 at 15:00

You must log in to answer this question.

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