当前位置：网站首页>C语言·前缀树实现
C语言·前缀树实现
2022-07-15 17:39:00 【小迅想变强】
Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。Trie又称前缀树或字典树，是一棵有根树，其每个节点包含以下字段：
指向子节点的指针数组 next。
布尔字段 isEnd，表示该节点是否为字符串的结尾
typedef struct Trie{
bool isEnd; //该结点是否是一个串的结束
struct Trie * next[26]; //字母映射表
}Trie;初始化树节点
对于每一个待插入的树节点来说，需要保存isEnd为字符串为结束，并且对于next数组指向NULL
/* false：表示未结束 true：表示结束*/
Trie* trieCreate() {
Trie * obj = malloc(sizeof(Trie) * 1);
for(int i = 0; i < 26; i++)
{
obj->next[i] = NULL;
}
obj->isEnd = false;
return obj;
}插入字符串
我们从字典树的根开始，插入字符串。对于当前字符对应的子节点，有两种情况：
子节点存在。沿着指针移动到子节点，继续处理下一个字符。
子节点不存在。创建一个新的子节点，记录在 children 数组的对应位置上，然后沿着指针移动到子节点，继续搜索下一个字符。
重复以上步骤，直到处理字符串的最后一个字符，然后将当前节点标记为字符串的结尾。
/*
*void trieInsert(Trie* obj, char * word)
void trieInsert：向前缀数插入字符串
Trie* obj：前缀树头结点
char * word：字符串
返回值：无
*/
void trieInsert(Trie* obj, char * word) {
int len = strlen(word);
for(int i = 0; i < len; i++)
{
if(obj->next[(word[i]-'a')] == NULL)
{
Trie * objNode = trieCreate();
obj->next[(word[i]-'a')] = objNode;
}
obj = obj->next[(word[i]-'a')];
}
obj->isEnd = true;
}查找前缀
我们从字典树的根开始，查找前缀。对于当前字符对应的子节点，有两种情况：
子节点存在。沿着指针移动到子节点，继续搜索下一个字符。
子节点不存在。说明字典树中不包含该前缀，返回空指针。
重复以上步骤，直到返回空指针或搜索完前缀的最后一个字符。
若搜索到了前缀的末尾，就说明字典树中存在该前缀。此外，若前缀末尾对应节点的 isEnd 为真，则说明字典树中存在该字符串。
/*
bool trieSearch(Trie* obj, char * word)
*bool trieSearch：检查字符串word是否在前缀树上
Trie* obj：前缀树头结点
char * word:字符串
返回值：存在返回true
不存在返回false
*/
bool trieSearch(Trie* obj, char * word) {
int len = strlen(word);
for(int i = 0; i < len; i++)
{
if(obj->next[(word[i]-'a')] == NULL)
{
return false;
}
obj = obj->next[(word[i]-'a')];
}
if(obj->isEnd == false)
{
return false;
}
return true;
}销毁
对于已经存在的前缀树，递归销毁是比较方便的
void trieFree(Trie* obj) {
for(int i = 0; i < 26; i++)
{
if(obj->next[i])
trieFree(obj->next[i]);
}
free(obj);
}具体实现
typedef struct Trie{
bool isEnd; //该结点是否是一个串的结束
struct Trie * next[26]; //字母映射表
}Trie;
/* false：表示未结束 true：表示结束*/
Trie* trieCreate() {
Trie * obj = malloc(sizeof(Trie) * 1);
for(int i = 0; i < 26; i++)
{
obj->next[i] = NULL;
}
obj->isEnd = false;
return obj;
}
/*
*void trieInsert(Trie* obj, char * word)
void trieInsert：向前缀数插入字符串
Trie* obj：前缀树头结点
char * word：字符串
返回值：无
*/
void trieInsert(Trie* obj, char * word) {
int len = strlen(word);
for(int i = 0; i < len; i++)
{
if(obj->next[(word[i]-'a')] == NULL)
{
Trie * objNode = trieCreate();
obj->next[(word[i]-'a')] = objNode;
}
obj = obj->next[(word[i]-'a')];
}
obj->isEnd = true;
}
/*
bool trieSearch(Trie* obj, char * word)
*bool trieSearch：检查字符串word是否在前缀树上
Trie* obj：前缀树头结点
char * word:字符串
返回值：存在返回true
不存在返回false
*/
bool trieSearch(Trie* obj, char * word) {
int len = strlen(word);
for(int i = 0; i < len; i++)
{
if(obj->next[(word[i]-'a')] == NULL)
{
return false;
}
obj = obj->next[(word[i]-'a')];
}
if(obj->isEnd == false)
{
return false;
}
return true;
}
bool trieStartsWith(Trie* obj, char * prefix) {
int len = strlen(prefix);
for(int i = 0; i < len; i++)
{
if(obj->next[(prefix[i]-'a')] == NULL)
{
return false;
}
obj = obj->next[(prefix[i]-'a')];
}
return true;
}
void trieFree(Trie* obj) {
for(int i = 0; i < 26; i++)
{
if(obj->next[i])
trieFree(obj->next[i]);
}
free(obj);
}
/**
* Your Trie struct will be instantiated and called as such:
* Trie* obj = trieCreate();
* trieInsert(obj, word);
* bool param_2 = trieSearch(obj, word);
* bool param_3 = trieStartsWith(obj, prefix);
* trieFree(obj);
*/练习1 力扣第208题
力扣
https://leetcode.cn/problems/implement-trie-prefix-tree/
参考链接
http://t.csdn.cn/2UBpShttp://t.csdn.cn/2UBpS思路
前缀：字符串的前缀是指字符串的任意首部。比如字符串“abbc”的前缀有“a”,“ab”,“abb”,“abbc”。
前缀树：前缀树是一种用于快速检索的多叉树结构，利用字符串的公共前缀来降低查询时间，核心思想是空间换时间，经常被搜索引擎用于文本词频统计。
每一个节点表示一个树的节点，然后每一个树的节点又可以指向26个子节点，这样子就可以构建一个字符串树
实现代码
typedef struct Trie{
bool isEnd; //该结点是否是一个串的结束
struct Trie * next[26]; //字母映射表
}Trie;
/* false：表示未结束 true：表示结束*/
Trie* trieCreate() {
Trie * obj = malloc(sizeof(Trie) * 1);
for(int i = 0; i < 26; i++)
{
obj->next[i] = NULL;
}
obj->isEnd = false;
return obj;
}
/*
*void trieInsert(Trie* obj, char * word)
void trieInsert：向前缀数插入字符串
Trie* obj：前缀树头结点
char * word：字符串
返回值：无
*/
void trieInsert(Trie* obj, char * word) {
int len = strlen(word);
for(int i = 0; i < len; i++)
{
if(obj->next[(word[i]-'a')] == NULL)
{
Trie * objNode = trieCreate();
obj->next[(word[i]-'a')] = objNode;
}
obj = obj->next[(word[i]-'a')];
}
obj->isEnd = true;
}
/*
bool trieSearch(Trie* obj, char * word)
*bool trieSearch：检查字符串word是否在前缀树上
Trie* obj：前缀树头结点
char * word:字符串
返回值：存在返回true
不存在返回false
*/
bool trieSearch(Trie* obj, char * word) {
int len = strlen(word);
for(int i = 0; i < len; i++)
{
if(obj->next[(word[i]-'a')] == NULL)
{
return false;
}
obj = obj->next[(word[i]-'a')];
}
if(obj->isEnd == false)
{
return false;
}
return true;
}
bool trieStartsWith(Trie* obj, char * prefix) {
int len = strlen(prefix);
for(int i = 0; i < len; i++)
{
if(obj->next[(prefix[i]-'a')] == NULL)
{
return false;
}
obj = obj->next[(prefix[i]-'a')];
}
return true;
}
void trieFree(Trie* obj) {
for(int i = 0; i < 26; i++)
{
if(obj->next[i])
trieFree(obj->next[i]);
}
free(obj);
}
/**
* Your Trie struct will be instantiated and called as such:
* Trie* obj = trieCreate();
* trieInsert(obj, word);
* bool param_2 = trieSearch(obj, word);
* bool param_3 = trieStartsWith(obj, prefix);
* trieFree(obj);
*/
练习2 力扣第648题
力扣https://leetcode.cn/problems/replace-words/
参考链接
http://t.csdn.cn/aKq0zhttp://t.csdn.cn/aKq0z思路
前缀：字符串的前缀是指字符串的任意首部。比如字符串“abbc”的前缀有“a”,“ab”,“abb”,“abbc”。
前缀树：前缀树是一种用于快速检索的多叉树结构，利用字符串的公共前缀来降低查询时间，核心思想是空间换时间，经常被搜索引擎用于文本词频统计。前缀树多用于字符串。
思路
将本题dictionary转换为前缀树，然后对sentence遍历，判断字符串前缀是否位于树上，存在就进行简化输出，不存在就完全输出，最后定义的字符串链接所有结果的比较结果
以下代码还可以优化
实现代码
//0：结束，1：没有结束
typedef struct word{
int end;
struct word * next[26];
}word;
//初始化前缀树
word * trieCreate(){
word * obj = malloc(sizeof(word) * 1);
for(int i = 0; i < 26; i++)
{
obj->next[i] = NULL;
}
obj->end = 0;;
return obj;
}
/*
*void word_create(word * root, char ** dictionary, int inode)
void word_create：向前缀数插入字符串
word * root：前缀树头结点
char ** dictionary：字符串
int inod：字符串行下标
返回值：无
*/
void word_create(word * root, char ** dictionary, int inode)
{
int len = strlen(dictionary[inode]);
for(int i = 0; i < len; i++)
{
if(root->next[dictionary[inode][i] - 'a'] == NULL)
{
word * n = trieCreate();
root->next[dictionary[inode][i] - 'a'] = n;
}
root = root->next[dictionary[inode][i] - 'a'];
}
root->end = 1;
}
//判断字符串是否在前缀树上
char * str_if(word * root, char * sentence, int len_left, int len_right)
{
int len = 0;
for(int i = len_left; i < len_right; i++)
{
if(root->next[sentence[i] - 'a'] && root->end == 0)
{
len++;
root = root->next[sentence[i] - 'a'];
}
else
{
if(root->end == 0)
{
len = len_right - len_left;
}
break;
}
}
if(len)
{
char * str = malloc(sizeof(char) * (len + 1 + 1));
strncpy(str, sentence+len_left, len);
str[len] = ' ';
str[len + 1] = '\0';
return str;
}
else
{
char * str = malloc(sizeof(char) * (len_right - len_left + 1 + 1));
strncpy(str, sentence+len_left, len_right - len_left);
str[len_right - len_left] = ' ';
str[len_right - len_left + 1] = '\0';
return str;
}
return NULL;
}
//优化字符串sentence
char * replaceWords(char ** dictionary, int dictionarySize, char * sentence){
char * str = malloc(sizeof(char) * (1000 * 1000 + 1));
str[0] = '\0';
word * root = trieCreate();
for(int i = 0; i < dictionarySize; i++)
{
word_create(root, dictionary, i);
}
int len = strlen(sentence);
int len_left = 0;
int i;
for(i = 0; i < len; i++)
{
if(sentence[i] == ' ')
{
strcat(str , str_if(root, sentence, len_left, i));
len_left = i+1;
}
}
strcat(str , str_if(root, sentence, len_left, i));
len = strlen(str);
str[len - 1] = '\0';
trieFree(root);
return str;
}
//销毁前缀树
void trieFree(word * obj) {
for(int i = 0; i < 26; i++)
{
if(obj->next[i])
trieFree(obj->next[i]);
}
free(obj);
}边栏推荐
猜你喜欢
驳'一切不谈考核的管理都是扯淡'
亿万富豪们的太空梦，正在杀死地球
Can you use redis? Then come and learn about redis protocol
LAN attack and network device security configuration
Pytorch中torch.sort()和torch.argsort()函数解析
Those things about the client
2. Trend technology 2017 school recruitment development post test questions
MySQL 为什么临时表可以重名 ？
想到多线程并发就心虚？先来巩固下这些线程基础知识吧！
FrameWork源码——Binder 驱动解析
随机推荐
记录Yolov5的使用（1）
若依框架之定时任务
LINQ implements query string splicing: and and or
Openharmony module 2 file samgr_ Server parsing (5)
李沐动手学深度学习V2-目标检测SSD
Parsing of header files under interfaces in module 2 (2)
Allure测试报告怎么设置
2022 China mobile maker marathon Internet of things special competition kicks off
在创建生成WIFI二维码手机扫码链接
李沐动手学深度学习V2-目标检测数据集
30岁被裁，我想明白的几件事
How to make Sitemaps website map
Matlab：交换矩阵的两行（列）
OpenHarmony模块二interfaces下头文件解析（9）
如何制作sitemaps网站地图
渗透测试流程
LINQ implements dynamic orderby
Openharmony related knowledge learning
Openharmony module II parsing of header files under interfaces (9)
leetcode 605. Can Place Flowers 种花问题 (简单)