使用C语言写一个程序输入n个叶子结点的权值构造哈夫曼树;根据哈夫曼树构造哈夫曼编码,并对密文完成解码工作。
时间: 2023-06-29 07:15:19 浏览: 66
好的,我会尽力回答你的问题。
以下是使用C语言实现构造哈夫曼树、生成哈夫曼编码和解码的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_NODE_NUM 100 // 哈夫曼树节点最大数量
#define MAX_CODE_LEN 100 // 哈夫曼编码最大长度
// 哈夫曼树节点结构体
typedef struct huffman_node{
int weight; // 权值
int parent; // 父节点下标
int left; // 左子节点下标
int right; // 右子节点下标
}HuffmanNode;
// 哈夫曼编码结构体
typedef struct huffman_code{
int bit[MAX_CODE_LEN]; // 编码位串
int start; // 编码起始位下标
}HuffmanCode;
// 构造哈夫曼树
void create_huffman_tree(HuffmanNode *huffman_tree, int n){
if(n <= 1){
return;
}
int m = 2 * n - 1; // 哈夫曼树节点总数
for(int i = 0; i < n; i++){
huffman_tree[i].parent = -1; // 初始化父节点
huffman_tree[i].left = -1; // 初始化左子节点
huffman_tree[i].right = -1; // 初始化右子节点
}
for(int i = n; i < m; i++){
int min1 = -1, min2 = -1; // 找出权值最小的两个节点
for(int j = 0; j < i; j++){
if(huffman_tree[j].parent == -1){
if(min1 == -1){
min1 = j;
}else if(min2 == -1){
min2 = j;
}else{
if(huffman_tree[j].weight < huffman_tree[min1].weight){
min2 = min1;
min1 = j;
}else if(huffman_tree[j].weight < huffman_tree[min2].weight){
min2 = j;
}
}
}
}
huffman_tree[min1].parent = i; // 合并两个权值最小的节点
huffman_tree[min2].parent = i;
huffman_tree[i].left = min1;
huffman_tree[i].right = min2;
huffman_tree[i].weight = huffman_tree[min1].weight + huffman_tree[min2].weight;
}
}
// 生成哈夫曼编码
void create_huffman_code(HuffmanNode *huffman_tree, HuffmanCode *huffman_code, int n){
for(int i = 0; i < n; i++){
int current = i, parent = huffman_tree[i].parent;
huffman_code[i].start = n - 1; // 初始化编码起始位下标
while(parent != -1){
if(huffman_tree[parent].left == current){
huffman_code[i].bit[huffman_code[i].start] = 0;
}else{
huffman_code[i].bit[huffman_code[i].start] = 1;
}
huffman_code[i].start--;
current = parent;
parent = huffman_tree[parent].parent;
}
huffman_code[i].start++; // 还原编码起始位下标
}
}
// 编码明文
void encode(char *plaintext, HuffmanCode *huffman_code, char *ciphertext){
int len = strlen(plaintext);
int k = 0, bit_count = 0;
for(int i = 0; i < len; i++){
int j = plaintext[i] - '0';
for(int m = huffman_code[j].start; m < MAX_CODE_LEN; m++){
if(huffman_code[j].bit[m] == 1){
k = k * 2 + 1;
}else{
k = k * 2;
}
bit_count++;
if(bit_count == 8){
*ciphertext++ = k;
k = 0;
bit_count = 0;
}
}
}
if(bit_count > 0){
k = k * (1 << (8 - bit_count));
*ciphertext++ = k;
}
*ciphertext = '\0';
}
// 解码密文
void decode(char *ciphertext, HuffmanNode *huffman_tree, char *plaintext, int plaintext_len){
int current = 2 * plaintext_len - 2;
for(int i = 0; i < strlen(ciphertext); i++){
int k = ciphertext[i];
for(int j = 0; j < 8; j++){
if((k & 128) == 128){
current = huffman_tree[current].right;
}else{
current = huffman_tree[current].left;
}
if(current < plaintext_len){
*plaintext++ = current + '0';
current = 2 * plaintext_len - 2;
}
k <<= 1;
}
}
*plaintext = '\0';
}
int main(){
int n; // 叶子节点数
scanf("%d", &n);
HuffmanNode huffman_tree[MAX_NODE_NUM]; // 哈夫曼树
HuffmanCode huffman_code[MAX_NODE_NUM]; // 哈夫曼编码
char plaintext[MAX_NODE_NUM], ciphertext[MAX_NODE_NUM]; // 明文和密文
// 输入叶子节点权值
for(int i = 0; i < n; i++){
scanf("%d", &huffman_tree[i].weight);
}
create_huffman_tree(huffman_tree, n); // 构造哈夫曼树
create_huffman_code(huffman_tree, huffman_code, n); // 生成哈夫曼编码
scanf("%s", plaintext);
encode(plaintext, huffman_code, ciphertext); // 编码明文
printf("Plaintext: %s\nCiphertext: %s\n", plaintext, ciphertext);
decode(ciphertext, huffman_tree, plaintext, strlen(plaintext)); // 解码密文
printf("Decoded plaintext: %s\n", plaintext);
return 0;
}
```
以上代码实现了输入n个叶子结点的权值,构造哈夫曼树;根据哈夫曼树构造哈夫曼编码,并使用哈夫曼编码对明文进行编码和密文进行解码的功能。