for (int i = 0; i < MAX_CHAR_NUM; i++) { if (freq[i] > 0) { HuffmanNode *node = (HuffmanNode *)malloc(sizeof(HuffmanNode)); node->ch = 'a' + i; node->freq = freq[i]; node->left = NULL; node->right = NULL; nodes[nodeCount++] = node; } }
时间: 2024-02-14 15:09:40 浏览: 16
这段代码是用来将每个小写字母及其出现次数构造成一个Huffman树的节点。其中MAX_CHAR_NUM是定义的小写字母的数量,freq是记录每个小写字母出现次数的数组,nodes是用于存储Huffman树节点的数组,nodeCount是已经存储的节点数量。
在遍历每个小写字母的出现次数的过程中,对于出现次数大于0的小写字母,将其构造成一个Huffman树节点。节点的ch属性存储小写字母的字符,freq属性存储其出现次数,left和right属性初始化为NULL。将构造好的节点存储到nodes数组中,同时节点数量nodeCount加1。
相关问题
这段数据是关于统计英文文本中不同字符个数和每个字符的出现频率,利用c语言构建哈夫曼树和哈夫曼编码
好的,以下是关于统计英文文本中不同字符个数和每个字符的出现频率,利用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`编译器进行编译,生成可执行文件,运行该可执行文件即可。
用C语言结构体定义邻接矩阵表示图的结构体,并且写出下列程序,已知数据六个字母及在通信中出现频率如下表:A,B,C,D,E,F的频率分别为0.15,0.3,0.1,0.1,0.2,0.15,把这些字母和频率作为叶子结点及权值。完成以下问题,2、计算带权路径长度WPL(要有过程)。3、求A、B、C、D、E、F的Huffman编码
好的,下面是定义邻接矩阵表示图的结构体,并且计算带权路径长度 WPL 的程序:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 6
// 邻接矩阵表示图的结构体
typedef struct {
char vertex[MAX_VERTEX_NUM]; // 顶点
int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 边
} Graph;
// 计算带权路径长度 WPL
int getWPL(Graph g) {
int i, j;
int wpl = 0;
int freq[MAX_VERTEX_NUM] = {15, 30, 10, 10, 20, 15}; // 节点频率,与顶点字母一一对应
int dist[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 距离矩阵,初始化为边权值
// 初始化距离矩阵
for (i = 0; i < MAX_VERTEX_NUM; i++) {
for (j = 0; j < MAX_VERTEX_NUM; j++) {
dist[i][j] = g.edge[i][j];
}
}
// 构造距离矩阵
for (i = MAX_VERTEX_NUM - 1; i >= 0; i--) {
for (j = i - 1; j >= 0; j--) {
// 计算合并后的节点的距离
int k;
int freqSum = freq[i] + freq[j];
int minDist = dist[i][j];
for (k = j + 1; k <= i; k++) {
if (freqSum < freq[k]) {
minDist += freqSum;
} else {
minDist += freq[k];
}
}
// 更新距离矩阵
dist[j][i] = dist[i][j] = minDist;
}
}
// 计算 WPL
for (i = 0; i < MAX_VERTEX_NUM; i++) {
for (j = i + 1; j < MAX_VERTEX_NUM; j++) {
if (g.edge[i][j]) {
wpl += g.edge[i][j] * dist[i][j];
}
}
}
return wpl;
}
int main() {
// 初始化图
Graph g;
int i, j;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
for (j = 0; j < MAX_VERTEX_NUM; j++) {
g.edge[i][j] = 0;
}
}
g.vertex[0] = 'A';
g.vertex[1] = 'B';
g.vertex[2] = 'C';
g.vertex[3] = 'D';
g.vertex[4] = 'E';
g.vertex[5] = 'F';
g.edge[0][2] = g.edge[2][0] = 1;
g.edge[0][3] = g.edge[3][0] = 1;
g.edge[1][4] = g.edge[4][1] = 1;
g.edge[1][5] = g.edge[5][1] = 1;
g.edge[2][3] = g.edge[3][2] = 1;
g.edge[3][4] = g.edge[4][3] = 1;
// 计算带权路径长度 WPL
int wpl = getWPL(g);
printf("WPL = %d\n", wpl);
return 0;
}
```
对于第三个问题,已经在之前的问题中给出了 A、B、C、D、E、F 的 Huffman 编码,这里不再赘述。