0

my check function is returning an incorrect amount of misspelled words. I created test.txt file containing all and only the words in my small dictionary. Yet check is returning matches only for the head of each linked list (terminal output):

MISSPELLED WORDS

Word matched! apple
No word matching the following: aunt
Word matched! back
No word matching the following: beautiful
Word matched! club
No word matching the following: changes

Initially I thought it must have been because the links in list were not made correctly. Debug50 showed me that the node->next fields were filled. I've found that when traversing the list in check(), cursor->next is NULL so the while loop does not move down the list. Why does this happen? Here is my code below. Please and thank you.

   #include <ctype.h>
   #include <stdbool.h>
   #include <stdio.h>
   #include <string.h>
   #include <stdlib.h>

   #include "dictionary.h"

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

   // Represents a node in a hash table
   typedef struct node
   {
       char word[LENGTH + 1];
       struct node *next;
   }
   node;

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

   // Hashes word to a number between 0 and 25, inclusive, based on its first letter
   unsigned int hash(const char *word)
   {
       return tolower(word[0]) - 'a';
   }

   unsigned int Insert(int key, char *buffer);

   int count = 0;

   // node *head = NULL;

   // 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 dictionary file into hash table
       while (fscanf(file, "%s", word) != EOF)
       {
           // node *head = hashtable[hash(word)];
           Insert(hash(word), word);
           //traverse the list to count size
           count++;
       }

       // Close dictionary
       fclose(file);

       // Indicate success
       return true;
   }


   // Returns number of words in dictionary if loaded else 0 if not yet loaded
   unsigned int size(void)
   {
       if (!&load)
       {
           return 0;
       }
       else
       {
           printf("Count: %i\n", count);
           return count;
       }
   }

   unsigned int Insert(int key, char *buffer)
   {
       node *newnode = malloc(sizeof(node));
       node *head = hashtable[key];
       if(newnode == NULL)
       {
           fprintf(stderr, "Could not allocate memory for newnode.");
           //unload() TODO
           return 0;
       }
       // fill node fields
       strcpy(newnode->word, buffer);

       // if linked list at key is not empty,
       if (hashtable[key] != NULL)
       {
           newnode->next = hashtable[key];
           head = newnode;
           // printf("New node added: %s\n", head->word);
       }

       else
       {
           hashtable[key] = newnode;
           head = newnode;
           newnode->next = NULL;
       }

       return 1;
   }


   // Unloads dictionary from memory, returning true if successful else false
   bool unload()
   {
       for(int i = 0; i < N; i++)
       {
           int index = i;
           node *cursor = hashtable[index]; // returns null for some reason.
           while (cursor != NULL)
           {
               node *temp = cursor;
               cursor = cursor->next;
               free(temp);
           }
       }
       return true;
   }



   // Returns true if word is in dictionary else false
   bool check(const char *word)
   {
       int length = strlen(word);
       // allocate heap memory for the converted word to alter it.
       char *convertedWord = malloc(sizeof(char)  * (length + 1));

       // make sure the array includes the null char.
       convertedWord[length + 1] = '\0';

       // only allow check to run on valid words
       for (int i = 0; i < length; i++)
       {
           if (isalpha(word[i]) != 0 ||  (word[i] == '\'' && i > 0))
           {
               convertedWord[i] = tolower(word[i]);
           }
           else
           {
               fprintf(stderr, "Word cannot be checked.");
               return false;
           }
       }

       // hash the word
       int hashed = hash(convertedWord);

       // go to the right bucket of hash table
       node *cursor = hashtable[hashed];

       // traverse the dictionary to find word
       // *** problem area *** // temp becomes null after the first node.
       // could it be that cursor is breaking the list?
       while (cursor != NULL)
       {
           if (strcmp(cursor->word, convertedWord) == 0)
           {
               printf("Word matched! %s\n", convertedWord);
               return true;
           }
           else
           {
               cursor = cursor->next;
           }
       }
       printf("No word matching the following: %s\n", convertedWord);
       return false;
   } 
   ```






0

Look at the following code from your Insert() function:

   if (hashtable[key] != NULL)
   {
       newnode->next = hashtable[key];
       head = newnode;
       // printf("New node added: %s\n", head->word);
   }

It looks like it should insert a node, but it doesn't. The problem is head=newnode; This will reset head to point to the newnode, but that doesn't help. All that does is put the address of the newnode into head, while hashtable[key] still points at the first node that was inserted. The code needs to actually put the address of newnode in hashtable[key].

This is the most obvious problem to me. This error would make it impossible to add nodes to any of the linked lists after the first node.

This is a good demonstration of why you need to be careful with intermediate vars, and not to use them where they're not needed.

There may be more issues, but this should get you going.

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

You must log in to answer this question.

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