汉字字典树[通俗易懂]

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

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

字典树的概念我就不说了，不过大多题目都是英文的字典树，我就闲的蛋疼去写了中文的字典树，实现起来也挺简单的。

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

using namespace std;

//字典树，根节点为1
struct Node
{
    
    int length=0;
    string lines="";
    map<string,int> words;
    map<string,int> count;
}tree[1005];
//表示字典树的节点数
int len;
string res[105];

/*char* word(char *aw,int j)
{
    char w[105]={'#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <map>
using namespace std;
//字典树，根节点为1
struct Node
{
int length=0;
string lines="";
map<string,int> words;
map<string,int> count;
}tree[1005];
//表示字典树的节点数
int len;
string res[105];
/*char* word(char *aw,int j)
{
char w[105]={'\0'};
int p=0;
for(int i=j*3;i<j*3+3;i++)
{
w[p++]=aw[i];
}
return w;
}
void strcatt(char *as,char *bs,int j)
{
int l=strlen(as);
for(int i=l;i<l+3;i++)
{
as[i]=bs[j*3+i-l];
}
}*/
//往字典树立插入字符串
void insert(string a,int i,int j)
{
if(i==a.length()/3)
{
return;
}
if(tree[j].words[a.substr(i*3,3)]!=0)
{
insert(a,i+1,tree[j].words[a.substr(i*3,3)]);
}
else
{
tree[j].words[a.substr(i*3,3)]=++len;
tree[j].lines+=a.substr(i*3,3);
tree[j].length+=3;
if(i==a.length()/3-1)
tree[j].count[a.substr(i*3,3)]++;
insert(a,i+1,len);
}
}
/*
bool equal(char *ae,char *be)
{
if(strlen(ae)!=strlen(be))
return false;
else
{
for(int i=0;i<strlen(ae);i++)
{
if(ae[i]!=be[i])
return false;
}
return true;
}
}*/
void remove(Node &s,string x)
{
int y=0;
for(int i=0;i<s.length/3;i++)
{
if(s.lines.substr(i*3,3)==x)
{
y=i;break;
}
}
for(int i=y*3;i<s.length;i++)
{
s.lines[i]=s.lines[i+3];
}
s.length-=3;
}
//删除字符串
bool del(string a,int i,int j)
{
if(tree[j].words[a.substr(i*3,3)]==0)
return false;
else
{
int x=tree[j].words[a.substr(i*3,3)];
tree[j].words[a.substr(i*3,3)]=0;
remove(tree[j],a.substr(i*3,3));
return del(a,i+1,x);
}
}
//查询某个字符串为前缀的所有词
void QueryPrefix(string a,int i,int j,string str,int &l2)
{
if(i>=a.length()/3)
{
if(tree[j].length==0)
{
return;
}
for(int k=0;k<tree[j].length/3;k++)
{
str+=tree[j].lines.substr(k*3,3);
if(tree[j].count[tree[j].lines.substr(k*3,3)]!=0)
res[l2++]=str;
QueryPrefix(a, i+1, tree[j].words[tree[j].lines.substr(k*3,3)],str,l2);
}
}
else if(tree[j].words[a.substr(i*3,3)]==0)
return;
else
{
//strcatt(str,aq,i);
str+=a.substr(i*3,3);
if(i==a.length()/3-1)
res[l2++]=str;
QueryPrefix(a, i+1, tree[j].words[a.substr(i*3,3)],str,l2);
}
}
//查询某个字符串是否存在
bool IsExist(string a,int i,int j)
{
if(i==a.length()/3)
{
return false;
}
if(tree[j].words[a.substr(i*3,3)]==0)
return false;
else
{
if(i==a.length()/3-1&&tree[j].count[a.substr(i*3,3)]!=0)
{
return true;
}
return IsExist(a, i+1,tree[j].words[a.substr(i*3,3)]);
}
}
string input[1005];
int n;
string output;
int main()
{
printf("请输入要插入字典树的字符串数组的长度\n");
scanf("%d",&n);
printf("请输入要插入字典树的字符串数组\n");
len=1;
for(int i=0;i<n;i++)
{
cin>>input[i];
insert(input[i],0,1);
}
printf("请输入key\n");
cin>>output;
printf("查找key是否存在\n");
IsExist(output,0, 1);
if(IsExist(output,0,1))
printf("key存在\n");
else
printf("key不存在\n");
printf("找出所有以key为前缀的字符串\n");
string str="";
int l1=0;int l2=0;
QueryPrefix(output, 0, 1,str, l2);
for(int i=0;i<l2;i++)
cout<<res[i]<<endl;
printf("key为一句话，找出key中存在的最长词\n");
printf("输入key\n");
cin>>output;
int le=output.length();
string xx="";
string ans="";
int res2=0;
for(int i=0;i<le/3;i++)
{
for(int l=3;i*3+l<=le;l+=3)
{
xx=output.substr(i*3,l);
if(IsExist(xx, 0, 1))
{
if(res2<l)
{
res2=l;
ans=xx;
}
}
}
}
if(res2==0)
{
printf("不存在\n");
}
else
{
cout<<ans<<endl;
}
return 0;
}'};
    int p=0;
    for(int i=j*3;i<j*3+3;i++)
    {
        w[p++]=aw[i];
    }
    return w;
}
void strcatt(char *as,char *bs,int j)
{
    int l=strlen(as);
    
    for(int i=l;i<l+3;i++)
    {
        as[i]=bs[j*3+i-l];
    }
}*/
//往字典树立插入字符串
void insert(string a,int i,int j)
{
  
    if(i==a.length()/3)
    {
        
        return;
    }
    if(tree[j].words[a.substr(i*3,3)]!=0)
    {
        insert(a,i+1,tree[j].words[a.substr(i*3,3)]);
    }
    else
    {
        tree[j].words[a.substr(i*3,3)]=++len;
        tree[j].lines+=a.substr(i*3,3);
        tree[j].length+=3;
        if(i==a.length()/3-1)
            tree[j].count[a.substr(i*3,3)]++;
        insert(a,i+1,len);
    }
}
/*
bool equal(char *ae,char *be)
{
    if(strlen(ae)!=strlen(be))
        return false;
    else
    {
        for(int i=0;i<strlen(ae);i++)
        {
            if(ae[i]!=be[i])
                return false;
        }
        return true;
    }
        
}*/
void remove(Node &s,string x)
{
    int y=0;
    for(int i=0;i<s.length/3;i++)
    {
        if(s.lines.substr(i*3,3)==x)
        {
            y=i;break;
        }
    }
    for(int i=y*3;i<s.length;i++)
    {
        s.lines[i]=s.lines[i+3];
    }
    s.length-=3;
}
//删除字符串
bool del(string a,int i,int j)
{
    if(tree[j].words[a.substr(i*3,3)]==0)
        return false;
    else
    {
        int x=tree[j].words[a.substr(i*3,3)];
        tree[j].words[a.substr(i*3,3)]=0;
        remove(tree[j],a.substr(i*3,3));
        return del(a,i+1,x);
    }
}

//查询某个字符串为前缀的所有词

void QueryPrefix(string a,int i,int j,string str,int &l2)
{
    if(i>=a.length()/3)
    {
        if(tree[j].length==0)
        {
          
            return;
        }
        
        for(int k=0;k<tree[j].length/3;k++)
        {
           
            str+=tree[j].lines.substr(k*3,3);
          
            if(tree[j].count[tree[j].lines.substr(k*3,3)]!=0)
                res[l2++]=str;
            QueryPrefix(a, i+1, tree[j].words[tree[j].lines.substr(k*3,3)],str,l2);
            
        }
    }
    else if(tree[j].words[a.substr(i*3,3)]==0)
        return;
    else
    {
        //strcatt(str,aq,i);
        str+=a.substr(i*3,3);
      
        if(i==a.length()/3-1)
            res[l2++]=str;
        QueryPrefix(a, i+1, tree[j].words[a.substr(i*3,3)],str,l2);
    }
}
//查询某个字符串是否存在
bool IsExist(string a,int i,int j)
{
    if(i==a.length()/3)
    {
        return false;
    }
 
    if(tree[j].words[a.substr(i*3,3)]==0)
        return false;
    else
    {
        if(i==a.length()/3-1&&tree[j].count[a.substr(i*3,3)]!=0)
        {
            return true;
        }
        return IsExist(a, i+1,tree[j].words[a.substr(i*3,3)]);
    }
}
string input[1005];
int n;
string output;

int main()
{
    printf("请输入要插入字典树的字符串数组的长度\n");
    scanf("%d",&n);
    printf("请输入要插入字典树的字符串数组\n");
    len=1;
    for(int i=0;i<n;i++)
    {
        cin>>input[i];
        insert(input[i],0,1);
    }
    
    printf("请输入key\n");
    cin>>output;
    printf("查找key是否存在\n");
    IsExist(output,0, 1);
    if(IsExist(output,0,1))
        printf("key存在\n");
    else
        printf("key不存在\n");
    
    printf("找出所有以key为前缀的字符串\n");
    

    string str="";
    int l1=0;int l2=0;
    QueryPrefix(output, 0, 1,str, l2);
    for(int i=0;i<l2;i++)
        cout<<res[i]<<endl;
    
    
    
    printf("key为一句话，找出key中存在的最长词\n");
    printf("输入key\n");
    cin>>output;
    int le=output.length();
    string xx="";
    string ans="";
    int res2=0;
    for(int i=0;i<le/3;i++)
    {
        for(int l=3;i*3+l<=le;l+=3)
        {
            xx=output.substr(i*3,l);
            
            if(IsExist(xx, 0, 1))
            {
                if(res2<l)
                {
                    res2=l;
                    ans=xx;
                }
            }
        }
    }
    if(res2==0)
    {
        printf("不存在\n");
    }
    else
    {
        cout<<ans<<endl;
    }
    return 0;
    
}

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

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

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