利用C语言编写完整代码。具体要求为: 从键盘任意输入一个由英文字母带空格构成的文本字符串,例如“I like Learning datastructure course”,首先根据该字符串创建Huffman树,之后进行Huffman编码,然后把该字符串的Huffman编码结果向屏幕输出。能够利用前述的Huffman编码结果对某0-1码流进行解码得到字符串,并做详细注释
时间: 2024-03-07 17:47:40 浏览: 168
以下是基于C语言的Huffman编码和解码示例代码,代码中会使用到哈希表和优先队列这两个数据结构:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_N 1000 // 字符串最大长度
#define MAX_HUFF 512 // 哈夫曼编码最大长度
#define MAX_HASH 128 // 哈希表大小
// 定义哈夫曼树节点
typedef struct huff_node {
char ch; // 字符
int freq; // 频率
int lson, rson; // 左右子节点
} huff_node;
// 定义哈夫曼编码表
typedef struct huff_code {
char ch; // 字符
char code[MAX_HUFF]; // 编码
} huff_code;
// 定义哈希表节点
typedef struct hash_node {
char ch; // 字符
int index; // 索引
} hash_node;
// 定义优先队列节点
typedef struct pq_node {
int index; // 索引
int priority; // 优先级
} pq_node;
// 定义哈希表
hash_node hash_table[MAX_HASH];
// 定义哈夫曼树和编码表
huff_node huff_tree[MAX_HASH * 2 - 1];
huff_code huff_codes[MAX_HASH];
// 定义优先队列
pq_node pq[MAX_HASH * 2 - 1];
int pq_size = 0;
// 定义字符出现频率数组
int freq[MAX_HASH];
// 定义字符串和哈夫曼编码结果
char str[MAX_N], huff_result[MAX_N * MAX_HUFF];
// 定义哈夫曼树节点个数和哈夫曼编码表长度
int num_nodes = 0, num_codes = 0;
/* 哈希表相关函数 */
// 初始化哈希表
void init_hash_table() {
for (int i = 0; i < MAX_HASH; i++) {
hash_table[i].ch = 0;
hash_table[i].index = -1;
}
}
// 向哈希表中添加字符和索引
void add_to_hash_table(char ch, int index) {
int hash_index = ch % MAX_HASH;
while (hash_table[hash_index].ch != 0) {
hash_index = (hash_index + 1) % MAX_HASH;
}
hash_table[hash_index].ch = ch;
hash_table[hash_index].index = index;
}
// 从哈希表中获取字符的索引
int get_from_hash_table(char ch) {
int hash_index = ch % MAX_HASH;
while (hash_table[hash_index].ch != ch && hash_table[hash_index].ch != 0) {
hash_index = (hash_index + 1) % MAX_HASH;
}
if (hash_table[hash_index].ch == ch) {
return hash_table[hash_index].index;
} else {
return -1;
}
}
/* 优先队列相关函数 */
// 初始化优先队列
void init_priority_queue() {
pq_size = 0;
}
// 向优先队列中添加节点
void add_to_priority_queue(int index, int priority) {
int i = pq_size++;
pq[i].index = index;
pq[i].priority = priority;
while (i > 0 && pq[i].priority < pq[(i - 1) / 2].priority) {
pq_node temp = pq[i];
pq[i] = pq[(i - 1) / 2];
pq[(i - 1) / 2] = temp;
i = (i - 1) / 2;
}
}
// 从优先队列中获取最小节点
pq_node pop_priority_queue() {
pq_node min_node = pq[0];
pq[0] = pq[--pq_size];
int i = 0;
while (i * 2 + 1 < pq_size) {
int lson = i * 2 + 1;
int rson = i * 2 + 2;
int min_son = lson;
if (rson < pq_size && pq[rson].priority < pq[lson].priority) {
min_son = rson;
}
if (pq[min_son].priority < pq[i].priority) {
pq_node temp = pq[i];
pq[i] = pq[min_son];
pq[min_son] = temp;
i = min_son;
} else {
break;
}
}
return min_node;
}
/* 哈夫曼树相关函数 */
// 创建哈夫曼树
void create_huff_tree() {
for (int i = 0; i < MAX_HASH; i++) {
if (freq[i] > 0) {
huff_tree[num_nodes].ch = i;
huff_tree[num_nodes].freq = freq[i];
huff_tree[num_nodes].lson = huff_tree[num_nodes].rson = -1;
add_to_hash_table(i, num_nodes);
add_to_priority_queue(num_nodes, freq[i]);
num_nodes++;
}
}
while (pq_size > 1) {
pq_node node1 = pop_priority_queue();
pq_node node2 = pop_priority_queue();
huff_tree[num_nodes].ch = 0;
huff_tree[num_nodes].freq = node1.priority + node2.priority;
huff_tree[num_nodes].lson = node1.index;
huff_tree[num_nodes].rson = node2.index;
add_to_priority_queue(num_nodes, huff_tree[num_nodes].freq);
num_nodes++;
}
}
// 深度优先遍历哈夫曼树,生成哈夫曼编码
void dfs_huff_tree(int node_index, char* code, int len) {
if (huff_tree[node_index].lson == -1 && huff_tree[node_index].rson == -1) {
huff_codes[num_codes].ch = huff_tree[node_index].ch;
strcpy(huff_codes[num_codes].code, code);
num_codes++;
} else {
code[len] = '0';
dfs_huff_tree(huff_tree[node_index].lson, code, len + 1);
code[len] = '1';
dfs_huff_tree(huff_tree[node_index].rson, code, len + 1);
}
}
// 获取字符的哈夫曼编码
char* get_huff_code(char ch) {
int index = get_from_hash_table(ch);
if (index != -1) {
return huff_codes[index].code;
} else {
return NULL;
}
}
/* 哈夫曼编码函数 */
// 对字符串进行哈夫曼编码
void huff_encode() {
char code[MAX_HUFF];
memset(code, 0, sizeof(code));
for (int i = 0; str[i] != '\0'; i++) {
char* huff_code = get_huff_code(str[i]);
strcat(huff_result, huff_code);
}
}
/* 哈夫曼解码函数 */
// 对哈夫曼编码进行解码
void huff_decode(char* code) {
int len = strlen(code);
int node_index = num_nodes - 1;
for (int i = 0; i < len; i++) {
if (code[i] == '0') {
node_index = huff_tree[node_index].lson;
} else {
node_index = huff_tree[node_index].rson;
}
if (huff_tree[node_index].lson == -1 && huff_tree[node_index].rson == -1) {
putchar(huff_tree[node_index].ch);
node_index = num_nodes - 1;
}
}
}
/* 主函数 */
int main() {
// 初始化哈希表和优先队列
init_hash_table();
init_priority_queue();
// 从键盘读入字符串
printf("请输入一个由英文字母带空格构成的文本字符串:\n");
fgets(str, MAX_N, stdin);
// 统计字符出现频率
for (int i = 0; str[i] != '\0'; i++) {
if (str[i] != ' ') {
freq[str[i]]++;
}
}
// 创建哈夫曼树并生成哈夫曼编码
create_huff_tree();
char code[MAX_HUFF];
memset(code, 0, sizeof(code));
dfs_huff_tree(num_nodes - 1, code, 0);
// 输出哈夫曼编码结果
printf("哈夫曼编码结果为:\n");
huff_encode();
printf("%s\n", huff_result);
// 对哈夫曼编码进行解码
printf("请输入一个0-1编码字符串进行解码:\n");
fgets(huff_result, MAX_N * MAX_HUFF, stdin);
printf("解码结果为:\n");
huff_decode(huff_result);
return 0;
}
```
此代码实现了从键盘读入字符串,统计字符出现频率,创建哈夫曼树并生成哈夫曼编码,输出哈夫曼编码结果,对哈夫曼编码进行解码等功能。
阅读全文