#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define MAX_LEN 8
typedef struct _TrieTree{
int kind; // 0-leaf; 1-branch
union{
struct {char keys[MAX_LEN]; char *infoptr;} leaf;
struct {struct _TrieTree *ptr[27]; int num;} branch;
};
}TrieTree;
char *SearchTrie(TrieTree *T, char *keys)
{
TrieTree *p = T;
int i=0;
int c;
int n = strlen(keys);
while(p && p->kind == 1 && i<n){
c = keys[i++] - 'a' + 1;
p = p->branch.ptr[c];
}
if(p && p->kind == 0 && strcmp(p->leaf.keys, keys) == 0){
return p->leaf.infoptr;
}else{
return NULL;
}
}
void InsertTrie(TrieTree **T, char *keys)
{
TrieTree *p = *T;
TrieTree *q = NULL;
int i=0;
int j;
int n = strlen(keys);
int c;
if(!p){
q = malloc(sizeof(TrieTree));
for(j=0; j<27; j++){
q->branch.ptr[j] = NULL;
}
q->kind = 1;
*T = q;
p = *T;
}
for(i=0; i<n; i++){
c = keys[i] - 'a' + 1;
if(p->kind == 0){
q = malloc(sizeof(TrieTree));
for(j=0; j<27; j++){
q->branch.ptr[j] = NULL;
}
q->kind = 1;
*q = *p;
p->kind = 1;
p->branch.ptr[0] = q;
}
if(!p->branch.ptr[c]){
q = malloc(sizeof(TrieTree));
for(j=0; j<27; j++){
q->branch.ptr[j] = NULL;
}
if(i==n-1){
q->kind = 0;
strcpy(q->leaf.keys, keys);
q->leaf.infoptr = keys;
}else{
q->kind = 1;
}
p->branch.ptr[c] = q;
}
p = p->branch.ptr[c];
}
}
void main()
{
char seq1[] = "aboutge";
char seq2[] = "hello";
char seq3[] = "world";
char seq4[] = "again";
char seq5[] = "help";
int i;
TrieTree *F;
TrieTree *T = NULL;
printf("log.anycle.com\n\n");
printf("Original data:\n");
printf("%s\n", seq1);
printf("%s\n", seq2);
printf("%s\n", seq3);
printf("%s\n", seq4);
printf("%s\n", seq5);
printf("Insert trie tree:\n");
InsertTrie(&T, seq1);
InsertTrie(&T, seq2);
InsertTrie(&T, seq3);
InsertTrie(&T, seq4);
InsertTrie(&T, seq5);
printf("Print the tree:\n");
printf("%s", (char *)SearchTrie(T, seq2) );
printf("\n");
}