2

my dictionary.c is running but it simply marks every word as misspelled. Also check50 says itsnot compiling. Which it is clearly... Anybody has any ideas? Here my code

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

#include "dictionary.h"


typedef struct node
{
    bool isWord;
    struct node* node[27];
}
node;
node* root;
int wordCount = 0;
int index = 0;
int nodeIndex;
char charWord;

bool check(const char* word)
{
    struct node* cursor = root;

    //for each letter
    while(word[index] != '\0')
    {
        //if in the alphabte set node
        if(isalpha(word[index]))
        {
            //if letter is uppercase
            if(isupper(word[index]))
            {
                nodeIndex = word[index] - 'A';
            }
            //if letter is lower case
            else
            {
                nodeIndex = word[index] - 'a';
            }
        }
             //if letter is apostrophe, set node index
             else
             {
                 nodeIndex = 26;
             }
            // go to corresponding element in children, word is misspelled if NULL
            if(cursor ->node[nodeIndex] == NULL)
            {
                return false;
            }
            //if not
            else
            {
                //move to next letter
                cursor = cursor -> node[nodeIndex];
            }


        index++;
    }
    if(cursor ->isWord ==true)
    {
        return true;
    }
    return false;
}

bool load(const char* dictionary)
{
    struct node* cursor = root;

    // open textfile
    FILE* fp = fopen(dictionary, "r");
    if(fp == NULL)
    return false;

    root = (struct node*) malloc(sizeof(node));
    char word[LENGTH +1];

    //for each word in the dictionary
    for( int c = fgetc(fp); c != EOF; c = fgetc(fp))
    {
        //if it is the end of a string
        if(c =='\n')
        {
            word[index] = c;
            // insert word in trie
            wordCount++;

            for(int i = 0; i<= index; i++)
            {
                // if character is in alphabet
                if (isalpha(charWord))
                {
                    //if element is NULL , malloc a new node
                    if(cursor -> node[charWord - 'a'] == NULL)
                    {
                        cursor -> node[charWord - 'a'] = (struct node*) malloc(sizeof(node));
                    }
                        cursor = cursor -> node[charWord - 'a'];

                }
                //if character is an apostrophe
                else if(charWord == '\'')
                {
                    //if element is NULL, malloc a new node
                    if(cursor -> node[26] == NULL)
                    {
                        cursor -> node[26] = (struct node *) malloc(sizeof(node));
                    }
                    cursor = cursor -> node[26];
                }
                //if end of word is reached
                else if(charWord == '\n')
                {
                    cursor -> isWord = true;
                }
            }
            index = 0;
        }

        else 
            {
            word[index] = c;
            index++;

            }

    }

    fclose(fp);
    return true;

}
2
  • can you please add all of the global declarations from dictionary.c? Also, have you altered any other files, like dictionary.h or speller.c?
    – Cliff B
    Aug 2 '16 at 20:41
  • I edited it. And I haven't altered any other file. Maybe that's the mistake? I wanted to, but I felt insecure which one to alter and also if it´s really necessary... so I decided not to do it. I didn`t want to make it worse..
    – user10882
    Aug 3 '16 at 7:34
1

Take a closer look at your load() function. The most common reason for every word to be misspelled is a lack of words in the dictionary. In particular, since you are using a trie data structure to store the words in memory, make certain that you do not malloc() a new node before testing to see whether it is NULL or exists already. If this is the case, valgrind should alert you to a memory leak.

5
  • I don't think this is the problem, as the program output tells me that it found 143091 words in the dictionary and I think that´s all of them... It says misspelled words 29758 and words in text 29758 though... Anyway I edited my load function. Maybe I am just not seeing it...
    – user10882
    Aug 2 '16 at 17:59
  • also valgrind doens´t give me any errors...
    – user10882
    Aug 2 '16 at 18:46
  • OK, I trust the program output ... if it says that you are actually loading 143091 words, then your trie must be loading properly. I can't see exactly what's wrong with check() ... I wonder whether your cursor position is off by one when you check the value of cursor->isWord. I recommend stepping through very closely with gdb and printing values of struct members as you go. Aug 2 '16 at 22:40
  • Thank you for your help.
    – user10882
    Aug 3 '16 at 7:35
  • 1
    Never assume that something is working properly. PROVE it or DISprove it! There were 0 words actually going into the trie. It was only counting the words read from the dictionary file. See my answer for more. ;-)
    – Cliff B
    Aug 3 '16 at 9:09
1

Oh, my. There's a lot of work to be done. Because of this, I only looked at load. I haven't looked at check at all.

There are at least three problems that I see. First, although you are counting how many words are being read from the dictionary file, none are going into the trie. The load()function depends highly on each letter of the word being in charWord, but charWord is never initialized and no letters are ever copied into it. Nothing is ever being processed! If you want a more accurate count of words actually added to the dictionary, you should increment wordCount right after you set isWord = true. This is the only place in the code that positively confirms that a word has been added to the trie (it may not be right, but it has been added.)

Next, once that's fixed, you have this:

 if(cursor -> node[charWord - 'a'] == NULL)

The problem here is that you will get to a place in the tree where cursor == NULL, so cursor -> node[x] doesn't exist, no matter what x is, so this if statement will generate a seg fault.

Third, if the code were to successfully process a word, cursor is not reset to point at root, so the next word will, at best, be tacked onto the end of the previous word. The only word that will ever be found is the first word from the dictionary. (If it happens to be "a", then maybe 2 words.)

Some notes on efficiency.

Your program reads one letter in at a time and stores it in a char array. The code only processes the word into the trie after the whole word is read in. Instead, you could read each word in at once, using fscanf(). This will dramatically cut the processing time for load by the average length of words in the dictionary. (If the average word is 6 letters plus linefeed, the processing time should be cut to about 1/7 depending on hardware.) This is because of the overhead and inefficiency of a disk read. You will be doing 1 read per word instead of 1 read per letter or linefeed.

When mallocing nodes, it isn't necessary to cast them as (struct node *).

You might want to take a look at the global vars that you declared. If you find any that are only used in a particular function, you should declare them as local vars inside that function. Even vars that are used in multiple functions should be examined. If the values in them do not need to be carried from one function to another, and the var just happens to be used in multiple functions, then they should be local, like index, nodeIndex and charWord. Global vars should be kept to an absolute minimum, like root and wordCount.

This will get you going, and there may be more issues to come.

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 .