Hello, I do not understand the following C code. If there are any errors could they be fixed along with explanations, and a sample out put please, thank you.

/*trieFunctions.c*/

/*

* This implementation of tries provide the functionality

* - to insert a string,

* - search a string,

* - delete a string from a dictionary or list.

*

* NB The insertion and deletion operation takes O(n) time

* where n is the length of the string to be deleted

* or inserted.

*/

#include

#include "trie.h"

#include

trieNode_t *createTrieNode(char key, int data);

// Build the root of the trie

void createTrie(trieNode_t **root)

{

*root = createTrieNode('\0', 0xffffffff);

}

//Generic trie node creation

trieNode_t *createTrieNode(char key, int data)

{

trieNode_t *node = NULL;

node = (trieNode_t *)malloc(sizeof(trieNode_t));

if(NULL == node)

{

printf("Malloc failed ");

return node;

}

node->key = key;

node->next = NULL;

node->children = NULL;

node->value = data;

node->parent= NULL;

node->prev= NULL;

return node;

}

void addTrie(trieNode_t **root, char *key, int data)

{

trieNode_t *pTrav = NULL;

if(NULL == *root)

{

printf("NULL tree ");

return;

}

#ifdef DEBUG

printf(" Inserting key %s: ",key);

#endif

pTrav = (*root)->children;

if(pTrav == NULL)

{

/*First Node*/

for(pTrav = *root; *key; pTrav = pTrav->children)

{

pTrav->children = createTrieNode(*key, 0xffffffff);

pTrav->children->parent = pTrav;

#ifdef DEBUG

printf("Inserting: [%c] ",pTrav->children->key);

#endif

key++;

}

pTrav->children = createTrieNode('\0', data);

pTrav->children->parent = pTrav;

#ifdef DEBUG

printf("Inserting: [%c] ",pTrav->children->key);

#endif

return;

}

if(searchTrie(pTrav, key))

{

printf("Duplicate! ");

return;

}

while(*key != '\0')

{

if(*key == pTrav->key)

{

key++;

#ifdef DEBUG

printf("Traversing child: [%c] ",pTrav->children->key);

#endif

pTrav = pTrav->children;

}

else

break;

}

while(pTrav->next)

{

if(*key == pTrav->next->key)

{

key++;

addTrie(&(pTrav->next), key, data);

return;

}

pTrav = pTrav->next;

}

if(*key)

{

pTrav->next = createTrieNode(*key, 0xffffffff);

}

else

{

pTrav->next = createTrieNode(*key, data);

}

pTrav->next->parent = pTrav->parent;

pTrav->next->prev = pTrav;

#ifdef DEBUG

printf("Inserting [%c] as peer of [%c] ",pTrav->next->key, pTrav->key);

#endif

if(!(*key))

return;

key++;

for(pTrav = pTrav->next; *key; pTrav = pTrav->children)

{

pTrav->children = createTrieNode(*key, 0xffffffff);

pTrav->children->parent = pTrav;

#ifdef DEBUG

printf("Inserting: [%c] ",pTrav->children->key);

#endif

key++;

}

pTrav->children = createTrieNode('\0', data);

pTrav->children->parent = pTrav;

#ifdef DEBUG

printf("Inserting: [%c] ",pTrav->children->key);

#endif

return;

}

trieNode_t* searchTrie(trieNode_t *root, const char *key)

{

trieNode_t *level = root;

trieNode_t *pPtr = NULL;

int lvl=0;

while(1)

{

trieNode_t *found = NULL;

trieNode_t *curr;

for (curr = level; curr != NULL; curr = curr->next)

{

if (curr->key == *key)

{

found = curr;

lvl++;

break;

}

}

if (found == NULL)

return NULL;

if (*key == '\0')

{

pPtr = curr;

return pPtr;

}

level = found->children;

key++;

}

}

void removeTrie(trieNode_t **root, char *key)

{

trieNode_t *tPtr = NULL;

trieNode_t *tmp = NULL;

if(NULL == *root || NULL == key)

return;

tPtr = searchTrie((*root)->children, key);

if(NULL == tPtr)

{

printf("Key [%s] not found in trie ", key);

return;

}

#ifdef DEBUG

printf("Deleting key [%s] from trie ", key);

#endif

while(1)

{

if( tPtr->prev && tPtr->next)

{

tmp = tPtr;

tPtr->next->prev = tPtr->prev;

tPtr->prev->next = tPtr->next;

#ifdef DEBUG

printf("Deleted [%c] ", tmp->key);

#endif

free(tmp);

break;

}

else if(tPtr->prev && !(tPtr->next))

{

tmp = tPtr;

tPtr->prev->next = NULL;

#ifdef DEBUG

printf("Deleted [%c] ", tmp->key);

#endif

free(tmp);

break;

}

else if(!(tPtr->prev) && tPtr->next)

{

tmp = tPtr;

tPtr->parent->children = tPtr->next;

#ifdef DEBUG

printf("Deleted [%c] ", tmp->key);

#endif

free(tmp);

break;

}

else

{

tmp = tPtr;

tPtr = tPtr->parent;

tPtr->children = NULL;

#ifdef DEBUG

printf("Deleted [%c] ", tmp->key);

#endif

free(tmp);

}

}

#ifdef DEBUG

printf("Deleted key [%s] from trie ", key);

#endif

}

void destroyTrie( trieNode_t* root )

{

trieNode_t *tPtr = root;

trieNode_t *tmp = root;

while(tPtr)

{

while(tPtr->children)

tPtr = tPtr->children;

if( tPtr->prev && tPtr->next)

{

tmp = tPtr;

tPtr->next->prev = tPtr->prev;

tPtr->prev->next = tPtr->next;

#ifdef DEBUG

printf("Deleted [%c] ", tmp->key);

#endif

free(tmp);

}

else if(tPtr->prev && !(tPtr->next))

{

tmp = tPtr;

tPtr->prev->next = NULL;

#ifdef DEBUG

printf("Deleted [%c] ", tmp->key);

#endif

free(tmp);

}

else if(!(tPtr->prev) && tPtr->next)

{

tmp = tPtr;

tPtr->parent->children = tPtr->next;

tPtr->next->prev = NULL;

tPtr = tPtr->next;

#ifdef DEBUG

printf("Deleted [%c] ", tmp->key);

#endif

free(tmp);

}

else

{

tmp = tPtr;

if(tPtr->parent == NULL)

{

/*Root*/

free(tmp);

return;

}

tPtr = tPtr->parent;

tPtr->children = NULL;

#ifdef DEBUG

printf("Deleted [%c] ", tmp->key);

#endif

free(tmp);

}

}

}

/*trieHarness.c*/

/*

* The big picture: a "trie" solves an interesting class of problem(s):

*

* - URL completion in autocomplete feature

* - Spell check

* - Dictionary lookup

* - Search term autocomplete

*

* For example:

*

* /--f--r--e--d--(\0)

* /

* root(\0)--w--i--l--m--a--(\0)

* \ \

* \ \--s--o--n--(\0)

* \

* \--b--a--r--n--e--y--(\0)

* \

* \--m--b--a--m--(\0)

* \

* \--i--(\0)

*

* ^^^^ The trie shown above is a logical representation of tries.

*

* vvvv The diagram below shows the 'peer' relationships as implemented.

* b--a--r--n--e--y--(\0)

* | |

* | m--b--a--m--(\0)

* | |

* | i--(\0)

* |

* f--r--e--d--(\0)

* |

* root(\0)--w--i--l--m--a--(\0)

* |

* s--o--n--(\0)

*

*

*/

#include

#include

#include "trie.h"

int main()

{

trieNode_t *root;

printf("Trie Example ");

/*Create a trie*/

createTrie(&root);

/* Bedrock peeps */

addTrie(&root, "fred", 1);

addTrie(&root, "wilma", 2);

addTrie(&root, "wilson", 3);

addTrie(&root, "barney", 5);

removeTrie(&root, "bambam");

addTrie(&root, "bambam", 6);

addTrie(&root, "bam", 6);

removeTrie(&root, "bambi");

addTrie(&root, "bambi", 7);

addTrie(&root, "pebbles", 8);

addTrie(&root, "bambam", 8);

/*Destroy the trie*/

destroyTrie(root);

}

/* Useful notes:

*

* To Compile : gcc -o trieX trieFunctions.c trieHarness.c

*

* In order to print the debug messages,

* use -DDEBUG while compiling with gcc:

**> gcc -o trieX trieFunctions.c trieHarness.c -DDEBUG

*/

/*trie.h*/

/*

* Provide coverage for referencing data such as:

*

* (\0) {root}

* |

* a

* |

* l----m----x

* | | |

* (\0) b l

* | |

* e e

* | |

* r (\0)

* |

* (\0)

*/

typedef int trieVal_t; //simple data element

/*

* Doubly chained trie

*/

typedef struct trieNode {

char key; // the character

trieVal_t value; // "data"! (struc, other type, etc.)

struct trieNode *next; // the pointer to adjacent letter (right)

struct trieNode *prev; // and the previous adjacent letter (left)

struct trieNode *children; // to the child

struct trieNode *parent; // to the parent

} trieNode_t;

void createTrie(trieNode_t **root);

trieNode_t* searchTrie(trieNode_t *root, const char *key);

void addTrie(trieNode_t **root, char *key, int data);

void removeTrie(trieNode_t **root, char *key);

void destroyTrie( trieNode_t* root );