2023年6月22日发(作者：)

c语⾔联想词搜索实现,使⽤Trie字典树来实现搜索框检索词联想功能我们在使⽤百度或其它搜索框的时候经常会看到如下情况：下拉框中会显⽰检索词的联想，这个功能是怎么实现的呢？其实这就是Trie树(或者字典树)的⼀个实际应⽤。这⾥不具体介绍Trie树，接下来简单实现⼀下这种联想功能。#include#include#include#include#define N 256using namespace std;struct TreeNode{bool isEnd;struct TreeNode *next[N];};class Trie{public:Trie();void InsertNode(string query); //将query插⼊Trie树中void FindStr(string query,vector &result); //当检索query时，从Trie树中获取联想结果并存⼊vector中void FindStrCore(TreeNode *root,string query,vector &result);void Clear();void DeleteNode(TreeNode *root);~Trie();private:TreeNode *root;};Trie::Trie(){root = new TreeNode();root->isEnd = false;}void Trie::FindStrCore(TreeNode *root,string str,vector &result){if(root == NULL)return ;if(root->isEnd)_back(str);for(int j=0;j{if(root->next[j] != NULL)FindStrCore(root->next[j],str+(char)j,result);}}void Trie::FindStr(string src,vector &result) //当检索query时，从Trie树中获取联想结果并存⼊vector中{int cur = 0;TreeNode *tmp = this->root;unsigned char index = (unsigned char)src[cur];while(cur < () && tmp->next[index] != NULL){tmp = tmp->next[index];++cur;index = (unsigned char)src[cur];}if(cur != () || tmp == NULL)return;FindStrCore(tmp,src+(char)cur,result);}void Trie::InsertNode(string str) //将query插⼊Trie树中{int i=0;TreeNode *tmp = this->root;for(;i{unsigned char index = (unsigned char)str[i];if(tmp->next[index] == NULL){tmp->next[index] = new TreeNode();}tmp = tmp->next[index];}tmp->isEnd = true;}void Trie::DeleteNode(TreeNode *root){int i=0;for(;i{if(root->next[i] != NULL)DeleteNode(root->next[i]);}root = NULL;root->isEnd = false;}void Trie::Clear(){int i=0;for(;i{if(root->next[i] != NULL){DeleteNode(root->next[i]);}}}Trie::~Trie(){Clear();}int main(){Trie *myTrie = new Trie(); //先插⼊数据myTrie->InsertNode("宝马1系");myTrie->InsertNode("宝马2系");myTrie->InsertNode("宝马3系");string query;cout>query; //输⼊要检索的queryvector result;myTrie->FindStr(query,result);vector::iterator iter = (); //输出联想结果cout