首页 > 代码库 > 字典树模板

字典树模板

2024-07-16 11:42:05   230人阅读

定义一颗字典树：

struct Trie
{
    int n;  // n可以存储相关有用信息，视情况而定
    Trie *next[maxn];  //maxn视字典树中有多少种元素而定
}


定义字典树的根并初始化：

Trie *root;
void init()
{
    root = (Trie *)malloc(sizeof(Trie));
    root -> n = 0;
    for(int i = 0;i < maxn; i++)
    root -> next[i] = NULL;
}

建立字典树：

void insert(char *word)
{
    Trie *temp = root;
    for(int i = 0; i < strlen(word); i++)
    {
        int pos = word[i] - 'a';
        if(temp -> next[pos] == NULL)
        {
            Trie *cur = (Trie *)malloc(sizeof(Trie));
            for(int j = 0;i < maxn; i++)
            {
                cur -> next[i] = NULL;
                cur -> n = 0;
            }
            temp -> next[pos] = cur;
        }
        temp = temp ->next[pos];
    }
    temp -> n = 1;   // 单词结尾处标记1
}

查找：

bool search(char *word)
{
    Trie *temp = root;
    for(int i = 0; i < strlen(word); i++)
    {
        temp = temp -> next[word[i] - 'a'];
        if(temp == NULL) 
            return false; //没有以次为前缀的单词
        if(temp -> n = 1) 
            return true; //该单词是别的单词的前缀 
    } 
    return true; //别的单词是该单词的前缀
}
释放内存

void del(Trie *cur)    //采用递归来释放
{
    for(int i = 0;i < maxn; i++)
    {
        if(cur -> next[i] != NULL)
        del(cur -> next[i]);
    }
    free(cur);
}


联系
我们