电文编码译码

从键盘接收一串电文字符，输出对应的Huffman编码。同时，能翻译有Huffman编码生成的代码串，输出对应的电文字符串。

设计要求

  • 构造一棵Huffman树
  • 实现Huffman编码，并用Huffman编码生成的代码串进行译码
  • 程序中字符和权值是可变的，实现程序的灵活性
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 定义Huffman树的节点结构
typedef struct Node {
    char data;
    int frequency;
    struct Node* left;
    struct Node* right;
} Node;
// 创建Huffman树节点
Node* createNode(char data, int frequency) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = data;
    newNode->frequency = frequency;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
// 插入节点到Huffman树
void insertNode(Node** tree, Node* node) {
    if (*tree == NULL) {
        *tree = node;
        return;
    }
    if (node->frequency < (*tree)->frequency) {
        insertNode(&((*tree)->left), node);
    }
    else {
        insertNode(&((*tree)->right), node);
    }
}
// 构造Huffman树
Node* buildHuffmanTree(char* text, int* frequency) {
    Node* root = NULL;
    for (int i = 0; i < strlen(text); i++) {
        if (text[i] != ' ') {
            Node* newNode = createNode(text[i], frequency[text[i]]);
            insertNode(&root, newNode);
        }
    }
    return root;
}
// 打印Huffman编码
void printHuffmanCode(Node* root, int* code, int top) {
    if (root->left) {
        code[top] = 0;
        printHuffmanCode(root->left, code, top + 1);
    }
    if (root->right) {
        code[top] = 1;
        printHuffmanCode(root->right, code, top + 1);
    }
    if (root->left == NULL && root->right == NULL) {
        printf("%c: ", root->data);
        for (int i = 0; i < top; i++) {
            printf("%d", code[i]);
        }
        printf("\n");
    }
}
// 编码电文字符
void encodeText(char* text, Node* root, int* code, int top) {
    if (root->left == NULL && root->right == NULL) {
        printf("%d", root->data);
        return;
    }
    if (text[top] == '0') {
        encodeText(text, root->left, code, top + 1);
    }
    else {
        encodeText(text, root->right, code, top + 1);
    }
}
// 解码Huffman编码
void decodeCode(char* code, Node* root) {
    Node* current = root;
    for (int i = 0; i < strlen(code); i++) {
        if (code[i] == '0') {
            current = current->left;
        }
        else {
            current = current->right;
        }
        if (current->left == NULL && current->right == NULL) {
            printf("%c", current->data);
            current = root;
        }
    }
}
int main() {
    char text[1000];
    printf("请输入字符: ");
    fgets(text, sizeof(text), stdin);
    text[strcspn(text, "\n")] = '\0';

    int frequency[256] = { 0 };
    for (int i = 0; i < strlen(text); i++) {
        frequency[text[i]]++;
    }
    Node* root = buildHuffmanTree(text, frequency);
    int code[100];
    printf("\nHuffman编码:\n");
    printHuffmanCode(root, code, 0);
    printf("\n编码: ");
    for (int i = 0; i < strlen(text); i++) {
        encodeText(text + i, root, code, 0);
    }
    printf("\n\n输入Huffman编码来解码: ");
    char codeToDecode[100];
    fgets(codeToDecode, sizeof(codeToDecode), stdin);
    codeToDecode[strcspn(codeToDecode, "\n")] = '\0';

    printf("\n解码后: ");
    decodeCode(codeToDecode, root);
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
请输入字符: hello world
Huffman编码:
d: 000
e: 001
h: 010
l: 011
o: 100
r: 101
w: 110
 : 1110
l: 1111
编码:  0100011011111100110110001110101100110111001010011001001111100011101010
解码后：hello world