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

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

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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)


相关推荐

  • Spring Boot 核心编程思想-第一部分-读书笔记「建议收藏」

    怕什么真理无穷进一步有近一步的欢喜说明本文是Spring Boot核心编程思想记录的笔记,书籍地址:Spring Boot编程思想(核心篇):本书已经简单读过一遍,在第一遍读的时候发现里面…

  • StoredProcedure “存储过程名” 的TextHeader 中存在语法错误

    StoredProcedure “存储过程名” 的TextHeader 中存在语法错误修改存储过程的时候出现StoredProcedure“存储过程名”的TextHeader中存在语法错误出现这样的问题的解决方法(本人修改已成功)在创建存储过程的时候加了注释,把注释删掉就没有问题了(或者把注释放到其他地方)错误代码如下:CREATEPROCEDURE[dbo].[tableToTxtExport]@dbTabNamenvarchar(4000),@dbBoo…

  • 虚拟机安装centos7及网络配置

    虚拟机安装centos7及网络配置原文:https://blog.csdn.net/babyxue/article/details/80970526本篇文章主要介绍了VMware安装Centos7超详细过程(图文),具有一定的参考价值,感兴趣的小伙伴们可以参考一下1.软硬件准备软件:推荐使用VMwear,我用的是VMwear14镜像:CentOS7,下载地址:http://isoredirect.cen…

  • VMware Ubuntu 详尽版安装教程[通俗易懂]

    /**写在前边,本文纯属复制粘贴*/转载地址:http://blog.csdn.net/u013142781/article/details/50529030不是每一个程序员都必须玩过linux,只是博主觉得现在的很多服务器都是linux系统的,而自己属于那种前端也搞,后台也搞,对框架搭建也感兴趣,但是很多生产上的框架和工具都是安装在服务器上的,而且有不少大公司都要求…

  • SSM整合Shiro进行登陆认证和授权详细配置

    SSM整合Shiro进行登陆认证和授权详细配置

  • 位运算符有哪些_或运算和异或运算

    位运算符有哪些_或运算和异或运算位运算符的计算主要用在二进制中。实际开发中也经常会遇到需要用到这些运算符的时候,同时这些运算符也被作为基础的面试笔试题。所以了解这些运算符对程序员来说是十分必要的。于此,记录下我所理解的运算符:如果以开关开灯论:有这样两个开关,0为开关关闭,1为开关打开。与(&)运算与运算进行的是这样的算法:0&0=0,0&1=0,1&0=0,1&1=1在与运算中两个开关是

    2022年10月10日

发表回复

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

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