本文共 1537 字,大约阅读时间需要 5 分钟。
//字典树//2016.6.6//yqtao@whu.edu.cn#include "stdafx.h"#include#include using namespace std;const int Num = 26;//struct TrieNode{ bool Isword;//判断是否是单词 TrieNode* next[Num]; TrieNode() :Isword(false)//初始化 { memset(next, NULL, sizeof(next)); }};class Trie{public: Trie() { root = new TrieNode(); } void insert(string word); bool search(string word); void deleteTrie(TrieNode* root);private: TrieNode* root;};void Trie::insert(string word){ TrieNode* location = root; for (int i = 0; i < word.length();i++) { if (location->next[word[i] - 'a'] == nullptr) { TrieNode* temp = new TrieNode(); location->next[word[i] - 'a']=temp; } location = location->next[word[i] - 'a']; } location->Isword = true;}bool Trie::search(string word){ TrieNode* location = root; //while (word&&location)//注意location不能为空 for (int i = 0; i < word.length()&&location;i++) location = location->next[word[i] - 'a']; return(location != NULL && location->Isword);}void Trie::deleteTrie(TrieNode* root){ for (int i = 0; i < Num; i++) { if (root->next[i] != NULL) { deleteTrie(root->next[i]); } } delete root;}void main() //简单测试 { Trie tree; int n;//输入n个单词在字典树中 cin >> n; while (n--) { string s; cin >> s; tree.insert(s); } string input; cout << "输入要检查的单词" << endl; cin >> input; cout << boolalpha << tree.search(input) << endl;//查找是否存在是个单词}
转载地址:http://qidoi.baihongyu.com/