字典樹的根本常識及應用C說話的相干完成。本站提示廣大學習愛好者：（字典樹的根本常識及應用C說話的相干完成）文章只能為提供參考，不一定能成為您想要的結果。以下是字典樹的根本常識及應用C說話的相干完成正文
概念
假如我們有and,as,at,cn,com這些症結詞，那末trie樹（字典樹）是如許的：
從下面的圖中，我們或多或少的可以發明一些好玩的特征。
第一：根節點不包括字符，除根節點外的每個子節點都包括一個字符。
第二：從根節點到某一節點，途徑上經由的字符銜接起來，就是該節點對應的字符串。
第三：每一個單詞的公共前綴作為一個字符節點保留。
應用規模
既然學Trie樹，我們確定要曉得這玩意是用來干嗎的。
第一：詞頻統計。
能夠有人要說了，詞頻統計簡略啊，一個hash或許一個堆便可以打完出工，但成績來了，假如內存無限呢？還能這麼
玩嗎？所以這裡我們便可以用trie樹來緊縮下空間，由於公共前綴都是用一個節點保留的。
第二: 前綴婚配
就拿下面的圖來講吧，假如我想獲得一切以"a"開首的字符串，從圖中可以很顯著的看到是：and,as,at，假如不消trie樹，
你該怎樣做呢？很明顯樸實的做法時光龐雜度為O(N2) ，那末用Trie樹就紛歧樣了，它可以做到h，h為你檢索單詞的長度，
可以說這是秒殺的後果。
數據構造界說
#define MAX 26 // 字符集年夜小
typedef struct trieNode {
struct trieNode *next[MAX];
int count; // 記載該字符湧現次數
} trieNode;
next數組表現每層有若干類的數，假如只是小寫字母，26便可
完成辦法
搜刮字典項目標辦法：
其他操作相似
完成模板
初始化根結點
/**
* 初始化Trie樹根結點
*/
void initTrie(trieNode **root)
{
int i;
*root = (trieNode *)malloc(sizeof(trieNode));
(*root)->count = 0;
for (i = 0; i < MAX; i ++) {
(*root)->next[i] = NULL;
}
}
拔出單詞到trie樹
/**
* Trie樹拔出操作
*/
void insert(char *str, trieNode *root)
{
int i;
trieNode *p = root;
while (*str != '\0') {
if (p->next[*str - 'a'] == NULL) {
trieNode *tmp = (trieNode *)malloc(sizeof(trieNode));
for (i = 0; i < MAX; i ++) {
tmp->next[i] = NULL;
}
tmp->count = 1;
p->next[*str - 'a'] = tmp;
p = p->next[*str - 'a'];
} else {
p = p->next[*str - 'a'];
p->count ++;
}
str ++;
}
}
統計查找單詞數目
/**
* 統計前綴湧現次數
*/
int count(char *search, trieNode *root)
{
trieNode *p = root;
while (*search != '\0') {
if (p->next[*search - 'a'] == NULL) {
return 0;
} else {
p = p->next[*search - 'a'];
search ++;
}
}
return p->count;
}
清算trie樹
/**
* 清算trie樹
*/
void delTrie(trieNode *root)
{
int i;
for (i = 0; i < MAX; i ++) {
if (root->next[i] != NULL) {
delTrie(root->next[i]);
}
}
free(root);
}
時光龐雜度
拔出、查找的時光龐雜度均為O(n),n為字符串的長度
空間龐雜度較高，O(26^n),典范空間換時光
參考標題
ac代碼：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 26 // 字符集年夜小
typedef struct trieNode {
struct trieNode *next[MAX];
int count; // 記載該字符湧現次數
} trieNode;
/**
* 初始化Trie樹根結點
*/
void initTrie(trieNode **root)
{
int i;
*root = (trieNode *)malloc(sizeof(trieNode));
(*root)->count = 0;
for (i = 0; i < MAX; i ++) {
(*root)->next[i] = NULL;
}
}
/**
* Trie樹拔出操作
*/
void insert(char *str, trieNode *root)
{
int i;
trieNode *p = root;
while (*str != '\0') {
if (p->next[*str - 'a'] == NULL) {
trieNode *tmp = (trieNode *)malloc(sizeof(trieNode));
for (i = 0; i < MAX; i ++) {
tmp->next[i] = NULL;
}
tmp->count = 1;
p->next[*str - 'a'] = tmp;
p = p->next[*str - 'a'];
} else {
p = p->next[*str - 'a'];
p->count ++;
}
str ++;
}
}
/**
* 統計前綴湧現次數
*/
int count(char *search, trieNode *root)
{
trieNode *p = root;
while (*search != '\0') {
if (p->next[*search - 'a'] == NULL) {
return 0;
} else {
p = p->next[*search - 'a'];
search ++;
}
}
return p->count;
}
/**
* 清算trie樹
*/
void delTrie(trieNode *root)
{
int i;
for (i = 0; i < MAX; i ++) {
if (root->next[i] != NULL) {
delTrie(root->next[i]);
}
}
free(root);
}
int main(void)
{
char str[15];
trieNode *root;
// 初始化根結點
initTrie(&root);
while (gets(str) && str[0] != '\0') {
// 拔出Trie樹
insert(str, root);
}
// 查找前綴湧現次數
while (gets(str) && str[0] != '\0') {
printf("%d\n", count(str, root));
}
delTrie(root);
return 0;
}
