現(xiàn))
Trie樹是保存字符串公共前綴信息的數(shù)據(jù)結(jié)構(gòu),可用于字符串多模匹配普通的非壓縮Trie樹實(shí)現(xiàn)如下第一種實(shí)現(xiàn):每個(gè)分支節(jié)點(diǎn)使用map標(biāo)準(zhǔn)庫容器保存前綴索引#include map #include stack #include vector #include string #include iostream #include random using namespace std; enum Compare_Result {EQUAL, LEFT_IS_PREFIX, RIGHT_IS_PREFIX, NOT_EQUAL}; struct TrieTreeNode //Trie樹節(jié)點(diǎn)類型 { enum NodeType { DATANODE, BRANCHNODE } type_flag; //節(jié)點(diǎn)類型標(biāo)志分支節(jié)點(diǎn)或存放關(guān)鍵字的葉節(jié)點(diǎn) union { string key_in_trie; //葉節(jié)點(diǎn)關(guān)鍵字 mapchar, TrieTreeNode* sub_ptr; //分支節(jié)點(diǎn)的分支字符和對(duì)應(yīng)的指向分支字符對(duì)應(yīng)的子節(jié)點(diǎn)的指針之間的映射關(guān)系 }; TrieTreeNode(const string k) :type_flag(NodeType::DATANODE), key_in_trie(k) {} TrieTreeNode() :type_flag(NodeType::BRANCHNODE), sub_ptr() {} TrieTreeNode(TrieTreeNode be_copied) { switch (be_copied.type_flag) { case NodeType::DATANODE: new (key_in_trie) string(be_copied.key_in_trie); break; case NodeType::BRANCHNODE: { new (sub_ptr) mapchar, TrieTreeNode*(); for (mapchar, TrieTreeNode*::iterator p be_copied.sub_ptr.begin(); p ! be_copied.sub_ptr.end(); p) sub_ptr.insert(make_pair(p-first, nullptr)); } break; } type_flag be_copied.type_flag; } ~TrieTreeNode() { switch (type_flag) { case NodeType::DATANODE: key_in_trie.~string(); break; case NodeType::BRANCHNODE: sub_ptr.~mapchar, TrieTreeNode*(); break; } } }; class TrieTree { public: bool insert(const string be_inserted) const; //Trie樹中插入關(guān)鍵字,true成功false失敗 bool deleteElem(const string be_deleted) const; //Trie樹中刪除指定關(guān)鍵字,true成功false失敗 TrieTreeNode* copy(); //拷貝Trie樹返回指向副本Trie樹的指針 TrieTree() { root new TrieTreeNode(); } void printTrieTree(TrieTreeNode* cur, size_t offset) const; bool isEmpty() const { return root-sub_ptr.empty(); } TrieTreeNode* getTrieTree() const { return root; } TrieTree(TrieTree be_copied) { root be_copied.copy(); } ~TrieTree(); private: Compare_Result static strCompare(const string left, const string right, string::size_type i); TrieTreeNode* root; //Trie樹根節(jié)點(diǎn) }; ostream operator(ostream o, const TrieTree be_output) { if (be_output.isEmpty()) { o NULL endl; return o; } be_output.printTrieTree(be_output.getTrieTree(), 0); return o; } Compare_Result TrieTree::strCompare(const string left, const string right, string::size_type i) { for (; ; i) { if (i left.size() i right.size()) return Compare_Result::EQUAL; else if (i left.size() || i right.size()) { if (i left.size()) return Compare_Result::LEFT_IS_PREFIX; else return Compare_Result::RIGHT_IS_PREFIX; } else if (left[i] ! right[i]) return Compare_Result::NOT_EQUAL; } } bool TrieTree::deleteElem(const string be_deleted) const { TrieTreeNode* run root; vectorTrieTreeNode* stack; vectorTrieTreeNode*::size_type index; mapchar, TrieTreeNode*::iterator stop_branch_node; mapchar, TrieTreeNode*::iterator leaf_father_point_to_leaf; { string::size_type i 0; while (true) { if (i be_deleted.size()) { mapchar, TrieTreeNode*::iterator it; it run-sub_ptr.find(be_deleted[i]); if (it run-sub_ptr.end()) return false; i; if (run root || run-sub_ptr.size() 2) { if (it-second-type_flag TrieTreeNode::NodeType::BRANCHNODE) { index stack.size(); stop_branch_node it; } else { leaf_father_point_to_leaf it; break; } } else stack.push_back(run); run it-second; } else { if (run-sub_ptr.empty() || \0 ! run-sub_ptr.begin()-first) return false; leaf_father_point_to_leaf run-sub_ptr.begin(); break; } } if (leaf_father_point_to_leaf-first ! \0 strCompare(be_deleted, leaf_father_point_to_leaf-second-key_in_trie, i) ! Compare_Result::EQUAL) return false; } delete leaf_father_point_to_leaf-second; run-sub_ptr.erase(leaf_father_point_to_leaf); if (run ! root run-sub_ptr.size() 1 run-sub_ptr.begin()-second-type_flag TrieTreeNode::NodeType::DATANODE) { if (stop_branch_node-second ! run) { for (size_t j stack.size() - 1; j index; --j) delete stack[j]; delete stack[index]; } stop_branch_node-second run-sub_ptr.begin()-second; delete run; } return true; } bool TrieTree::insert(const string be_inserted) const { TrieTreeNode* run root; string::size_type i 0; pairmapchar, TrieTreeNode*::iterator, bool result; while (run-type_flag ! TrieTreeNode::NodeType::DATANODE) { if (i be_inserted.size()) { result run-sub_ptr.insert(make_pair(be_inserted[i], new TrieTreeNode(be_inserted))); if (result.second) return true; run result.first-second; i; } else { if (run-sub_ptr.empty() || run-sub_ptr.begin()-first ! \0) { run-sub_ptr.insert(make_pair(\0, new TrieTreeNode(be_inserted))); return true; } return false; } } Compare_Result compare_result; { string::size_type start_index i; compare_result strCompare(be_inserted, run-key_in_trie, i); if (compare_result Compare_Result::EQUAL) return false; result.first-second new TrieTreeNode(); for (; start_index i; start_index) result.first result.first-second-sub_ptr.insert(make_pair(be_inserted[start_index], new TrieTreeNode())).first; } if (compare_result Compare_Result::LEFT_IS_PREFIX) { result.first-second-sub_ptr.insert(make_pair(\0, new TrieTreeNode(be_inserted))); result.first-second-sub_ptr.insert(make_pair(run-key_in_trie[i], run)); } else if (compare_result Compare_Result::RIGHT_IS_PREFIX) { result.first-second-sub_ptr.insert(make_pair(\0, run)); result.first-second-sub_ptr.insert(make_pair(be_inserted[i], new TrieTreeNode(be_inserted))); } else { result.first-second-sub_ptr.insert(make_pair(run-key_in_trie[i], run)); result.first-second-sub_ptr.insert(make_pair(be_inserted[i], new TrieTreeNode(be_inserted))); } return true; } TrieTree::~TrieTree() { TrieTreeNode* run root; stackpairTrieTreeNode*, mapchar, TrieTreeNode*::iterator work_stack; bool trace_back_flag true; while (true) { if (trace_back_flag true) { if (run root) { if (run-sub_ptr.begin() run-sub_ptr.end()) { delete root; return; } } else { if (run-type_flag TrieTreeNode::DATANODE) { delete run; run work_stack.top().first; work_stack.top().second; //work_stack.top().second run-sub_ptr.erase(work_stack.top().second); trace_back_flag false; continue; } } work_stack.push(make_pair(run, run-sub_ptr.begin())); run run-sub_ptr.begin()-second; } else { if (run root || work_stack.top().second ! run-sub_ptr.end()) { if (run root) { if (work_stack.top().second root-sub_ptr.end()) { delete root; return; } } run work_stack.top().second-second; trace_back_flag true; } else { delete run; work_stack.pop(); run work_stack.top().first; work_stack.top().second; // work_stack.top().second run-sub_ptr.erase(work_stack.top().second); } } } } TrieTreeNode* TrieTree::copy() { TrieTreeNode* be_copied root; stackpairTrieTreeNode*, mapchar, TrieTreeNode*::iterator work_stack; stackpairTrieTreeNode*, mapchar, TrieTreeNode*::iterator copy_trace_stack; TrieTreeNode* root_of_copy nullptr; bool trace_back_flag true; while (true) { if (trace_back_flag true) { if (be_copied root) { root_of_copy new TrieTreeNode(*be_copied); if (be_copied-sub_ptr.begin() be_copied-sub_ptr.end()) break; copy_trace_stack.push(make_pair(root_of_copy, root_of_copy-sub_ptr.begin())); } else { if (work_stack.top().second ! work_stack.top().first-sub_ptr.begin()) copy_trace_stack.top().second; copy_trace_stack.top().second-second new TrieTreeNode(*be_copied); if (be_copied-type_flag ! TrieTreeNode::DATANODE) copy_trace_stack.push(make_pair(copy_trace_stack.top().second-second, copy_trace_stack.top().second-second-sub_ptr.begin())); else { be_copied work_stack.top().first; trace_back_flag false; continue; } } work_stack.push(make_pair(be_copied, be_copied-sub_ptr.begin())); be_copied be_copied-sub_ptr.begin()-second; } else { if (work_stack.top().second-second-type_flag ! TrieTreeNode::DATANODE) copy_trace_stack.pop(); if (be_copied root || (work_stack.top().second) ! be_copied-sub_ptr.end()) { if (be_copied root) { if ((work_stack.top().second) root-sub_ptr.end()) break; } be_copied work_stack.top().second-second; trace_back_flag true; } else { work_stack.pop(); be_copied work_stack.top().first; } } } return root_of_copy; } void TrieTree::printTrieTree(TrieTreeNode* cur, size_t offset) const { if (cur-type_flag TrieTreeNode::BRANCHNODE) { size_t max_length; if (cur-sub_ptr.begin()-first \0) max_length 4; else max_length 1; for (mapchar, TrieTreeNode*::iterator run cur-sub_ptr.begin(); run ! cur-sub_ptr.end(); run) { for (size_t go 1; go offset; go) cout ; if (run-first \0) cout NULL; else { cout run-first; for (size_t go 2; go max_length; go) cout ; } cout |- endl; printTrieTree(run-second, offset 2 max_length); } } else { for (size_t go 1; go offset; go) cout ; cout leaf: cur-key_in_trie endl; } } int main() { vectorstring test { bluebird, bunting, bobwhite, bluejay }; TrieTree test_obj; for (vectorstring::iterator p test.begin(); p ! test.end(); p) { cout 插入字符串 *p endl; if (test_obj.insert(*p)) { cout 插入成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 插入失敗 endl; exit(0); } } cout endl; // TrieTreeNode *copy test_ptr.copy(); //for (vectorstring::iterator p test.begin(); p ! test.end(); p) { cout 刪除字符串 bobwhite endl; if (test_obj.deleteElem(bobwhite)) { cout 刪除成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 刪除失敗 endl; exit(0); } cout 刪除字符串 bluejay endl; if (test_obj.deleteElem(bluejay)) { cout 刪除成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 刪除失敗 endl; exit(0); } } cout endl; string mod abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789; const int L 9; // 隨機(jī)字符串最大長(zhǎng)度 const int r 2; //相同長(zhǎng)度重復(fù)次數(shù) vectorint LList(L); vectorstring random_str; for (int run 0; run LList.size(); run) LList[run] run 1; shuffle(LList.begin(), LList.end(), default_random_engine()); for (int re 1; re r; re) { for (int run 0; run LList.size(); run) { string r; for (int go 1; go LList[run]; go) { r.append(1, mod[rand() % mod.size()]); } random_str.push_back(r); } } for (vectorstring::iterator p random_str.begin(); p ! random_str.end(); p) { cout 插入字符串 *p endl; if (test_obj.insert(*p)) { cout 插入成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 插入失敗 endl; exit(0); } } cout endl; // TrieTreeNode *copy test_ptr.copy(); for (vectorstring::iterator p random_str.begin(); p ! random_str.end(); p) { cout 刪除字符串 *p endl; if (test_obj.deleteElem(*p)) { cout 刪除成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 刪除失敗 endl; exit(0); } } cout endl; random_str.clear(); for (int i 1; i 7; i) { string temp(mod, 0, i); for (int run 1; run 7; run) { string r; for (int go 1; go run; go) { r.append(1, mod[rand() % mod.size()]); } random_str.push_back(temp r); } } cout 測(cè)試字符串有共同前綴不相等情形 endl; for (vectorstring::iterator p random_str.begin(); p ! random_str.end(); p) { cout 插入字符串 *p endl; if (test_obj.insert(*p)) { cout 插入成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 插入失敗 endl; exit(0); } } cout endl; // TrieTreeNode *copy test_ptr.copy(); for (vectorstring::iterator p random_str.begin(); p ! random_str.end(); p) { cout 刪除字符串 *p endl; if (test_obj.deleteElem(*p)) { cout 刪除成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 刪除失敗 endl; exit(0); } } cout endl; shuffle(mod.begin(), mod.end(), default_random_engine()); for (string::size_type i 1; i mod.size(); i) { string temp(mod, 0, i); cout 插入字符串 mod 的前綴 temp endl; if (test_obj.insert(temp)) { cout 插入成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 插入失敗 endl; exit(0); } } for (string::size_type i 1; i mod.size(); i) { string temp(mod, 0, i); cout 刪除字符串 mod 的前綴 temp endl; if (test_obj.deleteElem(temp)) { cout 刪除成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 刪除失敗 endl; exit(0); } } return 0; }第二種實(shí)現(xiàn)分支節(jié)點(diǎn)使用數(shù)組保存前綴的索引#include map #include stack #include vector #include string #include iostream #include random #include tuple using namespace std; enum Compare_Result { EQUAL, LEFT_IS_PREFIX, RIGHT_IS_PREFIX, NOT_EQUAL }; struct TrieTreeNode //Trie樹節(jié)點(diǎn)類型 { enum NodeType { DATANODE, BRANCHNODE } type_flag; //節(jié)點(diǎn)類型標(biāo)志分支節(jié)點(diǎn)或存放關(guān)鍵字的葉節(jié)點(diǎn) struct BranchNode { vectorTrieTreeNode* sub_ptr; size_t num; BranchNode() :sub_ptr(128, nullptr), num(0){} BranchNode(const BranchNode B) :num(B.num), sub_ptr(128, nullptr) {} }; union { string key_in_trie; //葉節(jié)點(diǎn)關(guān)鍵字 BranchNode branch_ptr; //分支節(jié)點(diǎn)的分支字符和對(duì)應(yīng)的指向分支字符對(duì)應(yīng)的子節(jié)點(diǎn)的指針之間的映射關(guān)系 }; TrieTreeNode(const string k) :type_flag(NodeType::DATANODE), key_in_trie(k) {} TrieTreeNode() :type_flag(NodeType::BRANCHNODE), branch_ptr() {} TrieTreeNode(TrieTreeNode be_copied) { switch (be_copied.type_flag) { case NodeType::DATANODE:{ new (key_in_trie) string(be_copied.key_in_trie); break; } case NodeType::BRANCHNODE:{ new (branch_ptr) BranchNode(be_copied.branch_ptr); break; } } type_flag be_copied.type_flag; } ~TrieTreeNode() { switch (type_flag) { case NodeType::DATANODE: key_in_trie.~string(); break; case NodeType::BRANCHNODE: branch_ptr.~BranchNode(); break; } } }; class TrieTree { public: bool insert(const string be_inserted) const; //Trie樹中插入關(guān)鍵字,true成功false失敗 bool deleteElem(const string be_deleted) const; //Trie樹中刪除指定關(guān)鍵字,true成功false失敗 TrieTreeNode* copy(); //拷貝Trie樹返回指向副本Trie樹的指針 TrieTree() { root new TrieTreeNode(); } TrieTree(TrieTree be_copied) { root be_copied.copy(); } void printTrieTree(TrieTreeNode* cur, size_t offset) const; bool isEmpty() const { return root-branch_ptr.num 0; } TrieTreeNode* getTrieTree() const { return root; } ~TrieTree(); private: template typename T Compare_Result static strCompare(const string left, const string right, T i); static size_t char_to_index(const char ch) { return ch; } TrieTreeNode* root; //Trie樹根節(jié)點(diǎn) }; ostream operator(ostream o, const TrieTree be_output) { if (be_output.isEmpty()) { o NULL endl; return o; } be_output.printTrieTree(be_output.getTrieTree(), 0); return o; } template typename T Compare_Result TrieTree::strCompare(const string left, const string right, T i) { for (; ; i) { if (i left.size() i right.size()) return Compare_Result::EQUAL; else if (i left.size() || i right.size()) { if (i left.size()) return Compare_Result::LEFT_IS_PREFIX; else return Compare_Result::RIGHT_IS_PREFIX; } else if (left[i] ! right[i]) return Compare_Result::NOT_EQUAL; } } bool TrieTree::deleteElem(const string be_deleted) const { TrieTreeNode* run root; stackTrieTreeNode* work_stack; size_t index; { string::size_type i 0; while (run-type_flag TrieTreeNode::NodeType::BRANCHNODE) { if (i be_deleted.size()) { index char_to_index(be_deleted[i]); if (run-branch_ptr.sub_ptr[index] nullptr) return false; i; work_stack.push(run); run run-branch_ptr.sub_ptr[index]; } else { if (run-branch_ptr.sub_ptr[0] nullptr) return false; work_stack.push(run); run run-branch_ptr.sub_ptr[0]; index 0; } } if (run ! work_stack.top()-branch_ptr.sub_ptr[0] strCompare(be_deleted, run-key_in_trie, i) ! Compare_Result::EQUAL) return false; } work_stack.top()-branch_ptr.sub_ptr[index] nullptr; delete run; --work_stack.top()-branch_ptr.num; if (work_stack.top() ! root work_stack.top()-branch_ptr.num 1) { for (index 0; index work_stack.top()-branch_ptr.sub_ptr.size(); index) { if (work_stack.top()-branch_ptr.sub_ptr[index] ! nullptr) break; } if (work_stack.top()-branch_ptr.sub_ptr[index]-type_flag TrieTreeNode::NodeType::DATANODE) { run work_stack.top()-branch_ptr.sub_ptr[index]; delete work_stack.top(); work_stack.pop(); while (work_stack.top() ! root) { if (work_stack.top()-branch_ptr.num 2) { work_stack.top()-branch_ptr.sub_ptr[char_to_index(be_deleted[work_stack.size() - 1])] run; return true; } else { delete work_stack.top(); work_stack.pop(); } } work_stack.top()-branch_ptr.sub_ptr[char_to_index(be_deleted[0])] run; } } return true; } bool TrieTree::insert(const string be_inserted) const { TrieTreeNode* run root; string::size_type i 0; size_t index; TrieTreeNode* father_of_leaf nullptr; while (run-type_flag ! TrieTreeNode::NodeType::DATANODE) { if (i be_inserted.size()) { index char_to_index(be_inserted[i]); if (run-branch_ptr.sub_ptr[index] nullptr) { run-branch_ptr.sub_ptr[index] new TrieTreeNode(be_inserted); run-branch_ptr.num; return true; } father_of_leaf run; run run-branch_ptr.sub_ptr[index]; i; } else { if (run-branch_ptr.sub_ptr[0] nullptr) { run-branch_ptr.sub_ptr[0] new TrieTreeNode(be_inserted); run-branch_ptr.num; return true; } return false; } } Compare_Result compare_result; { string::size_type start_index i; compare_result strComparestring::size_type (be_inserted, run-key_in_trie, i); if (compare_result Compare_Result::EQUAL) return false; father_of_leaf father_of_leaf-branch_ptr.sub_ptr[index] new TrieTreeNode(); for (; start_index i; start_index) { father_of_leaf-branch_ptr.num 1; father_of_leaf father_of_leaf-branch_ptr.sub_ptr[char_to_index(be_inserted[start_index])] new TrieTreeNode(); } } if (compare_result Compare_Result::LEFT_IS_PREFIX) { father_of_leaf-branch_ptr.sub_ptr[0] new TrieTreeNode(be_inserted); father_of_leaf-branch_ptr.sub_ptr[char_to_index(run-key_in_trie[i])] run; } else if (compare_result Compare_Result::RIGHT_IS_PREFIX) { father_of_leaf-branch_ptr.sub_ptr[0] run; father_of_leaf-branch_ptr.sub_ptr[char_to_index(be_inserted[i])] new TrieTreeNode(be_inserted); } else { father_of_leaf-branch_ptr.sub_ptr[char_to_index(run-key_in_trie[i])] run; father_of_leaf-branch_ptr.sub_ptr[char_to_index(be_inserted[i])] new TrieTreeNode(be_inserted); } father_of_leaf-branch_ptr.num 2; return true; } size_t find_next(TrieTreeNode* cur, size_t run) { for (; run cur-branch_ptr.sub_ptr.size(); run) { if (cur-branch_ptr.sub_ptr[run] ! nullptr) return run; } } TrieTree::~TrieTree() { TrieTreeNode* run root; stacktupleTrieTreeNode*, size_t, short work_stack; bool trace_back_flag true; while (true) { if (trace_back_flag true) { if (run root) { if (run-branch_ptr.num 0) { delete root; return; } } else { if (run-type_flag TrieTreeNode::DATANODE) { delete run; run get0(work_stack.top()); if (run-branch_ptr.num ! get2(work_stack.top())) get1(work_stack.top()) find_next(run, get1(work_stack.top()) 1); trace_back_flag false; continue; } } work_stack.push(make_tuple(run, find_next(run, 0), 1)); run run-branch_ptr.sub_ptr[get1(work_stack.top())]; } else { if (run root || get2(work_stack.top()) ! run-branch_ptr.num) { if (run root) { if (get2(work_stack.top()) root-branch_ptr.num) { delete root; return; } } get2(work_stack.top()); run run-branch_ptr.sub_ptr[get1(work_stack.top())]; trace_back_flag true; } else { delete run; work_stack.pop(); run get0(work_stack.top()); if (run-branch_ptr.num ! get2(work_stack.top())) get1(work_stack.top()) find_next(run, get1(work_stack.top()) 1); } } } } TrieTreeNode* TrieTree::copy() { TrieTreeNode* be_copied root; stacktupleTrieTreeNode*, size_t, short work_stack; stackTrieTreeNode* copy_trace_stack; TrieTreeNode* root_of_copy nullptr; bool trace_back_flag true; while (true) { if (trace_back_flag) { if (be_copied-type_flag TrieTreeNode::BRANCHNODE) { if (be_copied root) { root_of_copy new TrieTreeNode(*be_copied); if (be_copied-branch_ptr.num 0) { break; } copy_trace_stack.push(root_of_copy); } else copy_trace_stack.push(copy_trace_stack.top()-branch_ptr.sub_ptr[get1(work_stack.top())] new TrieTreeNode(*be_copied)); work_stack.push(make_tuple(be_copied, find_next(be_copied, 0), 1)); be_copied be_copied-branch_ptr.sub_ptr[get1(work_stack.top())]; } else { copy_trace_stack.top()-branch_ptr.sub_ptr[get1(work_stack.top())] new TrieTreeNode(*be_copied); be_copied get0(work_stack.top()); trace_back_flag false; } } else { if (be_copied-branch_ptr.num ! get2(work_stack.top())) { get1(work_stack.top()) find_next(be_copied, get1(work_stack.top()) 1); get2(work_stack.top()); be_copied be_copied-branch_ptr.sub_ptr[get1(work_stack.top())]; trace_back_flag true; } else { if (be_copied root) break; work_stack.pop(); be_copied get0(work_stack.top()); copy_trace_stack.pop(); } } } return root_of_copy; } void TrieTree::printTrieTree(TrieTreeNode* cur, size_t offset) const { if (cur-type_flag TrieTreeNode::BRANCHNODE) { size_t max_length; if (cur-branch_ptr.sub_ptr[0] ! nullptr) max_length 4; else max_length 1; int count 0; for (size_t run 0; ; run) { if (cur-branch_ptr.sub_ptr[run] ! nullptr) { count; for (size_t go 1; go offset; go) cout ; if (run 0) cout NULL; else { cout static_castchar(run); for (size_t go 2; go max_length; go) cout ; } cout |- endl; printTrieTree(cur-branch_ptr.sub_ptr[run], offset max_length 2); if (count cur-branch_ptr.num) break; } } } else { for (size_t go 1; go offset; go) cout ; cout leaf: cur-key_in_trie endl; } } int main() { vectorstring test { bluebird, bunting, bobwhite, bluejay }; TrieTree test_obj; for (vectorstring::iterator p test.begin(); p ! test.end(); p) { cout 插入字符串 *p endl; if (test_obj.insert(*p)) { cout 插入成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 插入失敗 endl; exit(0); } } cout endl; // TrieTreeNode *copy test_ptr.copy(); //for (vectorstring::iterator p test.begin(); p ! test.end(); p) { cout 刪除字符串 bobwhite endl; if (test_obj.deleteElem(bobwhite)) { cout 刪除成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 刪除失敗 endl; exit(0); } cout 刪除字符串 bluejay endl; if (test_obj.deleteElem(bluejay)) { cout 刪除成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 刪除失敗 endl; exit(0); } } cout endl; string mod abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789; const int L 9; // 隨機(jī)字符串最大長(zhǎng)度 const int r 2; //相同長(zhǎng)度重復(fù)次數(shù) vectorint LList(L); vectorstring random_str; for (int run 0; run LList.size(); run) LList[run] run 1; shuffle(LList.begin(), LList.end(), default_random_engine()); for (int re 1; re r; re) { for (int run 0; run LList.size(); run) { string r; for (int go 1; go LList[run]; go) { r.append(1, mod[rand() % mod.size()]); } random_str.push_back(r); } } for (vectorstring::iterator p random_str.begin(); p ! random_str.end(); p) { cout 插入字符串 *p endl; if (test_obj.insert(*p)) { cout 插入成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 插入失敗 endl; exit(0); } } cout endl; // TrieTreeNode *copy test_ptr.copy(); for (vectorstring::iterator p random_str.begin(); p ! random_str.end(); p) { cout 刪除字符串 *p endl; if (test_obj.deleteElem(*p)) { cout 刪除成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 刪除失敗 endl; exit(0); } } cout endl; random_str.clear(); for (int i 1; i 7; i) { string temp(mod, 0, i); for (int run 1; run 7; run) { string r; for (int go 1; go run; go) { r.append(1, mod[rand() % mod.size()]); } random_str.push_back(temp r); } } cout 測(cè)試字符串有共同前綴不相等情形 endl; for (vectorstring::iterator p random_str.begin(); p ! random_str.end(); p) { cout 插入字符串 *p endl; if (test_obj.insert(*p)) { cout 插入成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 插入失敗 endl; exit(0); } } cout endl; // TrieTreeNode *copy test_ptr.copy(); for (vectorstring::iterator p random_str.begin(); p ! random_str.end(); p) { cout 刪除字符串 *p endl; if (test_obj.deleteElem(*p)) { cout 刪除成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 刪除失敗 endl; exit(0); } } cout endl; shuffle(mod.begin(), mod.end(), default_random_engine()); for (string::size_type i 1; i mod.size(); i) { string temp(mod, 0, i); cout 插入字符串 mod 的前綴 temp endl; if (test_obj.insert(temp)) { cout 插入成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 插入失敗 endl; exit(0); } } for (string::size_type i 1; i mod.size(); i) { string temp(mod, 0, i); cout 刪除字符串 mod 的前綴 temp endl; if (test_obj.deleteElem(temp)) { cout 刪除成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 刪除失敗 endl; exit(0); } } return 0; }每種實(shí)現(xiàn)應(yīng)該都能適用于空串的插入刪除自己沒有驗(yàn)證過感興趣可自行驗(yàn)證 Trie樹的實(shí)現(xiàn)
Trie樹是保存字符串公共前綴信息的數(shù)據(jù)結(jié)構(gòu),可用于字符串多模匹配普通的非壓縮Trie樹實(shí)現(xiàn)如下第一種實(shí)現(xiàn):每個(gè)分支節(jié)點(diǎn)使用map標(biāo)準(zhǔn)庫容器保存前綴索引#include map #include stack #include vector #include string #include iostream #include random using namespace std; enum Compare_Result {EQUAL, LEFT_IS_PREFIX, RIGHT_IS_PREFIX, NOT_EQUAL}; struct TrieTreeNode //Trie樹節(jié)點(diǎn)類型 { enum NodeType { DATANODE, BRANCHNODE } type_flag; //節(jié)點(diǎn)類型標(biāo)志分支節(jié)點(diǎn)或存放關(guān)鍵字的葉節(jié)點(diǎn) union { string key_in_trie; //葉節(jié)點(diǎn)關(guān)鍵字 mapchar, TrieTreeNode* sub_ptr; //分支節(jié)點(diǎn)的分支字符和對(duì)應(yīng)的指向分支字符對(duì)應(yīng)的子節(jié)點(diǎn)的指針之間的映射關(guān)系 }; TrieTreeNode(const string k) :type_flag(NodeType::DATANODE), key_in_trie(k) {} TrieTreeNode() :type_flag(NodeType::BRANCHNODE), sub_ptr() {} TrieTreeNode(TrieTreeNode be_copied) { switch (be_copied.type_flag) { case NodeType::DATANODE: new (key_in_trie) string(be_copied.key_in_trie); break; case NodeType::BRANCHNODE: { new (sub_ptr) mapchar, TrieTreeNode*(); for (mapchar, TrieTreeNode*::iterator p be_copied.sub_ptr.begin(); p ! be_copied.sub_ptr.end(); p) sub_ptr.insert(make_pair(p-first, nullptr)); } break; } type_flag be_copied.type_flag; } ~TrieTreeNode() { switch (type_flag) { case NodeType::DATANODE: key_in_trie.~string(); break; case NodeType::BRANCHNODE: sub_ptr.~mapchar, TrieTreeNode*(); break; } } }; class TrieTree { public: bool insert(const string be_inserted) const; //Trie樹中插入關(guān)鍵字,true成功false失敗 bool deleteElem(const string be_deleted) const; //Trie樹中刪除指定關(guān)鍵字,true成功false失敗 TrieTreeNode* copy(); //拷貝Trie樹返回指向副本Trie樹的指針 TrieTree() { root new TrieTreeNode(); } void printTrieTree(TrieTreeNode* cur, size_t offset) const; bool isEmpty() const { return root-sub_ptr.empty(); } TrieTreeNode* getTrieTree() const { return root; } TrieTree(TrieTree be_copied) { root be_copied.copy(); } ~TrieTree(); private: Compare_Result static strCompare(const string left, const string right, string::size_type i); TrieTreeNode* root; //Trie樹根節(jié)點(diǎn) }; ostream operator(ostream o, const TrieTree be_output) { if (be_output.isEmpty()) { o NULL endl; return o; } be_output.printTrieTree(be_output.getTrieTree(), 0); return o; } Compare_Result TrieTree::strCompare(const string left, const string right, string::size_type i) { for (; ; i) { if (i left.size() i right.size()) return Compare_Result::EQUAL; else if (i left.size() || i right.size()) { if (i left.size()) return Compare_Result::LEFT_IS_PREFIX; else return Compare_Result::RIGHT_IS_PREFIX; } else if (left[i] ! right[i]) return Compare_Result::NOT_EQUAL; } } bool TrieTree::deleteElem(const string be_deleted) const { TrieTreeNode* run root; vectorTrieTreeNode* stack; vectorTrieTreeNode*::size_type index; mapchar, TrieTreeNode*::iterator stop_branch_node; mapchar, TrieTreeNode*::iterator leaf_father_point_to_leaf; { string::size_type i 0; while (true) { if (i be_deleted.size()) { mapchar, TrieTreeNode*::iterator it; it run-sub_ptr.find(be_deleted[i]); if (it run-sub_ptr.end()) return false; i; if (run root || run-sub_ptr.size() 2) { if (it-second-type_flag TrieTreeNode::NodeType::BRANCHNODE) { index stack.size(); stop_branch_node it; } else { leaf_father_point_to_leaf it; break; } } else stack.push_back(run); run it-second; } else { if (run-sub_ptr.empty() || \0 ! run-sub_ptr.begin()-first) return false; leaf_father_point_to_leaf run-sub_ptr.begin(); break; } } if (leaf_father_point_to_leaf-first ! \0 strCompare(be_deleted, leaf_father_point_to_leaf-second-key_in_trie, i) ! Compare_Result::EQUAL) return false; } delete leaf_father_point_to_leaf-second; run-sub_ptr.erase(leaf_father_point_to_leaf); if (run ! root run-sub_ptr.size() 1 run-sub_ptr.begin()-second-type_flag TrieTreeNode::NodeType::DATANODE) { if (stop_branch_node-second ! run) { for (size_t j stack.size() - 1; j index; --j) delete stack[j]; delete stack[index]; } stop_branch_node-second run-sub_ptr.begin()-second; delete run; } return true; } bool TrieTree::insert(const string be_inserted) const { TrieTreeNode* run root; string::size_type i 0; pairmapchar, TrieTreeNode*::iterator, bool result; while (run-type_flag ! TrieTreeNode::NodeType::DATANODE) { if (i be_inserted.size()) { result run-sub_ptr.insert(make_pair(be_inserted[i], new TrieTreeNode(be_inserted))); if (result.second) return true; run result.first-second; i; } else { if (run-sub_ptr.empty() || run-sub_ptr.begin()-first ! \0) { run-sub_ptr.insert(make_pair(\0, new TrieTreeNode(be_inserted))); return true; } return false; } } Compare_Result compare_result; { string::size_type start_index i; compare_result strCompare(be_inserted, run-key_in_trie, i); if (compare_result Compare_Result::EQUAL) return false; result.first-second new TrieTreeNode(); for (; start_index i; start_index) result.first result.first-second-sub_ptr.insert(make_pair(be_inserted[start_index], new TrieTreeNode())).first; } if (compare_result Compare_Result::LEFT_IS_PREFIX) { result.first-second-sub_ptr.insert(make_pair(\0, new TrieTreeNode(be_inserted))); result.first-second-sub_ptr.insert(make_pair(run-key_in_trie[i], run)); } else if (compare_result Compare_Result::RIGHT_IS_PREFIX) { result.first-second-sub_ptr.insert(make_pair(\0, run)); result.first-second-sub_ptr.insert(make_pair(be_inserted[i], new TrieTreeNode(be_inserted))); } else { result.first-second-sub_ptr.insert(make_pair(run-key_in_trie[i], run)); result.first-second-sub_ptr.insert(make_pair(be_inserted[i], new TrieTreeNode(be_inserted))); } return true; } TrieTree::~TrieTree() { TrieTreeNode* run root; stackpairTrieTreeNode*, mapchar, TrieTreeNode*::iterator work_stack; bool trace_back_flag true; while (true) { if (trace_back_flag true) { if (run root) { if (run-sub_ptr.begin() run-sub_ptr.end()) { delete root; return; } } else { if (run-type_flag TrieTreeNode::DATANODE) { delete run; run work_stack.top().first; work_stack.top().second; //work_stack.top().second run-sub_ptr.erase(work_stack.top().second); trace_back_flag false; continue; } } work_stack.push(make_pair(run, run-sub_ptr.begin())); run run-sub_ptr.begin()-second; } else { if (run root || work_stack.top().second ! run-sub_ptr.end()) { if (run root) { if (work_stack.top().second root-sub_ptr.end()) { delete root; return; } } run work_stack.top().second-second; trace_back_flag true; } else { delete run; work_stack.pop(); run work_stack.top().first; work_stack.top().second; // work_stack.top().second run-sub_ptr.erase(work_stack.top().second); } } } } TrieTreeNode* TrieTree::copy() { TrieTreeNode* be_copied root; stackpairTrieTreeNode*, mapchar, TrieTreeNode*::iterator work_stack; stackpairTrieTreeNode*, mapchar, TrieTreeNode*::iterator copy_trace_stack; TrieTreeNode* root_of_copy nullptr; bool trace_back_flag true; while (true) { if (trace_back_flag true) { if (be_copied root) { root_of_copy new TrieTreeNode(*be_copied); if (be_copied-sub_ptr.begin() be_copied-sub_ptr.end()) break; copy_trace_stack.push(make_pair(root_of_copy, root_of_copy-sub_ptr.begin())); } else { if (work_stack.top().second ! work_stack.top().first-sub_ptr.begin()) copy_trace_stack.top().second; copy_trace_stack.top().second-second new TrieTreeNode(*be_copied); if (be_copied-type_flag ! TrieTreeNode::DATANODE) copy_trace_stack.push(make_pair(copy_trace_stack.top().second-second, copy_trace_stack.top().second-second-sub_ptr.begin())); else { be_copied work_stack.top().first; trace_back_flag false; continue; } } work_stack.push(make_pair(be_copied, be_copied-sub_ptr.begin())); be_copied be_copied-sub_ptr.begin()-second; } else { if (work_stack.top().second-second-type_flag ! TrieTreeNode::DATANODE) copy_trace_stack.pop(); if (be_copied root || (work_stack.top().second) ! be_copied-sub_ptr.end()) { if (be_copied root) { if ((work_stack.top().second) root-sub_ptr.end()) break; } be_copied work_stack.top().second-second; trace_back_flag true; } else { work_stack.pop(); be_copied work_stack.top().first; } } } return root_of_copy; } void TrieTree::printTrieTree(TrieTreeNode* cur, size_t offset) const { if (cur-type_flag TrieTreeNode::BRANCHNODE) { size_t max_length; if (cur-sub_ptr.begin()-first \0) max_length 4; else max_length 1; for (mapchar, TrieTreeNode*::iterator run cur-sub_ptr.begin(); run ! cur-sub_ptr.end(); run) { for (size_t go 1; go offset; go) cout ; if (run-first \0) cout NULL; else { cout run-first; for (size_t go 2; go max_length; go) cout ; } cout |- endl; printTrieTree(run-second, offset 2 max_length); } } else { for (size_t go 1; go offset; go) cout ; cout leaf: cur-key_in_trie endl; } } int main() { vectorstring test { bluebird, bunting, bobwhite, bluejay }; TrieTree test_obj; for (vectorstring::iterator p test.begin(); p ! test.end(); p) { cout 插入字符串 *p endl; if (test_obj.insert(*p)) { cout 插入成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 插入失敗 endl; exit(0); } } cout endl; // TrieTreeNode *copy test_ptr.copy(); //for (vectorstring::iterator p test.begin(); p ! test.end(); p) { cout 刪除字符串 bobwhite endl; if (test_obj.deleteElem(bobwhite)) { cout 刪除成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 刪除失敗 endl; exit(0); } cout 刪除字符串 bluejay endl; if (test_obj.deleteElem(bluejay)) { cout 刪除成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 刪除失敗 endl; exit(0); } } cout endl; string mod abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789; const int L 9; // 隨機(jī)字符串最大長(zhǎng)度 const int r 2; //相同長(zhǎng)度重復(fù)次數(shù) vectorint LList(L); vectorstring random_str; for (int run 0; run LList.size(); run) LList[run] run 1; shuffle(LList.begin(), LList.end(), default_random_engine()); for (int re 1; re r; re) { for (int run 0; run LList.size(); run) { string r; for (int go 1; go LList[run]; go) { r.append(1, mod[rand() % mod.size()]); } random_str.push_back(r); } } for (vectorstring::iterator p random_str.begin(); p ! random_str.end(); p) { cout 插入字符串 *p endl; if (test_obj.insert(*p)) { cout 插入成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 插入失敗 endl; exit(0); } } cout endl; // TrieTreeNode *copy test_ptr.copy(); for (vectorstring::iterator p random_str.begin(); p ! random_str.end(); p) { cout 刪除字符串 *p endl; if (test_obj.deleteElem(*p)) { cout 刪除成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 刪除失敗 endl; exit(0); } } cout endl; random_str.clear(); for (int i 1; i 7; i) { string temp(mod, 0, i); for (int run 1; run 7; run) { string r; for (int go 1; go run; go) { r.append(1, mod[rand() % mod.size()]); } random_str.push_back(temp r); } } cout 測(cè)試字符串有共同前綴不相等情形 endl; for (vectorstring::iterator p random_str.begin(); p ! random_str.end(); p) { cout 插入字符串 *p endl; if (test_obj.insert(*p)) { cout 插入成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 插入失敗 endl; exit(0); } } cout endl; // TrieTreeNode *copy test_ptr.copy(); for (vectorstring::iterator p random_str.begin(); p ! random_str.end(); p) { cout 刪除字符串 *p endl; if (test_obj.deleteElem(*p)) { cout 刪除成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 刪除失敗 endl; exit(0); } } cout endl; shuffle(mod.begin(), mod.end(), default_random_engine()); for (string::size_type i 1; i mod.size(); i) { string temp(mod, 0, i); cout 插入字符串 mod 的前綴 temp endl; if (test_obj.insert(temp)) { cout 插入成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 插入失敗 endl; exit(0); } } for (string::size_type i 1; i mod.size(); i) { string temp(mod, 0, i); cout 刪除字符串 mod 的前綴 temp endl; if (test_obj.deleteElem(temp)) { cout 刪除成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 刪除失敗 endl; exit(0); } } return 0; }第二種實(shí)現(xiàn)分支節(jié)點(diǎn)使用數(shù)組保存前綴的索引#include map #include stack #include vector #include string #include iostream #include random #include tuple using namespace std; enum Compare_Result { EQUAL, LEFT_IS_PREFIX, RIGHT_IS_PREFIX, NOT_EQUAL }; struct TrieTreeNode //Trie樹節(jié)點(diǎn)類型 { enum NodeType { DATANODE, BRANCHNODE } type_flag; //節(jié)點(diǎn)類型標(biāo)志分支節(jié)點(diǎn)或存放關(guān)鍵字的葉節(jié)點(diǎn) struct BranchNode { vectorTrieTreeNode* sub_ptr; size_t num; BranchNode() :sub_ptr(128, nullptr), num(0){} BranchNode(const BranchNode B) :num(B.num), sub_ptr(128, nullptr) {} }; union { string key_in_trie; //葉節(jié)點(diǎn)關(guān)鍵字 BranchNode branch_ptr; //分支節(jié)點(diǎn)的分支字符和對(duì)應(yīng)的指向分支字符對(duì)應(yīng)的子節(jié)點(diǎn)的指針之間的映射關(guān)系 }; TrieTreeNode(const string k) :type_flag(NodeType::DATANODE), key_in_trie(k) {} TrieTreeNode() :type_flag(NodeType::BRANCHNODE), branch_ptr() {} TrieTreeNode(TrieTreeNode be_copied) { switch (be_copied.type_flag) { case NodeType::DATANODE:{ new (key_in_trie) string(be_copied.key_in_trie); break; } case NodeType::BRANCHNODE:{ new (branch_ptr) BranchNode(be_copied.branch_ptr); break; } } type_flag be_copied.type_flag; } ~TrieTreeNode() { switch (type_flag) { case NodeType::DATANODE: key_in_trie.~string(); break; case NodeType::BRANCHNODE: branch_ptr.~BranchNode(); break; } } }; class TrieTree { public: bool insert(const string be_inserted) const; //Trie樹中插入關(guān)鍵字,true成功false失敗 bool deleteElem(const string be_deleted) const; //Trie樹中刪除指定關(guān)鍵字,true成功false失敗 TrieTreeNode* copy(); //拷貝Trie樹返回指向副本Trie樹的指針 TrieTree() { root new TrieTreeNode(); } TrieTree(TrieTree be_copied) { root be_copied.copy(); } void printTrieTree(TrieTreeNode* cur, size_t offset) const; bool isEmpty() const { return root-branch_ptr.num 0; } TrieTreeNode* getTrieTree() const { return root; } ~TrieTree(); private: template typename T Compare_Result static strCompare(const string left, const string right, T i); static size_t char_to_index(const char ch) { return ch; } TrieTreeNode* root; //Trie樹根節(jié)點(diǎn) }; ostream operator(ostream o, const TrieTree be_output) { if (be_output.isEmpty()) { o NULL endl; return o; } be_output.printTrieTree(be_output.getTrieTree(), 0); return o; } template typename T Compare_Result TrieTree::strCompare(const string left, const string right, T i) { for (; ; i) { if (i left.size() i right.size()) return Compare_Result::EQUAL; else if (i left.size() || i right.size()) { if (i left.size()) return Compare_Result::LEFT_IS_PREFIX; else return Compare_Result::RIGHT_IS_PREFIX; } else if (left[i] ! right[i]) return Compare_Result::NOT_EQUAL; } } bool TrieTree::deleteElem(const string be_deleted) const { TrieTreeNode* run root; stackTrieTreeNode* work_stack; size_t index; { string::size_type i 0; while (run-type_flag TrieTreeNode::NodeType::BRANCHNODE) { if (i be_deleted.size()) { index char_to_index(be_deleted[i]); if (run-branch_ptr.sub_ptr[index] nullptr) return false; i; work_stack.push(run); run run-branch_ptr.sub_ptr[index]; } else { if (run-branch_ptr.sub_ptr[0] nullptr) return false; work_stack.push(run); run run-branch_ptr.sub_ptr[0]; index 0; } } if (run ! work_stack.top()-branch_ptr.sub_ptr[0] strCompare(be_deleted, run-key_in_trie, i) ! Compare_Result::EQUAL) return false; } work_stack.top()-branch_ptr.sub_ptr[index] nullptr; delete run; --work_stack.top()-branch_ptr.num; if (work_stack.top() ! root work_stack.top()-branch_ptr.num 1) { for (index 0; index work_stack.top()-branch_ptr.sub_ptr.size(); index) { if (work_stack.top()-branch_ptr.sub_ptr[index] ! nullptr) break; } if (work_stack.top()-branch_ptr.sub_ptr[index]-type_flag TrieTreeNode::NodeType::DATANODE) { run work_stack.top()-branch_ptr.sub_ptr[index]; delete work_stack.top(); work_stack.pop(); while (work_stack.top() ! root) { if (work_stack.top()-branch_ptr.num 2) { work_stack.top()-branch_ptr.sub_ptr[char_to_index(be_deleted[work_stack.size() - 1])] run; return true; } else { delete work_stack.top(); work_stack.pop(); } } work_stack.top()-branch_ptr.sub_ptr[char_to_index(be_deleted[0])] run; } } return true; } bool TrieTree::insert(const string be_inserted) const { TrieTreeNode* run root; string::size_type i 0; size_t index; TrieTreeNode* father_of_leaf nullptr; while (run-type_flag ! TrieTreeNode::NodeType::DATANODE) { if (i be_inserted.size()) { index char_to_index(be_inserted[i]); if (run-branch_ptr.sub_ptr[index] nullptr) { run-branch_ptr.sub_ptr[index] new TrieTreeNode(be_inserted); run-branch_ptr.num; return true; } father_of_leaf run; run run-branch_ptr.sub_ptr[index]; i; } else { if (run-branch_ptr.sub_ptr[0] nullptr) { run-branch_ptr.sub_ptr[0] new TrieTreeNode(be_inserted); run-branch_ptr.num; return true; } return false; } } Compare_Result compare_result; { string::size_type start_index i; compare_result strComparestring::size_type (be_inserted, run-key_in_trie, i); if (compare_result Compare_Result::EQUAL) return false; father_of_leaf father_of_leaf-branch_ptr.sub_ptr[index] new TrieTreeNode(); for (; start_index i; start_index) { father_of_leaf-branch_ptr.num 1; father_of_leaf father_of_leaf-branch_ptr.sub_ptr[char_to_index(be_inserted[start_index])] new TrieTreeNode(); } } if (compare_result Compare_Result::LEFT_IS_PREFIX) { father_of_leaf-branch_ptr.sub_ptr[0] new TrieTreeNode(be_inserted); father_of_leaf-branch_ptr.sub_ptr[char_to_index(run-key_in_trie[i])] run; } else if (compare_result Compare_Result::RIGHT_IS_PREFIX) { father_of_leaf-branch_ptr.sub_ptr[0] run; father_of_leaf-branch_ptr.sub_ptr[char_to_index(be_inserted[i])] new TrieTreeNode(be_inserted); } else { father_of_leaf-branch_ptr.sub_ptr[char_to_index(run-key_in_trie[i])] run; father_of_leaf-branch_ptr.sub_ptr[char_to_index(be_inserted[i])] new TrieTreeNode(be_inserted); } father_of_leaf-branch_ptr.num 2; return true; } size_t find_next(TrieTreeNode* cur, size_t run) { for (; run cur-branch_ptr.sub_ptr.size(); run) { if (cur-branch_ptr.sub_ptr[run] ! nullptr) return run; } } TrieTree::~TrieTree() { TrieTreeNode* run root; stacktupleTrieTreeNode*, size_t, short work_stack; bool trace_back_flag true; while (true) { if (trace_back_flag true) { if (run root) { if (run-branch_ptr.num 0) { delete root; return; } } else { if (run-type_flag TrieTreeNode::DATANODE) { delete run; run get0(work_stack.top()); if (run-branch_ptr.num ! get2(work_stack.top())) get1(work_stack.top()) find_next(run, get1(work_stack.top()) 1); trace_back_flag false; continue; } } work_stack.push(make_tuple(run, find_next(run, 0), 1)); run run-branch_ptr.sub_ptr[get1(work_stack.top())]; } else { if (run root || get2(work_stack.top()) ! run-branch_ptr.num) { if (run root) { if (get2(work_stack.top()) root-branch_ptr.num) { delete root; return; } } get2(work_stack.top()); run run-branch_ptr.sub_ptr[get1(work_stack.top())]; trace_back_flag true; } else { delete run; work_stack.pop(); run get0(work_stack.top()); if (run-branch_ptr.num ! get2(work_stack.top())) get1(work_stack.top()) find_next(run, get1(work_stack.top()) 1); } } } } TrieTreeNode* TrieTree::copy() { TrieTreeNode* be_copied root; stacktupleTrieTreeNode*, size_t, short work_stack; stackTrieTreeNode* copy_trace_stack; TrieTreeNode* root_of_copy nullptr; bool trace_back_flag true; while (true) { if (trace_back_flag) { if (be_copied-type_flag TrieTreeNode::BRANCHNODE) { if (be_copied root) { root_of_copy new TrieTreeNode(*be_copied); if (be_copied-branch_ptr.num 0) { break; } copy_trace_stack.push(root_of_copy); } else copy_trace_stack.push(copy_trace_stack.top()-branch_ptr.sub_ptr[get1(work_stack.top())] new TrieTreeNode(*be_copied)); work_stack.push(make_tuple(be_copied, find_next(be_copied, 0), 1)); be_copied be_copied-branch_ptr.sub_ptr[get1(work_stack.top())]; } else { copy_trace_stack.top()-branch_ptr.sub_ptr[get1(work_stack.top())] new TrieTreeNode(*be_copied); be_copied get0(work_stack.top()); trace_back_flag false; } } else { if (be_copied-branch_ptr.num ! get2(work_stack.top())) { get1(work_stack.top()) find_next(be_copied, get1(work_stack.top()) 1); get2(work_stack.top()); be_copied be_copied-branch_ptr.sub_ptr[get1(work_stack.top())]; trace_back_flag true; } else { if (be_copied root) break; work_stack.pop(); be_copied get0(work_stack.top()); copy_trace_stack.pop(); } } } return root_of_copy; } void TrieTree::printTrieTree(TrieTreeNode* cur, size_t offset) const { if (cur-type_flag TrieTreeNode::BRANCHNODE) { size_t max_length; if (cur-branch_ptr.sub_ptr[0] ! nullptr) max_length 4; else max_length 1; int count 0; for (size_t run 0; ; run) { if (cur-branch_ptr.sub_ptr[run] ! nullptr) { count; for (size_t go 1; go offset; go) cout ; if (run 0) cout NULL; else { cout static_castchar(run); for (size_t go 2; go max_length; go) cout ; } cout |- endl; printTrieTree(cur-branch_ptr.sub_ptr[run], offset max_length 2); if (count cur-branch_ptr.num) break; } } } else { for (size_t go 1; go offset; go) cout ; cout leaf: cur-key_in_trie endl; } } int main() { vectorstring test { bluebird, bunting, bobwhite, bluejay }; TrieTree test_obj; for (vectorstring::iterator p test.begin(); p ! test.end(); p) { cout 插入字符串 *p endl; if (test_obj.insert(*p)) { cout 插入成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 插入失敗 endl; exit(0); } } cout endl; // TrieTreeNode *copy test_ptr.copy(); //for (vectorstring::iterator p test.begin(); p ! test.end(); p) { cout 刪除字符串 bobwhite endl; if (test_obj.deleteElem(bobwhite)) { cout 刪除成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 刪除失敗 endl; exit(0); } cout 刪除字符串 bluejay endl; if (test_obj.deleteElem(bluejay)) { cout 刪除成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 刪除失敗 endl; exit(0); } } cout endl; string mod abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789; const int L 9; // 隨機(jī)字符串最大長(zhǎng)度 const int r 2; //相同長(zhǎng)度重復(fù)次數(shù) vectorint LList(L); vectorstring random_str; for (int run 0; run LList.size(); run) LList[run] run 1; shuffle(LList.begin(), LList.end(), default_random_engine()); for (int re 1; re r; re) { for (int run 0; run LList.size(); run) { string r; for (int go 1; go LList[run]; go) { r.append(1, mod[rand() % mod.size()]); } random_str.push_back(r); } } for (vectorstring::iterator p random_str.begin(); p ! random_str.end(); p) { cout 插入字符串 *p endl; if (test_obj.insert(*p)) { cout 插入成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 插入失敗 endl; exit(0); } } cout endl; // TrieTreeNode *copy test_ptr.copy(); for (vectorstring::iterator p random_str.begin(); p ! random_str.end(); p) { cout 刪除字符串 *p endl; if (test_obj.deleteElem(*p)) { cout 刪除成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 刪除失敗 endl; exit(0); } } cout endl; random_str.clear(); for (int i 1; i 7; i) { string temp(mod, 0, i); for (int run 1; run 7; run) { string r; for (int go 1; go run; go) { r.append(1, mod[rand() % mod.size()]); } random_str.push_back(temp r); } } cout 測(cè)試字符串有共同前綴不相等情形 endl; for (vectorstring::iterator p random_str.begin(); p ! random_str.end(); p) { cout 插入字符串 *p endl; if (test_obj.insert(*p)) { cout 插入成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 插入失敗 endl; exit(0); } } cout endl; // TrieTreeNode *copy test_ptr.copy(); for (vectorstring::iterator p random_str.begin(); p ! random_str.end(); p) { cout 刪除字符串 *p endl; if (test_obj.deleteElem(*p)) { cout 刪除成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 刪除失敗 endl; exit(0); } } cout endl; shuffle(mod.begin(), mod.end(), default_random_engine()); for (string::size_type i 1; i mod.size(); i) { string temp(mod, 0, i); cout 插入字符串 mod 的前綴 temp endl; if (test_obj.insert(temp)) { cout 插入成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 插入失敗 endl; exit(0); } } for (string::size_type i 1; i mod.size(); i) { string temp(mod, 0, i); cout 刪除字符串 mod 的前綴 temp endl; if (test_obj.deleteElem(temp)) { cout 刪除成功 endl; cout 當(dāng)前Trie為: endl test_obj endl; TrieTree copy(test_obj); cout 當(dāng)前Trie的副本為: endl copy endl; } else { cout 刪除失敗 endl; exit(0); } } return 0; }每種實(shí)現(xiàn)應(yīng)該都能適用于空串的插入刪除自己沒有驗(yàn)證過感興趣可自行驗(yàn)證