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