这篇文章给大家分享的是有关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字典树是什么”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，让大家可以学到更多知识，如果觉得文章不错，可以把它分享出去让更多的人看到吧！