0

After debugging for a long long time, it turned out that my hashtable must have some problem. Therefore, to find out where the problem is, I put this line of code after I insert a word in the hashtable. I suppose that this will print out just the first word in the first linked list. However, after I run my code, all the words in the dictionary are printed! Moreover, only words started with 'z' are fully printed, while other words, started with 'a' to 'y', are all printed "null" (just like the pictures below) By the way, whenever I run my code, the result always stops at MISSPELLED WORDS. Please help me figure this out! Thanks a lot!

printf("%s\n", hashtable[0]);

enter image description here enter image description here

// Represents number of buckets in a hash table
#define N 26

// Represents a hash table
node *hashtable[N];

// Initializes sizeCounter
int sizeCounter = 0;

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)
        {
            // Malloc a node* for each new word
            node *new_node = malloc(sizeof(node));
            if (new_node == NULL)
            {
                unload();
                return false;
            }

            // If it succeeds, copy the word into the node
            strcpy(new_node->word, word);

            // Insert into a linked list
            int hashCode = hash(word);
            printf("%i\n", hashCode);
            if (hashtable[hashCode] == NULL)
            {
                hashtable[hashCode] = new_node;
                new_node->next = NULL;
            }
            else
            {
                new_node->next = hashtable[hashCode];
                hashtable[hashCode] = new_node;
            }

            printf("%s\n", hashtable[0]);


            // Add 1 to count_size each time after inserting a word into a linked list
            sizeCounter++;

            // Free memory
            free(new_node);
        }

        // Close dictionary
        fclose(file);

        // Indicate success
        return true;
    }

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    int l = strlen(word);
    char *tempWord = malloc(sizeof(char) * (l + 1));
    for(int i = 0; i < l; i++)
    {
        tempWord[i] = tolower(word[i]);
    }
    tempWord[l + 1] = '\0';

    node *cursor = hashtable[hash(tempWord)];

    // Check whether word is in dictionary
    while (cursor != NULL)
    {
        if (strcmp(tempWord, cursor->word) == 0)
        {
            free(tempWord);
            return true;
        }

        else
        {
            cursor = cursor->next;
        }
    }

    free(tempWord);
    // If word not in dictionary
    return false;
}
3
  • Exactly how did you declare the hashtable[] array? I would think that printf("%s\n", hashtable[0]); would cause a compiler failure. Isn't hashtable an array of pointers? Can you please add all the relevant declarations, and the hash and check functions to the question?
    – Cliff B
    Sep 14 '19 at 21:06
  • I used "hashtable[0] -> word" instead of "hashtable[0]" as the second parameter of printf function at first, but it turned out that the results are the same. Thank you for reminding me, I have added those code to my question.
    – AvisTai
    Sep 14 '19 at 22:51
  • Still need the declaration for the node struct.
    – Cliff B
    Sep 16 '19 at 10:10
1

The code doesn't actually stop after MISSPELLED WORDS. It is actually going into an infinite loop. The line while (cursor != NULL) is looking for a NULL pointer value. Unfortunately, the nodes are not initialized when created, so the pointers contain garbage data. While that garbage data isn't a valid address, it's also not NULL. So, the while loop never ends. Hint: calloc() is your friend.

There are other problems that follow, but since you probably haven't had a chance to debug them, I'll leave it for you to find and fix them. If you can't, please open a new question and include the new code, including the node struct declaration.

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

2
  • Now, I change while (cursor != NULL) to while (cursor->next != NULL). But seems that it is still going into an infinite loop. But, why? I have built the dictionary in load function. It means each of the hashtables I initialized now has some nodes following after it, and the last node is pointing to NULL, right? Thus, I suppose that cursor will ultimately find a NULL and then break this loop. But the reality is that it is still a infinite loop... Need more detail, thanks.
    – AvisTai
    Sep 22 '19 at 2:58
  • Changing the test doesn't help. The underlying problem remains the same. When a new node is allocated with malloc, the memory space is created for the node, but the node elements are NOT initialized! The pointers are NOT set to NULL, they just contain whatever garbage data that was in that memory location when the node was allocated. The code needs to initialize every element in every node when created, by either explicitly initializing them, or by using calloc instead of malloc. (read the man pages for both calloc and malloc.)
    – Cliff B
    Sep 22 '19 at 12:43

You must log in to answer this question.

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