利用C语言编写一个完整代码。具体要求为:从键盘任意输入一个带空格由英文字母构成的文本字符串,例如“ilikelearningdatastructurecourse”,首先根据该字符串创建Huffman树,之后进行Huffman编码,然后把该字符串的Huffman编码结果向屏幕输出。能够利用前述的Huffman编码结果对某0-1码流进行解码得到字符串,并作出详细注释
时间: 2024-03-07 14:47:37 浏览: 68
去掉重复的字符串及在第一个字符串中删除在第二个字符串中出现的字符
以下是利用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解码结果。
阅读全文