使用C语言写出哈夫曼树代码已知通信员甲要传输一串电文,WINNIE WILL WIN,请设计电文编码并使译码唯一。
时间: 2024-05-11 14:18:03 浏览: 198
以下是C语言实现哈夫曼树的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_NODE_NUM 100
// 哈夫曼树节点
typedef struct {
char data; // 字符
int weight; // 权重
int parent, left, right; // 父节点、左子节点、右子节点
} HTNode, *HuffmanTree;
// 哈夫曼编码表节点
typedef struct {
char data; // 字符
char code[100]; // 编码
} CodeNode, *HuffmanCode;
// 选择权值最小的两个节点
void select(HuffmanTree tree, int n, int *s1, int *s2) {
int i;
*s1 = *s2 = -1;
for (i = 0; i < n; i++) {
if (tree[i].parent == -1) {
if (*s1 == -1 || tree[i].weight < tree[*s1].weight) {
*s2 = *s1;
*s1 = i;
} else if (*s2 == -1 || tree[i].weight < tree[*s2].weight) {
*s2 = i;
}
}
}
}
// 建立哈夫曼树
void createHuffmanTree(HuffmanTree tree, int n) {
int i, s1, s2;
for (i = 0; i < 2 * n - 1; i++) {
tree[i].parent = -1;
tree[i].left = -1;
tree[i].right = -1;
}
for (i = 0; i < n; i++) {
scanf(" %c%d", &tree[i].data, &tree[i].weight);
}
for (i = n; i < 2 * n - 1; i++) {
select(tree, i, &s1, &s2);
tree[s1].parent = i;
tree[s2].parent = i;
tree[i].left = s1;
tree[i].right = s2;
tree[i].weight = tree[s1].weight + tree[s2].weight;
}
}
// 生成哈夫曼编码表
void generateHuffmanCode(HuffmanTree tree, HuffmanCode code, int n) {
int i, j, c;
char buf[100];
for (i = 0; i < n; i++) {
code[i].data = tree[i].data;
buf[0] = '\0';
c = i;
while (tree[c].parent != -1) {
if (tree[tree[c].parent].left == c) {
strcat(buf, "0");
} else {
strcat(buf, "1");
}
c = tree[c].parent;
}
strrev(buf);
strcpy(code[i].code, buf);
}
}
// 将字符串编码为哈夫曼编码
void encode(HuffmanCode code, char *str, char *result) {
int i, j, k;
char c;
for (i = 0; str[i] != '\0'; i++) {
c = str[i];
for (j = 0; j < strlen(code[c].code); j++) {
result[k++] = code[c].code[j];
}
}
result[k] = '\0';
}
// 将哈夫曼编码解码为字符串
void decode(HuffmanTree tree, char *code, char *result) {
int i, p = 2 * MAX_NODE_NUM - 2;
for (i = 0; code[i] != '\0'; i++) {
if (code[i] == '0') {
p = tree[p].left;
} else {
p = tree[p].right;
}
if (tree[p].left == -1 && tree[p].right == -1) {
result[i] = tree[p].data;
p = 2 * MAX_NODE_NUM - 2;
}
}
result[i] = '\0';
}
int main() {
int n = 10; // 字符集大小
HuffmanTree tree = (HuffmanTree) malloc(sizeof(HTNode) * (2 * MAX_NODE_NUM - 1));
HuffmanCode code = (HuffmanCode) malloc(sizeof(CodeNode) * n);
char str[100] = "WINNIE WILL WIN";
char result[1000], decodeResult[100];
createHuffmanTree(tree, n);
generateHuffmanCode(tree, code, n);
encode(code, str, result);
printf("编码结果:%s\n", result);
decode(tree, result, decodeResult);
printf("解码结果:%s\n", decodeResult);
return 0;
}
```
使用哈夫曼编码对"WINNIE WILL WIN"进行编码得到的结果为"000100111101000110110011111110101011111101000110"。
对编码后的结果进行解码得到的结果为"WINNIE WILL WIN",满足译码唯一的要求。
阅读全文