//client1.cpp #include #include \"trie.h\" using namespace std; int main() { Tri
ID: 3839509 • Letter: #
Question
//client1.cpp
#include
#include "trie.h"
using namespace std;
int main()
{
Trie vocabulary;
cout << "Type '0'--quit; '1'--add a word; '2'--search a word; '3'--search prefix: ";
int choice;
cin >> choice;
while(choice) {
if(choice == 1) {
cout << "Add to the vocabulary this word: ";
string word;
cin >> word;
vocabulary.add(word);
} else if(choice == 2) {
cout << "Search this word: ";
string key;
cin >> key;
if(vocabulary.contains(key))
cout << key << " exists!" << endl;
else
cout << key << " does not exists." << endl;
} else if(choice == 3) {
cout << "Search this prefix: ";
string key;
cin >> key;
if(vocabulary.isPrefix(key))
cout << key << " is a prefix." << endl;
else
cout << key << " is not a prefix." << endl;
} else {
cout << "Input incorrect. Try again." << endl;
}
cout << "Type '0'--quit; '1'--add a word; '2'--search a word; '3'--search prefix: ";
cin >> choice;
}
return 0;
}
//trie.h
#ifndef TRIE_H
#define TRIE_H
#define MAX_CHAR 256
class Node
{
private:
Node *children[MAX_CHAR];
bool bisEnd;
public:
Node();
bool isEnd();
void insert(string suffix);
Node* search(string pat);
};
class Trie
{
private:
Node root;
public:
void add(string word);
bool contains(string pat);
bool isPrefix(string pat);
};
#endif
Please help me with completing trie.cpp(shown below) in accordance with trie.h and client1.cpp shown above. Thank you so much for helping me out...
//trie.cpp
#include
#include "trie.h"
using namespace std;
/* add your Trie implementation here */
Explanation / Answer
here is my code for trie implementation
#include <stdio.h>
#include "trie.h"
#include <stdlib.h>
trienode_t *trieCreateNode(char key, int data);
void trieCreate(trieNode_t **root)
{
*root = trieCreateNode('', 0xffffffff);
}
trienode_t *trieCreateNode(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 trieadd(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)
{
for(ptrav = *root; *key; ptrav = ptrav->children)
{
ptrav->children = trieCreateNode(*key, 0xffffffff);
ptrav->children->parent = ptrav;
#ifdef DEBUG
printf("Inserting: [%c] ",ptrav->children->key);
#endif
key++;
}
ptrav->children = trieCreateNode('', data);
ptrav->children->parent = ptrav;
#ifdef DEBUG
printf("Inserting: [%c] ",ptrav->children->key);
#endif
return;
}
if(trieSearch(ptrav, key))
{
printf("duplicate! ");
return;
}
while(*key != '')
{
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++;
trieAdd(&(ptrav->next), key, data);
return;
}
ptrav = ptrav->next;
}
if(*key)
{
ptrav->next = trieCreateNode(*key, 0xffffffff);
}
else
{
ptrav->next = trieCreateNode(*key, data);
}
ptrav->next->parent = ptrav->parent;
ptrav->next->prev = ptrav;
#ifdef DEBUG
printf("Inserting [%c] as neighbour of [%c] ",pTrav->next->key, pTrav->key);
#endif
if(!(*key))
return;
key++;
for(ptrav = ptrav->next; *key; ptrav = ptrav->children)
{
ptrav->children = trieCreateNode(*key, 0xffffffff);
ptrav->children->parent = ptrav;
#ifdef DEBUG
printf("Inserting: [%c] ",ptrav->children->key);
#endif
key++;
}
ptrav->children = trieCreateNode('', data);
ptrav->children->parent = ptrav;
#ifdef DEBUG
printf("Inserting: [%c] ",ptrav->children->key);
#endif
return;
}
trieNode_t* trieSearch(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 == '')
{
pPtr = curr;
return pPtr;
}
level = found->children;
key++;
}
}
void trieRemove(trieNode_t **root, char *key)
{
trieNode_t *tPtr = NULL;
trieNode_t *tmp = NULL;
if(NULL == *root || NULL == key)
return;
tPtr = TrieSearch((*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 trieDestroy( 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;
printf("Deleted [%c] ", tmp->key);
free(tmp);
}
else if(tPtr->prev && !(tPtr->next))
{
tmp = tPtr;
tPtr->prev->next = NULL;
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);
}
}
]}
node->children = null;
node->value = data;
node->parent= null;
node->prev= null;
return node;
}
void trieadd(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)
{
for(ptrav = *root; *key; ptrav = ptrav->children)
{
ptrav->children = trieCreateNode(*key, 0xffffffff);
ptrav->children->parent = ptrav;
#ifdef DEBUG
printf("Inserting: [%c] ",ptrav->children->key);
#endif
key++;
}
ptrav->children = trieCreateNode('', data);
ptrav->children->parent = ptrav;
#ifdef DEBUG
printf("Inserting: [%c] ",ptrav->children->key);
#endif
return;
}
if(trieSearch(ptrav, key))
{
printf("duplicate! ");
return;
}
while(*key != '')
{
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++;
trieAdd(&(ptrav->next), key, data);
return;
}
ptrav = ptrav->next;
}
if(*key)
{
ptrav->next = trieCreateNode(*key, 0xffffffff);
}
else
{
ptrav->next = trieCreateNode(*key, data);
}
ptrav->next->parent = ptrav->parent;
ptrav->next->prev = ptrav;
#ifdef DEBUG
printf("Inserting [%c] as neighbour of [%c] ",pTrav->next->key, pTrav->key);
#endif
if(!(*key))
return;
key++;
for(ptrav = ptrav->next; *key; ptrav = ptrav->children)
{
ptrav->children = trieCreateNode(*key, 0xffffffff);
ptrav->children->parent = ptrav;
#ifdef DEBUG
printf("Inserting: [%c] ",ptrav->children->key);
#endif
key++;
}
ptrav->children = trieCreateNode('', data);
ptrav->children->parent = ptrav;
#ifdef DEBUG
printf("Inserting: [%c] ",ptrav->children->key);
#endif
return;
}
trieNode_t* trieSearch(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 == '')
{
pPtr = curr;
return pPtr;
}
level = found->children;
key++;
}
}
void trieRemove(trieNode_t **root, char *key)
{
trieNode_t *tPtr = NULL;
trieNode_t *tmp = NULL;
if(NULL == *root || NULL == key)
return;
tPtr = TrieSearch((*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 trieDestroy( 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;
printf("Deleted [%c] ", tmp->key);
free(tmp);
}
else if(tPtr->prev && !(tPtr->next))
{
tmp = tPtr;
tPtr->prev->next = NULL;
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);
}
}
]}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.