文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

C语言中trie字典树是什么

2023-06-03 09:41

关注

这篇文章给大家分享的是有关C语言中trie字典树是什么的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。

字典树介绍

字典树简单的是用一个二维数组表示,如果想更加节省空间,大神的做法肯定是用指针链表来搞定了。比如我们用g_trie[i][j]=k这个二维数组表示字典树,那么他们的含义有三点,i,j,k,这个是字典树的核心,只有理解i,j,k代表的意义,才能更好的去写代码构建字典树,运用字典树。

i >>>这个可以理解为根节点(上面的e,k字符都可以认为是i),如果这个没有孩子,下面没有分支,就可以理解为i

j>>>j可以理解为i的孩子,他的值意思就是第几个孩子的意思

k>>>这个我认为就是一共有多少个字符,统计所有字符数量的意思

实例代码

#include "stdio.h"

#define false (0)

#define true (1)

int g_trie[100][100];

char g_str[100];

int g_root = ;

int g_tot = ;

void insert(char *s)

{

    int id = ;

    g_root = ;

    while(*s != '\0')

    {

        id  = *s++ - 'a';

        if(g_trie[g_root][id] == )

        {

            g_trie[g_root][id] = ++g_tot;

        }

        g_root = g_trie[g_root][id];

    }

}

int find_str(char *s)

{

    g_root = ;

    while(*s != '\0')

    {

        int id = *s++ -'a';

        if(g_trie[g_root][id] == ) return false;

        g_root = g_trie[g_root][id];

    }

    return true;

}

void main(void)

{

    int N = ;

    memset(g_trie, , sizeof(int) * 100 * 100);

    scanf("%d",&N);

    for(int i = ;i <= N;i++)

    {

        scanf("%s",g_str);

        insert(g_str);

    }

    puts("Please input find string");

    while(~scanf("%s",g_str))

    {

        if(find_str(g_str) == true)

        {

            puts("find str");

        }

        else

        {

            puts("find nothing!");

        }

    }  

}

解释

为什么 id =*s++- 'a'; 这个是为了节省空间,本来数组建立的字典树就浪费了很多空间,这个写法能节省很多空间。

if(g_trie[g_root][id] == 0) 我们在前面已经初始化数组为,这里如果检测是,那么就说明里面没有东西,就可以往里面存东西。

用链表实现的字典树代码

// C implementation of search and insert operations 

// on Trie 

#include <stdio.h> 

#include <stdlib.h> 

#include <string.h> 

#include <stdbool.h> 

#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0]) 

// Alphabet size (# of symbols) 

#define ALPHABET_SIZE (26) 

// Converts key current character into index 

// use only 'a' through 'z' and lower case 

#define CHAR_TO_INDEX(c) ((int)c - (int)'a') 

// trie node 

struct TrieNode 

    struct TrieNode *children[ALPHABET_SIZE]; 

    // isEndOfWord is true if the node represents 

    // end of a word 

    bool isEndOfWord; 

}; 

// Returns new trie node (initialized to NULLs) 

struct TrieNode *getNode(void

    struct TrieNode *pNode = NULL; 

    pNode = (struct TrieNode *)malloc(sizeof(struct TrieNode)); 

    if (pNode) 

    { 

        int i; 

        pNode->isEndOfWord = false; 

        for (i = ; i < ALPHABET_SIZE; i++

            pNode->children[i] = NULL; 

    } 

    return pNode; 

// If not present, inserts key into trie 

// If the key is prefix of trie node, just marks leaf node 

void insert(struct TrieNode *root, const char *key) 

    int level; 

    int length = strlen(key); 

    int index; 

    struct TrieNode *pCrawl = root; 

    for (level = ; level < length; level++

    { 

        index = CHAR_TO_INDEX(key[level]); 

        if (!pCrawl->children[index]) 

            pCrawl->children[index] = getNode(); 

        pCrawl = pCrawl->children[index]; 

    } 

    // mark last node as leaf 

    pCrawl->isEndOfWord = true; 

// Returns true if key presents in trie, else false 

bool search(struct TrieNode *root, const char *key) 

    int level; 

    int length = strlen(key); 

    int index; 

    struct TrieNode *pCrawl = root; 

    for (level = ; level < length; level++

    { 

        index = CHAR_TO_INDEX(key[level]); 

        if (!pCrawl->children[index]) 

            return false; 

        pCrawl = pCrawl->children[index]; 

    } 

    return (pCrawl != NULL && pCrawl->isEndOfWord); 

// Driver 

int main() 

    // Input keys (use only 'a' through 'z' and lower case) 

    char keys[][8] = {"the", "a", "there", "answer", "any", 

                     "by", "bye", "their"}; 

    char output[][32] = {"Not present in trie", "Present in trie"}; 

    struct TrieNode *root = getNode(); 

    // Construct trie 

    int i; 

    for (i = ; i < ARRAY_SIZE(keys); i++

        insert(root, keys[i]); 

    // Search for different keys 

    printf("%s --- %s\n", "the", output[search(root, "the")] ); 

    printf("%s --- %s\n", "these", output[search(root, "these")] ); 

    printf("%s --- %s\n", "their", output[search(root, "their")] ); 

    printf("%s --- %s\n", "thaw", output[search(root, "thaw")] ); 

    return

}

感谢各位的阅读!关于“C语言中trie字典树是什么”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯