标准trie应用之文本词频统计

缘起

题目:

读取一篇全是英文小写字母构成的单词的文章，要你按字典序输出所有单词以及此单词出现的次数.

分析

算法很简单，和【1】类似. 只是这里除了输出单词之外，还需要输出频次. 所以trie树节点这个数据结构还需要多一个域（下面的cnt域）就是次数统计.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#define LOCAL


const int SIZE = 26;

typedef struct TrieNode
{
	int ch,cnt; // 如果end是true的话, cnt就是此单词出现的频次
	bool end;
	TrieNode *next[SIZE];
	TrieNode(int ch=0):ch(ch),cnt(0),end(false) {memset(next, 0, sizeof(next));}
}TrieNode,*Trie;

void init(Trie &root) {root = new TrieNode;}

void insert(Trie root, char *key)
{
	Trie p = root;
	int i = 0;
	while(key[i])
	{
		if (!p->next[key[i]-'a']) p->next[key[i]-'a'] = new TrieNode(key[i]);
		p = p->next[key[i++]-'a'];
	}
	p->end =  true;
	p->cnt++; // 出现频次+1
}

void print(Trie current, char *text, int n) // 先序遍历trie, current是当前节点, text是当前已经积攒的要打印的字符, n是当前已经积攒的字符串长度
{
	if (current->ch) text[n] = current->ch; // 只有当前字符存在的时候(根节点就不行),才加入
	if (current->end) // 如果当前节点是一个字符串的结束, 则就要打印了
	{
		text[n+1] = 0;
		printf("%s 出现了 %d次\n",text, current->cnt);
	}
	for (int i = 0;i<SIZE; i++)
	{
		if (current->next[i])
		{
			print(current->next[i], text, n+1); // 遍历其子节点
		}
	}
}

void del(Trie &root)
{
	if (!root) return;
	for (int i = 0; i<SIZE; i++)del(root->next[i]);
	delete root;
	root = 0;
}


int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	Trie root = 0;
	init(root);
	char key[15];
	while(~scanf("%s", key)) insert(root, key);
	print(root, key, -1); // 之所以是-1. 是因为-1对应根节点, 根节点一定不会奏效(因为它的ch是0)
	del(root);
	return 0;
}
/*
测试数据
i am mike mike is also my father father like mother
i like chicken egg mike also like egg father and 
mother like dog cat hate dog
*/

参考

【1】https://yfsyfs.github.io/2019/07/21/%E6%A0%87%E5%87%86trie%E6%A0%91%E5%BA%94%E7%94%A8%E4%B9%8B%E4%B8%B2%E6%8E%92%E5%BA%8F/