字典树

功能

字典树是用数组存储大量字符串的一种算法

字典树算法开辟空间非常大，但是对于字符串插入和查询有很快的速度

用法

结构

{

当前结点数；

存储字符串的数组[MAX_N][26];

存储字符串结点数组[MAX_N];

}

例如存储apple和apl的例子

下面一段代码：

struct trietree

{

int nodenumber;  //结点数量

int *ch[MAX_N];  //存储字符串数组指针 同int ch[MAX_N][26]

int node[MAX_N];//存储字符串终止结点的数组

void init()//初始化函数

{

nodenumber=0;//结点数置0

memset(ch,0,sizeof(ch));

memset(node,0,sizeof(node));

}

void insert(char *str)//插入函数

{

int p=0;

for(int i=0;str[i];i++)

{

if(ch[p]==NULL)

{

ch[p]=new int[MAX_C];//开辟存储空间

memset(ch[p],-1,sizeof(int)*MAX_C);

}

if(ch[p][str[i]-'a']==-1)

{

ch[p][str[i]-'a']=++nodenumber;

}

p=ch[p][str[i]-'a'];

}

node[p]++;//生成结点

}

};