1. 全栈程序员必看首页

字典树模板及例题_模板计算公式

全栈程序员-用户IM • • 未分类

字典树模板及例题_模板计算公式转载：Trie树的常见应用大总结（面试+附代码实现）（一）Trie的简介Trie树，又称字典树，单词查找树或者前缀树，是一种用于快速检索的多叉树结构，如英文字母的字典树是一个26叉树，数字的字典树是一个10叉树。他的核心思想是空间换时间，空间消耗大但是插入和查询有着很优秀的时间复杂度。（二）Trie的定义Trie树的键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子…

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

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

转载：Trie树的常见应用大总结（面试+附代码实现）

（一）Trie的简介
Trie树，又称字典树，单词查找树或者前缀树，是一种用于快速检索的多叉树结构，如英文字母的字典树是一个26叉树，数字的字典树是一个10叉树。他的核心思想是空间换时间，空间消耗大但是插入和查询有着很优秀的时间复杂度。

（二）Trie的定义

Trie树的键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀（prefix）,从根节点到当前结点的路径上的所有字母组成当前位置的字符串，结点可以保存当前字符串、出现次数、指针数组(指向子树)以及是否是结尾标志等等。

struct Trie
{

    int count;//前缀出现的次数
    struct Trie *next[SIZE];//孩子节点的数目
    bool isEnd; //判断到这个位置是否是一个单词
    string name;
    
    Trie()//构造函数
    {

        count=0;
        memset(next,0,sizeof(next));
        isEnd=false;
        name.clear();
    }
};

Trie树可以利用字符串的公共前缀来节约存储空间，如下图所示：

字典树模板及例题_模板计算公式

它有3个基本性质：
(1) 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
(2) 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
(3) 每个节点的所有子节点包含的字符都不相同。 

 

（三）Trie树的基本操作
（1）插入操作
按下标索引逐个插入字母，若当前字母存在则继续下一个，否则new出当前字母的结点，所以插入的时间复杂度只和字符串的长度n有关，为O(n)。

void Insert(string s)
{

    int len=s.length();
    int pos;
    struct Trie *u=root;
    for(int i=0;i<len;i++)
    {

        pos=s[i]-‘0’;
        if(u->next[pos]==NULL)//数字在边上，或者说是以位置的方式体现，不需要存储
            u->next[pos]=new Trie;
        u=u->next[pos];
        u->count++;        
    }
    u->isEnd=true;//表明为一个单词的节点
    u->name=s;//同时存储单词
}

 

（2）查询操作
和插入操作相仿，若查询途中某一个结点并不存在，则直接就return返回。否则继续下去，当字符串结束时，trie树上也有结束标志，那么证明此字符串存在，return true；

int Search(string s)
{

    struct Trie *u=root;
    int len=s.length();
    for(int i=0;i<len;i++)
    {

        int pos=s[i]-‘0’;
        if(u->next[pos]==NULL)
            return 0;
        else
            u=u->next[pos];
    }
    return u->count;
} 

（3）删除操作

一般来说，对Trie单个结点的删除操作不常见，所以我在这里也只提供递归删除整个树的操作

void del(struct Trie *u)
{

    for(int i=0;i<SIZE;i++)
    {

        if(u->next[i]!=NULL)
            del(u->next[i]);
    }
    delete(u);
}

 

（4）遍历操作

如果我们想要将trie中的字符串排序输出，直接先序遍历即可。

void print(struct Trie *u)
{

    if(u->isEnd)
        cout<<u->name<<“:”<<u->count<<endl;
    for(int i=0;i<SIZE;i++)
        if(u->next[i]!=NULL)
            print(u->next[i]);
}

 

上面整体的模板：

#include<iostream>
#include<cstring>
using namespace std;

const int SIZE=10; 
struct Trie
{
	int count;//前缀出现的次数
	struct Trie *next[SIZE];//孩子节点的数目 
	bool isEnd; //判断到这个位置是否是一个单词
	string name; 
	
	Trie()//构造函数 
	{
		count=0;
		memset(next,0,sizeof(next));
		isEnd=false;
	} 
}; 

struct Trie *root=new Trie;//建立根节点

void Insert(string s)
{
	int len=s.length();
	int pos;
	struct Trie *u=root;
	for(int i=0;i<len;i++)
	{
		pos=s[i]-'0';
		if(u->next[pos]==NULL)//数字在边上，或者说是以位置的方式体现，不需要存储 
			u->next[pos]=new Trie;
		u=u->next[pos];
		u->count++;		
	}
	u->isEnd=true;//表明为一个单词的节点
	u->name=s;//同时存储单词 
} 

int Search(string s)
{
	struct Trie *u=root;
	int len=s.length();
	for(int i=0;i<len;i++)
	{
		int pos=s[i]-'0';
		if(u->next[pos]==NULL)
			return 0;
		else
			u=u->next[pos];
	}
	return u->count;
} 

void del(struct Trie *u)
{
	for(int i=0;i<SIZE;i++)
	{
		if(u->next[i]!=NULL)
			del(u->next[i]);
	}
	delete(u);
}

void print(struct Trie *u)
{
	if(u->isEnd)
		cout<<u->name<<":"<<u->count<<endl;
	for(int i=0;i<SIZE;i++)
		if(u->next[i]!=NULL)
			print(u->next[i]); 
}

int main()
{
	int n;
	string s;

	cin>>n;
	while(n--)
	{
		cin>>s;
		Insert(s);
	}
		
	print(root);//打印检查下 
		
	del(root);//释放树，下次重新建立 

	return 0;
}

 

对于不同的题目，将模板稍微改动就好。

下面是一个例题，用来判断是否存在前缀。

来源：POJ3630 HDU1671 ZOJ2876 UVA11362 Phone List【字典树】

字典树模板及例题_模板计算公式

字典树模板及例题_模板计算公式

 

代码：

#include<iostream>
#include<cstring>
using namespace std;

const int SIZE=10; 
struct Trie
{
	int count;//前缀出现的次数
	struct Trie *next[SIZE];//孩子节点的数目 
	bool isEnd; //判断到这个位置是否是一个单词
	string name; 
	
	Trie()//构造函数 
	{
		count=0;
		memset(next,0,sizeof(next));
		isEnd=false;
		name.clear();
	} 
}; 

struct Trie *root=new Trie;//建立根节点

bool Insert(string s)
{
	int len=s.length();
	int pos;
	struct Trie *u=root;
	for(int i=0;i<len;i++)
	{
		pos=s[i]-'0';
		if(u->next[pos]==NULL)//数字在边上，或者说是以位置的方式体现，不需要存储 
			u->next[pos]=new Trie;
		u=u->next[pos];
		u->count++;
		
		if(u->count>1&&u->isEnd==true)//如果出现前缀问题 
			return false;	 		
	}
	u->isEnd=true;//表明为一个单词的节点
	u->name=s;//同时存储单词 
	if(u->count>1&&u->isEnd==true)//如果出现前缀问题 
			return false;	
	return true;
} 

int Search(string s)
{
	struct Trie *u=root;
	int len=s.length();
	for(int i=0;i<len;i++)
	{
		int pos=s[i]-'0';
		if(u->next[pos]==NULL)
			return 0;
		else
			u=u->next[pos];
	}
	return u->count;
} 

void del(struct Trie *u)
{
	for(int i=0;i<SIZE;i++)
	{
		if(u->next[i]!=NULL)
			del(u->next[i]);
	}
	delete(u);
}

void print(struct Trie *u)
{
	if(u->isEnd)
		cout<<u->name<<":"<<u->count<<endl;
	for(int i=0;i<SIZE;i++)
		if(u->next[i]!=NULL)
			print(u->next[i]); 
}

int main()
{
	int t,n;
	bool flag;
	string s;
	cin>>t;
	while(t--)
	{
		flag=true;//开始没有前缀 
		cin>>n;
		while(n--)
		{
			cin>>s;
			if(flag)
				if(!Insert(s)) 
					flag=false;
		}
		
		//print(root);//打印检查下 
		
		if(flag)
			cout<<"YES"<<endl;
		else
			cout<<"NO"<<endl;
			 
		del(root);//释放树，下次重新建立 
	}
	return 0;
}

 

 

阅读文章：hdu1251-字符前缀查找问题 map容器

#include<iostream>
#include<string>
#include<map>
using namespace std;
int main()
{

    string str,str1;
    map<string, int> map1;
    while(getline(cin, str)&& str.length() !=0)
    {

        for(int i = 1; i != str.size()+1; i++)
        {

            str1 = str.substr(0, i);               //把当作字典的单词从第一个字母依次增长的往后复制在map中
            map1[str1]++;                          
        }
    }
    while(cin >> str)
    {

        cout << map1[str] << endl;
    }
}
——————————————https://blog.csdn.net/imush/article/details/52039806

 

 

参考文章：

字典树(Trie树)实现与应用

Trie树的常见应用大总结（面试+附代码实现）

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

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

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

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

赞 (0)
全栈程序员-用户IM全栈程序员-用户IM
0 0
blank

相关推荐

  • Tomcat内存设置方法

    Tomcat内存设置方法

    Tomcat内存设置方法

    全栈程序员-用户IM 全栈程序员-用户IM
    2021年5月6日
  • centos7系列关闭防火墙但是端口依然无法访问

    centos7系列关闭防火墙但是端口依然无法访问

    centos7系列关闭防火墙但是端口依然无法访问centos7.3系统，已经关闭firewalld，但是除了22端口，其余端口无法被外界访问，本地访问正常，解决步骤：1、先开启firewalld：systemctl start firewalld2、放通端口：firewall-cmd –zone=public –add-port=8080/tcp –permanent3、重新加载配置文件：firewall-cmd –reload此时测试，端口已经能够访问了，如果不需要firewall，可以再关闭，已放通端口不受影响（为什么一开始我不放

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年6月13日
  • Python-random函数用法

    Python-random函数用法

    Python-random函数用法Python标准库中的random函数，可以生成随机浮点数、整数、字符串，甚至帮助你随机选择列表序列中的一个元素，打乱一组数据等。random中的一些重要函数的用法：random.random()random.random()函数是这个模块中最常用的方法了，它会生成一个随机的浮点数，范围是在0.0~1.0之间。importrandomprint(random.random())&…

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年5月2日
  • jQuery简洁大方的登录页面模板

    jQuery简洁大方的登录页面模板

    jQuery+CSS网站登录模板本模板带验证码在线体验：http://hovertree.com/texiao/jquery/13.htmDemo2：http://hovertree.com/hvt

    全栈程序员-用户IM 全栈程序员-用户IM
    2021年12月21日
  • B样条曲线拟合原理「建议收藏」

    B样条曲线拟合原理「建议收藏」

    B样条曲线拟合原理「建议收藏」1.与贝塞尔曲线对比B样条曲线是在Bezier曲线基础上发展起来的一类曲线，它克服了Bezier曲线整体控制性所带来的不便，最常用的是二次和三次B样条曲线。2.二次B样条2.1参数方程已知三个平面离散点P0、P1、P2，由这三点可以定义二次抛物线段，其参数矢量方程形式为：二次B样条曲线参数方程的矩阵形式为：对比着看，

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年6月18日
  • mysql中文乱码

    mysql中文乱码

    mysql中文乱码

    全栈程序员-用户IM 全栈程序员-用户IM
    2021年9月13日

发表回复

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

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