Tire用于字符串统计,快速查找:
实例:
// example_Trie.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <stdlib.h>
#include <memory.h> ?
/************************************************************************/
/*
利用trie树进行词频统计
*/
/************************************************************************/
const int num_chars = 26; ?
typedef struct Trie_node{
int ?count;
struct Trie_node *next[26];
}TrieNode,*Trie;
TrieNode* createTrieNode()
{
TrieNode* root =(TrieNode*)malloc(sizeof(TrieNode));
root->count = 0;
memset(root->next,sizeof(root->next));
return root;
}
void trie_insert(Trie root,const char* word)
{
TrieNode* node = root;
const char* p = word;
while(*p != ' ')
{
if (NULL == node->next[(*p)-'a'])
{
node->next[(*p)-'a'] = createTrieNode();
}
node = node->next[(*p)-'a'];
p++;
}
node->count +=1;?
}
int trie_search(Trie root,const char* word)
{
TrieNode* node = root;
const char* p = word;
while(*p != ' ')
{
if (node->next[*p-'a'] == NULL)
{
break;
}
node = node->next[*p-'a'];
p++;
}
return ((*p == ' ') && (node->count > 0) );
}
int trie_count(Trie root,const char* word)
{
int ret = 0;
TrieNode* node = root;
const char* p =word;
while(*p != ' ')
{
if (node->next[*p - 'a'] == NULL)
{
break;
}
node = node->next[*p - 'a'];
p++;
}
if (*p == ' ')
{
ret = node->count;
}
return ret;
}
int main(){ ?
Trie t = createTrieNode(); ?
char word[][10] = {"test","study","open","show","shit","work","test","tea","word","area","test"}; ?
for(int i = 0;i < 15;i++ ){ ?
trie_insert(t,word[i]); ?
} ?
for(int i = 0;i < 15;i++ ){ ?
printf("the word %s appears %d times in the trie-treen",word[i],trie_count(t,word[i])); ?
} ?
char s[10] = "testit"; ?
printf("the word %s exist? %d n",s,trie_search(t,s)); ?
return 0; ?
} ?
运行结果:
the word test appears 5 times in the trie-tree the word study appears 1 times in the trie-tree the word open appears 1 times in the trie-tree the word show appears 1 times in the trie-tree the word shit appears 1 times in the trie-tree the word work appears 2 times in the trie-tree the word work appears 2 times in the trie-tree the word test appears 5 times in the trie-tree the word tea appears 1 times in the trie-tree the word word appears 2 times in the trie-tree the word area appears 1 times in the trie-tree the word word appears 2 times in the trie-tree the word test appears 5 times in the trie-tree the word test appears 5 times in the trie-tree the word test appears 5 times in the trie-tree the word testit exist? 0 请按任意键继续. . .