初始化一个数据元素为数值型的序列,将其作为叶子结点构造哈夫曼树并对其进行编码。示例: 给定序列 5 29 7 8 14 23 3 11使用c语言表示
时间: 2024-02-23 10:02:27 浏览: 61
构造哈夫曼树,并生成编码
好的,下面是使用 C 语言表示初始化一个数据元素为数值型的序列、构造哈夫曼树并对其进行编码的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct {
int weight;
int parent, left, right;
} HTNode, *HuffmanTree;
typedef char *HuffmanCode[MAX_SIZE];
void HuffmanCoding(HuffmanTree *HT, HuffmanCode *HC, int *w, int n) {
int i, j, start, c, f;
HuffmanTree p;
char *cd;
int m = 2 * n - 1;
*HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));
*HC = (HuffmanCode)malloc((n + 1) * sizeof(char *));
for (i = 1; i <= n; i++) {
(*HT)[i].weight = w[i - 1];
(*HT)[i].parent = 0;
(*HT)[i].left = 0;
(*HT)[i].right = 0;
}
for (; i <= m; i++) {
(*HT)[i].weight = 0;
(*HT)[i].parent = 0;
(*HT)[i].left = 0;
(*HT)[i].right = 0;
}
for (i = n + 1; i <= m; i++) {
int s1 = 0, s2 = 0;
for (j = 1; j < i; j++) {
if ((*HT)[j].parent == 0) {
if ((*HT)[j].weight < (*HT)[s1].weight) {
s2 = s1;
s1 = j;
} else if ((*HT)[j].weight < (*HT)[s2].weight) {
s2 = j;
}
}
}
(*HT)[s1].parent = i;
(*HT)[s2].parent = i;
(*HT)[i].left = s1;
(*HT)[i].right = s2;
(*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
}
*HC = (HuffmanCode)malloc((n + 1) * sizeof(char *));
cd = (char *)malloc(n * sizeof(char));
cd[n - 1] = '\0';
for (i = 1; i <= n; i++) {
start = n - 1;
for (c = i, f = (*HT)[i].parent; f != 0; c = f, f = (*HT)[f].parent) {
if ((*HT)[f].left == c) {
cd[--start] = '0';
} else {
cd[--start] = '1';
}
}
(*HC)[i] = (char *)malloc((n - start) * sizeof(char));
strcpy((*HC)[i], &cd[start]);
}
free(cd);
}
int main() {
int w[] = {5, 29, 7, 8, 14, 23, 3, 11};
int n = sizeof(w) / sizeof(w[0]);
HuffmanTree HT;
HuffmanCode HC;
HuffmanCoding(&HT, &HC, w, n);
printf("Huffman codes:\n");
for (int i = 1; i <= n; i++) {
printf("%d: %s\n", w[i - 1], HC[i]);
}
return 0;
}
```
希望能够解答您的疑问。
阅读全文