字典树数组实现「建议收藏」

字典树数组实现「建议收藏」字典树是一种很实用也相对好理解的数据

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

   

字典树又称单词查找树,Trie树,是一种树形结构。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较。

之前在网上找的都是些用指针实现的,代码看起来很难懂,今天学习了一种用数组实现的。学习起来简单易懂


int ch[200010][27];  //节点编号   
int sz;        //字典树节点个数
int val[200010];   //节点的值
void init()
{
    sz=1;
    memset(ch,0,sizeof(ch));
    memset(val,0,sizeof(val));
}
void insert(char *s)
{
    int u=0,c;
    for(int i=0;i<strlen(s);i++)
    {
        c=s[i]-'a';
        if(!ch[u][c])
            ch[u][c]=sz++;
        u=ch[u][c];
        val[u]++;        //!!!
    }
}
int query(char *s)
{
    int u=0,c;
    for(int i=0;i<strlen(s);i++)
    {
        c=s[i]-'a';
        if(!ch[u][c])
            return 0;
        u=ch[u][c];
    }
    return  val[u];
}

说明一下代码中注释的部分,这个语句放在for循环外面有时也是很方便的,当遇到一些特殊的标记,比如1或-1,就代表着字符串的结束,而字符串的中间部分默认都为0。这在有些题中使用是很方便的。


这个数组实现和指针的版本也是有些区别的,数组的版本并不怎么直观,因为在数组中实现的树没有“层”的概念。代替的是节点的“编号”,通过这个编号可以向“下一层”去找节点,也可以通过编号获得字符串的一些其他信息,很多题都需要在结构体或是数组中记录或保存信息,当然这个下标利用的就是“编号”。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/197523.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 导入导出封装的工具类 (一) 利用POI封装

    导入导出封装的工具类 (一) 利用POI封装

    2021年11月24日
  • shell中if elif_shell编程if语句格式

    shell中if elif_shell编程if语句格式测试shell脚本编程时,写了如下代码:在对if-elif-else分支进行数值判断时,发现一个奇怪的现象:如果使用testconditon(即[condition])进行判定,当第一条if条件为假时,无论代码中的elif语句条件是否为真,都输出elif分支下的语句;查看输出结果,发现输出结果显然与期望值不一样为了能够得到预期结果,发现如果采用双圆括号是进行判断,可得到预期结…

  • bootstrap-fileinput使用手册

    bootstrap-fileinput使用手册一、准备1、插件下载地址:https://github.com/kartik-v/bootstrap-fileinput/下载后的压缩包解压文件夹内容如下:  js:插件核心js代码,引用fileinput.min.js/fileinput.js即可,默认插件语言为英文,如需要中文需要引用js/locales/zh.js(其他语言引用相应的js文件) …

  • dategrip激活码(JetBrains全家桶)

    (dategrip激活码)本文适用于JetBrains家族所有ide,包括IntelliJidea,phpstorm,webstorm,pycharm,datagrip等。https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~C…

  • Cubieboard2开发要点简记

    Cubieboard2开发要点简记要在Cubieboard2上开发四轴飞行器的控制模块,需要编写远程控制的接收端和底层控制模块。换言之需要编写用户层client软件和driver,本人负责单片机模块,此文是跟踪笔记,权当参考和提醒。值得声明的是,由于嵌入式平台的平台相关性很大,相关操作不一定可以完全再现。学习资料主要参考论坛——————————————————————————————2013年12月23号14点

  • matlab的插值方法[通俗易懂]

    matlab的插值方法[通俗易懂]1.Lagrange插值插值是在已知数据之间寻找估计值的过程。在信号处理和图像处理中,插值极其常用。类型很多:比如多项式插值,一、二、三维插值,样条插值等。方法介绍:对给定的n个插值点x1,x2,⋯,xnx1,x2,⋯,xn{x_1},{x_2},\cdots,{x_n}及对应的函数值y1,y2,⋯,yny1,y2,⋯,yn{y_1},{y_2},\cdots,{y_n}…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号