trie data structure C

Question

ok so i define my structure like this.

    struct trie {
        struct trie *child[26];
        int count;
        char letter;
    };

the problem is when i try to fill my trie with words i get a segmentation fault. ive been told that the problem is that the child variable isn't pointing to anything and setting them to NULL would fix this. Also creating a second structure would be a good way to achieve this. i am new to C programming and am confused on how to create a second structure to achieve this. any help would be much appreciated.

int addWordOccurrence(const char* word)
{

    struct trie *root;
    root = (struct trie *)malloc(sizeof(struct trie*));
    struct trie *initRoot=root;
    int count;

    int x=strlen(word);
    printf("%d",x);
    int i;
    for(i=0; i<x; i++)
    {  
        int z=word[i]-97;
        if(word[i]=='\n')
        {
            z=word[i-1]-97;
            root->child[z]->count++;
            root=initRoot;
        }

        root->child[z] = (struct trie *)malloc(sizeof(struct trie));
        root->child[z]->letter=word[i];
        root->child[z]=root;
    }
    return 0;
}

You have to allocate memory for the pointers in child. Do you know malloc/calloc? Or you create other tries and put them in. Can you show us your code? — wkl
– wkl, Commented Oct 31, 2011 at 20:57
yes i use malloc in my method that adds the words to the trie. — Relics
– Relics, Commented Oct 31, 2011 at 20:59
The struct definition looks OK (though I don't know what count is for), but you haven't posted the code for inserting, and that's where the problem is. Please post that code. — Omnifarious
– Omnifarious, Commented Oct 31, 2011 at 20:59

Mooing Duck · Accepted Answer · 2011-10-31 22:13:49Z

1

root->child[z] = (struct trie *)malloc(sizeof(struct trie));
root->child[z]->letter=word[i];
root->child[z]=root;

This is problematic.
1) What if child[z] was already set?
2) You never set child[z]->child or child[z]->count to anything

#2 is causing your segfaults, #1 is a memory leak.

My solution would be to write a function for allocating new children:

struct trie* newtrie(char newchar) {
    struct trie* r = malloc(sizeof(struct trie));
    memset(r, 0, sizeof(struct trie));
    r->letter = newchar;
    return r;
}

Then your code would become:

    if (root->child[z] == NULL)
        root->child[z] = newtrie(word[i]);
    root->child[z]=root;

You also have to change the malloc of root:

struct trie *root = newtrie(0);

Which is more clear, and avoids the errors I mentioned. http://codepad.org/J6oFQJMb No segfaults after 6 or so calls.

I've also noticed that your code mallocs a new root, but never returns it, so nobody except this function can ever see it. This is also a memory leak.

edited Oct 31, 2011 at 22:13

answered Oct 31, 2011 at 21:04

Mooing Duck

67.6k19 gold badges107 silver badges169 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Relics Over a year ago

should i use malloc for the children when i define the structure?

Relics Over a year ago

ug i appreciate your help, maybe im just implementing it wrong but i am still getting the seg fault

Lajos Arpad Over a year ago

Mark, you might be implementing it in the wrong way or you might have misunderstood the answer. I think you should edit your question and add more information (for example put there the new version of your source code) and you'll suddenly get much more answers.

wkl · Accepted Answer · 2011-10-31 21:14:50Z

1

In addition to @MooingDuck's answer, there is another problem with your code here:

int addWordOccurrence(const char* word)
{

    struct trie *root;
    root = (struct trie *)malloc(sizeof(struct trie*));
    struct trie *initRoot=root;
    int count;
    /* ... */
}

You did a

root = (struct trie *)malloc(sizeof(struct trie*));

but you really mean to allocate the `sizeof(struct trie), and not sizeof a pointer (which will likely be 4 or 8 if you're on x86 or x86_64).

This is better (don't need explicit cast of malloc's return pointer in C, and you can do sizeof like this:

struct tree *root = malloc(sizeof(*root));

answered Oct 31, 2011 at 21:14

wkl

80.4k16 gold badges171 silver badges178 bronze badges

Collectives™ on Stack Overflow

trie data structure C

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related