0

so I am stuck on this PSET5 speller for a quite while now, trying different approaches, looking at available information in CS50, shorts, pset problem explanation and I couldn't get to free all the memory from the trie since from my understanding each time I need atleast two nodes ( one being the main - 'root' and the next one being 'node1' for traversing the root for e.g ).

Speller.c:

// Implements a dictionary's functionality

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

#include "dictionary.h"


node * root = NULL; // Main trie in which we store all the information
node * node1 = NULL; // Secondary node which we use for traversing/adding words into the main one.


int wordcount = 0; // Counts words in the dictionary
int target = 0;  // Global int for storing char's numerical value.
char longest_word[LENGTH+1]; // We store our longest word in here.
int long_word = 0; // We store our longest word's length in here.

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // We are counting found letters to check for a word.
    int letcount = 0;


    for ( int i = 0; i < strlen(word);i++)
    {
        target = get_char_index(word[i]);


        if ( i == 0 )
        {
            // Initialize node1 and start our navigation process here.

            if ( root->children[target] != NULL )
            {
                if ( root->children[target]->letter == word[i] || toupper(root->children[target]->letter) == word[i])
                {
                    letcount++;
                    node1 = root->children[target];
                }
            }
            else if ( root->children[target] == NULL )
            {
                break;
            }
        }
        else
        {
            if ( node1->children[target] != NULL )
            {
                if ( node1->children[target]->letter == word[i] || toupper(node1->children[target]->letter) == word[i] )
                {
                    // If we are not at the end of the word,
                    // move to another level.
                    // If we are at the end,
                    // check is_word boolean value.
                    if ( i + 1 < strlen(word) )
                    {
                       letcount++;
                       node1 = node1->children[target];
                    }
                    else if ( i + 1 == strlen(word))
                    {
                        if ( node1->children[target]->is_word == true)
                            letcount++;
                    }
                }
            }
            else
            {
               break;
            }
        }

    }

    if ( letcount == strlen(word) && letcount != 0 )
        return true;
    else
        return false;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
   char word[LENGTH+1];
   FILE *filee = fopen(dictionary, "r");

   root = malloc(sizeof(node));

    while ( fscanf(filee,"%s",word) != EOF )
    {
        if ( strlen(word) > long_word)
        {
            strcpy(longest_word,word);
            long_word = strlen(word);
        }

        for ( int i = 0; i < strlen(word);i++)
        {
            target = get_char_index(word[i]);

            if ( i == 0  )
            {
                // Same as with search, we start
                // our 'journey' with the top level.

                if ( root->children[target] == NULL )
                {
                    node1 = malloc(sizeof(node));
                    node1->letter = word[i];
                    node1->is_word = false;
                    root->children[target] = node1;

                }
                // If the word is only a single letter
                // add one to the counter, else move to the next
                // level.
                if ( strlen(word) == 1 )
                {
                    wordcount++;
                    break;
                }
                else
                    node1 = root->children[target];
            }
            else
            {
                if ( node1->children[target] == NULL )
                {
                    node1->children[target] = malloc(sizeof(node));
                    node1->children[target]->letter = word[i];
                    node1->children[target]->is_word = false;
                }

                if ( i + 1 != strlen(word))
                    node1 = node1->children[target];
            }
            // If the letter is the last one, add one to
            // the counter and set is_word to true.

             if ( i + 1 == strlen(word) )
             {
                wordcount++;
                node1->children[target]->is_word = true;
             }


        }
        // Reseting the trav node after each word.
        node1 = NULL;
    }

    if ( wordcount != 0)
        return true;
    else
        return false;
}

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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // Here I am having a problem.
    // My approach to this (and recommended by Zamyla from the pset tutorials) is
    // that I navigate to the lowest possible node (level).From there I free one
    // level at the time.

    /* Example:
    I have a single word in my dictionary - 'cat'.

    Below loop navigates to the letter 'a', it frees a's children 't'
    then it moves to the position of c letter and frees it's children 'a'.

    Then the last loop in this function frees the top row.

    */
    // Int variable to 'push' the bottom level of a trie
    // each time we free a row.
    int w_length = strlen(longest_word);

    // Bool to determine if we reached the top row.
    bool lastone = false;

    if ( w_length != 1)
    {
        for ( int x = 0;x < w_length;x++)
        {
            target = get_char_index(longest_word[x]);

            if ( x > 0 && lastone == false)
                node1 = node1->children[target];
            else if ( x == 0)
                node1 = root->children[get_char_index(longest_word[0])];

            if ( x + 2 == w_length)
            {
                // Freeing current letter's children row.
                for ( int t = 0; t < 27;t++)
                {
                    if ( node1->children[t] != NULL)
                    {
                        free(node1->children[t]);
                    }
                }
                // Get one closer to the top.
                w_length--;

                if ( w_length == 2)
                    lastone = true;

                // Reset the starting position.
                x = -1;
                node1 = root->children[get_char_index(longest_word[0])];
            }
    }
    }
    // Freeing the top level.
    for ( int y = 0;y < 27;y++)
    {
        if ( root->children[y] != NULL )
            free(root->children[y]);
    }


    return true;
}
// Special function to ease the process of finding indexes for each of the letters.
int get_char_index(char c)
{
    int numb = 0;

    if ( (int)c == 39 )
        numb = 26;
    else if ( (int)c >= 97 && (int)c <= 122 )
        numb = (int)c - 97;
    else if ( (int)c >= 65 && (int)c <= 90 )
        numb = (int)c - 65;

    return numb;
}

Where I am having a problem:

bool unload(void)
{
    // Here I am having a problem.
    // My approach to this (and recommended by Zamyla from the pset tutorials) is
    // that I navigate to the lowest possible node (level).From there I free one
    // level at the time.

    /* Example:
    I have a single word in my dictionary - 'cat'.

    Below loop navigates to the letter 'a', it frees a's children 't'
    then it moves to the position of c letter and frees it's children 'a'.

    Then the last loop in this function frees the top row.

    */
    // Int variable to 'push' the bottom level of a trie
    // each time we free a row.
    int w_length = strlen(longest_word);

    // Bool to determine if we reached the top row.
    bool lastone = false;

    if ( w_length != 1)
    {
        for ( int x = 0;x < w_length;x++)
        {
            target = get_char_index(longest_word[x]);

            if ( x > 0 && lastone == false)
                node1 = node1->children[target];
            else if ( x == 0)
                node1 = root->children[get_char_index(longest_word[0])];

            if ( x + 2 == w_length)
            {
                // Freeing current letter's children row.
                for ( int t = 0; t < 27;t++)
                {
                    if ( node1->children[t] != NULL)
                    {
                        free(node1->children[t]);
                    }
                }
                // Get one closer to the top.
                w_length--;

                if ( w_length == 2)
                    lastone = true;

                // Reset the starting position.
                x = -1;
                node1 = root->children[get_char_index(longest_word[0])];
            }
    }
    }
    // Freeing the top level.
    for ( int y = 0;y < 27;y++)
    {
        if ( root->children[y] != NULL )
            free(root->children[y]);
    }


    return true;
}

CHECK50 does return everything in green except for the memory part.

Any tips are appreciated :) BTW: I am not looking for the specific code based answer, I am looking for guidance/any tips regarding this issue!

0

I don't understand your code, so I'm not able to fix it :-(

Note that memory malloced initially can have any value. Don't forget to initialise the allocated nodes. calloc might do that in a way you want. Not sure what letter member is meant for. The index should already tell you the letter. In a trie, the key is encoded in the position of a node.

Also, special treatment of the first letter can be avoided by using node1 = root; in front of the for loop.

An efficient solution for trie unload requires a stack, so that you remember the position in the trie you're at.

The simplest version is by using the call stack, by utilizing a recursive function.

This recursive function would take one parameter, a node. It would then call itself for all non-NULL child nodes, and after that free the node, as you know that there are no more nodes depending on that one.

unload would call the recursive function for the root node.

10
  • I am sorry what you can't understand :) Maybe you could specify what part you don't understand? – Gintas Jul 23 '18 at 16:14
  • The whole part with the longest word. You have a trie. Any sub-trie could have a different depth. Keeping track of the global depth doesn't make much sense to me. Also, your use of pointers, with special treatment for first or last character everywhere instead of putting that code before and after the for loop. – Blauelf Jul 23 '18 at 16:32
  • Longest word is used to navigate to the deepest possible node, I don't know how can you navigate without it, oh and yes for the threatment part its bad code design on my part. – Gintas Jul 23 '18 at 16:37
  • Still tho, if I use iterative approach, i'll have two tries anyways, so ho do I free them both at the same time,I'll need atleast one to traverse another?! – Gintas Jul 23 '18 at 17:38
  • I think there are just too many variables to keep track of while reading the code. I agree that you should try your hand at a recursive algorithm. It'll be cleaner and easier to read and understand. – Allan Clayton Jul 23 '18 at 17:40

You must log in to answer this question.

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