中文字典树实现 发布于 2018-04-27 2.81k 次阅读 参考链接 参考链接 代码 #include #include #include #include #include #include using namespace std; struct chtrie{ // 字典树的结构体 chtrie(){ count = 0; } int count; // 记录改字串个数 map next; // 键值记录的是当前汉字,实值记录的为后面汉字节点的指针 }; class trie{ // 字典树的类 public: trie(); ~trie(); void insertStr(string str); // 插入字符串 bool delectStr(string str); // 删除字符串 void clear(); // 清空树 chtrie *searchStr(string str); // 查询整个str字符串 chtrie *searchStrPre(string str); // 查询包含str的字符串 vector getStr(string str); // 用vector保存查询到所有包含str的字符串 private: void addStr(chtrie *root, string preStr, vector &ret); // 递归的将含有str的字符串保存到ret中 chtrie *root; // 字典树的根节点 }; trie::trie(){ // 创建trie类 root = new chtrie(); } trie::~trie(){ // 销毁trie类 } void trie::insertStr(string str){ // 插入字符串 chtrie *p; if(root == NULL || str == "") // 输入和根节点的值不能为空 return; p = root; for(int i = 0; i < str.size(); i++){ string nowStr = str.substr(i, 1); // 每次从str中提取一个字符 map::iterator it = p->next.find(nowStr); if(it == p->next.end()){ // 如果没有找到该字符则创建一个新节点 chtrie *tmp = new chtrie(); // 新节点 p->next.insert(pair (nowStr, tmp)); // 将该字符和新节点加入到map中 p = tmp; // 更新p } else // 找到的话 p = it->second; // 更新p } p->count++; // 改字符串最后一个节点count++ } bool trie::delectStr(string str){ // 删除字符串 chtrie *p = searchStr(str); // 先查找是否存在改字符串 if(p != NULL){ // 存在 p->count--; // 该字符串的count-- return true; } return false; } void trie::clear(){ // 清空树 vector clr; clr.push_back(root); // 将根节点加入到clr中 while(!clr.empty()){ // 当clr不为空时 map::iterator it; for(it = root->next.begin(); it != root->next.end(); it++) clr.push_back(it->second); // 将根节点的实值加入到clr中; chtrie *del = clr.front(); // 取clr第一个元素 clr.pop_back(); // 删除clr第一个元素 delete del; // 删除该节点实值 } } chtrie *trie::searchStrPre(string str){ // 查询包含str的字符串 chtrie *p; if(str == "" || root == NULL) // 当输入为空或者根节点为空时返回root的值 return root; p = root; int i; for(i = 0; i < str.size(); i++){ string nowStr = str.substr(i, 1);// 每次从str中提取一个字符 map::iterator it = p->next.find(nowStr); if(it == p->next.end()) // 没有找到该字符返回NULL return NULL; else p = it->second; // 更新p } if(i == str.size()) return p; return NULL; } chtrie *trie::searchStr(string str){ // 查询整个str字符串 chtrie *p = searchStrPre(str); // 先判断是否存在str前缀的字符串 if(p != NULL){ // 如果存在 if(p->count != 0) // 且改字符串count != 0 return p; // 返回p return NULL; } return NULL; } void trie::addStr(chtrie *root, string preStr, vector &ret){// 递归的将含有str的字符串保存到ret中 map::iterator it; for(it = root->next.begin(); it != root->next.end(); it++) addStr(it->second, preStr + it->first, ret); // 每次加一个字符 if(root->count != 0) // 改字符串count != 0 ret.push_back(preStr); // 加入到ret中 } vector trie::getStr(string str){ // 用vector保存查询到所有包含str的字符串 vector ret; chtrie *p = searchStrPre(str); // 先判断是否存在str前缀的字符串 if(p != NULL) // 如果存在 addStr(p, str, ret); // 加入到ret中 return ret; // 返回ret集合 } int main(){ trie t; int n, com; vector ret; cout << "Please input the num of dictionary:" << endl; cin >> n; for(int i = 0; i < n; i++){ string str; cin >> str; t.insertStr(str); } while(1){ cout << "Please input command:" << endl; cin >> com; if(com == 1){ // 插入字串 cout << "Begin to insert, input the num:" << endl; cin >> n; for(int i = 0; i < n; i++){ string str; cin >> str; t.insertStr(str); } } else if(com == 2){ // 查询字串 cout << "Start the query" << endl; string str; cin >> str; ret = t.getStr(str); vector::iterator it; if(ret.empty()) // 当ret为空时 cout << "Query failed" << endl; else{ for(it = ret.begin(); it != ret.end(); it++) cout << *it << endl; cout << "Query completed" << endl; } } else if(com == 3){ // 删除字串 cout << "Start deleting" << endl; string str; cin >> str; if(t.delectStr(str)) cout << "Successfully deleted" << endl; else cout << "Failed to delect" << endl; } } t.clear(); } 目录 参考链接 代码
Comments | NOTHING