美文网首页
Trie树 模板

Trie树 模板

作者: 失树 | 来源:发表于2017-12-26 11:00 被阅读0次
#include <iostream>
#include <string>
using namespace std;

#define ALPHABET_SIZE 26

typedef struct trie_node
{
    int count;   // 记录该节点代表的单词的个数
    trie_node *children[ALPHABET_SIZE]; // 各个子节点 
}*trie;

trie_node* create_trie_node()
{
    trie_node* pNode = new trie_node();
    pNode->count = 0;
    for(int i=0; i<ALPHABET_SIZE; ++i)
        pNode->children[i] = NULL;
    return pNode;
}

void trie_insert(trie root, char* key)
{
    trie_node* node = root;
    char* p = key;
    while(*p)
    {
        if(node->children[*p-'a'] == NULL)
        {
            node->children[*p-'a'] = create_trie_node();
        }
        node = node->children[*p-'a'];
        ++p;
    }
    node->count += 1;
}

/**
 * 查询:不存在返回0,存在返回出现的次数
 */ 
int trie_search(trie root, char* key)
{
    trie_node* node = root;
    char* p = key;
    while(*p && node!=NULL)
    {
        node = node->children[*p-'a'];
        ++p;
    }

    if(node == NULL)
        return 0;
    else
        return node->count;
}

int main()
{
    // 关键字集合
    char keys[][8] = {"the", "a", "there", "answer", "any", "by", "bye", "their"};
    trie root = create_trie_node();

    // 创建trie树
    for(int i = 0; i < 8; i++)
        trie_insert(root, keys[i]);

    // 检索字符串
    char s[][32] = {"Present in trie", "Not present in trie"};
    printf("%s --- %s\n", "the", trie_search(root, "the")>0?s[0]:s[1]);
    printf("%s --- %s\n", "these", trie_search(root, "these")>0?s[0]:s[1]);
    printf("%s --- %s\n", "their", trie_search(root, "their")>0?s[0]:s[1]);
    printf("%s --- %s\n", "thaw", trie_search(root, "thaw")>0?s[0]:s[1]);

    return 0;
}

相关文章

  • Trie树 模板

  • trie树

    文章内容来自 Trie树:应用于统计和排序Trie树 trie树又称:字典树、单词查找树、前缀树等,总之是一种树状...

  • 树结构之Trie

    1. 什么是trie树 1.Trie树 (特例结构树)Trie树,又称单词查找树、字典树,是一种树形结构,是一种哈...

  • 实现 Trie

    数据结构之Trie树Trie树:应用于统计和排序

  • Trie树

    一、定义 Trie树,又称为单词查找树,是一种树形结构(Trie一词源于单词Retrieval-取出)。Trie树...

  • leetcode——字典树(Trie树)的实现

    leetcode——实现Trie(前缀树) 题目 实现一个 Trie (前缀树),包含 insert, searc...

  • 算法笔记 - Trie 树

    Trie树是一种非常常见的算法 Trie树的主要用途是快速地匹配字符串 Tire树可以记录数值 Trie树的实现成...

  • 以太坊详解 之 Merkle Patricia Tree

    基础知识 Trie树 Trie是一种搜索树,又称字典树(digital tree)和前缀树(prefix tree...

  • 数据结构与算法笔记day21:Trie树|AC自动机

    1Trie树 这节课学习了一种特殊的树,Trie树。Trie树是一种解决字符串快速匹配问题的数据结构。如果用来...

  • Leetcode 208 实现 Trie (前缀树)

    实现 Trie (前缀树) 题目 实现一个 Trie (前缀树),包含 insert, search, 和 sta...

网友评论

      本文标题:Trie树 模板

      本文链接:https://www.haomeiwen.com/subject/gbudgxtx.html