利用C语言编写软件实现上述功能。具体要求为: 从键盘任意输入一个由英文字母构成的文本字符串,例如“i like learning datastructure course”,首先根据该字符串创建Huffman树,之后进行Huffman编码,然后把该字符串的Huffman编码结果向屏幕输出。能够利用前述的Huffman编码结果对某0-1码流进行解码得到字符串,并为代码写详细注释
时间: 2024-03-03 20:50:42 浏览: 65
从键盘输入一个字符串,如“www.moe.gov.cn”,编写程序,实现如下功能
好的,以下是利用C语言实现该功能的代码及注释。
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_CHAR_NUM 26 // 限制输入的字符串只能由26个英文字母构成
// 哈夫曼树结点的结构体
typedef struct huffman_node {
char data; // 存储字符
int weight; // 存储字符出现的频率
int parent; // 存储父结点的下标
int lchild; // 存储左孩子结点的下标
int rchild; // 存储右孩子结点的下标
} HuffmanNode;
// 哈夫曼编码结构体
typedef struct huffman_code {
char data; // 存储字符
char *code; // 存储字符的哈夫曼编码
} HuffmanCode;
// 获取字符在哈夫曼编码数组中的下标
int get_index(char ch, HuffmanCode *huffman_code, int n) {
int i;
for (i = 0; i < n; i++) {
if (huffman_code[i].data == ch) {
return i;
}
}
return -1; // 如果找不到,则返回-1
}
// 建立哈夫曼树
void create_huffman_tree(HuffmanNode *huffman_tree, int n) {
int i, j, min1, min2; // min1和min2是权值最小的两个结点的下标
for (i = 0; i < 2 * n - 1; i++) {
huffman_tree[i].weight = huffman_tree[i].parent = huffman_tree[i].lchild = huffman_tree[i].rchild = -1;
}
for (i = 0; i < n; i++) {
huffman_tree[i].data = 'a' + i;
printf("请输入字符%c出现的次数:", huffman_tree[i].data);
scanf("%d", &huffman_tree[i].weight);
}
for (i = n; i < 2 * n - 1; i++) {
min1 = min2 = -1;
for (j = 0; j < i; j++) {
if (huffman_tree[j].parent == -1) { // 如果结点没有父结点
if (min1 == -1 || huffman_tree[j].weight < huffman_tree[min1].weight) {
min2 = min1;
min1 = j;
} else if (min2 == -1 || huffman_tree[j].weight < huffman_tree[min2].weight) {
min2 = j;
}
}
}
huffman_tree[min1].parent = i;
huffman_tree[min2].parent = i;
huffman_tree[i].lchild = min1;
huffman_tree[i].rchild = min2;
huffman_tree[i].weight = huffman_tree[min1].weight + huffman_tree[min2].weight;
}
}
// 编码哈夫曼树
void huffman_encode(HuffmanNode *huffman_tree, int n, HuffmanCode *huffman_code) {
int i, j, parent, current;
char *code;
for (i = 0; i < n; i++) {
code = (char *) malloc(sizeof(char) * n); // 申请足够的空间,存储编码
code[n - 1] = '\0'; // 末尾置为'\0'
current = i; // 当前结点的下标
parent = huffman_tree[current].parent; // 父结点的下标
j = n - 2; // 从后往前存储编码
while (parent != -1) { // 如果结点有父结点
if (huffman_tree[parent].lchild == current) { // 如果当前结点是父结点的左孩子
code[j--] = '0';
} else { // 如果当前结点是父结点的右孩子
code[j--] = '1';
}
current = parent;
parent = huffman_tree[current].parent;
}
huffman_code[i].data = huffman_tree[i].data;
huffman_code[i].code = (char *) malloc(sizeof(char) * (n - j)); // 申请足够的空间存储编码
strcpy(huffman_code[i].code, &code[j + 1]); // 将编码拷贝到哈夫曼编码数组中
free(code); // 释放空间
}
}
// 哈夫曼编码
void encode(char *str, HuffmanCode *huffman_code, int n) {
int i, index;
for (i = 0; i < strlen(str); i++) {
index = get_index(str[i], huffman_code, n); // 获取字符在哈夫曼编码数组中的下标
printf("%s", huffman_code[index].code); // 输出字符的哈夫曼编码
}
}
// 解码哈夫曼编码
void decode(char *code, HuffmanNode *huffman_tree, int n) {
int i, current = 2 * n - 2; // 从根结点开始遍历哈夫曼树
for (i = 0; i < strlen(code); i++) {
if (code[i] == '0') { // 如果当前编码是'0'
current = huffman_tree[current].lchild; // 则遍历左子树
} else { // 如果当前编码是'1'
current = huffman_tree[current].rchild; // 则遍历右子树
}
if (huffman_tree[current].lchild == -1 && huffman_tree[current].rchild == -1) { // 如果当前结点是叶子结点
printf("%c", huffman_tree[current].data); // 输出字符
current = 2 * n - 2; // 从根结点开始遍历哈夫曼树
}
}
}
int main() {
char str[100];
int n = MAX_CHAR_NUM;
HuffmanNode huffman_tree[2 * MAX_CHAR_NUM - 1];
HuffmanCode huffman_code[MAX_CHAR_NUM];
printf("请输入一个由英文字母构成的字符串:");
scanf("%[^\n]", str);
create_huffman_tree(huffman_tree, n);
huffman_encode(huffman_tree, n, huffman_code);
printf("该字符串的哈夫曼编码为:");
encode(str, huffman_code, n);
printf("\n请输入一个由哈夫曼编码构成的01串:");
scanf("%s", str);
printf("该01串对应的字符串为:");
decode(str, huffman_tree, n);
printf("\n");
return 0;
}
```
上述代码实现了从键盘任意输入一个由英文字母构成的文本字符串,首先根据该字符串创建Huffman树,之后进行Huffman编码,然后把该字符串的Huffman编码结果向屏幕输出。能够利用前述的Huffman编码结果对某0-1码流进行解码得到字符串。
阅读全文