澳门新葡萄京官网首页萌新笔记——C++里创建 Trie字典树(中文词典)(插入、查找、遍历、导入、导出)(上),trie字典

帝国CMS有“顶”与“踩”的功能。

  萌新做字典第一篇,做得不佳,还请指正,谢谢大佬!

萌新笔记——C++里创立 Trie词典树(中文词典)(插入、查找、遍历、导入、导出)(上),trie辞书

  写了二个字典,用到了Trie辞典树。

  写这些辞典的指标,三个是为着减少一些多少,另二个是为了尝试寻觅提示,有如在谷歌(Google卡塔尔(قطر‎找出的时候,打出有个别关键字,会唤起一串只怕要探索的东西。

  首先放上最后的结果:

 

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

  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

 

Trie词典树(普通话词典)(插入、查找、遍历、导入、导出)(上),trie字典写了八个辞典,用到了Trie字典树。 写…

不过官方却从不实际的学科,引致于超级多朋友在增添 顶
代码时,点击未有弹出提醒,顶数也绝非增加,再点贰回却提醒“你早已顶过了”

  写了七个字典,用到了Trie辞书树。

那是因为未有进展以下第三步的原故:

  写那么些词典的目标,叁个是为着减小一些数额,另一个是为了尝试找出提示,犹如在谷歌(GoogleState of Qatar找寻的时候,打出有个别关键字,会唤起一串可能要物色的事物。

首先步:在模板里援用JS代码:

  首先放上最终的结果:

script type="text/javascript" src="[!---news.url--]skin/default/js/tabs.js"/scriptscript type="text/javascript" src="[!---news.url--]e/data/js/ajax.js"/script

 

其次步:加多顶的链接代码:

input:

a href="JavaScript:makeRequest('[!---news.url--]e/public/digg?classid=[!---classid--]amp;id=[!---id--]amp;dotop=1amp;doajax=1amp;ajaxarea=diggnum','EchoReturnedText','GET','');"赞一个/a
1 编程入门
2 编程软件
3 编程学习
4 编程学习网站

其三步:设置显示顶数量的DIV ID为diggnum

 

span script src=[!---news.url--]e/public/ViewClick/?classid=[!---classid--]id=[!---id--]down=5/script/div

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

澳门新葡萄京官网首页 2澳门新葡萄京官网首页 3

  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

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注