`

Trie- 字典树(单词树)的基本应用

阅读更多
#include <stdio.h>
 #include <stdlib.h>
 #include <string.h>


 int const N= 1000000;
 struct Trie{
     int id;  // 标记每一个单词
     int cnt; // 标记单词前缀的数量
     int next[26]; //  26 个孩子结点
         void init(){
         id= 0; cnt= 0;
         for( int i= 0; i< 26; ++i ) next= 0;
     }
 };


 Trie tree[N];
 int num= 0, root= 0, cid= 0;


 void insert( char* s ){
     int rt= root;
     while( *s ){
         int t= *s- 'a';
         if( tree[rt].next[t]== 0 ){
             tree[++num].init();
             tree[rt].next[t]= num;
         }
         rt= tree[rt].next[t];
         tree[rt].cnt++;
         s++;
     }
     tree[rt].id= ++cid;
 }


 int find( char* s ){
     int rt= root;
     while( *s ){
         int t= *s- 'a';
         rt= tree[rt].next[t];
         if( rt== 0 ) return 0;
         s++;
     }
     return tree[rt].cnt;
 }


 int main(){
     char str[100];
     while( gets(str)!= NULL ){
         if( strlen(str)== 0 ) break;
         insert( str );
     }
     while( gets(str)!= NULL )
     printf("%d\n", find(str) );
    
     return 0;
 }
 

 

Another implement: http://www.cnblogs.com/Xredman/archive/2009/04/10/1433167.html

分享到:
评论

相关推荐

    Go-trie-单词查找树实现Go实现

    Trie,又称为前缀树或字典树,是一种用于存储动态集合或关联数组的树形数据结构。它的主要特点是通过键的前缀来组织节点,从而快速进行前缀查询和模糊搜索。在Go语言中实现Trie,可以有效地支持字符串集合的增删查改...

    HASH(Trie)-.rar_HashTree.h_TRIE_hash树_trie树_字典树

    **哈希 Trie 树(HashTrie)与字典树(Trie树)详解** 哈希 Trie 树,也称为 HashTrie 或者是哈希化的 Trie 树,是一种结合了哈希表和 Trie 数据结构特点的数据结构。它在 Trie 树的基础上引入了哈希函数,提高了...

    Python库 | autocomplete_trie-0.1.tar.gz

    本文将深入探讨“autocomplete_trie-0.1.tar.gz”这个Python库,它是一个专为实现自动补全功能的字典树结构。 标题中的“Python库 | autocomplete_trie-0.1.tar.gz”揭示了我们要讨论的主题是一个名为...

    Java实现字典树TrieTree

    在计算机科学中,字典树(也称为前缀树或TrieTree)是一种高效的数据结构,主要用于存储字符串集合。它能够快速地进行关键词查找、插入和删除操作,尤其适合于处理大量的词汇数据,如在四六级英语考试的高频词汇查询...

    快速单词拼写检错程序(字典树实现)

    这个Java程序利用了数据结构——字典树(Trie),也被称为前缀树或PAT树,它在处理字符串相关的搜索问题时表现出色。下面我们将深入探讨字典树的工作原理及其在拼写检错中的应用。 字典树是一种树形数据结构,每个...

    字典树及其应用 功能介绍及实现

    字典树是一种树形结构,也称为单词查找树或Trie树。它是一种哈希树的变种,典型应用是用于统计、排序和保存大量的字符串(但不仅限于字符串)。字典树的优点是利用字符串的公共前缀来节约存储空间,最大限度地减少...

    字典树查找统计及单词

    在IT领域,字典树(Trie,也称为前缀树或字首树)是一种非常重要的数据结构,常用于高效地存储和检索字符串。在这个场景中,标题“字典树查找统计及单词”指的是利用字典树进行单词查找、统计以及可能的分析操作。...

    trie-dictionary:Patriciaradix树数据结构的实现,存储字典

    trie-dictionary是一个基于Patricia Radix树数据结构的实现,主要用于存储和检索字典中的单词。Patricia Radix树,也称为最小前缀树或PATRICIA树,是一种高效的空间节省的数据结构,用于存储键值对,尤其适用于字符...

    从Trie树(字典树)谈到后缀树.pdf

    Trie树(字典树)和后缀树是两种用于处理字符串问题的高级数据结构,在算法面试中是高频考点,对于程序员来说,掌握它们对于解决实际问题非常重要。Trie树适合解决单词查找以及统计问题,而后缀树则在字符串模式匹配...

    qp-trie-rs:纯Rust中的惯用且快速的QP-trie实现

    首先,我们要理解Trie(字典树)的基本概念。Trie是一种树形数据结构,每个节点代表一个字符串的前缀,根节点不包含任何字符,而叶节点则表示完整的单词。通过这种结构,可以快速地进行前缀查找,因为从根节点到某个...

    算法面试通关40讲完整课件 37-39 字典树

    2. **单词搜索II**:这个题目要求在一个二维网格中找出所有符合特定模式的单词,这需要结合深度优先搜索(DFS)和字典树进行解决,展示了字典树在实际问题中的应用。 ### 5. 应用场景 - **搜索引擎**:字典树常...

    字典树~java语言

    在IT领域,字典树(Trie,也称为前缀树或字首树)是一种用于存储动态集合或关联数组的数据结构。它以高效的方式处理字符串查询,尤其适用于查找具有共同前缀的单词。字典树的主要优点是它可以快速地通过共享前缀来...

    字典树应用,检索文本文件单词

    字典树,也被称为Trie或Prefix Tree,是一种用于存储字符串的数据结构,它在IT领域尤其是在文本处理、搜索引擎和编程语言实现中具有广泛的应用。字典树的主要特点是能够快速进行字符串的查找、插入和删除操作,尤其...

    字典树_英汉词典

    ### 字典树(Trie Tree)相关知识点 #### 一、什么是字典树? 字典树,也称为前缀树或Trie树,是一种用于存储字符串的高效数据结构。它利用了字符串之间的公共前缀来减少存储空间的需求,并且能够快速进行插入、...

    二十六叉字典树

    ### 二十六叉字典树知识点详解 ...二十六叉字典树(Trie)是一种非常有用的数据结构,在处理字符串相关的应用场景中具有独特的优势。无论是从理论研究还是实际应用的角度来看,掌握Trie树的相关知识都是非常有价值的。

    深度优先遍历字典树(统计单词出现的个数)

    在字典树(Trie,也称为前缀树或数字检索树)中应用深度优先遍历,可以有效地统计单词出现的个数。字典树是一种数据结构,常用于存储大量字符串,它允许我们快速查找以特定前缀开头的所有单词。 在Java中,实现字典...

    字典树算法 c语言实现

    字典树,也被称为Trie或前缀树,是一种用于高效存储和检索字符串的数据结构。在C语言中实现字典树,主要涉及到链表、指针操作和动态内存分配等核心概念。以下是对字典树算法及其C语言实现的详细说明: ### 1. 字典...

    字典树的模版(模版)

    字典树作为一种高效的数据结构,在文本搜索、自动补全、拼写检查等领域有着广泛的应用。通过理解其基本原理和实现模版,我们可以更灵活地运用字典树解决实际问题。希望本文能够帮助读者掌握字典树的核心概念,并鼓励...

Global site tag (gtag.js) - Google Analytics