0

So, I have struggled with this set for a long time and managed to answer many questions myself, but this one I don't even know where to look.

The only test I fail is the max length, so I thought maybe I wasn't allowing enough characters but the check returned is this:

enter image description here

If I understand correctly my program has both said the word is misspelled AND that it is in the dictionary. I'm not sure where to look for the error. I have run my program and it counts an extra word in the text for the text with the max length word. It does not do this on other short texts I have tried. Any help appreciated.

I haven't changed dictionary.h, so here's the code for dictionary.c:

/**
* Implements a dictionary's functionality.
*/

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

#include "dictionary.h"

const int CHARACTERS = 27;
unsigned int wordcount = 0;

//new structure node: contains bool to determine if is end of word and pointer to array
typedef struct node
{
    bool word_complete;
    struct node* child[CHARACTERS];
}
node;

//create root node
struct node* root = NULL;

struct node* newNode()
{
    //allocate new node memory and automatically assign end of word a value of false
    struct node* next = NULL;
    next = (struct node*)calloc(1, sizeof(struct node));
    next->word_complete = false;

    //set pointer to first empty place in array
    for (int i = 0; i < CHARACTERS; i++)
    {
        next->child[i] = NULL;
    }
    return next;
}

void insert(const char* string)
{
    //start at root
    struct node* current = root;

    while (*string != '\n')
    {
        //create new node if no path
        if (current->child[*string - 'a'] == NULL)
        {
            current->child[*string - 'a'] = newNode();
        }

        //next node
        current = current->child[*string - 'a'];

        //next character
        string++;
    }
    //mark end of word
    current->word_complete = true;
    wordcount++;
}

bool search(struct node* root, char* string)
{
    //false if Trie empty
    if (root == NULL)
   {
        return false;
    }

    //set current node to root
    struct node* current = root;
    while(*string)
    {
        //go to next node
        current = current->child[*string - 'a'];

        //if string not in Trie (reached a NULL value)
        if (current == NULL)
        {
            return false;
        }

        //go to next character
        string++;
    }
    //if reach end of string: is word
    return current->word_complete;
}

/**
 * Loads dictionary into memory. Returns true if successful else false.
*/
bool load(const char *dictionary)
{
    root = (struct node*)calloc(1, sizeof(struct node));

    //check memory??
    if (root == NULL)
    {
        fprintf(stderr, "Insufficient memory.\n");
        return 1;
    }

    char str[LENGTH];
    // open file
    FILE *fp = fopen(dictionary, "r");
    if (fp == NULL)
    {
        fprintf(stderr, "Could not open %s.\n", dictionary);
        return 2;
    }

    while(fgets (str, 27, fp) != NULL)
    {
        int newline = strcspn(str, "\n");

        for (int ch = 0; ch < strlen(&str[newline]); ch++)
        {
            insert(&str[ch]);
        }
    }
    fclose(fp);
    return true;
}

/**
* Returns true if word is in dictionary else false.
*/
bool check(const char *word)
{
    //change to lowercase:
    char lower[LENGTH];
    int size = strlen(word);

    strncpy(lower, word, size);
    lower[size] = '\0';
    int i = 0;
    while (lower[i] != '\0' )
    {
        lower[i] = tolower(lower[i]);
        i++;
    }

    //search dictionary for word
    return (search(root, lower));
}

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

void erase(node *current)
{
    for (int i = 0; i < CHARACTERS; i++)
    {
        if (current->child[i] != NULL)
        {
            erase(current->child[i]);
        }
    }

    free(current);
}

/**
* Unloads dictionary from memory. Returns true if successful else false.
*/
bool unload(void)
{
    erase(root);
    return true;
}

**EDIT: Have printed the output of my loaded dictionary to the terminal in a file and all that was there for the max word was s. (final character). All other words were loaded correctly. I added + 1 to all LENGTH in code and then in output I got an empty line, the s was gone. I have tried debug50 and the problem is that for that one word it is not loaded to dictionary the problem code that is skipped over on this word is:

    while(fgets (str, 27, fp) != NULL)
    {
        int newline = strcspn(str, "\n");

        for (int ch = 0; ch < strlen(&str[newline]); ch++)
        {
            insert(&str[ch]);
        }
     }

1 Answer 1

0

The length of the longest possible word is stored in constant LENGTH, so char str[LENGTH+1]; and fgets (str, sizeof(str), fp). Not sure about how to use fgets (especially how it deals with the line end, whether that's returned as well, and what happens if line end is file end), but it definitely should get the length of the buffer as second argument. Especially not sure how it handles newlines. I read individual characters instead, which may not be your preference, others used get_string from cs50.h.

Also, I'm somewhat confused your code works at all. For example, in insert and search, you don't handle apostrophes. In load, for each word you seem to also insert all the endings, so for "cat" you would also insert "at" and "t", which are not in the dictionary.

In check, you declare lower of length LENGTH, while it has to store at most LENGTH+1 characters (remember the null terminator).

In newNode, the use of calloc rather than malloc already means the memory is zeroed, which means false for booleans and NULL for pointers (both are actually same as 0 in their value).

4
  • in terms of LENGTH that is an issue I looked at but the line: while (*string != '\n') was put in so they aren't included Commented Nov 24, 2017 at 19:56
  • As I understood it; fgetc gets each character, therefore meaning I didn't have to worry about the apostrophes accept to allow 27 characters in the array in my node structure. Commented Nov 24, 2017 at 20:04
  • Realised that if the above was true I did not need (LENGTH + 1), but (LENGTH + 2) fixed my problem. I think the newline was being read as two characters?? I honestly still don't fully understand some of the functions, but learnt a lot from this project. Commented Nov 24, 2017 at 21:29
  • The longest word is LENGTH characters, but fgets will read to the end of the line, including the \n. It will then store the string with the \n and the end of string marker, \0. So, the +2 accounts for two chars, \n and \0.
    – Cliff B
    Commented Nov 25, 2017 at 1:49

You must log in to answer this question.

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