POJ2945(Find the Clones)--字典树，map

题意：给你n个规定长度的单词，问你其中出现了1次的单词，出现两次的单词...出现n次单词分别有多少个。

当然这题map也能过，但是这里介绍字典树的做法。

首相对于n个单词存入树中，当然建树过程中遇到一样的单词就把那个单词最后一个结点的计数++就行。否则为这个单词是第一次建立，计数为1。

count[i]数组用来存放出现i次的字符串出现的次数。

Travel函数用来递归统计每个单词，将不同出现次数的数字记录到arr数组中，最后打印count数组即可

  1 #include 
  2 #include <string>
  3 #include 
  4 #include 
  5 #include 
  6 #include 
  7 #include 
  8 #include 
  9 using namespace std;
 10 
 11 const int LetterCount = 26;//最大长度
 12 
 13 struct Node
 14 {
 15     Node* next[LetterCount];//结点的下一个指针
 16     int count;
 17     bool end;//标记是否为最后一个单词
 18     Node();
 19 };
 20 
 21 Node::Node()
 22 {
 23     for (int i = 0; i < LetterCount; i++)
 24     {
 25         next[i] = NULL;
 26     }
 27     count = 1;
 28     end = false;
 29 }
 30 
 31 class Trie
 32 {
 33 protected:
 34     Node* root;
 35     void GreateRoot();
 36     void Distroy(const Node* root);
 37     void Travel(Node* root, int* arr);
 38 public:
 39     Trie();
 40     ~Trie();
 41     int Insert(char* word);
 42     int Query(char* word);
 43     void Travel(int* arr, int n);
 44 };
 45 
 46 Trie::Trie()
 47 {
 48     root = NULL;
 49     GreateRoot();
 50 }
 51 
 52 Trie::~Trie()
 53 {
 54     Distroy(root);
 55 }
 56 
 57 void Trie::GreateRoot()
 58 {
 59     if (!root)//根结点为false
 60     {
 61         root = new Node();//建根
 62         for (int i = 0; i < LetterCount; i++)
 63         {
 64             root->next[i] = NULL;
 65         }
 66     }
 67 }
 68 
 69 void Trie::Distroy(const Node* root)
 70 {
 71     if (!root)
 72     {
 73         return;
 74     }
 75     for (int i = 0; i < LetterCount; i++)
 76     {
 77         if (root->next[i] != NULL)
 78         {
 79             Distroy(root->next[i]);
 80         }
 81     }
 82     delete[] root;
 83 }
 84 
 85 int Trie::Insert(char* word)
 86 {
 87     Node* p = root;//根结点为root
 88     int length = strlen(word);//计算长度
 89     for (int i = 0; i < length; i++)
 90     {
 91         int index = word[i] - 'A';
 92         if (!(p->next[index]))//当前没有那个字母
 93         {
 94             Node* q = new Node();
 95             q->end = false;
 96             for (int j = 0; j < LetterCount; j++)
 97             {
 98                 q->next[j] = NULL;
 99             }
100             p->next[index] = q;
101         }
102         p = p->next[index];
103     }
104     if (p->end)
105     {
106         p->count++;
107     }
108     else
109     {
110         p->end = true;
111         p->count = 1;
112     }
113     return p->count;
114 }
115 
116 int Trie::Query(char* word)
117 {
118     Node* p = root;
119     bool found = true;
120     int length = strlen(word);
121     for (int i = 0; i < length; i++)
122     {
123         int index = word[i] - 'A';
124         p = p->next[index];
125         if (!p)//p为false
126         {
127             found = false;//没找到
128             break;
129         }
130     }
131     if (!found || !p->end)//没找到或已经是结束标记
132     {
133         return 0;
134     }
135     return p->count;//否则返回计数
136 }
137 
138 void Trie::Travel(Node* root, int* arr)
139 {
140     if (!root)
141     {
142         return;
143     }
144     if (root->end)//表示为最后一个词
145     {
146         arr[root->count]++;
147         return;
148     }
149     for (int i = 0; i < LetterCount; i++)
150     {
151         Travel(root->next[i], arr);//递归计算
152     }
153 }
154 
155 void Trie::Travel(int* arr, int n)
156 {
157     for (int i = 0; i < n; i++)
158     {
159         arr[i] = 0;
160     }
161     Travel(root, arr);
162 }
163 
164 class FindTheClones
165 {
166 protected:
167     int n;
168     int* count;
169     Trie tree;
170 public:
171     FindTheClones(int n);
172     ~FindTheClones();
173     void Insert(char* word);
174     void Travel();
175     void Output() const;
176 };
177 
178 FindTheClones::FindTheClones(int n)
179 {
180     this->n = n;
181     count = new int[n + 1];
182     memset(count, 0, sizeof(int) * (n + 1));
183 }
184 
185 FindTheClones::~FindTheClones()
186 {
187     delete[] count;
188 }
189 
190 void FindTheClones::Insert(char* word)
191 {
192     tree.Insert(word);
193 }
194 
195 void FindTheClones::Travel()
196 {
197     tree.Travel(count, n + 1);
198 }
199 
200 void FindTheClones::Output() const
201 {
202     for (int i = 1; i < n + 1; i++)
203     {
204         printf("%d\n", count[i]);
205     }
206 }
207 
208 int main()
209 {
210     int n = 0, m = 0;
211     while (scanf("%d%d", &n, &m))
212     {
213         if (n <= 0)
214         {
215             break;
216         }
217         char str[32];
218         FindTheClones obj(n);
219         for (int i = 0; i < n; i++)
220         {
221             scanf("%s", str);
222             obj.Insert(str);
223         }
224         obj.Travel();
225         obj.Output();
226     }
227     return 0;
228 }
树形结构-字典树(Trie-Tree)poj数据结构字典树

相关

数据结构--栈（C语言实现）

数据结构----单链表升级版

数据结构/PTA-畅通工程之最低成本建设问题-畅通工程之局部最小花费问题/图/最小生成树

数据结构+java中常用的集合类

数据结构 之二叉树

数据结构与算法之PHP查找算法（哈希查找）

数据结构与算法之PHP查找算法（二分查找）

数据结构与算法之PHP排序算法（冒泡排序）

03java算法与数据结构------环形队列代码实现

Redis | 第一部分：数据结构与对象 上篇《Redis设计与实现》

poj 2301（水题）

数据结构 -- 004.1 串的基本概念

标签