0

I have been sitting on this pset for weeks but i have not figured what i wrote wrongly.. I implement the solution to this problem using a trie, however i think my trie is not properly linked/connected. Could anyone please take a look at my code and highlight some of my mistakes please?

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

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

#include "dictionary.h"

//function prototype
int char_number(char c);

//node structure definition
typedef struct node
{
    bool is_word;
    struct node *children[27];
}
node;

//root node pointer declaration
struct node root = {false,{NULL}};

//number of words in dictionary
int count = 0;

/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char *word)
{
    node* nextnode = &root;

    for (int i = 0; i < strlen(word); i++)
    {
        if (nextnode -> children[char_number(word[i])] == NULL)
        {
            return false;
        }
        nextnode = nextnode -> children[char_number(word[i])];
    }

    if (nextnode -> is_word)
    {
        return true;
    }
    else
    {
        return false;
    }
}

/**
 * Loads dictionary into memory. Returns true if successful else false.
 */
bool load(const char *dictionary)
{
    // very first node
    node* nextnode = &root;

    //integer value for character in word of dictionary
    unsigned int character = 0;

    //open dictionary file, check if NULL
    FILE* fp = fopen(dictionary, "r");
    if (fp == NULL)
    {
        printf("Could not load dictionary.\n");
        return false;
    }

    while (!feof(fp))
    {
        character = fgetc(fp);
        if (character != '\n' && character != EOF)
        {
            // if node does not exist, create one. if exist, point to it
            if (nextnode -> children[char_number(character)] == NULL)
            {
                nextnode -> children[char_number(character)] = malloc(sizeof(node));
            }
            nextnode = nextnode -> children[char_number(character)];
        }

        else if (character == '\n')
        {
            nextnode -> is_word = true;
            count++;
            nextnode = &root;
        }
    }

    fclose(fp);
    return true;
}

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

/**
 * Unloads dictionary from memory. Returns true if successful else false.
 */

void freenode(node* nextnode)
{
    for (int i = 0; i < 27; i++)
    {
        if (nextnode -> children[i] != NULL)
        {
            freenode(nextnode -> children[i]);
        }
    }

    free(nextnode);
}

bool unload(void)
{
    freenode(&root);
    return true;
}

// function prototype
int char_number(char c)
{
    int number;
    if (c == '\'')
    {
        return 26;
    }
    else if(c >= 'A' && c <= 'Z')
    {
        c += 32;
    }
    number = c - 'a';
    return number;
}

1 Answer 1

0

I would expect that your global root would be a node pointer, not a node.

4
  • Thank you! When ran the code through Valgrind it responded with mainly: Conditional jump or move depends on uninitialised value(s) and Uninitialised value was created by a heap allocation Does this mean my pointers are not pointing to where they should be?
    – jaylearns
    Commented Aug 6, 2017 at 2:48
  • It means that you have malloced a node but not initialized it. Perhaps use calloc instead of malloc.
    – curiouskiwi
    Commented Aug 6, 2017 at 3:07
  • IT WORKED!! Thank you!! But would there be any other way to write it without using calloc?
    – jaylearns
    Commented Aug 6, 2017 at 5:01
  • You would have to loop over all the children in the node and initialize them to NULL (and the is_word to false).
    – curiouskiwi
    Commented Aug 6, 2017 at 8:19

You must log in to answer this question.

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