寫了一個詞典，用到了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
