【问题描述】

给定一组字符的Huffman编码表（从标准输入读取），给定一个用该编码表进行编码的Huffman编码文件（存在当前目录下的in.txt中），编写程序对Huffman编码文件进行解码。

例如给定的一组字符的Huffman编码表为：

6

1:111

2:0

+:110

*:1010

=:1011

8:100

第一行的6表示要对6个不同的字符进行编码，后面每行中冒号（:）左边的字符为待编码的字符，右边为其Huffman编码，冒号两边无空格。对于该编码表，对应的Huffman树（树中左分支表示0，右分支表示1）应为：

1701071826572013708.png

假如Huffman编码文件in.txt中的内容（由0和1字符组成的序列）为：

111011010010110101010011001100

则遍历上述Huffman树即可对该文件进行解码，解码后的文件内容为：

12+8=2*8+2+2

【输入形式】

先从标准输入读入待编码的字符个数（大于等于2，小于等于30），然后分行输入各字符的Huffman编码（先输入字符，再输入其编码，字符和编码中间以一个英文字符冒号:分隔），编码只由0和1组成。

Huffman编码文件为当前目录下的in.txt文本文件，即：其中的0和1都是以单个字符的形式存储，文件末尾有一个回车换行符。

【输出形式】

将解码后的文件内容输出到标准输出上

【样例输入】

6

1:111

2:0

+:110

*:1010

=:1011

8:100

假如in.txt中的内容为：

111011010010110101010011001100

【样例输出】

12+8=2*8+2+2

【样例说明】

从标准输入读取了6个字符的Huffman编码，因为规定Huffman树中左分支表示0，右分支表示1，所以利用该编码表可构造上述Huffman树（见图1）。遍历该Huffman树对编码文件in.txt的进行解码，即可得到解码后的原文件内容。

【评分标准】

该题要求根据字符的Huffman编码表对编码文件进行解码。

思路

这道题还是很简单的，我们只需要做两件事：

  • 根据输入的数据构建Huffman树
  • 根据构建好的树对Huffman编码文件进行解码

建树

  1. 创建根节点
  2. 调整接收到的输入的格式，”:”前的内容作为结点的数据，”:”后的内容作为该结点的的路径
  3. 根据路径(path)插入结点：
    1. 由于是插入结点且，所以每次个结点的路径中的最后一位数据对应的位置必然是没有节点的，所以最后一个path中的数据无需进行判断，直接插入即可
    2. 对path最后一位数据之前的元素，则需要逐个遍历，如果沿途没有结点，则需要自行添加
      （根节点和占位结点其实数据域是没有作用的，但是为了防止意外访问到了它们的数据域，这里我将它们的数据域设置为’#’）

上面可以看出，其实建树的过程可以分为 找路/填路 和 插入 两个部分的，如果path长度为n，则0到n-2的子串是用于找路/填路的，n-1的字符是用于插入的

解码

  1. 树指针指向root,编码指针指向串首
  2. 编码指针所对应的值用来帮助树的指针进行移动
  3. 每次移动后判断是否是叶子结点
    • 如果是叶子结点，证明此段编码已经找到了解码时对应的值，输出其值，并且将树指针指回root，以待继续解码

代码

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
#include<iostream>
#include<fstream>
using namespace std;

struct BNode{
    char val;
    BNode* left;
    BNode* right;
    BNode(){}
    BNode(char ch) : val(ch), left(nullptr), right(nullptr) {}
};

void InsertNode(BNode* root, BNode* p, string path){
    BNode* cur = root;
    int i = 0;
    while(i < path.size() - 1){
        char ch = path[i];
        if(ch == '0'){
            if(cur->left == nullptr){
                BNode* holder = new BNode('#');//用于填补path上面的空缺
                cur->left = holder;
            }
            cur = cur->left;
        }else{
            if(cur->right == nullptr){
                BNode* holder = new BNode('#');//用于填补path上面的空缺
                cur->right = holder;
            }
            cur = cur->right;
        }   
        i++;
    }
    if(path[i] == '0'){
        cur->left = p;
    }else{
        cur->right = p;
    }
}

//辅助函数，判断建树是否有误
// void PreOrder(BNode* b){
//     if(b != nullptr){
//         cout << b->val << ' ';
//         PreOrder(b->left);
//         PreOrder(b->right);
//     }
// }

void Translation(string Huffman, BNode* root){
    BNode* cur = root; 
    char ch;
    int i = 0;
    while(i < Huffman.size()){
        ch = Huffman[i];
        if(ch == '0'){
            cur = cur->left;
        }else{
            cur = cur->right;
        }
        if(cur->left == nullptr && cur->right == nullptr){
            cout << cur->val;
            cur = root;
        }
        i++;
    }
}

int main(){
    BNode* root = new BNode('#'); 
    char val;
    string str;
    stringstream ss;
    int nums;
    ifstream file("in.txt");
    cin >> nums;
    BNode* p;
    for(int i = 0; i < nums; i++){
        cin >> str;
        val = str[0];
        p = new BNode(val);
        string path= str.substr(2);
        InsertNode(root, p, path);
    }
    //PreOrder(root);
    file >> str;//此时将str用于接收Huffman编码文件的文件
    Translation(str,root);
    return 0;
}