字典樹的基本知識及使用C語言的相關(guān)實現(xiàn)
概念
如果我們有and,as,at,cn,com這些關(guān)鍵詞，那么trie樹（字典樹）是這樣的：
從上面的圖中，我們或多或少的可以發(fā)現(xiàn)一些好玩的特性。
第一：根節(jié)點不包含字符，除根節(jié)點外的每一個子節(jié)點都包含一個字符。
第二：從根節(jié)點到某一節(jié)點，路徑上經(jīng)過的字符連接起來，就是該節(jié)點對應(yīng)的字符串。
第三：每個單詞的公共前綴作為一個字符節(jié)點保存。
使用范圍
既然學(xué)Trie樹，我們肯定要知道這玩意是用來干嘛的。
第一：詞頻統(tǒng)計。
可能有人要說了，詞頻統(tǒng)計簡單啊，一個hash或者一個堆就可以打完收工，但問題來了，如果內(nèi)存有限呢？還能這么
玩嗎？所以這里我們就可以用trie樹來壓縮下空間，因為公共前綴都是用一個節(jié)點保存的。
第二: 前綴匹配
就拿上面的圖來說吧，如果我想獲取所有以"a"開頭的字符串，從圖中可以很明顯的看到是：and,as,at，如果不用trie樹，
你該怎么做呢？很顯然樸素的做法時間復(fù)雜度為O(N2) ，那么用Trie樹就不一樣了，它可以做到h，h為你檢索單詞的長度，
可以說這是秒殺的效果。
數(shù)據(jù)結(jié)構(gòu)定義
#define MAX 26 // 字符集大小
typedef struct trieNode {
struct trieNode *next[MAX];
int count; // 記錄該字符出現(xiàn)次數(shù)
} trieNode;
next數(shù)組表示每層有多少類的數(shù)，如果只是小寫字母，26即可
實現(xiàn)方法
搜索字典項目的方法：
- 從根節(jié)點開始一次搜索
- 獲取要查找關(guān)鍵詞的第一個字母，并根據(jù)該字母選擇對應(yīng)的子樹并轉(zhuǎn)到該子樹繼續(xù)進行檢索
- 在相應(yīng)的子樹上，獲取要查找關(guān)鍵詞的第二個字母，并進一步選擇對應(yīng)的子樹進行檢索
- 迭代過程
- 在某個節(jié)點處，關(guān)鍵詞的所有字母已被取出，則讀取附在該結(jié)點上的信息，即完成查找
其他操作類似
實現(xiàn)模板
初始化根結(jié)點
/**
* 初始化Trie樹根結(jié)點
*/
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 ++;
}
}
統(tǒng)計查找單詞數(shù)量
/**
* 統(tǒng)計前綴出現(xiàn)次數(shù)
*/
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);
}
時間復(fù)雜度
插入、查找的時間復(fù)雜度均為O(n),n為字符串的長度
空間復(fù)雜度較高，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; // 記錄該字符出現(xiàn)次數(shù)
} trieNode;
/**
* 初始化Trie樹根結(jié)點
*/
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 ++;
}
}
/**
* 統(tǒng)計前綴出現(xiàn)次數(shù)
*/
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;
// 初始化根結(jié)點
initTrie(&root);
while (gets(str) && str[0] != '\0') {
// 插入Trie樹
insert(str, root);
}
// 查找前綴出現(xiàn)次數(shù)
while (gets(str) && str[0] != '\0') {
printf("%d\n", count(str, root));
}
delTrie(root);
return 0;
}
相關(guān)文章
這篇文章主要為大家詳細介紹了C++實現(xiàn)簡易的彈球小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-10-10
定義命名空間，使用namespace關(guān)鍵字，后面跟命名空間的名字，然后接一對花括號{ } 即可，{ }中即為命名空間的成員，這篇文章主要介紹了C++命名空間 namespace,需要的朋友可以參考下2023-04-04
解析為何要關(guān)閉數(shù)據(jù)庫連接,可不可以不關(guān)閉的問題詳解
本篇文章是對為何要關(guān)閉數(shù)據(jù)庫連接,可不可以不關(guān)閉的問題進行了詳細的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要介紹了C++采用TLS線程局部存儲的用法實例,詳細講述了TLS索引及線程的操作,非常具有實用價值,需要的朋友可以參考下2014-10-10
這篇文章主要介紹了C語言中的參數(shù)傳遞機制,C語言中函數(shù)參數(shù)的傳遞有：值傳遞、地址傳遞、引用傳遞這三種形式。下面我們詳細探討下2017-04-04
這篇文章主要介紹了詳解C++中的菱形繼承問題,在多繼承結(jié)構(gòu)中，存在著很多問題，比如從不同基類中繼承了同名成員，派生類中也定義了同名成員，這種二義性問題很好解決，加上要訪問的基類的類名限制就可以了,需要的朋友可以參考下2023-08-08
本篇文章介紹了，基于歐幾里德算法的使用。需要的朋友參考下2013-05-05
本文將會介紹如何使用模板以及參數(shù)生成器來批量生成測試用例，簡化繁瑣的性能測試代碼2021-06-06
這篇文章主要介紹了C++ OpenCV方框濾波的實現(xiàn),方框濾波是均值濾波的一種形式，今天通過實例代碼給大家介紹的非常詳細，需要的朋友可以參考下2021-10-10
智能指針是C++11引入的一種指針封裝類型,用于自動管理動態(tài)分配的內(nèi)存,本文主要介紹了Qt 智能指針QScopedPoint用法小結(jié),感興趣的可以了解一下2024-01-01