哈夫曼树读取文件c语言代码
时间: 2023-10-16 20:11:40 浏览: 39
以下是一个简单的读取文件并构建哈夫曼树的 C 语言代码:
```
#include <stdio.h>
#include <stdlib.h>
struct node {
int freq;
char data;
struct node *left;
struct node *right;
};
struct node *new_node(int freq, char data) {
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->freq = freq;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
struct node *build_huffman_tree(FILE *fp) {
int freq[256] = {0};
char c;
// 统计每个字符的频率
while((c = fgetc(fp)) != EOF) {
freq[c]++;
}
// 创建叶子节点并插入优先队列
struct node *pq[256];
int pq_size = 0;
for(int i = 0; i < 256; i++) {
if(freq[i] > 0) {
pq[pq_size++] = new_node(freq[i], (char)i);
}
}
// 构建哈夫曼树
while(pq_size > 1) {
// 找到2个最小的节点
struct node *min1 = pq[0];
int min1_index = 0;
for(int i = 1; i < pq_size; i++) {
if(pq[i]->freq < min1->freq) {
min1 = pq[i];
min1_index = i;
}
}
struct node *min2 = NULL;
for(int i = 0; i < pq_size; i++) {
if(i != min1_index && (min2 == NULL || pq[i]->freq < min2->freq)) {
min2 = pq[i];
}
}
// 将它们合并成一个新节点
struct node *new = new_node(min1->freq + min2->freq, '\0');
new->left = min1;
new->right = min2;
// 将新节点插入优先队列
pq[min1_index] = new;
for(int i = min1_index+1; i < pq_size-1; i++) {
pq[i] = pq[i+1];
}
pq_size--;
}
return pq[0];
}
int main() {
FILE *fp = fopen("input.txt", "r");
struct node *root = build_huffman_tree(fp);
// TODO: 遍历哈夫曼树进行编码
fclose(fp);
return 0;
}
```
这个代码中的 `build_huffman_tree` 函数会读取指定文件中的每个字符,统计它们的频率,并构建哈夫曼树。在构建哈夫曼树的过程中,我们使用了一个优先队列来维护节点的顺序。最后的哈夫曼树根节点就是队列中唯一剩余的节点。
相关推荐
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)