字典树的基本知识及使用C语言的相关实现_C 语言

概念

     如果我们有and,as,at,cn,com这些关键词,那么trie树(字典树)是这样的:

     从上面的图中,我们或多或少的可以发现一些好玩的特性。

      第一:根节点不包含字符,除根节点外的每一个子节点都包含一个字符。

      第二:从根节点到某一节点,路径上经过的字符连接起来,就是该节点对应的字符串。

      第三:每个单词的公共前缀作为一个字符节点保存。

 

使用范围

     既然学Trie树,我们肯定要知道这玩意是用来干嘛的。

     第一:词频统计。

            可能有人要说了,词频统计简单啊,一个hash或者一个堆就可以打完收工,但问题来了,如果内存有限呢?还能这么

             玩吗?所以这里我们就可以用trie树来压缩下空间,因为公共前缀都是用一个节点保存的。

     第二: 前缀匹配

            就拿上面的图来说吧,如果我想获取所有以"a"开头的字符串,从图中可以很明显的看到是:and,as,at,如果不用trie树,

            你该怎么做呢?很显然朴素的做法时间复杂度为O(N2) ,那么用Trie树就不一样了,它可以做到h,h为你检索单词的长度,

            可以说这是秒杀的效果。

数据结构定义

  #define MAX 26 // 字符集大小 

  typedef struct trieNode {
    struct trieNode *next[MAX];
    int count; // 记录该字符出现次数
  } trieNode; 

next数组表示每层有多少类的数,如果只是小写字母,26即可

实现方法
搜索字典项目的方法:

  •     从根节点开始一次搜索
  •     获取要查找关键词的第一个字母,并根据该字母选择对应的子树并转到该子树继续进行检索
  •     在相应的子树上,获取要查找关键词的第二个字母,并进一步选择对应的子树进行检索
  •     迭代过程
  •     在某个节点处,关键词的所有字母已被取出,则读取附在该结点上的信息,即完成查找

其他操作类似

实现模板

初始化根结点

  /**
   * 初始化Trie树根结点
   */
  void initTrie(trieNode **root)
  {
    int i; 

    *root = (trieNode *)malloc(sizeof(trieNode));
    (*root)->count = 0; 

    for (i = 0; i < MAX; i ++) {
      (*root)->next[i] = NULL;
    }
  } 

插入单词到trie树

 

  /**
   * Trie树插入操作
   */
  void insert(char *str, trieNode *root)
  {
    int i; 

    trieNode *p = root; 

    while (*str != '\0') {
      if (p->next[*str - 'a'] == NULL) {
        trieNode *tmp = (trieNode *)malloc(sizeof(trieNode));
        for (i = 0; i < MAX; i ++) {
          tmp->next[i] = NULL;
        }
        tmp->count = 1;
        p->next[*str - 'a'] = tmp;
        p = p->next[*str - 'a'];
      } else {
        p = p->next[*str - 'a'];
        p->count ++;
      } 

      str ++;
    }
  }

统计查找单词数量

  /**
   * 统计前缀出现次数
   */
  int count(char *search, trieNode *root)
  {
    trieNode *p = root; 

    while (*search != '\0') {
      if (p->next[*search - 'a'] == NULL) {
        return 0;
      } else {
        p = p->next[*search - 'a'];
        search ++;
      }
    } 

    return p->count;
  } 

清理trie树

  /**
   * 清理trie树
   */
  void delTrie(trieNode *root)
  {
    int i; 

    for (i = 0; i < MAX; i ++) {
      if (root->next[i] != NULL) {
        delTrie(root->next[i]);
      }
    } 

    free(root);
  } 

时间复杂度
插入、查找的时间复杂度均为O(n),n为字符串的长度

空间复杂度较高,O(26^n),典型空间换时间

参考题目

ac代码:

 

  #include <stdio.h>
  #include <stdlib.h>
  #include <string.h> 

  #define MAX 26 // 字符集大小 

  typedef struct trieNode {
    struct trieNode *next[MAX];
    int count; // 记录该字符出现次数
  } trieNode; 

  /**
   * 初始化Trie树根结点
   */
  void initTrie(trieNode **root)
  {
    int i; 

    *root = (trieNode *)malloc(sizeof(trieNode));
    (*root)->count = 0; 

    for (i = 0; i < MAX; i ++) {
      (*root)->next[i] = NULL;
    }
  } 

  /**
   * Trie树插入操作
   */
  void insert(char *str, trieNode *root)
  {
    int i; 

    trieNode *p = root; 

    while (*str != '\0') {
      if (p->next[*str - 'a'] == NULL) {
        trieNode *tmp = (trieNode *)malloc(sizeof(trieNode));
        for (i = 0; i < MAX; i ++) {
          tmp->next[i] = NULL;
        }
        tmp->count = 1;
        p->next[*str - 'a'] = tmp;
        p = p->next[*str - 'a'];
      } else {
        p = p->next[*str - 'a'];
        p->count ++;
      } 

      str ++;
    }
  } 

  /**
   * 统计前缀出现次数
   */
  int count(char *search, trieNode *root)
  {
    trieNode *p = root; 

    while (*search != '\0') {
      if (p->next[*search - 'a'] == NULL) {
        return 0;
      } else {
        p = p->next[*search - 'a'];
        search ++;
      }
    } 

    return p->count;
  } 

  /**
   * 清理trie树
   */
  void delTrie(trieNode *root)
  {
    int i; 

    for (i = 0; i < MAX; i ++) {
      if (root->next[i] != NULL) {
        delTrie(root->next[i]);
      }
    } 

    free(root);
  } 

  int main(void)
  {
    char str[15];
    trieNode *root; 

    // 初始化根结点
    initTrie(&root); 

    while (gets(str) && str[0] != '\0') {
      // 插入Trie树
      insert(str, root);
    } 

    // 查找前缀出现次数
    while (gets(str) && str[0] != '\0') {
      printf("%d\n", count(str, root));
    } 

    delTrie(root); 

    return 0;
  }

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索c
字典树
哈夫曼编码c语言实现、des加密算法c语言实现、算法 c语言实现、aes加密算法c语言实现、rsa算法c语言实现,以便于您获取更多的相关知识。

时间: 2024-09-27 08:58:00

字典树的基本知识及使用C语言的相关实现_C 语言的相关文章

字典树概述

字典树简介 字典树(Trie Tree),又称单词查找树,是键树的一种,典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计. 字典树有3个基本性质: 1.根节点不包含字符,其余的每个节点都包含一个字符: 2.从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串: 3.每个节点的所有子节点包含的字符都不相同. 字典树的结构一般如下图所示: 以字符串为例,我们可以将其存储结构写成如下形式: #define MAX 26 //字符集的大

算法题:HDU 2846 Repository(字典树,计数)

链接: http://acm.hdu.edu.cn/showproblem.php?pid=2846 题目: Repository Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1657    Accepted Submission (s): 605 Problem Description When you go shopping,

算法题:HDU 1251 统计难题(字典树,统计前缀个数)

链接: http://acm.hdu.edu.cn/showproblem.php?pid=1251 题目 Problem Description Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组 成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的 前缀). Input 输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师 交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提

算法题:HDU 1247 Hat’s Words(字典树)

链接: http://acm.hdu.edu.cn/showproblem.php?pid=1247 题目大意: 按照字典序给出多个单词,  可以发现里面有些单词是由字典中其它的两个单词组成的.按顺 序输出所有符合这个条件的单词. 分析与总结: 用字典树存下所有的单词,然后对所有单词一一枚举, 对每个单词, 又进行"拆分", 拆分可能有多种情况,所以枚举单词拆分的中点,在字典序中查找拆分后的两部分是否存在,存在即输 出. 代码: #include<iostream> #in

算法题:HDU 1075 What Are You Talking About(字典树学习题)

链表: http://acm.hdu.edu.cn/showproblem.php?pid=1075 题目: What Are You Talking About Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 102400/204800 K (Java/Others) Total Submission(s): 7939    Accepted Submission(s): 2470 Problem Description Ign

从Trie树(字典树)谈到后缀树(10.28修订)

作者:July.yansha. 出处:http://blog.csdn.net/v_JULY_v .  引言     常关注本blog的读者朋友想必看过此篇文章:从B树.B+树.B*树谈到R 树,这次,咱们来讲另外两种树:Tire树与后缀树.不过,在此之前,先来看两个问题.     第一个问题: 一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词,请给出思想,给出时间复杂度分析.     之前在此文:海量数据处理面试题集锦与Bit-map详解中给出的参考答案:用trie

HDU 4099 字典树+高精度

题意:给出某项斐波那契数的前几位,让输出最小的一项前缀为这个串的项数. 先高精度算出前100000项斐波那契的前50位.并把前40位存进字典树预处理一下.字典树节点值存为第几项.然后输入字符串直接查找. #include <iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define N 50 int fib[3][N+1]; cla

算法题:HDU 3724 Encoded Barcodes(字典树,计算前缀数)

链接: http://acm.hdu.edu.cn/showproblem.php?pid=3724 题目: Encoded Barcodes Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1022    Accepted Submission (s): 337 Problem Description All the big mall

HDU1075 字典树

我用字典树写的 按照题意做就行 #include<iostream> #include<cstring> #include<cstdio> using namespace std; class trie { public: trie* next[26]; char str_temp[12]; int num; //记录前缀的个数 bool value; //标记这里是不是一个单词 trie() { for(int i=0; i<26; i++) next[i]=0