C语言实现哈夫曼编码
时间: 2023-11-24 15:50:22 浏览: 27
以下是C语言实现哈夫曼编码的基本步骤和代码示例:
1. 定义哈夫曼树的结构体
```c
struct HuffmanNode {
int weight; // 权重
int parent; // 父节点
int leftChild; // 左子节点
int rightChild; // 右子节点
};
```
2. 构建哈夫曼树
```c
void createHuffmanTree(struct HuffmanNode *huffmanTree, int n) {
int i, j, k;
int min1, min2;
for (i = 0; i < 2 * n - 1; i++) {
huffmanTree[i].weight = 0;
huffmanTree[i].parent = -1;
huffmanTree[i].leftChild = -1;
huffmanTree[i].rightChild = -1;
}
for (i = 0; i < n; i++) {
scanf("%d", &huffmanTree[i].weight);
}
for (i = 0; i < n - 1; i++) {
min1 = min2 = 99999;
k = 0;
for (j = 0; j < n + i; j++) {
if (huffmanTree[j].parent == -1 && huffmanTree[j].weight < min1) {
min2 = min1;
min1 = huffmanTree[j].weight;
k = j;
} else if (huffmanTree[j].parent == -1 && huffmanTree[j].weight < min2) {
min2 = huffmanTree[j].weight;
}
}
huffmanTree[k].parent = n + i; huffmanTree[n + i].weight = min1 + min2;
huffmanTree[n + i].leftChild = k;
huffmanTree[n + i].rightChild = j;
}
}
```
3. 生成哈夫曼编码
```c
void createHuffmanCode(struct HuffmanNode *huffmanTree, struct HuffmanCode *huffmanCode, int n) {
int i, j, c, p;
struct HuffmanCode hc;
for (i = 0; i < n; i++) {
hc.start = n - 1;
c = i;
p = huffmanTree[c].parent;
while (p != -1) {
if (huffmanTree[p].leftChild == c) {
hc.code[hc.start] = '0';
} else {
hc.code[hc.start] = '1';
}
hc.start--;
c = p;
p = huffmanTree[c].parent;
}
for (j = hc.start + 1; j < n; j++) {
huffmanCode[i].code[j] = hc.code[j];
}
huffmanCode[i].start = hc.start;
}
}
```
完整代码示例:
```c
#include <stdio.h>
#define MAX_N 100
struct HuffmanNode {
int weight; // 权重
int parent; // 父节点
int leftChild; // 左子节点
int rightChild; // 右子节点
};
struct HuffmanCode {
char code[MAX_N]; // 编码
int start; // 编码起始位置
};
void createHuffmanTree(struct HuffmanNode *huffmanTree, int n) {
int i, j, k;
int min1, min2;
for (i = 0; i < 2 * n - 1; i++) {
huffmanTree[i].weight = 0;
huffmanTree[i].parent = -1;
huffmanTree[i].leftChild = -1;
huffmanTree[i].rightChild = -1;
}
for (i = 0; i < n; i++) {
scanf("%d", &huffmanTree[i].weight);
}
for (i = 0; i < n - 1; i++) {
min1 = min2 = 99999;
k = 0;
for (j = 0; j < n + i; j++) {
if (huffmanTree[j].parent == -1 && huffmanTree[j].weight < min1) {
min2 = min1;
min1 = huffmanTree[j].weight;
k = j;
} else if (huffmanTree[j].parent == -1 && huffmanTree[j].weight < min2) {
min2 = huffmanTree[j].weight;
}
}
huffmanTree[k].parent = n + i;
huffmanTree[n + i].weight = min1 + min2;
huffmanTree[n + i].leftChild = k;
huffmanTree[n + i].rightChild = j;
}
}
void createHuffmanCode(struct HuffmanNode *huffmanTree, struct HuffmanCode *huffmanCode, int n) {
int i, j, c, p;
struct HuffmanCode hc;
for (i = 0; i < n; i++) {
hc.start = n - 1;
c = i;
p = huffmanTree[c].parent;
while (p != -1) {
if (huffmanTree[p].leftChild == c) {
hc.code[hc.start] = '0';
} else {
hc.code[hc.start] = '1';
}
hc.start--;
c = p;
p = huffmanTree[c].parent;
}
for (j = hc.start + 1; j < n; j++) {
huffmanCode[i].code[j] = hc.code[j];
}
huffmanCode[i].start = hc.start;
}
}
int main() {
int n, i, j;
struct HuffmanNode huffmanTree[MAX_N];
struct HuffmanCode huffmanCode[MAX_N];
printf("请输入叶子节点的个数:");
scanf("%d", &n);
printf("请输入每个叶子节点的权重:");
createHuffmanTree(huffmanTree, n);
createHuffmanCode(huffmanTree, huffmanCode, n);
printf("哈夫曼编码如下:\n");
for (i = 0; i < n; i++) {
printf("%d的哈夫曼编码为:", huffmanTree[i].weight);
for (j = huffmanCode[i].start + 1; j < n; j++) {
printf("%c", huffmanCode[i].code[j]);
}
printf("\n");
}
return 0;
}
```