字典树实现map容器
通过hdoj1075来演示如何通过字典树创建map容器
字典树的结构如下
其中，根结点上不存储数据，每个结点有唯一的字符串(key)标示，可在对应的结点中存储相应的值(value),比如ah结点上可以存储数据"I am handsome!"
那么，对应的map中一条为["ah" -> "I am handsome!"],字典树的数据结构中最多有MAX个子树，假如由26个英文字母组成的字典树，那么MAX就是26
#include <iostream>#include <string>#define MAX 26using namespace std;//字典树的数据结构struct Trie { Trie *next[MAX]; string v; Trie():v("") { for (int i = 0; i < MAX; ++i) { next[i] = NULL; } }};Trie *root = new Trie();//插入一条数据void createTrie(const string& value,const string& key) { int len = key.size(); Trie *p = root; for(int i = 0; i < len; ++i) { int id = key[i] - 'a'; if (p->next[id] == NULL) { p->next[id] = new Trie(); } p = p->next[id]; } p->v = value;}//查找数据const string& find(const string& key) { int len = key.size(); Trie *p = root; for(int i = 0; i < len; ++i) { int id = key[i] - 'a'; if (p->next[id] == NULL) return key; p = p->next[id]; } if (p->v == "") return key; else return p->v;}int main() { // freopen("1.in", "r", stdin); //建立字典树 string key, value, s, tmp; cin >> value; while (cin >> value && value != "END") { cin >> key; createTrie(value, key); } getchar(); getline(cin, tmp); while (getline(cin, tmp) && tmp != "END") { s += tmp + "\n"; } tmp = ""; for (int i = 0; i < s.length(); ++i) { if (s[i] > 'z' || s[i] < 'a') cout << s[i]; else tmp += s[i]; if (i == s.length() || (s[i+1] > 'z' || s[i+1] < 'a')) { cout << find(tmp); tmp = ""; } } return 0;}