hello my friends
i have a problem about implementation Trie with C++
the project which is included,must have the following
1. Ability to create a hollow tree
2. Ability to insert a new string tree
3. Ability to search for a specific string in a tree
4. The ability to find all the strings that begin with a particular substring
5. Find the following string that contains a specific string.
6. The ability to find all strings that end in a particular substring.
7. List all fields in the tree
8. View tree
9. Exit the program
now when I run 2 options, with a word that contains the string, number printing letters and numbers that come from unknown
next question : What options using option 4, 5 and 6 do. Please indicate in practice
and how can i view tree??
please Help me,I need this code.tanks
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include<malloc.h>
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])
#define ALPHABET_SIZE (26)
#define CHAR_TO_INDEX(c) ((int)c - (int)'a')
static int test;
typedef struct trie_node trie_node_t;
struct trie_node
{
int value;
trie_node_t *children[ALPHABET_SIZE];
};
typedef struct trie trie_t;
struct trie
{
trie_node_t *root;
int count;
};
trie_node_t *getNode(void)
{
trie_node_t *pNode = NULL;
pNode = (trie_node_t *)malloc(sizeof(trie_node_t));
if(!pNode)
{
printf("\n\n takhsise faza anjam nashod !! ");
return NULL;
}
if( pNode )
{
int i;
pNode->value = 0;
for(i = 0; i < ALPHABET_SIZE; i++)
{
pNode->children[i] = NULL;
}
}
return pNode;
}
void initialize(trie_t *pTrie)
{
pTrie->root = getNode();
pTrie->count = 0;
}
void insert(trie_t *pTrie, char key[])
{
int level;
int length = strlen(key);
int index;
trie_node_t *pCrawl;
pTrie->count++;
pCrawl = pTrie->root;
for( level = 0; level < length; level++ )
{
index = CHAR_TO_INDEX(key[level]);
if( !pCrawl->children[index] )
{
pCrawl->children[index] = getNode();
}
pCrawl = pCrawl->children[index];
}
pCrawl->value = pTrie->count;
}
int search(trie_t *pTrie, char key[])
{
int level,i;
int length = strlen(key);
int index;
trie_node_t *pCrawl;
pCrawl = pTrie->root;
for( level = 0; level < length; level++ )
{
index = CHAR_TO_INDEX(key[level]);
if( !pCrawl->children[index] )
{
return 0;
}
pCrawl = pCrawl->children[index];
}
return (0 != pCrawl && pCrawl->value);
}
void traverse(trie_node_t *pCrawl, char key[],int index)
{
int i;
char *temp;
if(!pCrawl)
{
return ;
}
if(pCrawl->value!=0&&pCrawl!=NULL)
{
printf("%s\n",key);
}
for(i=0;i<26;i++)
{
temp=(char *)malloc(sizeof(char)*strlen(key)+2);
strcpy(temp,key);
temp[strlen(key)]=(char)(97+i);
temp[strlen(key)+1]='\0';
if(pCrawl->children[i]!=NULL)
traverse(pCrawl->children[i], temp,i);
free(temp);
}
}
int suggestions(trie_t *pTrie, char key[])
{
int level,i;
int length = strlen(key);
int index;
trie_node_t *pCrawl;
pCrawl = pTrie->root;
if(strcmp(key,"")==0)
{
printf("The input is NULL!!");
return 0;
}
for( level = 0; level < length; level++ )
{
index = CHAR_TO_INDEX(key[level]);
if( !pCrawl->children[index] )
{
printf("Prefix is not present");
return 0;
}
pCrawl = pCrawl->children[index];
}
traverse(pCrawl, key,index);
}
int main()
{
int i,status,prompt;
char inputString[30];
prompt=1;
trie_t trie;
initialize(&trie);
while(prompt!='4')
{
printf("\nPress 1 to insert a string into the database\nPress 2 to look for suggestions\nPress 3 to search a string\nPress 4 to exit\n");
scanf("%d",&prompt);
switch(prompt)
{
case 1 : printf("\nPlease enter the string\n");
scanf("%s",inputString);
if(strcmp(inputString,"")==0)
{
printf("Empty strings are not allowed");
break;
}
insert(&trie, inputString);
strcpy(inputString,"");
break;
case 2 : printf("\nPlease enter the pattern\n");
scanf("%s",inputString);
if(strcmp(inputString,"")==0)
{
printf("Empty strings are not allowed");
break;
}
printf("\nThe patterns are ::\n");
suggestions(&trie,inputString);
break;
case 3 : printf("\nPlease enter the string to be searched\n");
scanf("%s",inputString);
if(strcmp(inputString,"")==0)
{
printf("Empty strings are not allowed");
break;
}
status=search(&trie,inputString);
strcpy(inputString,"");
if(status==0)
printf("\nThe string you are looking is not present in the databse\n");
else
printf("The string is present in the database");
break;
case 4 : return 0;
default: printf("Invalid option!!Please try again!!!!\n\n");
break;
}
}
return 0;
}