程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 萌新筆記——C++裡創立 Trie字典樹(中文詞典)(一)(拔出、遍歷)

萌新筆記——C++裡創立 Trie字典樹(中文詞典)(一)(拔出、遍歷)

編輯:關於C++

萌新筆記——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

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved