...

View Full Version : Trie Trees



DELOCH
11-27-2011, 11:59 PM
I am making a Trie tree library which allows a dictionary to be parsed words and inserted into the trie.

THIS IS AN ASSIGNMENT, AS SUCH, I AM ALLOWED TO RECEIVE FULL HELP, BUT I WANT SMALL, VERY VERY SMALL TIPS ON WHY IT IS CRASHING SO I CAN GET BACK ON TRACK. DO NOT LOCK THIS THREAD PLEASE, BUT MODERATE IF POSSIBLE!



This is my library:

assign2_lib.h


#ifndef ASSIGN2_LIB_H
/**
* some useful comments.
*/
#define ASSIGN2_LIB_H

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

#define BRANCH 1
#define LEAF 2
#define WORD_MAX 28
#define BRANCH_SIZE 27

typedef struct {
int type;
void* next[BRANCH_SIZE];
} stxTrieBranch;

typedef struct {
int type;
char word[WORD_MAX];
} stxTrieLeaf;

typedef void* TrieBranch;
typedef void* TrieLeaf;
typedef void* Trie;
typedef void* TrieNode;

extern Trie Trie_new();
extern void Trie_addLeaf(Trie trie, TrieLeaf leaf);

extern TrieBranch TrieBranch_new();
extern void TrieBranch_addNode(TrieBranch branch, TrieNode node);
extern void TrieBranch_removeNode(TrieBranch branch, int position);
extern TrieBranch TrieBranch_copy(TrieBranch branch);
extern TrieNode TrieBrench_getNode(TrieBranch branch);

extern TrieLeaf TrieLeaf_new();
extern void TrieLeaf_setWord(TrieLeaf* leaf, char* word);
extern char* TrieLeaf_getWord(TrieLeaf* leaf);

extern int TrieNode_isBranch(TrieNode node);
extern int TrieNode_isLeaf(TrieNode node);
#endif /* ASSIGN2_LIB_H */


assign2_lib.c


#include "assign2_lib.h"

/***************************************************************************
* Trie methods.
***************************************************************************/

/**
* A method for instantiating the Trie ADT.
*/
Trie Trie_new()
{
stxTrieBranch* trie = malloc(sizeof(stxTrieBranch));
trie->type = BRANCH;
return ((void*)trie);
}

/**
* A method for adding elements to the Trie.
*/
void Trie_addLeaf(Trie trie, TrieLeaf leaf)
{
TrieBranch_addNode(trie, leaf);
}

/***************************************************************************
* TrieBranch methods.
***************************************************************************/

/**
* A method for instantiating the TrieBranch.
*/
TrieBranch TrieBranch_new()
{
stxTrieBranch* trieBranch = malloc(sizeof(stxTrieBranch));
trieBranch->type = BRANCH;
return ((void*)trieBranch);
}

/**
* A method for adding a node to the TrieBranch.
*/
void TrieBranch_addNode(TrieBranch branch, TrieNode node)
{
stxTrieBranch* branchToAdd = (stxTrieBranch*)branch;
stxTrieLeaf* leafToAdd = (stxTrieLeaf*)node;
char* word = (char*)leafToAdd->word;
int iter;

for (iter = 0; iter < WORD_MAX; ++iter)
{
stxTrieBranch* bptr = (branchToAdd + (*word - 'a'));
/*
if (bptr == NULL) {
bptr = (stxTrieBranch*)leafToAdd;
break;
} else if (TrieNode_isBranch(bptr)) {
branchToAdd = ((stxTrieBranch*)(branchToAdd->next));
} else { // it is a leaf...
char* cword = (char*)malloc(WORD_MAX);

stxTrieLeaf* next = (stxTrieLeaf*)(bptr->next);
if (strlen(next->word) > WORD_MAX) {
strncpy(cword, next->word, WORD_MAX);
} else {
strcpy(cword, next->word);
}
if (!strcmp(word, cword)) {
break; // two strings are equal, no need for insert.
}

// while there is a conflict...
while (TrieNode_isLeaf(bptr))
{
TrieBranch newBranch = TrieBranch_new();
TrieBranch_removeNode((TrieBranch)bptr, (int)(word[0] - 'a'));
bptr = (stxTrieBranch*)newBranch;
}
}
*/
}
}

/**
* A method for retrieving a node from TrieBranch
*/
TrieNode TrieBranch_getNode(TrieBranch branch)
{
return (((stxTrieBranch*)branch)->next);
}

/**
* A method for removing the TrieBranch's associated node.
*/
void TrieBranch_removeNode(TrieBranch branch, int position)
{
free(((stxTrieBranch*)branch)->next);
stxTrieBranch** bptr = ((stxTrieBranch**)branch);
free((*(bptr + position))->next);
}

/**
* A method for copying a TrieBranch.
* returns a copy of a TrieBranch.
*/
TrieBranch TrieBranch_copy(TrieBranch branch)
{
TrieBranch newBranch = TrieBranch_new();
TrieBranch_addNode(newBranch, branch);
return newBranch;
}

/***************************************************************************
* TrieLeaf methods.
***************************************************************************/

/**
* A method for instantiating the TrieLeaf.
*/
TrieLeaf TrieLeaf_new()
{
stxTrieLeaf* trieLeaf = malloc(sizeof(stxTrieBranch));
trieLeaf->type = LEAF;
return ((void*)trieLeaf);
}

/**
* A method for setting the word for the leaf.
*/
void TrieLeaf_setWord(TrieLeaf* leaf, char* word)
{
strncpy((char*)(((int*)leaf) + 1), word, WORD_MAX);
}

/**
* A method for getting the word for a leaf.
*/
char* TrieLeaf_getWord(TrieLeaf* leaf)
{
return (((stxTrieLeaf*)leaf)->word);
}
/***************************************************************************
* TrieNode methods.
***************************************************************************/

/**
* A method for checking if the TrieNode is a branch.
* returns 0 if false and 1 if true.
*/
int TrieNode_isBranch(TrieNode node)
{
return *((int*)node);
}

/**
* A method for checking if the TrieNode is a branch.
* returns 0 if false and 1 if true.
*/
int TrieNode_isLeaf(TrieNode node)
{
return !TrieNode_isBranch(node);
}



assign2_main.c


#include "assign2_lib.h"
#include <stdio.h>

int main(int argc, char* argv[])
{
Trie myTrie = Trie_new();
TrieLeaf a, b, c;
a = TrieLeaf_new();
TrieLeaf_setWord(a, "A");
b = TrieLeaf_new();
TrieLeaf_setWord(b, "B");
c = TrieLeaf_new();
TrieLeaf_setWord(c, "C");

printf("A word: %s\n", TrieLeaf_getWord(a));
printf("B word: %s\n", TrieLeaf_getWord(b));
printf("C word: %s\n", TrieLeaf_getWord(c));

//Trie_addLeaf(myTrie, a); // crashing!
//Trie_addLeaf(myTrie, b); // crashing!
//Trie_addLeaf(myTrie, c); // crashing!

return 0;
}





Please help me fix this core dump error.
If at all allowed, why my TrieBranch_addNode is malfunctioning.

--I DO NOT WANT THIS ASSIGNMENT DONE FOR ME, I WANT TO LEARN BY MYSELF, BUT I AM STUCH AS IS, AND REQUIRE HELP, I BELIEVE I AM ALLOWED TO ASK FOR THAT MUCH--

Thanks Ahead of time!!!



EZ Archive Ads Plugin for vBulletin Copyright 2006 Computer Help Forum