利用C语言编写一个完整代码。具体要求为:从键盘任意输入一个带空格由英文字母构成的文本字符串,例如“ilikelearningdatastructurecourse”,首先根据该字符串创建Huffman树,之后进行Huffman编码,然后把该字符串的Huffman编码结果向屏幕输出。能够利用前述的Huffman编码结果对某0-1码流进行解码得到字符串,并作出详细注释
时间: 2024-03-06 16:51:11 浏览: 106
C语言实现Huffman树,Huffman编码
5星 · 资源好评率100%
以下是完整的代码,其中包含了创建Huffman树,进行Huffman编码以及对0-1码流进行解码的实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_N 1000
// 定义Huffman树节点
typedef struct TreeNode {
char data; // 节点存储的字符
int freq; // 节点的出现频率
struct TreeNode *left; // 左子节点
struct TreeNode *right; // 右子节点
} TreeNode;
// 定义Huffman编码表
typedef struct Code {
char data; // 字符
char code[MAX_N]; // 编码
} Code;
// 定义Huffman编码栈
typedef struct Stack {
int top; // 栈顶指针
char data[MAX_N]; // 存储编码结果的数组
} Stack;
// 定义全局变量
Code huffman_code[26]; // 存储Huffman编码表
int huffman_code_num = 0; // 存储Huffman编码表中的编码个数
/* 创建Huffman树 */
TreeNode* createHuffmanTree(int *freq) {
TreeNode *node, *left, *right;
int min1, min2, i;
int flag[MAX_N] = {0};
int n = 26;
// 创建n个只有一个节点的二叉树
TreeNode **tree = (TreeNode**) malloc(n * sizeof(TreeNode*));
for (i = 0; i < n; i++) {
tree[i] = (TreeNode*) malloc(sizeof(TreeNode));
tree[i]->data = 'a' + i;
tree[i]->freq = freq[i];
tree[i]->left = NULL;
tree[i]->right = NULL;
}
// 构建Huffman树
while (n > 1) {
min1 = min2 = -1;
// 找到权值最小的两个节点
for (i = 0; i < n; i++) {
if (!flag[i] && (min1 == -1 || tree[i]->freq < tree[min1]->freq)) {
min2 = min1;
min1 = i;
} else if (!flag[i] && (min2 == -1 || tree[i]->freq < tree[min2]->freq)) {
min2 = i;
}
}
// 合并两个节点
node = (TreeNode*) malloc(sizeof(TreeNode));
node->freq = tree[min1]->freq + tree[min2]->freq;
node->left = tree[min1];
node->right = tree[min2];
tree[min1] = node;
flag[min2] = 1;
n--;
}
return tree[min1];
}
/* 生成Huffman编码 */
void generateHuffmanCode(TreeNode *root, Stack *stack) {
if (root == NULL) {
return;
}
if (root->left == NULL && root->right == NULL) {
// 叶子节点
huffman_code[huffman_code_num].data = root->data;
huffman_code[huffman_code_num].code[0] = '\0';
int i;
// 将栈中的编码倒序输出
for (i = stack->top - 1; i >= 0; i--) {
huffman_code[huffman_code_num].code[strlen(huffman_code[huffman_code_num].code)] = stack->data[i];
}
huffman_code[huffman_code_num].code[strlen(huffman_code[huffman_code_num].code)] = '\0';
huffman_code_num++;
} else {
// 左子树编码为0
stack->data[stack->top++] = '0';
generateHuffmanCode(root->left, stack);
stack->top--;
// 右子树编码为1
stack->data[stack->top++] = '1';
generateHuffmanCode(root->right, stack);
stack->top--;
}
}
/* Huffman编码 */
void huffmanEncoding(char *text) {
int freq[26] = {0};
int i;
Stack stack;
stack.top = 0;
// 统计各个字符出现的频率
for (i = 0; i < strlen(text); i++) {
freq[text[i] - 'a']++;
}
// 创建Huffman树
TreeNode *root = createHuffmanTree(freq);
// 生成Huffman编码
generateHuffmanCode(root, &stack);
// 输出Huffman编码结果
printf("Huffman编码结果:\n");
for (i = 0; i < strlen(text); i++) {
int j;
for (j = 0; j < huffman_code_num; j++) {
if (text[i] == huffman_code[j].data) {
printf("%s", huffman_code[j].code);
break;
}
}
}
printf("\n");
}
/* Huffman解码 */
void huffmanDecoding(char *code) {
char text[MAX_N] = {'\0'};
int i, j, k;
// 逐个匹配Huffman编码
for (i = 0, j = 0; i < strlen(code);) {
for (k = 0; k < huffman_code_num; k++) {
if (strncmp(code + i, huffman_code[k].code, strlen(huffman_code[k].code)) == 0) {
text[j++] = huffman_code[k].data;
i += strlen(huffman_code[k].code);
break;
}
}
}
// 输出解码结果
printf("Huffman解码结果:%s\n", text);
}
int main() {
char text[MAX_N];
char code[MAX_N];
// 从键盘读入文本字符串
printf("请输入一个由英文字母构成的字符串(不超过1000个字符):\n");
fgets(text, MAX_N, stdin);
text[strlen(text) - 1] = '\0';
// 对文本字符串进行Huffman编码
huffmanEncoding(text);
// 测试Huffman解码
printf("请输入一个0-1码流:\n");
fgets(code, MAX_N, stdin);
code[strlen(code) - 1] = '\0';
huffmanDecoding(code);
return 0;
}
```
这个程序会先让用户从键盘输入一个带空格由英文字母构成的文本字符串,然后根据该字符串创建Huffman树,进行Huffman编码,把编码结果输出到屏幕上。接着,程序会提示用户输入一个0-1码流,利用前面生成的Huffman编码表对该码流进行解码,并将解码结果输出到屏幕上。
需要注意的是,本程序只支持由英文字母构成的字符串,且输入的字符串长度不得超过1000个字符。如果需要对其他类型的字符串进行编解码,请根据实际情况修改代码。
阅读全文