【数据结构】【程序填空】赫夫曼解码

目录

题目描述

思路分析

AC代码

---

题目描述

在掌握赫夫曼树构建的基础上，实现赫夫曼解码

赫夫曼构建中，默认左孩子权值不大于右孩子权值

如果遇到两个孩子权值相等，那么按输入顺序或生成顺序来排列。

例如有一个叶子权值是29，后来生成一个中间结点权值也是29，那么叶子为左孩子，中间结点为右孩子

例如有两个叶子权值都是4，那么按输入顺序，先输入权值的叶子是左孩子

请完成以下程序填空

输入

第一行输入n，表示有n个叶子

第二行输入n个叶子权值，权值全是正整数

第三行输入n个叶子对应的字符，权值全是正整数

第四行输入k，表示要输入k个编码串

接着输入k个编码串

输出

输出k行，每行输出一个编码串的解码结果。

如果编码串非法，则对应的一行输出error，不输出已解码的字符

输入样例1

5
15 4 4 3 2
K G C M W
2
11011010000001
0000011100010

输出样例1

KKCGWM
error

思路分析

遍历编码，从树的根节点开始找，如果当前字符是0，判断是否有左孩子，有的话，更新节点为左孩子节点，如果没有，退出输出error。如果当前字符是1，判断是否有有孩子，有的话，更新节点为右孩子节点，如果没有，退出输出error。

如果左右孩子都为0，说明到达叶子节点，尾部添加解码信息。

注意string类对象可直接通过+=实现尾部添加字符（串）。

AC代码

HuffMan::HuffMan(int n, int *w,char c[]) {
    lnum = n;
    len = lnum * 2 - 1;
    HuffTree = new HuffNode[len+1];
    for (int i = 1; i <= lnum; i++) {
        HuffTree[i].weight = w[i-1];
        HuffTree[i].letter=c[i-1];
        HuffTree[i].parent = HuffTree[i].lchild = HuffTree[i].rchild = 0;
    }
    for (int i = lnum+1; i <= len; i++)
        HuffTree[i].weight = HuffTree[i].parent = HuffTree[i].lchild = HuffTree[i].rchild = 0;
}
 
void HuffMan::buildTree() {
    int a, b;
    for (int i = lnum+1; i <= len; i++) {
        selectMin(i-1, a, b);
        HuffTree[a].parent = HuffTree[b].parent = i;
        HuffTree[i].lchild = a;
        HuffTree[i].rchild = b;
        HuffTree[i].weight = HuffTree[a].weight + HuffTree[b].weight;
    }
}
 
void HuffMan::selectMin(int n, int &x1, int &x2) {
    x1=x2=0;
    for (int i =1; i <= n; i++)
        if (HuffTree[i].parent == 0) {
            if(x1==0)
                x1=i;
            else if(x2==0)
                x2=i;
            if (HuffTree[i].weight < HuffTree[x1].weight) {
                x2 = x1;
                x1 = i;
            } else if (x2 != 0 && HuffTree[i].weight < HuffTree[x2].weight)
                x2 = i;
        }
}
 
void HuffMan::Decoding(std::string cs)  {
    int j=len;
    string temp;
    for (int i = 0;cs[i]; i++) {
        if(cs[i]=='0'){
            if(HuffTree[j].lchild)
                j=HuffTree[j].lchild;
            else{
                cout<<"error"<
                return;
            }
        }else{
            if(HuffTree[j].rchild)
                j=HuffTree[j].rchild;
            else{
                cout<<"error"<
                return;
            }
        }
        if (HuffTree[j].lchild == 0 && HuffTree[j].rchild == 0) {
            temp+=HuffTree[j].letter;
            j = len;
        }
    }
    if(j==len)
        cout<
    else
        cout<<"error"<
}
 
HuffMan::~HuffMan() {
    if (HuffTree)
        delete[]HuffTree;
}