利用C语言编写一个完整代码。具体要求为:从键盘任意输入一个带空格由英文字母构成的文本字符串,例如“ilikelearningdatastructurecourse”,首先根据该字符串创建Huffman树,之后进行Huffman编码,然后把该字符串的Huffman编码结果向屏幕输出。能够利用前述的Huffman编码结果对某0-1码流进行解码得到字符串,并作出详细注释
时间: 2024-03-07 14:47:37 浏览: 72
以下是利用C语言编写的完整代码,实现输入一个带空格由英文字母构成的文本字符串的Huffman编解码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//定义Huffman树节点结构体
struct HuffmanNode {
char ch; //字符
int freq; //频率
struct HuffmanNode *left;
struct HuffmanNode *right;
};
//定义Huffman编码结构体
struct HuffmanCode {
char ch; //字符
char *code; //编码
};
//创建Huffman节点
struct HuffmanNode* createHuffmanNode(char ch, int freq) {
struct HuffmanNode *node = (struct HuffmanNode*)malloc(sizeof(struct HuffmanNode));
node->ch = ch;
node->freq = freq;
node->left = NULL;
node->right = NULL;
return node;
}
//创建Huffman树
struct HuffmanNode* createHuffmanTree(char *str) {
int len = strlen(str);
int count[26] = {0}; //记录每个字母出现的频率
int i;
for (i = 0; i < len; i++) {
count[str[i]-'a']++;
}
//将每个字母出现的频率作为权值创建Huffman节点,加入优先队列
struct PriorityQueue *queue = createPriorityQueue();
for (i = 0; i < 26; i++) {
if (count[i] > 0) {
struct HuffmanNode *node = createHuffmanNode('a'+i, count[i]);
enqueue(queue, node, count[i]);
}
}
//从优先队列中取出两个权值最小的节点作为左右子树,合并成一个新节点,加入优先队列,直到优先队列中只剩下一个节点
while (queue->size > 1) {
struct HuffmanNode *left = (struct HuffmanNode*)dequeue(queue);
struct HuffmanNode *right = (struct HuffmanNode*)dequeue(queue);
struct HuffmanNode *parent = createHuffmanNode('\0', left->freq+right->freq);
parent->left = left;
parent->right = right;
enqueue(queue, parent, parent->freq);
}
struct HuffmanNode *root = (struct HuffmanNode*)dequeue(queue);
free(queue);
return root;
}
//递归遍历Huffman树,生成Huffman编码
void generateHuffmanCode(struct HuffmanNode *root, char *code, int depth, struct HuffmanCode *huffmanCodes, int *index) {
if (root == NULL) {
return;
}
if (root->left == NULL && root->right == NULL) { //叶子节点,保存编码
huffmanCodes[*index].ch = root->ch;
huffmanCodes[*index].code = (char*)malloc((depth+1)*sizeof(char));
strcpy(huffmanCodes[*index].code, code);
(*index)++;
}
code[depth] = '0';
code[depth+1] = '\0';
generateHuffmanCode(root->left, code, depth+1, huffmanCodes, index);
code[depth] = '1';
code[depth+1] = '\0';
generateHuffmanCode(root->right, code, depth+1, huffmanCodes, index);
}
//Huffman编码
char* huffmanEncode(char *str, struct HuffmanCode *huffmanCodes) {
int len = strlen(str);
char *encoded = (char*)malloc(len*10*sizeof(char)); //预留足够空间存储编码结果
int i, j;
int index = 0;
for (i = 0; i < len; i++) {
for (j = 0; j < 26; j++) {
if (huffmanCodes[j].ch == str[i]) { //查找编码
strcat(encoded, huffmanCodes[j].code);
index += strlen(huffmanCodes[j].code);
break;
}
}
}
encoded[index] = '\0';
return encoded;
}
//Huffman解码
char* huffmanDecode(char *encoded, struct HuffmanNode *root) {
int len = strlen(encoded);
char *decoded = (char*)malloc(len*sizeof(char)); //预留足够空间存储解码结果
struct HuffmanNode *p = root;
int i, j;
int index = 0;
for (i = 0; i < len; i++) {
if (encoded[i] == '0') { //左子树
p = p->left;
} else { //右子树
p = p->right;
}
if (p->left == NULL && p->right == NULL) { //叶子节点,保存字符
decoded[index++] = p->ch;
p = root;
}
}
decoded[index] = '\0';
return decoded;
}
int main() {
char str[1000];
printf("请输入一个带空格由英文字母构成的文本字符串:\n");
gets(str);
struct HuffmanNode *root = createHuffmanTree(str);
struct HuffmanCode huffmanCodes[26];
int index = 0;
char code[100];
generateHuffmanCode(root, code, 0, huffmanCodes, &index);
char *encoded = huffmanEncode(str, huffmanCodes);
printf("Huffman编码结果为:%s\n", encoded);
char *decoded = huffmanDecode(encoded, root);
printf("Huffman解码结果为:%s\n", decoded);
free(encoded);
free(decoded);
freeHuffmanTree(root);
return 0;
}
```
在上述代码中,我们首先定义了Huffman树节点结构体和Huffman编码结构体。然后,我们利用输入的字符串创建Huffman树,通过递归遍历Huffman树生成Huffman编码,最后对输入的字符串进行Huffman编码和解码。
编译运行上述代码,输入一个带空格由英文字母构成的文本字符串,例如“ilikelearningdatastructurecourse”,即可得到该字符串的Huffman编码结果和Huffman解码结果。
阅读全文