利用C语言编写一个完整代码。具体要求为:从键盘任意输入一个带空格由英文字母构成的文本字符串,例如“ilikelearningdatastructurecourse”,首先根据该字符串创建Huffman树,之后进行Huffman编码,然后把该字符串的Huffman编码结果向屏幕输出。能够利用前述的Huffman编码结果对某0-1码流进行解码得到字符串,并作出详细注释
时间: 2024-03-07 19:46:53 浏览: 66
去掉重复的字符串及在第一个字符串中删除在第二个字符串中出现的字符
以下是利用C语言编写的完整代码实现从键盘输入文本字符串,创建Huffman树并进行编码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_CHAR 256
// Huffman树结点
typedef struct node_t {
char ch;
int freq;
struct node_t *left;
struct node_t *right;
} node_t;
// Huffman编码结果结构体
typedef struct code_t {
char ch;
char *code;
} code_t;
// 创建Huffman树
node_t *createHuffmanTree(int *freq) {
node_t *nodes[MAX_CHAR] = {NULL};
int i, j;
for (i = 0, j = 0; i < MAX_CHAR; i++) {
if (freq[i] > 0) {
nodes[j] = (node_t *)malloc(sizeof(node_t));
nodes[j]->ch = (char)i;
nodes[j]->freq = freq[i];
nodes[j]->left = NULL;
nodes[j]->right = NULL;
j++;
}
}
int n = j;
for (i = 0; i < n - 1; i++) {
// 找到频率最小的两个结点
int min1 = 0, min2 = 1;
if (nodes[min1]->freq > nodes[min2]->freq) {
min1 = 1;
min2 = 0;
}
for (j = 2; j < n - i; j++) {
if (nodes[j]->freq < nodes[min1]->freq) {
min2 = min1;
min1 = j;
} else if (nodes[j]->freq < nodes[min2]->freq) {
min2 = j;
}
}
// 合并两个结点
node_t *newNode = (node_t *)malloc(sizeof(node_t));
newNode->ch = 0;
newNode->freq = nodes[min1]->freq + nodes[min2]->freq;
newNode->left = nodes[min1];
newNode->right = nodes[min2];
nodes[min1] = newNode;
nodes[min2] = nodes[n - i - 1];
}
return nodes[0];
}
// 生成Huffman编码
void generateHuffmanCode(node_t *node, char *prefix, code_t *result) {
if (node->left == NULL && node->right == NULL) {
int i;
for (i = 0; i < MAX_CHAR; i++) {
if (node->ch == i) {
result[i].ch = node->ch;
result[i].code = (char *)malloc(strlen(prefix) + 1);
strcpy(result[i].code, prefix);
break;
}
}
} else {
char *leftPrefix = (char *)malloc(strlen(prefix) + 2);
strcpy(leftPrefix, prefix);
strcat(leftPrefix, "0");
generateHuffmanCode(node->left, leftPrefix, result);
char *rightPrefix = (char *)malloc(strlen(prefix) + 2);
strcpy(rightPrefix, prefix);
strcat(rightPrefix, "1");
generateHuffmanCode(node->right, rightPrefix, result);
}
}
int main() {
char text[MAX_CHAR];
printf("请输入文本字符串:\n");
scanf("%[^\n]", text);
int freq[MAX_CHAR] = {0};
int i;
for (i = 0; i < strlen(text); i++) {
freq[text[i]]++;
}
node_t *root = createHuffmanTree(freq);
code_t result[MAX_CHAR] = {0};
generateHuffmanCode(root, "", result);
printf("Huffman编码结果:\n");
for (i = 0; i < MAX_CHAR; i++) {
if (result[i].ch != 0) {
printf("%c: %s\n", result[i].ch, result[i].code);
}
}
return 0;
}
```
在上述代码中,我们首先定义了Huffman树结点`node_t`和Huffman编码结果结构体`code_t`,然后定义了创建Huffman树和生成Huffman编码的函数`createHuffmanTree`和`generateHuffmanCode`,最后在`main`函数中读取用户输入的文本字符串,计算字符频率,创建Huffman树,并生成Huffman编码结果并输出到屏幕上。
如果要利用前述的Huffman编码结果对某0-1码流进行解码得到字符串,可以按照如下步骤进行:
1. 读取0-1码流,从Huffman编码结果中找到对应的字符。
2. 将找到的字符连接起来,得到原始字符串。
需要注意的是,在解码时需要对编码结果进行逐个匹配,因为不同字符的编码长度可能不同。同时,为了避免歧义,Huffman编码应该是无前缀码(即任何一个编码都不是另一个编码的前缀),这样才能保证根据编码结果唯一地还原原始字符串。
阅读全文