数据结构与算法学习（06）查找（3）Trie树（C语言）——BUAA

文章目录

• 查找（3）——Trie树（C语言）
• • 介绍
  • 结构实现
  • 典型应用（字典树）
  • 代码实现
  • 优势

查找（3）——Trie树（C语言）

介绍

本文为查找第三部分，主要是整理了本人上课时讲的内容，并给出了C语言代码实现

结构实现

1. 键值由固定的字符序列组成（如数字或字母），如Huffman码、英文单词；
2. 对应结点的分层标记；
3. 遍历一条路径便可以得到一个具体的单词

典型应用（字典树）

英文单词仅由26个字母组成（不考虑大小写）

对应字典树每个内部结点都有26个子结点

树的高度为最长单词长度

代码实现

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

struct trieNode
{
    int isWord;                    // 用于判断是否是一个完整的单词，预防前缀的情况
    struct trieNode *children[26]; // 一般小写英文字母有26个
};

// trie 节点内存分配函数
struct trieNode *trieMalloc()
{
    struct trieNode *ret = (struct trieNode *)malloc(sizeof(struct trieNode));
    ret->isWord = 0;
    for (int i = 0; i < 26; i++)
    {
        ret->children[i] = NULL;
    }
    return ret;
}

// trie 树构造函数
void wordTree(struct trieNode *root, char *words)
{
    struct trieNode *tmp = root;
    while (*words != '\0')
    {
        if (tmp->children[*words - 'a'] == NULL)
        {
            struct trieNode *ret = trieMalloc();
            tmp->children[*words - 'a'] = ret;
        }
        // 注意这两者的顺序
        tmp = tmp->children[*words - 'a'];
        words++;
    }
    tmp->isWord = 1; // 最后 isWord 置为1代表一个单词结束
}

// 查找单词函数
int findWord(struct trieNode *root, char *words)
{
    struct trieNode *tmp = root;
    while (*words != '\0')
    {
        if (tmp->children[*words - 'a'] != NULL)
        {
            tmp = tmp->children[*words - 'a'];
            words++;
        }
        else
        {
            return 0; // 一旦有等于 NULL 的情况，便表明没有查询到单词
        }
    }
    if (tmp->isWord == 1)
    {
        return 1;
    }
    else
    {
        return 0; // 如果此时 isWord 等于0代表查询的只是前缀，并非整个单词
    }
}

int main(void)
{
    char words[40];
    struct trieNode *root = NULL;
    FILE *fp = fopen("D:/C/project2024/keepwords.txt", "r");
    root = trieMalloc();
    while (fscanf(fp, "%s", words) != EOF)
    {
        wordTree(root, words);
    }

    printf("%d ", findWord(root, "auto"));
    return 0;
}

优势

在访问速度要求很高的系统中，如拼写检查、词频统计中，trie 结构是一个非常好的选择。

并且，它不需要像哈希查询那样去设计一个合理的哈希函数来避免冲突，对于大数据的查询十分有效。