这段数据是关于统计英文文本中不同字符个数和每个字符的出现频率,利用c语言构建哈夫曼树和哈夫曼编码
时间: 2023-06-25 17:06:19 浏览: 91
用哈夫曼编码统计一段英文中字母的频率
5星 · 资源好评率100%
好的,以下是关于统计英文文本中不同字符个数和每个字符的出现频率,利用c语言构建哈夫曼树和哈夫曼编码的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_CHAR_NUM 256
#define MAX_CODE_LEN 256
typedef struct huffman_node {
char ch; // 字符
int freq; // 频率
struct huffman_node *left; // 左子节点
struct huffman_node *right; // 右子节点
} HuffmanNode;
void count_char_freq(const char *str, int *char_freq) {
int len = strlen(str);
for (int i = 0; i < len; ++i) {
char_freq[(int)str[i]]++;
}
}
HuffmanNode *build_huffman_tree(int *char_freq) {
HuffmanNode *node_list[MAX_CHAR_NUM] = { NULL };
int node_list_len = 0;
for (int i = 0; i < MAX_CHAR_NUM; ++i) {
if (char_freq[i] > 0) {
HuffmanNode *node = (HuffmanNode *)malloc(sizeof(HuffmanNode));
node->ch = (char)i;
node->freq = char_freq[i];
node->left = NULL;
node->right = NULL;
node_list[node_list_len++] = node;
}
}
while (node_list_len > 1) {
int min_idx1 = 0, min_idx2 = 1;
if (node_list[min_idx1]->freq > node_list[min_idx2]->freq) {
min_idx1 = 1;
min_idx2 = 0;
}
for (int i = 2; i < node_list_len; ++i) {
if (node_list[i]->freq < node_list[min_idx1]->freq) {
min_idx2 = min_idx1;
min_idx1 = i;
} else if (node_list[i]->freq < node_list[min_idx2]->freq) {
min_idx2 = i;
}
}
HuffmanNode *new_node = (HuffmanNode *)malloc(sizeof(HuffmanNode));
new_node->ch = '\0';
new_node->freq = node_list[min_idx1]->freq + node_list[min_idx2]->freq;
new_node->left = node_list[min_idx1];
new_node->right = node_list[min_idx2];
node_list[min_idx1] = new_node;
node_list[min_idx2] = node_list[--node_list_len];
}
return node_list[0];
}
void traverse_huffman_tree(HuffmanNode *root, char *code, int code_len, char **code_table) {
if (root->left == NULL && root->right == NULL) {
code[code_len] = '\0';
code_table[(int)root->ch] = strdup(code);
return;
}
if (root->left != NULL) {
code[code_len] = '0';
traverse_huffman_tree(root->left, code, code_len + 1, code_table);
}
if (root->right != NULL) {
code[code_len] = '1';
traverse_huffman_tree(root->right, code, code_len + 1, code_table);
}
}
void print_huffman_codes(const char *str, char **code_table) {
int len = strlen(str);
printf("字符\t频率\t编码\n");
for (int i = 0; i < len; ++i) {
printf("%c\t%d\t%s\n", str[i], strlen(code_table[(int)str[i]]), code_table[(int)str[i]]);
}
}
int main() {
char str[MAX_CHAR_NUM];
printf("请输入字符串:");
fgets(str, MAX_CHAR_NUM, stdin);
int char_freq[MAX_CHAR_NUM] = { 0 };
count_char_freq(str, char_freq);
HuffmanNode *root = build_huffman_tree(char_freq);
char code[MAX_CODE_LEN];
char *code_table[MAX_CHAR_NUM] = { NULL };
traverse_huffman_tree(root, code, 0, code_table);
print_huffman_codes(str, code_table);
return 0;
}
```
你可以将上述代码保存为一个`.c`文件,然后使用`gcc`编译器进行编译,生成可执行文件,运行该可执行文件即可。
阅读全文