字典树介绍

字典树的图形如下

字典树简单的是用一个二维数组表示，如果想更加节省空间，大神的做法肯定是用指针链表来搞定了。比如我们用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 = 0;
int g_tot = 0;

void insert(char *s)
{
    int id = 0;
    g_root = 0;
    while(*s != '\0')
    {
        id  = *s++ - 'a';
        if(g_trie[g_root][id] == 0)
        {
            g_trie[g_root][id] = ++g_tot;
        }
        g_root = g_trie[g_root][id];
    }
}


int find_str(char *s)
{
    g_root = 0;
    while(*s != '\0')
    {
        int id = *s++ -'a';
        if(g_trie[g_root][id] == 0) return false;
        g_root = g_trie[g_root][id];
    }
    return true;
}

void main(void)
{
    int N = 0;
    memset(g_trie, 0, sizeof(int) * 100 * 100);
    scanf("%d",&N);
    for(int i = 0;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) 我们在前面已经初始化数组为0，这里如果检测是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 = 0; 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 = 0; 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 = 0; 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 = 0; 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 0; 
}

有问题请留言，谢谢！

ITPub博客

trie字典树

字典树介绍

实例代码

用链表实现的字典树代码

最新文章