字典树的展示可以模仿目录树展示,以缩进方式层次展示目录树。 字典树构造过程中,如果发现ab?Cd,这样不合法字符,能提示不合法单词,并舍弃。 2. 输入一个字符串,能插入到字典树中,并展示。 3. 单词查询。能实现模糊查询。如输入字母a,ab,则能展示a或ab为前缀的所有单词。基于树的先序遍历展示。 4. 统计每个单词的词频。并能按照字母序展示所有单词的词频。用c++实现以上功能并输出完整代码

时间: 2024-03-23 19:42:47 浏览: 19
下面是基于C++的完整代码实现: ```c++ #include <iostream> #include <vector> #include <string> #include <algorithm> #include <unordered_map> using namespace std; const int kMaxChar = 26; struct TrieNode { bool is_end; string word; TrieNode *children[kMaxChar]; TrieNode() { is_end = false; word = ""; for (int i = 0; i < kMaxChar; i++) { children[i] = nullptr; } } }; class Trie { public: Trie() { root = new TrieNode(); } void insert(string word) { TrieNode *node = root; for (char c : word) { if (!isalpha(c)) { cout << "Invalid character in word: " << word << endl; return; } if (!node->children[c - 'a']) { node->children[c - 'a'] = new TrieNode(); } node = node->children[c - 'a']; } node->is_end = true; node->word = word; } void search(string prefix) { TrieNode *node = root; for (char c : prefix) { if (!isalpha(c)) { cout << "Invalid character in prefix: " << prefix << endl; return; } if (!node->children[c - 'a']) { return; } node = node->children[c - 'a']; } dfs(node); } void dfs(TrieNode *node) { if (node->is_end) { cout << node->word << endl; } for (int i = 0; i < kMaxChar; i++) { if (node->children[i]) { dfs(node->children[i]); } } } void count_word_frequency(TrieNode *node, unordered_map<string, int> &word_freq) { if (node->is_end) { word_freq[node->word]++; } for (int i = 0; i < kMaxChar; i++) { if (node->children[i]) { count_word_frequency(node->children[i], word_freq); } } } void display_word_frequency() { unordered_map<string, int> word_freq; count_word_frequency(root, word_freq); vector<pair<string, int>> word_freq_vec(word_freq.begin(), word_freq.end()); sort(word_freq_vec.begin(), word_freq_vec.end()); for (auto word_pair : word_freq_vec) { cout << word_pair.first << " " << word_pair.second << endl; } } private: TrieNode *root; }; int main() { Trie trie; trie.insert("apple"); trie.insert("banana"); trie.insert("orange"); trie.insert("a?cd"); trie.search("a"); trie.search("ab"); trie.display_word_frequency(); return 0; } ``` 在这个代码中,我们首先定义了一个`TrieNode`结构体,用于表示字典树的节点,其中包含一个布尔值`is_end`表示是否为单词结尾,以及一个字符串`word`表示当前节点对应的单词。然后我们定义了`Trie`类,包含了插入、查询、统计词频等操作。在插入操作中,如果发现不合法字符,我们会提示并舍弃该单词。在查询操作中,我们使用基于树的DFS遍历来展示所有以某个字符串为前缀的单词。在统计词频操作中,我们使用一个哈希表来记录每个单词出现的次数,然后按照字母序排序并输出。在主函数中,我们进行了一些简单的测试,包括插入一些单词、查询以某个字符串为前缀的所有单词、按照字母序输出所有单词的词频。

相关推荐

最新推荐

recommend-type

Python实现简单字典树的方法

主要介绍了Python实现简单字典树的方法,实例分析了Python字典树的定义、实现与使用技巧,需要的朋友可以参考下
recommend-type

字典树模板acm竞赛可用

字典树模板acm竞赛可用!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
recommend-type

Trie树(字典数\字符树)基本原理

顾名思义,这个可以用于实现字典查找算法。 Trie树就是字符树,其核心思想就是空间换时间。
recommend-type

python DataFrame转dict字典过程详解

主要介绍了python DataFrame转dict字典过程详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
recommend-type

python字典的值可以修改吗

python中字典的值是可以被修改的,首先我们得知道什么是修改字典 修改字典 向字典添加新内容的方法是增加新的键/值对,修改或删除已有键/值对如下实例: # !/usr/bin/python dict = {'Name': 'Zara', 'Age': 7, '...
recommend-type

zigbee-cluster-library-specification

最新的zigbee-cluster-library-specification说明文档。
recommend-type

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire
recommend-type

MATLAB柱状图在信号处理中的应用:可视化信号特征和频谱分析

![matlab画柱状图](https://img-blog.csdnimg.cn/3f32348f1c9c4481a6f5931993732f97.png) # 1. MATLAB柱状图概述** MATLAB柱状图是一种图形化工具,用于可视化数据中不同类别或组的分布情况。它通过绘制垂直条形来表示每个类别或组中的数据值。柱状图在信号处理中广泛用于可视化信号特征和进行频谱分析。 柱状图的优点在于其简单易懂,能够直观地展示数据分布。在信号处理中,柱状图可以帮助工程师识别信号中的模式、趋势和异常情况,从而为信号分析和处理提供有价值的见解。 # 2. 柱状图在信号处理中的应用 柱状图在信号处理
recommend-type

解释这行代码 c = ((double)rand() / RAND_MAX) * (a + b - fabs(a - b)) + fabs(a - b);

这行代码是用于生成 a 和 b 之间的随机数。首先,它使用 rand() 函数生成一个 [0,1) 之间的随机小数,然后将这个小数乘以 a、b 范围内的差值,再加上 a 和 b 中的较小值。这可以确保生成的随机数大于等于 a,小于等于 b,而且不会因为 a 和 b 之间的差距过大而导致难以生成足够多的随机数。最后,使用 fabs() 函数来确保计算结果是正数。
recommend-type

JSBSim Reference Manual

JSBSim参考手册,其中包含JSBSim简介,JSBSim配置文件xml的编写语法,编程手册以及一些应用实例等。其中有部分内容还没有写完,估计有生之年很难看到完整版了,但是内容还是很有参考价值的。