萌新筆記——C++裡創立 Trie字典樹(中文詞典)(一)(拔出、遍歷)。本站提示廣大學習愛好者:(萌新筆記——C++裡創立 Trie字典樹(中文詞典)(一)(拔出、遍歷))文章只能為提供參考,不一定能成為您想要的結果。以下是萌新筆記——C++裡創立 Trie字典樹(中文詞典)(一)(拔出、遍歷)正文
萌新做詞典第一篇,做得不好,還請指正,謝謝大佬!
寫了一個詞典,用到了Trie字典樹。
寫這個詞典的目的,一個是為了緊縮一些數據,另一個是為了嘗試搜索提示,好像在谷歌搜索的時分,打出某個關鍵字,會提示一串能夠要搜索的東西。
首先放上最終的後果:
input:
1 編程入門 2 編程軟件 3 編程學習 4 編程學習網站
output:
1 char : 件 2 word : 編程軟件 3 char : 習 4 word : 編程學習 5 char : 網 6 word : 編程學習網 7 char : 門 8 word : 編程入門
其實這裡不應該用input,由於全是直接寫死在main中停止測試的--!
關於這個output,char表示此時指向的字,word表示從根到指向的字的途徑遍歷(原諒菜鳥的我想不到恰當的詞)。
“編程”兩字因沒有輸出,故不會當做一個詞,假如不這樣設定,“編”也會被當作一個詞打出來的。
然後來說說做這個的進程吧。
首先,我選擇struct與unordered_map結合才表示樹,詳細代碼如下:
1 #ifndef __DICTIONARYDATA_H__ 2 #define __DICTIONARYDATA_H__ 3 4 #include <string> 5 #include <unordered_map> 6 #include <memory> 7 8 namespace ccx{ 9 10 using std::string; 11 using std::unordered_map; 12 using std::shared_ptr; 13 14 struct DictElem 15 { 16 string _word;//假如是根結點,則填ROOT 17 int _wordId;//假如是根結點,則為總詞數 18 unordered_map<string, shared_ptr<DictElem> > _words; 19 }; 20 21 typedef shared_ptr<DictElem> pDictElem; 22 23 } 24 25 #endif
這裡的typedef是為了前面書寫的方便而設的。
然後,是設計Dictionary類,使它具有添加一個詞、添加一組詞、遍歷一切詞的功用,當然我比擬菜暫時沒想怎樣刪除一個詞的事。以下是最初的Dictionary
Dictionary.h
1 #ifndef __DICTIONARY_H__ 2 #define __DICTIONARY_H__ 3 4 #include "DictionaryData.h" 5 6 #include <memory> 7 #include <vector> 8 #include <list> 9 10 namespace ccx{ 11 12 using std::shared_ptr; 13 using std::vector; 14 using std::list; 15 16 class Dictionary 17 { 18 typedef unordered_map<string, pDictElem>::iterator WordIt; 19 public: 20 Dictionary(); 21 void push(const string & word); 22 void push(vector<string> & words); 23 private: 24 void splitWord(const string & word, vector<string> & characters);//把詞拆成字 25 pDictElem _dictionary; 26 27 //遍歷 28 public: 29 void next(); 30 string getCurChar(); 31 string getCurWord(); 32 void resetPoint(); 33 bool isEnd(); 34 private: 35 void nextWord(); 36 pDictElem _pcur; 37 WordIt _itcur; 38 39 //用list完成棧,遍歷時方便 40 list<WordIt> _stackWord; 41 list<pDictElem> _stackDict; 42 }; 43 44 } 45 46 #endif
有了類構造,就可以去完成它了。結構函數做了一個初始化的任務:
1 Dictionary::Dictionary() 2 : _dictionary(new DictElem) 3 { 4 _dictionary->_wordId = 0; 5 _pcur = _dictionary; 6 }
首先,要把一個string分解成單個的字。在做這個的時分,一開端是天真地以為中國就是占兩個字節(gbk編碼),總是呈現迷之亂碼。後來是發現我用的是utf-8編碼,才處理了問題(上一篇就是講這個)。完成代碼如下:
1 void Dictionary::splitWord(const string & word, vector<string> & characters) 2 { 3 int num = word.size(); 4 int i = 0; 5 while(i < num) 6 { 7 int size = 1; 8 if(word[i] & 0x80) 9 { 10 char temp = word[i]; 11 temp <<= 1; 12 do{ 13 temp <<= 1; 14 ++size; 15 }while(temp & 0x80); 16 } 17 string subWord; 18 subWord = word.substr(i, size); 19 characters.push_back(subWord); 20 i += size; 21 } 22 }
失掉了單個字的集合,並存在vector中,就可以生成Trie字典數了。拔出一個詞的代碼如下:
1 void Dictionary::push(const string & word) 2 { 3 vector<string> characters; 4 splitWord(word, characters); 5 6 vector<string>::iterator it_char; 7 it_char = characters.begin(); 8 pDictElem root; 9 root = _dictionary; 10 for(; it_char != characters.end(); ++it_char) 11 { 12 WordIt it_word; 13 it_word = root->_words.find(*it_char); 14 15 if(it_word == root->_words.end()) 16 { 17 pair<string, pDictElem> temp; 18 temp.first = *it_char; 19 pDictElem dictemp(new DictElem); 20 dictemp->_word = *it_char; 21 dictemp->_wordId = 0; 22 temp.second = dictemp; 23 root->_words.insert(temp); 24 root = dictemp; 25 }else{ 26 root = it_word->second; 27 } 28 } 29 if(!root->_wordId) 30 { 31 ++(_dictionary->_wordId); 32 root->_wordId = _dictionary->_wordId; 33 } 34 }
這裡有用到的wordId,其實是給拔出的詞停止編號。在遍歷的時分,假如發現編號是0,則闡明並沒有拔出這個詞,可以跳過。
然後是拔出一組詞的代碼:
1 void Dictionary::push(vector<string> & words) 2 { 3 int size = words.size(); 4 for(int i = 0; i < size; ++i) 5 { 6 push(words[i]); 7 } 8 }
直接復用了拔出一個詞的代碼,復雜粗犷。
接著是寫遍歷。想到二叉樹的遍歷既可以用遞歸,又可以用棧來完成,由於遞歸要發生額定的開支,我就采用了棧的辦法。但是,要把迭代器入棧呢,還是把智能指針入棧的問題又卡著了。由於我這裡是專門寫了一個next函數,遍歷不是在一個函數裡“一條龍”一樣地完成,於是會有以下兩個能夠的問題(對本萌新來說):
1、只要智能指針入棧,可以輕松打出一個詞,但是怎樣讓它知道下一個應該指向誰?
2、假如只要迭代器入棧,又要怎樣知道什麼時分應該出棧(end)?關於這個問題有一個處理方案,就是每次處置的時分先出棧,然後再用此時的棧頂元素(它的父節點)來停止判別。不過覺得這樣太費事了,於是沒有這樣做。
於是選擇了兩個都入棧的處置辦法,結合運用,智能指針棧的棧頂元素永遠是迭代器棧的父節點,並且關於root結點,迭代器棧中不存。從而有了以下代碼:
1 void Dictionary::nextWord() 2 { 3 if(_pcur) 4 { 5 if(_pcur->_words.size()) 6 { 7 _stackDict.push_back(_pcur); 8 _stackWord.push_back(_pcur->_words.begin()); 9 _pcur = _stackWord.back()->second; 10 }else{ 11 ++(_stackWord.back()); 12 } 13 while(_stackWord.back() == _stackDict.back()->_words.end()) 14 { 15 _stackDict.pop_back(); 16 _stackWord.pop_back(); 17 if(!_stackDict.size()) 18 { 19 _pcur = NULL; 20 } 21 ++(_stackWord.back()); 22 } 23 if(_pcur) 24 { 25 _pcur = _stackWord.back()->second; 26 } 27 } 28 }
1 void Dictionary::next() 2 { 3 while(_pcur) 4 { 5 nextWord(); 6 if(!_pcur || _pcur->_wordId) 7 { 8 break; 9 } 10 } 11 }
這個next()是後來加的,由於發現假如不加這個,會把並沒有輸出的詞也打出來,比方最開端的例子“編程軟件”,會輸入四個詞:”編“、”編程“、”編程軟“、”編程軟件“,這並不是我想要後果,於是加了這麼一個判別,跳過一切未輸出的詞。
當然,還要一個初始化的函數:
1 void Dictionary::resetPoint() 2 { 3 _pcur = _dictionary; 4 if(_stackDict.size()) 5 { 6 _stackDict.clear(); 7 } 8 if(_stackWord.size()) 9 { 10 _stackWord.clear(); 11 } 12 next(); 13 }
和判別能否讀取終了的函數:
1 bool Dictionary::isEnd() 2 { 3 return _pcur == NULL; 4 }
最後,就是獲取一個詞的函數了:
1 string Dictionary::getCurWord() 2 { 3 string temp; 4 list<WordIt>::iterator it_word; 5 it_word = _stackWord.begin(); 6 7 for(; it_word != _stackWord.end(); ++it_word) 8 { 9 temp += (*it_word)->first; 10 } 11 return temp; 12 }
並且額定寫了一個用於測試的,取得以後節點存的什麼字的函數
1 string Dictionary::getCurChar() 2 { 3 return _pcur->_word; 4 }
完成完了一切函數,就開端停止測試了。我專門寫了一個test.cc來運用這個類:
1 #include "Dictionary.h" 2 #include <iostream> 3 #include <string> 4 #include <vector> 5 using std::cout; 6 using std::endl; 7 using std::string; 8 using std::vector; 9 10 int main() 11 { 12 ccx::Dictionary words; 13 string word1 = "編程入門"; 14 string word2 = "編程軟件"; 15 string word3 = "編程學習"; 16 string word4 = "編程學習網站"; 17 18 words.push(word1); 19 words.push(word2); 20 words.push(word3); 21 words.push(word4); 22 23 words.resetPoint(); 24 25 while(!words.isEnd()) 26 { 27 cout << "char : " << words.getCurChar() << endl; 28 cout << "word : " << words.getCurWord() << endl; 29 words.next(); 30 } 31 }
測試後果就在掃尾局部。於是,一個復雜的可以拔出與遍歷的詞典就做好了。後來又想應該給它添加查找、導入與導出的功用,想想干脆再開一篇好了。
0。0 覺得辦法好low啊~~~~
Dictionary.cc
1 #include "Dictionary.h" 2 #include <iostream> 3 #include <string> 4 5 namespace ccx{ 6 7 using std::endl; 8 using std::cout; 9 using std::pair; 10 11 Dictionary::Dictionary() 12 : _dictionary(new DictElem) 13 { 14 _dictionary->_wordId = 0; 15 _pcur = _dictionary; 16 } 17 18 void Dictionary::splitWord(const string & word, vector<string> & characters) 19 { 20 int num = word.size(); 21 int i = 0; 22 while(i < num) 23 { 24 int size = 1; 25 if(word[i] & 0x80) 26 { 27 char temp = word[i]; 28 temp <<= 1; 29 do{ 30 temp <<= 1; 31 ++size; 32 }while(temp & 0x80); 33 } 34 string subWord; 35 subWord = word.substr(i, size); 36 characters.push_back(subWord); 37 i += size; 38 } 39 } 40 41 void Dictionary::push(const string & word) 42 { 43 vector<string> characters; 44 splitWord(word, characters); 45 46 vector<string>::iterator it_char; 47 it_char = characters.begin(); 48 pDictElem root; 49 root = _dictionary; 50 for(; it_char != characters.end(); ++it_char) 51 { 52 WordIt it_word; 53 it_word = root->_words.find(*it_char); 54 55 if(it_word == root->_words.end()) 56 { 57 pair<string, pDictElem> temp; 58 temp.first = *it_char; 59 pDictElem dictemp(new DictElem); 60 dictemp->_word = *it_char; 61 dictemp->_wordId = 0; 62 temp.second = dictemp; 63 root->_words.insert(temp); 64 root = dictemp; 65 }else{ 66 root = it_word->second; 67 } 68 } 69 if(!root->_wordId) 70 { 71 ++(_dictionary->_wordId); 72 root->_wordId = _dictionary->_wordId; 73 } 74 } 75 76 void Dictionary::push(vector<string> & words) 77 { 78 int size = words.size(); 79 for(int i = 0; i < size; ++i) 80 { 81 push(words[i]); 82 } 83 } 84 85 //遍歷用 86 87 void Dictionary::resetPoint() 88 { 89 _pcur = _dictionary; 90 if(_stackDict.size()) 91 { 92 _stackDict.clear(); 93 } 94 if(_stackWord.size()) 95 { 96 _stackWord.clear(); 97 } 98 next(); 99 } 100 101 void Dictionary::next() 102 { 103 while(_pcur) 104 { 105 nextWord(); 106 if(!_pcur || _pcur->_wordId) 107 { 108 break; 109 } 110 } 111 } 112 113 void Dictionary::nextWord() 114 { 115 if(_pcur) 116 { 117 if(_pcur->_words.size()) 118 { 119 _stackDict.push_back(_pcur); 120 _stackWord.push_back(_pcur->_words.begin()); 121 _pcur = _stackWord.back()->second; 122 }else{ 123 ++(_stackWord.back()); 124 } 125 while(_stackWord.back() == _stackDict.back()->_words.end()) 126 { 127 _stackDict.pop_back(); 128 _stackWord.pop_back(); 129 if(!_stackDict.size()) 130 { 131 _pcur = NULL; 132 } 133 ++(_stackWord.back()); 134 } 135 if(_pcur) 136 { 137 _pcur = _stackWord.back()->second; 138 } 139 } 140 } 141 142 string Dictionary::getCurChar() 143 { 144 return _pcur->_word; 145 } 146 147 string Dictionary::getCurWord() 148 { 149 string temp; 150 list<WordIt>::iterator it_word; 151 it_word = _stackWord.begin(); 152 153 for(; it_word != _stackWord.end(); ++it_word) 154 { 155 temp += (*it_word)->first; 156 } 157 return temp; 158 } 159 160 bool Dictionary::isEnd() 161 { 162 return _pcur == NULL; 163 } 164 165 }View Code