字典树知多少

字典树知多少？

今天看了字典树原理，顺便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;}

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

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