Trie树

这周将Trie树看了一下下面进行总结

概念:Trie,又称单词查找树键树,是一种形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。

在这个Trie结构中,保存了A、to、tea、ted、ten、i、in、inn这8个字符串(有数字的代表单词)

个人理解:Trie树就是将每个单词用树形进行存储,当有几个单词有一样的前缀的时候,可有几天支是相同的

zoj 2876 水题Trie树

#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
#define MAX 26//这是代表26个字母,如果包含数字需要重新定义

struct Trie
{
    Trie *next[MAX];
    int v;//v可以表示一个字典树到此有多少相同前缀的数目,这里根据需要应当学会自由变化。
};
Trie *root;

void creatTrie(char *str)//创建结点,并且插入单词
{
    int len=strlen(str);
    Trie *p=root,*q;
    for (int i=0;i<len;i++)
    {
        int id=str[i]-'0';
        if(p->next[id]==NULL)//如果该字母的下一个点为空,则可以插入新
        {
            q=(Trie *)malloc(sizeof(Trie));
            q->v=1;
            for (int j=0;j<MAX;j++)
                q->next[j]=NULL;
            p->next[id]=q;
            p=p->next[id];
        }
        else//若该结点的下一个字母已经在下一个结点中了
        {
            p->next[id]->v++;//跳过下一个到下下个
            p=p->next[id];
        }
    }
    p->v=-1;//该单词插入完毕,封结点
}

int findTrie(char *str)
{
    int len=strlen(str);
    Trie *p=root;
    for (int i=0;i<len;i++)
    {
        int id=str[i]-'0';
        p=p->next[id];
        if(p==NULL) return 0;//若为空集,表示不存以此为前缀的串
        if(p->v==-1) return -1;////字符集中已有串是此串的前缀
    }
    return -1;////此串是字符集中某串的前缀
}
//比如911为窜已存储,输入9133判断911是不是他的前窜
//当911到达第二个1的时候,p->next[id](2)=NULL

int dealTrie(Trie *T)//删除树
{
    int i;
    if(T==NULL) return 0;
    for (i=0;i<MAX;i++)
    {
        if(T->next[i]!=NULL) dealTrie(T->next[i]);
    }
    free(T);
    return 0;
}

int main()
{
    int T;
    char str[100];
    scanf("%d",&T);
    while(T--)
    {
        int n,i;
        int flag=0;
        root=(Trie *)malloc(sizeof(Trie));//刚开始需要建立结点
        for (i=0;i<MAX;i++)
             root->next[i]=NULL;
        scanf("%d",&n);
        scanf("%s",str);
        creatTrie(str);
        for (i=1;i<n;i++)
        {
             scanf("%s",str);
             if(flag) continue;
             if(findTrie(str)==-1) flag=1;
             else creatTrie(str);
        }
        if(flag) printf("NO\n");
        else printf("YES\n");
        dealTrie(root);
    }
}

模版网站:http://zh.wikipedia.org/wiki/Trie

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏TungHsu

这或许是对小白最友好的python入门了吧——8,初识for语句

有时候我们想要使用列表中所有元素,但是如果手打又不现实,这时候我们可以用for语句来遍历整个列表,我们先举个例子,还是昨天的列表 ? 现在我们用for语句来遍历...

30160
来自专栏恰童鞋骚年

C# 中的委托和事件

文中代码在VS2005下通过,由于VS2003(.Net Framework 1.1)不支持隐式的委托变量,所以如果在一个接受委托类型的位置直接赋予方法名,...

10620
来自专栏Java与Android技术栈

Scala学习笔记(四) 类的初步Scala 类相关总结

终于来到面向对象的地方了,虽说函数式编程是 Scala 的特性,让人们觉得 Scala 是更好的 Java。但是在架构层面上一直提倡着:小处用函数式编程,大处用...

12020
来自专栏分布式系统和大数据处理

C#中的委托和事件 - Part.1

文中代码在VS2005下通过,由于VS2003(.Net Framework 1.1)不支持隐式的委托变量,所以如果在一个接受委托类型的位置直接赋予方法名,在V...

12730
来自专栏刘远的专栏

airflow—给DAG实例传递参数(4)

我们需要在创建dag实例时传递参数,每个任务都可以从任务实例中获取需要的参数。

2.7K80
来自专栏JavaEdge

设计实现一个LRU Cache1 什么是LRU Cache2 实现思路

40170
来自专栏张善友的专栏

在Entity Framework 中执行T-sql语句

从Entity Framework  4开始在ObjectContext对象上提供了2个方法可以直接执行SQL语句:ExecuteStoreQuery<T> 和...

235100
来自专栏博客园

Core官方DI解析(4)--CallSiteRuntimeResolver

这两个类都在其CallSiteVisitor<TArgument, TResult>基类中

9930
来自专栏闵开慧

pig操作与注意事项

grunt> A = load 'hdfs://192.168.0.118:9000/user/hadoop/data.txt' as (name:charar...

28830
来自专栏刘望舒

Android深入理解JNI(二)类型转换、方法签名和JNIEnv

前言 1.数据类型的转换 首先给出上一篇文章中android_media_MediaRecorder.cpp中的android_media_MediaReco...

27160

扫码关注云+社区

领取腾讯云代金券