Pset5: speller.c listing all checked words as misspelled

Question

i implemented a trie and i think i have the load function sorted out, the check function however when i go through it with the GDB something weird happens and i can not figure out what that is. i tried changing alot of changes in the check function but still with no results.

here's my code:

 #define LETTERS 27


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

#include "dictionary.h"
 char c;
 char child[27];

typedef struct node {
        bool istrue;
        struct node* child[27];
    }
    node;
    node* root;

    int wordcount=0;

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char* word)
{
    root = malloc(sizeof(node));
     char Words[45];

   node* traverse = root;
    for(int K=0; K< strlen(word); K++)
    {
        Words[K] = word[K];
        if(isalpha(Words[K]))
        {
         Words[K]=tolower(Words[K]);  
        }
        else if(Words[K] == '\'')
        {
            Words[K] = 173;
        }



        if(traverse-> child[Words[K]-'a'] == NULL)
        {
            return false;
        }
       else if( word[K] != '\0')
        {
            traverse = traverse ->child[Words[K]-'a'];
        }
    }
    if(traverse ->istrue == true)
        return true;


        return true;
}

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
  root = malloc(sizeof(node));
   for(int u=0;u<27;u++)
    {
        root ->child[u] = NULL;
    }
    root ->istrue = false;
node* node_pntr = root;
    for(int u=0;u<27;u++)
    {
       node_pntr ->child[u] = NULL;
    }
    //opening the file to read from
    FILE* fp = fopen(dictionary, "r");
    if (fp== NULL)
    {
        printf("Could not open file");
        return false;
    }

    for(c =fgetc(fp); c != EOF; c=fgetc(fp))
    {
        if(c == EOF){
            node_pntr -> istrue = true;
            wordcount++;
            break;
        }
        else if(c == '\n')
        {
            node_pntr ->istrue = true;
            wordcount++;
            node_pntr = root;
        }
        else
        {
            if(c == '\'')
            {
                c= 173;
            }
            else
            c = tolower(c);
            if(node_pntr ->child[c-'a'] == NULL)
            {
                node_pntr ->child[c-'a'] = malloc(sizeof(node));
            }
            node_pntr= node_pntr -> child[c-'a'];
        }
    }
        fclose(fp);
    return true;
}

thanks :)

Answer 1

Didn't really look into the code because there's a major problem right at the beginning of check(). Look at the following:

bool check(const char* word)
{
    root = malloc(sizeof(node));

As soon as check() is executed, the entire trie is lost because a new address is assigned to root. The trie is still out there somewhere, but the one pointer to it, root, has been changed, so the trie has effectively been thrown away.

The check() function should not be altering any data in the trie, it should only be looking at it. If it changes something, it is altering the dictionary and corrupting it for later checks.

I'd also look very closely at how you are handling the asterisk. Setting it to 173 has a couple of issues. First, 173 - 'a' = 60, well outside the range of 0 to 26. And then, there's the problem that a char acts like a signed 1 byte integer, so that 173 gets treated like a two's complement version of a negative number. Either way, it's probably not doing what you expect. I wouldn't be surprised to see a seg fault with a large dictionary and text.

I don't know if the rest of the code works or not because this bug is so destructive that there's no point to look. Besides, you should have the first chance to debug the rest. ;-)

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

Answer 2

I'd be very surprised if all words are listed as misspelled. The check function always seems to return true.

      if(traverse ->istrue == true)
        return true;


        return true;
}