简单字典树

/*简单的字典树实现*/

#include <stdlib.h>

#include <stdio.h>

#include <string.h>

#define MAX_TRUNK_NUM 30

struct TrieNode

{

intcount;

charval;

struct TrieNode *trunk[MAX_TRUNK_NUM];

};

//初始化节点

void initRoot(struct TrieNode *root)

{

root->count= 0;

root->val= '#';

inti;

for(i = 0;i < MAX_TRUNK_NUM;i++)

root->trunk[i]= NULL;

}

int main(int argc,char *argv[])

{

inti,j;

intid;

intsum = 1;//节点数

struct TrieNode *root;

struct TrieNode *new_node;

/*切记要分配空间*/

root= (struct TrieNode*)malloc(sizeof(struct TrieNode));

initRoot(root);

/*构造字典树的数组*/

charstrs[20][20] ={{"hers"},{"her"},{"his"},{"self"},{"loft"},{"create"},{"baidu"},{"google"}};

//charstrs[20][20] ={{"hers"},{"her"},{"his"},{"self"}};

struct TrieNode *p = root;/*用于迭代*/

/*start构造字典树*/

for(i = 0;i < 20 && strs[i][0] > 0;i++)

{

p= root;

for(j = 0;j < strlen(strs[i]);j++)

{

/*通过id值找到所在位置*/

id= strs[i][j] - 'a';

/*若为空则分配新节点*/

if(p->trunk[id]== NULL)

{

new_node= (struct TrieNode *)malloc(sizeof(struct TrieNode));

initRoot(new_node);

new_node->val= strs[i][j];

p->trunk[id]= new_node;

p->count++;

sum++;

//printf("count:%d,val:%c\n",p->count,p->val);

}

p= p->trunk[id];//指针指向孩子节点

}

}

/*end构造字典树*/

printf("sum= %d\n",sum);//节点个数

charstr[10] = "baidu";//要查找的串

p= root;

i= 0;

/*start查找*/

while(p!= NULL && i < strlen(str) )

{

id= str[i] - 'a';

if (p->trunk[id] == NULL)

{

printf("notmatch!\n");

break;

}

p= p->trunk[id];

i++;

}

if(i == strlen(str))

printf("match!\n");

/*end查找*/

return0;

}