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

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"<<endl;
                return;
            }
        }else{
            if(HuffTree[j].rchild)
                j=HuffTree[j].rchild;
            else{
                cout<<"error"<<endl;
                return;
            }
        }
        if (HuffTree[j].lchild == 0 && HuffTree[j].rchild == 0) {
            temp+=HuffTree[j].letter;
            j = len;
        }
    }
    if(j==len)
        cout<<temp<<endl;
    else
        cout<<"error"<<endl;
}

HuffMan::~HuffMan() {
    if (HuffTree)
        delete[]HuffTree;
}