字典树知多少？

今天看了字典树原理，顺便AC了几个简单的题目，做一下总结。

（字典树）

字典树的基本功能是用来查询某个单词（前缀）在所有单词中出现次数的一种数据结构，它的插入和查询复杂度都为O(len),Len为单词（前缀）长度，但是它的空间复杂度却非常高，如果字符集是26个字母，那每个节点的度就有26个，典型的以空间换时间结构。

字典树基本模板：

下面是创建字典树的代码

// TrieNode.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <stdio.h>
#include <iostream>
#define MAX 26
using namespace std;

typedef struct TrieNode
{
int nCount;
struct TrieNode *next[MAX];
}TrieNode;

TrieNode Memory[1000000];
int allocp = 0;

void InitTrieRoot(TrieNode **pRoot)
{
*pRoot = NULL;
}

TrieNode *CreateTrieNode()
{
int i;
TrieNode *p;

p = &Memory[allocp++];
p->nCount = 1;
for(i = 0 ; i < MAX ; i++)
{
p->next[i] = NULL;
}

return p;
}

void InsertTrie(TrieNode **pRoot , char *s)
{
int i , k;
TrieNode *p;

if(!(p = *pRoot))
{
p = *pRoot = CreateTrieNode();
}
i = 0;
while(s[i])
{
k = s[i++] - 'a'; //确定branch
if(p->next[k])
p->next[k]->nCount++;
else
p->next[k] = CreateTrieNode();
p = p->next[k];
}
}

int SearchTrie(TrieNode **pRoot , char *s)
{
TrieNode *p;
int i , k;

if(!(p = *pRoot))
{
return 0;
}
i = 0;
while(s[i])
{
k = s[i++] - 'a';
if(p->next[k] == NULL) return 0;
p = p->next[k];
}
return p->nCount;
}

int main(void)
{
char s[11];

TrieNode *Root = NULL;
InitTrieRoot(&Root);
while(gets(s) && s[0])
{
InsertTrie(&Root , s);
cout<<" zz "<<endl;
}

while(gets(s))
{
printf("%d\n", SearchTrie(&Root , s));
}

system("pause");
return 0;
}

// TrieNode.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include <stdio.h>#include <iostream>#define  MAX    26 using namespace std;typedef struct TrieNode{int nCount; struct TrieNode *next[MAX];}TrieNode;TrieNode Memory[1000000];int allocp = 0;void InitTrieRoot(TrieNode **pRoot){*pRoot = NULL;}TrieNode *CreateTrieNode(){int i;TrieNode *p;p = &Memory[allocp++];p->nCount = 1;for(i = 0 ; i < MAX ; i++){p->next[i] = NULL;}return p;}void InsertTrie(TrieNode **pRoot , char *s){int i , k;TrieNode *p;if(!(p = *pRoot)){p = *pRoot = CreateTrieNode();}i = 0;while(s[i]){k = s[i++] - 'a'; //确定branchif(p->next[k])p->next[k]->nCount++;elsep->next[k] = CreateTrieNode();p = p->next[k];}}int SearchTrie(TrieNode **pRoot , char *s){TrieNode *p;int i , k;if(!(p = *pRoot)){return 0;}i = 0;while(s[i]){k = s[i++] - 'a'; if(p->next[k] == NULL)    return 0;p = p->next[k];}return p->nCount;}int main(void){char s[11];    TrieNode *Root = NULL;   InitTrieRoot(&Root);    while(gets(s) && s[0])  {       InsertTrie(&Root , s); cout<<"  zz "<<endl;}    while(gets(s))   {        printf("%d\n", SearchTrie(&Root , s));   }    system("pause");return    0;}

结果如下：很显然程序已经完成了功能

也看到了字典树的强大！！！