0

I wrote check() and then I tried to test speller with dictionary/small and a text file I'd written myself, but the text file couldn't be opened. Is there a problem with the way I implemented load() or check(), or is there something else I'm doing wrong?

This is what the text file looks like:

cata

catterpiller

katerpillar

caterpillar

cat

And here's the code (up to right before unload(), since I haven't implemented that yet - I do need to figure out how to write it as a recursive function and what the base condition has to be):

/**
 * dictionary.c
 *
 * Computer Science 50
 * Problem Set 5
 *
 * Implements a dictionary's functionality.
 */

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

#include "dictionary.h"

/**
 * declaration for trie struct
 * and length of children array
 */

#define ARRAY_SIZE 27;

typedef struct node
{
    bool is_word;
    struct node* children[ARRAY_SIZE];
}
node;

/**
 * Keeping track of first node of trie here
 */
 node* root;

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char* word)
{
    for (int index = 0; index < ARRAY_SIZE; index++)
    {
        if (strcmp((char*)cursor->children[index], word) != 0)
        {
            return false;
        }
    }
    return true;
}

/**
 * variable to hold size of dictionary
 */
 unsigned int dict_size = 0;

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */

node* new_node;
FILE* dictptr;
bool load(const char* dictionary)
{
    dictptr = fopen(dictionary, "r");
    if (dictptr == NULL)
    {
        fclose(dictptr);
        exit(1);
    }
    root = calloc(ARRAY_SIZE, sizeof(node));
    if (root == NULL)
    {
        exit(1);
    }
    node* cursor = root;

    char word[ARRAY_SIZE + 1];

    for (int index = 0, n = strlen(word); index < n; index++)
    {
        new_node = calloc(ARRAY_SIZE, sizeof(node));
        if (new_node == NULL)
        {
            exit(1);
        }
        fscanf(dictptr, "%s", word);
        if (root->children[index] == NULL && root->children[index] == new_node)
        {
            if (isalpha(word[index]) || word[index] == '\'')
            {
                cursor = cursor->children[index];
                cursor = new_node;
                cursor = root;
                if (word[index] == '\n')
                {
                    cursor = cursor->children[index];
                    cursor = new_node;
                    cursor->is_word = true;
                    cursor = root;
                    dict_size++;
                }
            }
            else if (root->children[index] != NULL && root->children[index] == new_node)
            {
                if (isalpha(word[index]) || word[index] == '\'')
                {
                    cursor = cursor->children[index];
                    cursor = new_node;
                    cursor = root;
                    if (word[index] == '\n')
                    {
                        cursor = cursor->children[index];
                        cursor = new_node;
                        cursor->is_word = true;
                        cursor = root;
                        dict_size++;
                    }
                }
            }
        }
    }
    fclose(dictptr);
    return true;
}

 /**
 * Returns number of words in dictionary if loaded else 0 if not yet loaded.
 */
unsigned int size(void)
{
    return dict_size;
}    

Any help would be appreciated.

Edit: I just edited the above to update it with the code I have now.

0

You should not use LENGTH that way, that's the length of the longest word to consider, determines the maximum number of layers in the trie, but not the node structure.

The children array should have one entry per possible character (makes 26 for a..z, plus one for apostrophe, totalling 27).

In check, you should not allocate anything. And you cannot cast a char* to a node* (you can, but it has little meaning), you'd have to walk the trie instead, one character at a time. If you meet a NULL pointer, return false, else return the target node's is_word.

And please, look into calloc. Dereferencing a random pointer you get from malloc is not better than dereferencing a NULL pointer you get from calloc, at least you can check for NULL.

BTW, it's a bit pointless to call free with a NULL pointer.

You need some loop in load to load the whole dictionary.

Your loop should work with the length of the string stored in word, not with LENGTH, the maximum length that word could have.

The index to children should not be the position inside word, but some value derived from the character stored at that position of word. (For example: a or A => 0, b or B => 1, ..., \' => 26, or add one to those letters and make \' the 0, just be consistent)

The logic inside load is not really clear to me, probably based on some misconceptions about how a trie works.

7
  • I did use calloc on my end, I just haven't edited the original post to reflect that yet. In load, I'm trying to loop through the trie by setting the cursor to first point at root, and then to have point at new_node if it matches a word in the dictionary, try to add that word into the trie, set is_word to true and increment dict_size, set cursor back to root and move on. As for the index into children, how do you propose I fix that? – Osman Zakir Nov 18 '16 at 14:01
  • And how should I fix the problem where it can't open the text file? How should I traverse the trie in check if I don't allocate anything? I have no idea what root is storing before I initialize it in load(), after all. – Osman Zakir Nov 18 '16 at 14:02
  • The string a node is representing is stored only in it position within the trie, so you cannot compare a string and a node in any way. You have to traverse the trie character for character, picking the children's entry that corresponds to the current character (and not its position). I posted a suggestion on how one could do that transformation from character to number between 0 and 26. – Blauelf Nov 18 '16 at 14:06
  • You can't open it? Is dictptr getting a NULL value? – Blauelf Nov 18 '16 at 14:07
  • I can't open the text file that the program is supposed to spell-check. As for indexing into the children array, do I need a separate variable for that (it should still be an int, right?)? I guess I don't fully understand how to traverse a trie, though I do kind of understand what not to do when trying to delete a node and that I can't randomly access a trie or a linked list like an array. – Osman Zakir Nov 18 '16 at 14:11

You must log in to answer this question.

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