0

I am having problems with pset 5. Honestly so far I have never had such a huge problems with a pset. I watched every video, read many questions and answers on stack exchange and wrote some code, which compiles, but it doesn't work. I was trying to find the problem, but I'm afraid I still don't understand everything in this pset, so I'm looking for any help I could get. I'm giving you my whole code in edit and hoping for your comments.

#include <stdbool.h>

#include "dictionary.h"

#include <stdio.h>

#include <ctype.h>

#include <stdlib.h>

int counter = 0;
// trie struct
typedef struct node
{
bool is_word;
struct node* children[27];
}
node;
node* root;
/**
* Returns true if word is in dictionary else false.
*/
bool check(const char* word)
{
// trie

node* root = malloc(sizeof(node));
node* csr = root;
int i = 0;
int idx = tolower(word[i]) - 'a';

while (word[i] != '\0')
{
    if (isalpha(word[i])) // if char is alphabetical
    {
        if (csr->children[idx] != NULL)
        {
            csr = csr->children[idx];
            i++;
        }
        else
        {
            return false;
        }
    }
    else if (word[i] == '\'') // if char is apostrophe
    {
        if (csr->children[idx] != NULL)
        {
            csr = csr->children[idx];
            i++;
        }
        else
        {
            return false;
        }
    }
    else
    return false;
}
if (csr->is_word == true)
return true;

else
return false;
}

/**
 * Loads dictionary into memory.  Returns true if successful else false.
 */
bool load(const char* dictionary)
{
// open file
FILE* dic = fopen("dictionary", "r");
if (dic == NULL)
{
    printf("Could not open dictionary\n");
    return 1;
}

// trie

node* root = malloc(sizeof(node));
node* csr = NULL;


int c = fgetc(dic); // reads each char
int index = tolower(c) - 'a';

while (c != EOF)
{
csr = root;
    do
    {
        // checks if it is alphabetical char
        if (isalpha(c))
        {
            if (csr->children[index] == NULL) // if lack of that char
            {
                csr->children[index] = malloc(sizeof(node));
            }
            csr = csr->children[index];
        }
        else if (c == '\'') // if apostrophe
        {
            if (csr->children[26] == NULL)
            {
                csr->children[26] = malloc(sizeof(node));
            }
            csr = csr->children[26];
        }
    c = fgetc(dic);
    } 
    while (c != '\n');
    csr->is_word = true;
    counter++;
    c = fgetc(dic);
}

return true;
}

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

/**
* Unloads dictionary from memory.  Returns true if successful else false.
*/
void ftrie (node* csr)
{
// children
for (int i = 0; i < 27; i++)
{
    if (csr->children[i] != NULL)
    {
        csr = csr->children[i];
        ftrie(csr);
    }
    else if (csr->children[i] == NULL)
    {
        free(csr->children[i]);
    }
}
}

bool unload(void)
{
node* csr = NULL;
csr = root;
ftrie(csr);
return true;
}
3
  • You have to specify what the problem is. Does it segfault? Does it find some words? Too many? Too few? And, have you tried running gdb to debug it? – Irene Nov 19 '15 at 21:13
  • Sorry, it outputs many words, and after THE END it hits segfault. – Keassie Nov 19 '15 at 22:06
  • I tried gdb it says it received segfault in unload part: " if (csr->children[i] != NULL) " – Keassie Nov 19 '15 at 22:12
0

A couple of comments about your recursive function for freeing the trie:

1) Reassigning csr is not correct: Your recursive function is supposed to traverse the whole trie. At the beginning, csr has the address of root. Recursion works by calling itself, every time with an address "deeper" in the trie. Now, suppose, for the sake of discussion, that root (that is, the original csr, holds address 0x1. And that, the first child, csr->children[i] holds address 0x2. Topmost function gets called, you pass root, so you pass the address 0x1. The idea would be to call the next function with address 0x2. You do that. But when you reassign csr, now csr also holds address 0x2, and you have lost root. So, instead of reassigning, just call your recursive function with the child as argument

2) Recursion here is meant to traverse the trie, and ONLY to traverse the trie. That is what your for loop is there for. Don't free the memory from inside the for loop. The reasoning is that the for loop will call the function recursively until it hits NULL. When it doesn't just let the for loop continue. When the for loop is done, that is when the lowermost for loop of the recursive calls is done, it will exit and then the memory freeing starts. Memory gets freed, function returns, the recursion starts unwinding the stack and each for loop will continue or end as necessary, freeing the memory at each level as the for loops end. All you have to do in the for loop is call the recursion until you hit NULL

You must log in to answer this question.

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