哈夫曼树的构造及编码与解码c语言代码
时间: 2023-11-24 11:05:13 浏览: 62
哈夫曼树的构造及编码与解码的C语言代码如下:
1. 哈夫曼树的构造
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct HuffmanNode {
char data; // 数据
int weight; // 权值
struct HuffmanNode *leftChild, *rightChild; // 左孩子和右孩子结点
} HuffmanNode, *HuffmanTree;
// 创建新结点
HuffmanNode *createHuffmanNode(char data, int weight) {
HuffmanNode *node = (HuffmanNode*) malloc(sizeof(HuffmanNode));
node->data = data;
node->weight = weight;
node->leftChild = NULL;
node->rightChild = NULL;
return node;
}
// 构造哈夫曼树
HuffmanTree createHuffmanTree(char *data, int *weight, int n) {
HuffmanNode **nodes = (HuffmanNode**) malloc(n * sizeof(HuffmanNode*));
for (int i = 0; i < n; i++) {
nodes[i] = createHuffmanNode(data[i], weight[i]);
}
while (n > 1) {
int min1 = 0, min2 = 1; // 找到权值最小和次小的两个结点
if (nodes[min1]->weight > nodes[min2]->weight) {
int tmp = min1;
min1 = min2;
min2 = tmp;
}
for (int i = 2; i < n; i++) {
if (nodes[i]->weight < nodes[min1]->weight) {
min2 = min1;
min1 = i;
} else if (nodes[i]->weight < nodes[min2]->weight) {
min2 = i;
}
}
HuffmanNode *newNode = createHuffmanNode(0, nodes[min1]->weight + nodes[min2]->weight);
newNode->leftChild = nodes[min1];
newNode->rightChild = nodes[min2];
if (min1 < min2) {
nodes[min1] = newNode;
nodes[min2] = nodes[n - 1];
} else {
nodes[min2] = newNode;
nodes[min1] = nodes[n - 1];
}
n--;
}
return nodes[0];
}
// 测试
int main() {
char data[] = {'A', 'B', 'C', 'D', 'E'};
int weight[] = {5, 1, 2, 4, 3};
HuffmanTree tree = createHuffmanTree(data, weight, 5);
return 0;
}
```
2. 哈夫曼编码
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct HuffmanNode {
char data; // 数据
int weight; // 权值
struct HuffmanNode *leftChild, *rightChild; // 左孩子和右孩子结点
} HuffmanNode, *HuffmanTree;
typedef struct HuffmanCode {
char data; // 数据
char *code; // 编码
} HuffmanCode;
// 创建新结点
HuffmanNode *createHuffmanNode(char data, int weight) {
HuffmanNode *node = (HuffmanNode*) malloc(sizeof(HuffmanNode));
node->data = data;
node->weight = weight;
node->leftChild = NULL;
node->rightChild = NULL;
return node;
}
// 构造哈夫曼树
HuffmanTree createHuffmanTree(char *data, int *weight, int n) {
HuffmanNode **nodes = (HuffmanNode**) malloc(n * sizeof(HuffmanNode*));
for (int i = 0; i < n; i++) {
nodes[i] = createHuffmanNode(data[i], weight[i]);
}
while (n > 1) {
int min1 = 0, min2 = 1; // 找到权值最小和次小的两个结点
if (nodes[min1]->weight > nodes[min2]->weight) {
int tmp = min1;
min1 = min2;
min2 = tmp;
}
for (int i = 2; i < n; i++) {
if (nodes[i]->weight < nodes[min1]->weight) {
min2 = min1;
min1 = i;
} else if (nodes[i]->weight < nodes[min2]->weight) {
min2 = i;
}
}
HuffmanNode *newNode = createHuffmanNode(0, nodes[min1]->weight + nodes[min2]->weight);
newNode->leftChild = nodes[min1];
newNode->rightChild = nodes[min2];
if (min1 < min2) {
nodes[min1] = newNode;
nodes[min2] = nodes[n - 1];
} else {
nodes[min2] = newNode;
nodes[min1] = nodes[n - 1];
}
n--;
}
return nodes[0];
}
// 哈夫曼编码
void huffmanEncoding(HuffmanTree tree, char *prefix, int depth, HuffmanCode *codes, int *codeIndex) {
if (tree->leftChild == NULL && tree->rightChild == NULL) {
codes[*codeIndex].data = tree->data;
codes[*codeIndex].code = (char*) malloc((depth + 1) * sizeof(char));
strcpy(codes[*codeIndex].code, prefix);
(*codeIndex)++;
} else {
prefix[depth] = '0';
prefix[depth + 1] = '\0';
huffmanEncoding(tree->leftChild, prefix, depth + 1, codes, codeIndex);
prefix[depth] = '1';
prefix[depth + 1] = '\0';
huffmanEncoding(tree->rightChild, prefix, depth + 1, codes, codeIndex);
}
}
// 测试
int main() {
char data[] = {'A', 'B', 'C', 'D', 'E'};
int weight[] = {5, 1, 2, 4, 3};
HuffmanTree tree = createHuffmanTree(data, weight, 5);
char prefix[100];
prefix[0] = '\0';
HuffmanCode codes[5];
int codeIndex = 0;
huffmanEncoding(tree, prefix, 0, codes, &codeIndex);
for (int i = 0; i < codeIndex; i++) {
printf("%c: %s\n", codes[i].data, codes[i].code);
}
return 0;
}
```
3. 哈夫曼解码
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct HuffmanNode {
char data; // 数据
int weight; // 权值
struct HuffmanNode *leftChild, *rightChild; // 左孩子和右孩子结点
} HuffmanNode, *HuffmanTree;
// 创建新结点
HuffmanNode *createHuffmanNode(char data, int weight) {
HuffmanNode *node = (HuffmanNode*) malloc(sizeof(HuffmanNode));
node->data = data;
node->weight = weight;
node->leftChild = NULL;
node->rightChild = NULL;
return node;
}
// 构造哈夫曼树
HuffmanTree createHuffmanTree(char *data, int *weight, int n) {
HuffmanNode **nodes = (HuffmanNode**) malloc(n * sizeof(HuffmanNode*));
for (int i = 0; i < n; i++) {
nodes[i] = createHuffmanNode(data[i], weight[i]);
}
while (n > 1) {
int min1 = 0, min2 = 1; // 找到权值最小和次小的两个结点
if (nodes[min1]->weight > nodes[min2]->weight) {
int tmp = min1;
min1 = min2;
min2 = tmp;
}
for (int i = 2; i < n; i++) {
if (nodes[i]->weight < nodes[min1]->weight) {
min2 = min1;
min1 = i;
} else if (nodes[i]->weight < nodes[min2]->weight) {
min2 = i;
}
}
HuffmanNode *newNode = createHuffmanNode(0, nodes[min1]->weight + nodes[min2]->weight);
newNode->leftChild = nodes[min1];
newNode->rightChild = nodes[min2];
if (min1 < min2) {
nodes[min1] = newNode;
nodes[min2] = nodes[n - 1];
} else {
nodes[min2] = newNode;
nodes[min1] = nodes[n - 1];
}
n--;
}
return nodes[0];
}
// 哈夫曼解码
void huffmanDecoding(HuffmanTree tree, char *code) {
HuffmanNode *p = tree;
for (int i = 0; code[i] != '\0'; i++) {
if (code[i] == '0') {
p = p->leftChild;
} else {
p = p->rightChild;
}
if (p->leftChild == NULL && p->rightChild == NULL) {
putchar(p->data);
p = tree;
}
}
}
// 测试
int main() {
char data[] = {'A', 'B', 'C', 'D', 'E'};
int weight[] = {5, 1, 2, 4, 3};
HuffmanTree tree = createHuffmanTree(data, weight, 5);
char *code = "1011010111001101011110";
huffmanDecoding(tree, code);
return 0;
}
```