字典树

[syswj@host 0813]$ cat dic_tree.cpp 
#include <iostream>
#include <stdio.h>

#define MAX 26
using namespace std;

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

void init(TrieNode **pRoot)//初始化
{
    *pRoot = NULL;
}

TrieNode* create()//创建新节点
{
    TrieNode *a = new TrieNode;
    a->ncount = 0;
    for(int i = 0; i < MAX; ++i)
        a->next[i] = NULL;
    return a;
}

void insert(TrieNode **pRoot, char *s)//插入
{
    int i, k;
    TrieNode *p;
    if(!(p = *pRoot))
    {
        p = *pRoot = create();
    }
    i = 0;
    while(s[i])
    {
        k = s[i++] - ‘a‘;
        if(!p->next[k])
        {
            p->next[k] = create();
        }
        p = p->next[k];
    }
    p->ncount++;
}

int search(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(int argc, const char *argv[])
{
  TrieNode *p;
  init(&p);
  char a[20] = {"abc"} ;
  insert(&p, a);
  insert(&p, a);
  insert(&p,"bcd");
  insert(&p,a);
  cout << search(p,a) << endl;
  cout << search(p,"bcd") << endl;
    return 0;
}