trie字典树实现

一时失言乱红尘 2022-09-27 15:22 185阅读 0赞

实现了一个简单的字典树.  
假设所有的字符只有26个小写字母，并且除了节点出现的次数之外还增加了类似map功能的索引。  
假如不只有26个字母，需要相应的做一些修改。

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    #define ALPHABET_SIZE 26
    int num = 0;
    
    typedef struct trie_node
    {
        int count;   // 记录该节点代表的单词的个数
        int index;   //该节点的索引
        trie_node *children[ALPHABET_SIZE]; // 各个子节点
    }*trie;
    
    trie_node* create_trie_node()
    {
        trie_node* pNode = (trie_node*) malloc(sizeof(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;
        node->index = num++;
    }
    
    /** * 查询：不存在返回-1，存在返回索引index */
    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 -1;
        }
        else {
            return node->index;
        }
    }
    
    int main()
    {
        trie root = create_trie_node();
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，185人围观）

还没有评论，来说两句吧...

相关阅读

相关字典树（Trie树）的 Java 实现

定义用了两个第三方jar包，lombok 和 hutool，可自行替换 @Data public class TrieNode {

落日映苍穹つ/ 2022年11月01日 10:54/ 0 赞/ 191 阅读

相关 Implement Trie (Prefix Tree) - 实现 Trie (前缀树 - 字典树)

Implement Trie (Prefix Tree) - 实现 Trie (前缀树 - 字典树) [https://leetcode-cn.com/problems/

待我称王封你为后i/ 2022年10月19日 00:56/ 0 赞/ 208 阅读

相关 trie字典树实现

实现了一个简单的字典树. 假设所有的字符只有26个小写字母，并且除了节点出现的次数之外还增加了类似map功能的索引。假如不只有26个字母，需要相应的做一些修改。

一时失言乱红尘/ 2022年09月27日 15:22/ 0 赞/ 186 阅读

相关 PHP实现Trie树（字典树）

Trie树的概念（百度的解释）：字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被

╰半橙微兮°/ 2022年09月21日 04:59/ 0 赞/ 179 阅读

相关 trie树(字典树)java实现

public class Trie{ private Node root; public Trie(){

àì夳堔傛蜴生んèń/ 2022年08月21日 15:00/ 0 赞/ 229 阅读

相关 Trie树（字典树）

很有段时间没写此系列了，今天我们来说Trie树，Trie树的名字有很多，比如字典树，前缀树等等。一：概念下面我们有and,as,at,cn,com这些关键词，那么如何

阳光穿透心脏的1/2处/ 2022年08月14日 00:00/ 0 赞/ 261 阅读

相关 python 实现 trie(字典) 树

`tire 树也叫字典树，也是一种 N 叉树，是一种特殊的前缀树结构。` `1、前缀树`是`N叉树`的一种特殊形式。通常来说，一个前缀树是用来`存储字符串`的。前缀树的每一

青旅半醒/ 2022年05月21日 06:23/ 0 赞/ 213 阅读

相关 Trie树——字典树

1、概述 Trie树，又称字典树，单词查找树或者前缀树，是一种用于快速检索的多叉树结构，如英文字母的字典树是一个26叉树，数字的字典树是一个10叉树。 Trie一词来自r

朴灿烈づ我的快乐病毒、/ 2022年05月21日 06:20/ 0 赞/ 307 阅读

相关 Trie树（字典树）

1. Trie树 Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索

梦里梦外;/ 2022年05月17日 05:21/ 0 赞/ 232 阅读

相关字典树trie

字典树　　又称单词查找树，[Trie树][Trie]，是一种[树形结构][Link 1]，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符

小灰灰/ 2021年09月30日 10:06/ 0 赞/ 423 阅读