哈夫曼树统计每个字符出现的次数
时间: 2023-12-19 13:07:12 浏览: 51
可以使用哈希表来统计每个字符出现的次数。遍历字符串,将每个字符作为键,出现次数作为值存入哈希表中。然后使用哈希表中的数据来构建哈夫曼树。
以下是Python代码示例:
```python
from collections import defaultdict
def count_chars(s):
counts = defaultdict(int)
for c in s:
counts[c] += 1
return counts
s = "hello world"
char_counts = count_chars(s)
print(char_counts) # {'h': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 1, 'w': 1, 'r': 1, 'd': 1}
```
此示例使用了Python中的`defaultdict`来自动为不存在的键设置默认值0,避免了手动检查键是否存在的麻烦。
相关问题
c++哈夫曼树统计每个字符出现的次数
哈夫曼树是一种用于压缩数据的算法,它可以将出现频率较高的字符编码为较短的二进制串,从而减小数据的存储空间。在构建哈夫曼树之前,需要统计每个字符出现的次数。以下是一种基于数组的实现方式:
```c
#include <stdio.h>
int main() {
int freq[256] = {0}; // 初始化字符频率数组为0
char str[100]; // 假设字符串长度不超过100
printf("请输入字符串:");
scanf("%s", str);
// 统计每个字符出现的次数
for (int i = 0; str[i] != '\0'; i++) {
freq[str[i]]++;
}
// 输出每个字符出现的次数
for (int i = 0; i < 256; i++) {
if (freq[i] > 0) {
printf("字符 '%c' 出现了 %d 次\n", i, freq[i]);
}
}
return 0;
}
```
该程序先初始化一个长度为256的数组 `freq`,表示 ASCII 码表中的所有字符。然后读入一个字符串,并遍历字符串中的每个字符,将该字符对应的频率加1。最后再遍历一次数组,输出所有出现次数大于0的字符及其出现次数。
需要注意的是,该程序只考虑了 ASCII 码表中的字符,如果需要统计 Unicode 码表中的字符,需要使用更大的数组。
c++实现哈夫曼树统计每个字符出现的次数
下面是一种C语言实现哈夫曼树统计每个字符出现次数的简单方法:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node {
int freq;
char c;
struct node *left;
struct node *right;
};
int count[256];
void count_chars(const char *str) {
int i;
for (i = 0; i < 256; i++) {
count[i] = 0;
}
while (*str) {
count[(unsigned char)*str++]++;
}
}
struct node *new_node(int freq, char c) {
struct node *n = (struct node *)malloc(sizeof(struct node));
n->freq = freq;
n->c = c;
n->left = NULL;
n->right = NULL;
return n;
}
struct node *build_huffman_tree() {
struct node *nodes[256];
int i, j, n_nodes = 0;
for (i = 0; i < 256; i++) {
if (count[i] > 0) {
nodes[n_nodes++] = new_node(count[i], (char)i);
}
}
while (n_nodes > 1) {
int min1 = 0, min2 = 1;
if (nodes[min1]->freq > nodes[min2]->freq) {
min1 = 1;
min2 = 0;
}
for (i = 2; i < n_nodes; i++) {
if (nodes[i]->freq < nodes[min1]->freq) {
min2 = min1;
min1 = i;
} else if (nodes[i]->freq < nodes[min2]->freq) {
min2 = i;
}
}
struct node *new_node = (struct node *)malloc(sizeof(struct node));
new_node->freq = nodes[min1]->freq + nodes[min2]->freq;
new_node->c = '\0';
new_node->left = nodes[min1];
new_node->right = nodes[min2];
nodes[min1] = new_node;
nodes[min2] = nodes[--n_nodes];
}
return nodes[0];
}
void print_codes(struct node *root, int depth, char *code) {
if (root->left == NULL && root->right == NULL) {
printf("%c: %s\n", root->c, code);
} else {
code[depth] = '0';
print_codes(root->left, depth + 1, code);
code[depth] = '1';
print_codes(root->right, depth + 1, code);
}
}
int main() {
const char *str = "hello world";
count_chars(str);
struct node *root = build_huffman_tree();
char code[256];
memset(code, 0, sizeof(code));
print_codes(root, 0, code);
return 0;
}
```
这个程序首先定义了一个`count`数组来统计每个字符出现的次数,然后使用`build_huffman_tree`函数来构建哈夫曼树。构建哈夫曼树的过程中,我们首先将所有出现过的字符作为叶子节点,然后不断地合并权重最小的两个节点,直到只剩下一个根节点。最后,我们使用`print_codes`函数来输出每个字符的编码。这个函数使用了递归来遍历整个哈夫曼树,并维护一个`code`数组来记录当前节点的编码。当遍历到叶子节点时,我们输出该节点对应的字符和编码。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)