利用C语言编写完整代码。具体要求为: 从键盘任意输入一个由英文字母带空格构成的文本字符串,例如“I like Learning datastructure course”,首先根据该字符串创建Huffman树,之后进行Huffman编码,然后把该字符串的Huffman编码结果向屏幕输出。能够利用前述的Huffman编码结果对某0-1码流进行解码得到字符串,并做详细注释
时间: 2024-03-07 14:48:27 浏览: 62
好的,以下是利用C语言编写的完整代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_CHAR_NUM 256
// 定义Huffman树结点
typedef struct HuffNode {
char ch; // 字符
int weight; // 权重
struct HuffNode *left, *right; // 左右子结点
} HuffNode;
// 定义Huffman编码表
typedef struct HuffCode {
char ch; // 字符
char *code; // 编码
} HuffCode;
// 从键盘读入字符串
char* readString() {
char *str = NULL;
int len = 0, capacity = 0;
char ch;
while ((ch = getchar()) != '\n') {
if (len >= capacity) {
capacity += 10;
str = (char*)realloc(str, capacity * sizeof(char));
}
str[len++] = ch;
}
str[len] = '\0';
return str;
}
// 统计字符出现频率
void countFrequency(char *str, int *freq) {
int len = strlen(str);
for (int i = 0; i < len; i++) {
freq[(int)str[i]]++;
}
}
// 创建Huffman树
HuffNode* createHuffmanTree(int *freq) {
HuffNode *nodes[MAX_CHAR_NUM];
int nodeCount = 0;
// 将所有出现过的字符作为叶子结点,加入结点数组
for (int i = 0; i < MAX_CHAR_NUM; i++) {
if (freq[i] > 0) {
HuffNode *node = (HuffNode*)malloc(sizeof(HuffNode));
node->ch = (char)i;
node->weight = freq[i];
node->left = node->right = NULL;
nodes[nodeCount++] = node;
}
}
// 从结点数组中挑选权重最小的两个结点,合并成一个新结点,再加入结点数组
while (nodeCount > 1) {
int min1Idx = 0, min2Idx = 1;
if (nodes[min1Idx]->weight > nodes[min2Idx]->weight) {
min1Idx = 1;
min2Idx = 0;
}
for (int i = 2; i < nodeCount; i++) {
if (nodes[i]->weight < nodes[min1Idx]->weight) {
min2Idx = min1Idx;
min1Idx = i;
} else if (nodes[i]->weight < nodes[min2Idx]->weight) {
min2Idx = i;
}
}
HuffNode *newNode = (HuffNode*)malloc(sizeof(HuffNode));
newNode->ch = '\0';
newNode->weight = nodes[min1Idx]->weight + nodes[min2Idx]->weight;
newNode->left = nodes[min1Idx];
newNode->right = nodes[min2Idx];
nodes[min1Idx] = newNode;
nodes[min2Idx] = nodes[--nodeCount];
}
return nodes[0];
}
// 递归生成Huffman编码表
void generateHuffmanCodeTable(HuffNode *root, char *prefix, int depth, HuffCode *table) {
if (root == NULL) {
return;
}
if (root->left == NULL && root->right == NULL) {
table[(int)root->ch].ch = root->ch;
table[(int)root->ch].code = (char*)malloc((depth + 1) * sizeof(char));
strcpy(table[(int)root->ch].code, prefix);
} else {
prefix[depth] = '0';
prefix[depth + 1] = '\0';
generateHuffmanCodeTable(root->left, prefix, depth + 1, table);
prefix[depth] = '1';
prefix[depth + 1] = '\0';
generateHuffmanCodeTable(root->right, prefix, depth + 1, table);
}
}
// 生成Huffman编码表
HuffCode* generateHuffmanCode(HuffNode *root) {
char prefix[MAX_CHAR_NUM] = "";
HuffCode *table = (HuffCode*)malloc(MAX_CHAR_NUM * sizeof(HuffCode));
memset(table, 0, MAX_CHAR_NUM * sizeof(HuffCode));
generateHuffmanCodeTable(root, prefix, 0, table);
return table;
}
// Huffman编码
char* huffmanEncode(char *str, HuffCode *table) {
int len = strlen(str);
int codeLen = 0;
char *code = (char*)malloc((len * 10 + 1) * sizeof(char));
code[0] = '\0';
for (int i = 0; i < len; i++) {
strcat(code, table[(int)str[i]].code);
}
return code;
}
// Huffman解码
char* huffmanDecode(char *code, HuffNode *root) {
int len = strlen(code);
int strLen = 0;
char *str = (char*)malloc((len / 10 + 1) * sizeof(char));
str[0] = '\0';
HuffNode *curNode = root;
for (int i = 0; i < len; i++) {
if (code[i] == '0') {
curNode = curNode->left;
} else if (code[i] == '1') {
curNode = curNode->right;
}
if (curNode->left == NULL && curNode->right == NULL) {
str[strLen++] = curNode->ch;
curNode = root;
}
}
str[strLen] = '\0';
return str;
}
int main() {
int freq[MAX_CHAR_NUM] = {0};
// 读入字符串并统计字符出现频率
printf("请输入一个由英文字母带空格构成的文本字符串:\n");
char *str = readString();
countFrequency(str, freq);
// 创建Huffman树并生成Huffman编码表
HuffNode *root = createHuffmanTree(freq);
HuffCode *table = generateHuffmanCode(root);
// Huffman编码并输出结果
char *code = huffmanEncode(str, table);
printf("Huffman编码结果为:%s\n", code);
// Huffman解码并输出结果
char *decodedStr = huffmanDecode(code, root);
printf("Huffman解码结果为:%s\n", decodedStr);
// 释放内存
free(str);
free(code);
free(decodedStr);
for (int i = 0; i < MAX_CHAR_NUM; i++) {
if (table[i].code != NULL) {
free(table[i].code);
}
}
return 0;
}
```
代码中的注释已经比较详细了,这里简单说明一下:
1. `readString()` 函数用于从键盘读入字符串,返回一个 `char*` 类型的指针。
2. `countFrequency()` 函数用于统计字符串中每个字符出现的频率,保存在一个 `int` 类型的数组中。
3. `createHuffmanTree()` 函数用于根据字符频率创建Huffman树,返回一个指向根节点的指针。
4. `generateHuffmanCode()` 函数用于生成Huffman编码表,返回一个指向 `HuffCode` 类型数组的指针。
5. `huffmanEncode()` 函数用于对字符串进行Huffman编码,返回一个 `char*` 类型的指针。
6. `huffmanDecode()` 函数用于对Huffman编码进行解码,返回一个 `char*` 类型的指针。
7. `main()` 函数中调用了上述函数,并输出了Huffman编码和解码的结果。
需要注意的是,在实现中,我们使用了一个 `HuffCode` 结构体来保存字符和对应的Huffman编码,这样可以方便的构建Huffman编码表。同时,为了方便输出Huffman编码结果,我们使用了一个 `char*` 类型的指针 `code` 来保存编码结果。在实际应用中,可能需要将Huffman编码结果转换成二进制数据流进行传输或存储。
阅读全文