课设题目描述：

题目大体思路： 构建Trie树

1.初始化：

        在 search 函数中，初始化一个空的 results 向量来存储搜索结果，一个空的 word 字符串来构建当前路径，然后从根节点开始调用 searchDFS。

2.递归搜索：

        在searchDFS中，对于当前节点的每个子节点，都会创建一个新的 word 和 newPos。如果 newPos 等于 targetPos 并且当前字符与 targetChar 匹配，说明找到了目标位置的字符，接下来将调用 dfs 函数从这个节点开始进行深度优先搜索，以找到所有可能的四字成语。

3.完整搜索：

        在 dfs 函数中，如果当前节点是词的结束，并且 word 的长度为 4，说明找到了一个四字成语，将其添加到 results 中。然后，继续递归地搜索当前节点的所有子节点，以找到更多的四字成语。

4.结束条件：

        在 dfs 和 searchDFS 中，如果当前节点为空（node == NULL），则返回，这是递归的结束条件。
        通过这种方式，程序能够根据给定的位置和字符找到所有匹配的四字成语，并将它们收集到结果集中返回。这种方法有效地利用了 Trie 结构的特点，实现了快速且准确的搜索。

详细描述：

1、查询函数 search：

        总体讲解：这个函数是 Trie 的一个公共接口，用于开始搜索过程。它接收两个参数：charPosition（目标字符的字符串形式）和 position（目标字符的位置）。
它初始化一个空的结果集 results，然后调用 searchDFS 函数从根节点开始深度优先搜索。

        具体步骤解释：首先初始化结果集：创建一个空的 vector<string> 类型的变量 results，用来存放搜索结果，即所有匹配的成语。然后初始化当前成语：创建一个空的 string 类型的变量 word，用来构建当前遍历到的成语。

        然后调用深度优先搜索函数：以Trie的根节点root、空成语 word、初始位置0、目标字符charPosition和目标位置position作为参数，调用私有成员函数searchDFS开始深度优先搜索。

        最后返回结果集：搜索完成后，返回 results 向量，其中包含了所有找到的符合条件的成语。

2、深度优先搜索函数 searchDFS：

        总体讲解：这个函数递归地遍历 Trie 的节点。它检查当前节点的所有子节点，对于每个子节点，它将子节点代表的字符添加到当前的 word 字符串中，并更新位置 currentPos。

如果当前位置 newPos 与目标位置 targetPos 相匹配，并且当前字符与目标字符 targetChar 相匹配，它将调用 dfs 函数进行完整的深度优先搜索。

如果不匹配，它将继续递归地搜索其他子节点。

        具体代码解释：如果当前节点 node 是 NULL，表示当前路径不合法或已经到达了 Trie 树的末端而没有找到匹配的子节点，因此函数返回，结束当前路径的搜索。

然后依次遍历子节点：函数遍历当前节点 node 的所有子节点。这是通过迭代 node->children 这个 map 来完成的，该 map 存储了子节点的映射关系，键是字符串（代表汉字），值是指向对应 TrieNode 子节点的指针。

然后再构建新的成语：对于每个子节点，函数通过将当前节点代表的汉字 it->first 添加到 word 字符串中来构建新的成语 newWord。

之后更新位置：更新当前的位置 currentPos 为 newPos，即 currentPos + 1。

        再检查目标位置和字符：检查更新后的位置 newPos 是否等于目标位置 targetPos，并且当前子节点的汉字 it->first 是否与目标字符 targetChar 匹配。

最后执行完整 DFS：如果当前位置和字符与目标匹配，说明找到了一个可能的成语路径，因此调用 dfs 函数从当前子节点开始进行完整的深度优先搜索，以收集所有从这个节点开始的成语。

之后继续搜索：如果当前位置和字符不匹配目标位置和字符，函数继续递归地调用 searchDFS 函数，从当前子节点开始，继续搜索其他可能的路径。

最后收集结果：在递归调用 searchDFS 或 dfs 的过程中，所有找到的符合条件的成语都会被添加到 results 向量中。

返回结果：递归搜索完成后，searchDFS 函数将通过 results 向量返回所有找到的符合条件的成语。

3、完整DFS搜索 dfs：

        总体解释：这个函数用于从当前节点开始进行深度优先搜索，以收集完整的四字成语。

如果当前节点是词的结束（node->isWordEnd 为 true）并且当前 word 的长度为 4（即四字成语），则将 word 添加到结果集 results 中。

然后，它继续递归地搜索当前节点的所有子节点。

题目细节展示：

1.如何提取汉字

        如果按照原来的一个一个的提取字母的方式提取汉字，最后会导致乱码，但是以下方式按照两个两个的提取，汉字就不会乱码。

 for (int i = 0; i < word.size(); i += 2) {string character = word.substr(i, 2); //获取单个汉字if (node->children.find(character) == node->children.end()) {node->children[character] = new TrieNode(); // 如果字符不在children中，添加它}node = node->children[character]; // 移动到下一个节点}

2.汉字input乱码

        用txt文件输入汉字时，也会导致乱码情况，所以按照以下方式可以避免

将记事本中UTF-8编码改成ANSI编码，就可以防止出现上面的情况

           

知识点学习：

1.Map

可以结合这两篇博客学习一下：

C++ Map常见用法说明_c++ map用法-CSDN博客

C++ map的常用用法（超详细）(*^ｰ^)人(^ｰ^*)_c++ map用法-CSDN博客

1）Map的find()函数

2）Map的end()函数返回的迭代器

2.BFS 和 DFS

如何通透理解：BFS和DFS优先搜索算法(23年修订版)_bfs和dfs算法-CSDN博客

3.Trie树

         字典树（Trie），也称为前缀树或单词查找树，是一种用于存储字符串集合的数据结构，特别适用于处理前缀相关的问题。字典树的基本特点是通过共享公共前缀来节省存储空间，并且可以高效地进行字符串查询操作。

字典树的优点

1、快速查找：查找一个字符串的时间复杂度为O(m)，其中 m 是字符串的长度，与字符串的数量无关。

2、节省空间：通过公共前缀的共享，节省了存储空间，尤其是在处理大量有相同前缀的字符串时。

3、前缀匹配：字典树特别适合用于解决前缀匹配问题，比如自动补全、前缀统计等问题。

Trie树结构展示：

        如图所示，天高云淡为一个四字成语，天高地厚也为一个四字成语，在该图中可以清晰的看到，天高云淡和天高地厚共享一个前缀 “天高”,这样节省了存储空间。

        所以在 Trie 树中，所有具有相同前缀的成语都会共享这个前缀路径上的节点。就像图中的“天高云淡”和“天高地厚”这两个成语共享“天高”作为前缀，因此“天”和“高”这两个节点只需要存储一次，不需要为每个成语重复存储。第二，节点重用：每个节点在 Trie 树中代表一个字符，如果多个成语有相同的起始字符或者中间的某个字符，那么这些字符对应的节点可以被重用，从而避免了重复存储相同信息。第三，空间复杂度降低：相比于将每个成语作为独立的字符串存储，Trie 树通过共享公共前缀减少了存储空间的需求。特别是在成语库中，很多成语会有共同的前两个字或更多，这种共享机制可以显著减少存储空间。

代码展示：

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <map>
using namespace std;//要改变txt的编码方式，改成ANSC编码 // Trie树节点
struct TrieNode {map<string, TrieNode*> children;     //汉字  和  子节点的指针   的映射 bool isWordEnd; // 标记是否是词组的结尾TrieNode() : isWordEnd(false) {}
};// Trie树类
class Trie {
private:TrieNode* root;public:Trie() : root(new TrieNode()) {}// 插入词组void insert(const string& word) {TrieNode* node = root;for (int i = 0; i < word.size(); i += 2) {string character = word.substr(i, 2); //获取单个汉字if (node->children.find(character) == node->children.end()) {node->children[character] = new TrieNode(); // 如果字符不在children中，添加它}node = node->children[character]; // 移动到下一个节点}node->isWordEnd = true; // 标记这个词的结束}// 查询函数vector<string> search(const string& charPosition, int position) {vector<string> results;string word;// 从根节点开始遍历所有可能的路径searchDFS(root, word, 0, charPosition, position, results);return results;}// 打印Trie树void printTrie() {printTrieDFS(root, "");}private:// 深度优先搜索打印Trie树void printTrieDFS(TrieNode* node, const string& prefix) {if (node == NULL) return;if (node->isWordEnd) {cout << prefix << endl;}for (map<string, TrieNode*>::iterator it = node->children.begin(); it != node->children.end(); ++it) {printTrieDFS(it->second, prefix + it->first);}}// 深度优先搜索函数void searchDFS(TrieNode* node, string word, int currentPos, const string& targetChar, int targetPos, vector<string>& results) {if (node == NULL) return;// 遍历当前节点的所有子节点int i=0;for (map<string, TrieNode*>::iterator it = node->children.begin(); it != node->children.end(); ++it) {i++;string newWord = word + it->first;//cout<<newWord<<"+++"<<i<<endl; int newPos = currentPos + 1;// 检查是否到达目标位置并且字符匹配if (newPos == targetPos && it->first == targetChar) {// 如果匹配，则从此路径进行完整的DFS搜索 //cout<<it->first <<"---"<<i<<endl;dfs(it->second, newWord, newPos, targetPos, targetChar, results);} else {// 否则继续遍历searchDFS(it->second, newWord, newPos, targetChar, targetPos, results);}}}// 从指定位置开始的完整DFS搜索void dfs(TrieNode* node, string word, int currentPos, int targetPos, const string& targetChar, vector<string>& results) {if (node == NULL) return;// 如果到达词尾且长度为4个汉字，则添加到结果中if (node->isWordEnd && currentPos == 4) {results.push_back(word);return;}// 继续DFS遍历for (map<string, TrieNode*>::iterator it = node->children.begin(); it != node->children.end(); ++it) {string newWord = word + it->first;dfs(it->second, newWord, currentPos + 1, targetPos, targetChar, results);}}
};int main() {Trie trie;ifstream inputFile("成语1.txt"); // 打开文件// 检查文件是否成功打开if (!inputFile.is_open()) { // 也可以使用is_open()方法检查文件是否打开cerr << "无法打开文件" << endl; return 1;}string line;// 逐行读取文件内容while (getline(inputFile, line)) { cout<<line<<endl;trie.insert(line); // 将每一行添加到向量中}// 关闭文件inputFile.close(); // 不再需要std::前缀//trie.printTrie();// 测试数据string input;int position;cout << "请输入一个汉字和位置（例如：天 2）：" << endl;cin >> input >> position;// 将汉字转换为UTF-8编码的字符串string targetChar = input.substr(0, 2);//位置 和  targetChar解析正确 vector<string> results = trie.search(targetChar, position);cout << "符合条件的四字词组有：" << endl;for (size_t i = 0; i < results.size(); ++i) {cout << results[i] << endl;}return 0;
}

结果展示：

可能会提问的问题：

1、成语在Trie树中具体是怎样存储的，请画一个图展示。

2、dfs函数具体是怎样实现的？

3、searchDFS和dfs函数有什么关系？

4、在实现过程中有没有遇到什么问题？

成语.txt文件展示： 

天高云淡
天马行空
天网恢恢
天寒地冻
天高地厚
天罗地网
天南海北
天长地久
天高地迥
雨后春笋
雨过天晴
雨丝风片
雨幕云垂
雨零星乱
雨沾云惹
雨愁烟恨
雨膏烟腻
雨零星星
坐井观天
雪窖冰天
一步登天
别有洞天
巧夺天工
叫苦连天
热火朝天
女娲补天
和风细雨
春风化雨
呼风唤雨
未雨绸缪
泪如雨下
倾盆大雨
瓢泼大雨
滂沱大雨
怒气冲天
烽火连天
和风丽日
风调雨顺
烟雨蒙蒙
挥汗如雨
云行雨洽
云消雨散
秋水伊人
以德服人
借刀杀人
下里巴人
一鸣惊人
富贵逼人
盛气凌人
乐于助人
咄咄逼人
自欺欺人
怨天尤人
睹物思人
楚楚动人
含血喷人
后发制人
暗锤打人
以理服人
治病救人
舍己为人
成人之美
成王败寇
约定俗成
约定事成
百炼成钢
点石成金
铁杵成针
众志成城
坐视不救
坐以待毙
坐而论道
坐井观天
坐享其成
指鹿为马
指日可待
指手画脚
指桑骂槐
指不胜屈
众志成城
众目睽睽
众口一词
众口铄金
众说纷纭
志同道合
志同道合
志在千里
志同道合
志高气扬
至高无上
至亲好友
至善至美
至死不屈
至圣至明
至圣先师
至人无梦
至人无己
至大至刚
至当不易
至公无私
至诚高节
至亲骨肉
雨过天晴
晴空万里
晴云秋月
晴初霜旦
物是人非
物华天宝
物美价廉
物尽其用
物极必反
暴殄天物
超然物外
成己成物
待人接物
睹物思人
非池中物
风云人物
抚世酬物
格物致知
厚德载物
化物为工
即物穷理
接人待物
冷血动物
悯天物情
民胞物与
庞然大物
轻世傲物
人物风流
人物一新
人物轩昂
人物出众
玩物丧志
威刑肃物
遗物忘形
萧然物外
一表人物
一物不知
风雨同舟
风华正茂
风驰电掣
风和日丽
风起云涌
风卷残云
风平浪静
风吹草动
风言风语
风雨飘摇
鹅毛大雪
毛骨悚然
毛遂自荐
毛手毛脚
毛举细故
仪表堂堂
风度翩翩
气宇轩昂
英姿飒爽
亭亭玉立
温文尔雅
落落大方
憨态可掬
威风凛凛
老态龙钟
美若天仙
如花似玉
闭月羞花
沉鱼落雁
倾国倾城
才高八斗
学富五车
满腹经纶
出口成章
才华横溢
冰清玉洁
冰肌玉骨
明眸皓齿
眉清目秀
唇红齿白
温文儒雅
温文尔雅
和蔼可亲
平易近人
慈眉善目
小巧玲珑
小巧精致
玲珑剔透
晶莹剔透
精美绝伦
威风八面
气势汹汹
气吞山河
雷霆万钧
锐不可当
憨厚老实
忠厚老实
聪明伶俐
机智过人
足智多谋
亭亭玉秀
端庄秀丽
秀丽端庄
明眸善睐
画蛇添足
狐假虎威
刻舟求剑
叶公好龙
守株待兔
囫囵吞枣
庖丁解牛
自相矛盾
亡羊补牢
掩耳盗铃
滥竽充数
买椟还珠
鹬蚌相争
井底之蛙
惊弓之鸟
愚公移山
黔驴技穷
杞人忧天
拔苗助长
郑人买履
望梅止渴
画龙点睛
坐井观天
画饼充饥
人面兽心
南辕北辙
火中取栗
抱薪救火
杯弓蛇影
量体裁衣
海阔天空
风花雪月
金玉满堂
龙飞凤舞
珠联璧合
鹤立鸡群
锦上添花