trietree.txt

trie tree, 是一个高效处理字符串的比较常见的算法,能够让我们在复杂度 O(log(n))的情况下插入和查询一个字符串

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

struct node
{
    struct node *branch[26];
    int cnt;
    node()
    {
        int i;
        for(i = 0; i < 26; i++)
            branch[i] = NULL;
        cnt = 0;
    }
} *root, p;

void insert(char *word)
{
    int i, pos;
    int char_code;
    struct node *loc = NULL;
    if( root == NULL )
    {
        root = ( struct node * )malloc(sizeof(p));
    }
    loc = root;
    pos = 0;
    while( loc != NULL && word[pos] != '\0' )
    {
        char_code = word[pos] - 'a';
        if( loc->branch[char_code] == NULL )
        {
            loc->branch[char_code] = ( struct node * )malloc( sizeof(p) );
        }
        loc->cnt++;
        pos++;
        loc = loc->branch[char_code];
    }
    loc->cnt++;
}

void search(char *word)
{
    char entry[22];
    struct node *loc = root;
    int i = 0;
    int char_code, step = 0;
    while(loc != NULL && word[i] != '\0' && loc->cnt != 1)
    {
        char_code = word[i] - 'a';
        entry[step++] = word[i];
        loc = loc->branch[char_code];
        i++;
    }
    entry[step] = '\0';
    printf("%s\n", entry);
}

int main()
{
    char s1[1001][22], s2[22];
    int sum, i;
    sum = 0;
    root = NULL;
    while( gets(s1[sum]) != NULL )
    {
        insert(s1[sum]);
        sum++;
    }
    
    for(i = 0; i < sum; i++)
    {
        printf("%s ", s1[i]);
        search(s1[i]);
    }
}


#include <stdio.h>
#include <iostream>
//#include <ciostream.h>

#include <string.h>
using namespace std;
const int num_chars = 26;
class Trie {
public:
      Trie();
      Trie(Trie& tr);
     virtual ~Trie();
     int trie_search(const char* word, char* entry ) const;
     int insert(const char* word, const char* entry);
     int remove(const char* word, char* entry);
protected:
     struct Trie_node
     {
         char* data;
          Trie_node* branch[num_chars];
          Trie_node();
     };
     
      Trie_node* root;
};
Trie::Trie_node::Trie_node() 
{
     data = NULL;
    for (int i=0; i<num_chars; ++i) 
         branch[i] = NULL;
}
Trie::Trie():root(NULL)
{
}
Trie::~Trie()
{
}
int Trie::trie_search(const char* word, char* entry ) const 
{
    int position = 0;
    char char_code;
     Trie_node *location = root;
    while( location!=NULL && *word!=0 ) 
    {
        if (*word>='A' && *word<='Z') 
             char_code = *word-'A';
        else if (*word>='a' && *word<='z') 
             char_code = *word-'a';
        else return 0;
         location = location->branch[char_code];
         position++;
         word++;
    }
    if ( location != NULL && location->data != NULL ) 
    {
        strcpy(entry,location->data);
        return 1;
    }
    else return 0;
}
int Trie::insert(const char* word, const char* entry) 
{
    int result = 1, position = 0;
    if ( root == NULL ) root = new Trie_node;
    char char_code;
     Trie_node *location = root;
    while( location!=NULL && *word!=0 )
    {
        if (*word>='A' && *word<='Z') 
             char_code = *word-'A';
        else if (*word>='a' && *word<='z') 
             char_code = *word-'a';
        else return 0;
        if( location->branch[char_code] == NULL ) 
             location->branch[char_code] = new Trie_node;
         location = location->branch[char_code];
         position++;
         word++;
    }
    if (location->data != NULL)
         result = 0;
    else {
         location->data = new char[strlen(entry)+1];
        strcpy(location->data, entry);
    }
    return result;
}
int main()
{
     Trie t;
    char entry[100];
     t.insert("aa", "DET"); 
     t.insert("abacus","NOUN");
     t.insert("abalone","NOUN"); 
     t.insert("abandon","VERB");
     t.insert("abandoned","ADJ"); 
     t.insert("abashed","ADJ");
     t.insert("abate","VERB"); 
     t.insert("this", "PRON");
    if (t.trie_search("this", entry))
        cout<<"'this' was found. pos: "<<entry<<endl;
    if (t.trie_search("abate", entry))
        cout<<"'abate' is found. pos: "<<entry<<endl;
    if (t.trie_search("baby", entry))
        cout<<"'baby' is found. pos: "<<entry<<endl;
    else
        cout<<"'baby' does not exist at all!"<<endl;
    
    if (t.trie_search("aa", entry))
        cout<<"'aa was found. pos: "<<entry<<endl;
    system("pause");
}