哈夫曼树和哈夫曼编码

#include<bits/stdc++.h>

using namespace std;

struct node{
    int weight;
    int parent;
    int left;
    int right;
};

class Huffman{
public:
    Huffman(int n, const int w[]);
    void HuffmanCode(int n);
    void Decode(int m, char *s);
    ~Huffman();
private:
    node *root;
    char **code;
    int getMin(int n);
    void select(int n, int &s1, int &s2);
};

Huffman:: Huffman(int n, const int w[]) {
    int m = 2*n-1, i;
    int s1, s2;

    if(n <= 1) {
        cout << "Size error!" << endl;
        return;
    }

    root = new node[m+5];
    if(!root) {
        cout << "Malloc error!" << endl;
        exit(-1);
    }

    // 初始化
    node *p = root+1;
    for (i = 1; i <= n; ++i, ++(p)) {
        p->weight = w[i];
        p->parent = 0;
        p->right = 0;
        p->left = 0;
    }
    while(i <= m) {
        p->parent = 0;
        p++;
        i++;
    }

    for (i = n+1; i <= m; ++i) {
        select(i-1, s1, s2);
        root[s1].parent = root[s2].parent = i;
        root[i].left = s1;
        root[i].right = s2;
        root[i].weight = root[s1].weight+root[s2].weight;
    }
}

void Huffman:: HuffmanCode(int n) {
    code = new char*[n+5];
    if(!*code) {
        cout << "Malloc error1" << endl;
        exit(-1);
    }

    char *tmp = new char[n+5];
    //char debug[100], dd;
    if(!tmp) {
        cout << "Malloc error2";
        exit(-1);
    }
    tmp[n-1] = 0;
    int st;
    for (int i = 1; i <= n; ++i) {
        st = n-1;
        for (int j = i, f = root[j].parent; f; j = f, f = root[f].parent) {
            if(root[f].left == j)
                tmp[--st] = '0';
            else if(root[f].right == j)
                tmp[--st] = '1';
            //dd = tmp[st+1]; // debug
            //cout << "dd: " << dd << endl;
        }
        code[i] = new char[n-st];
        //strcpy(debug, tmp+st);
        //cout << "debug: " << debug << endl;
        strcpy(code[i], tmp+st);
    }
    delete []tmp;
    for (int i = 1; i <= n; ++i) {
        cout << "The Huffmancode is " << root[i].weight << " : " << code[i] << endl;
    }
}

void Huffman:: Decode(int n, char *s) {
    int len = strlen(s), pt = 2*n-1;
    for (int i = 0; i < len; ++i) {
        if(s[i] == '0') {
            pt = root[pt].left;
            if(pt <= n) {
                cout << root[pt].weight << " ";
                pt = 2*n-1;
            }
        } else if(s[i] == '1') {
            pt = root[pt].right;
            if(pt <= n) {
                cout << root[pt].weight << " ";
                pt = 2*n-1;
            }
        }
    }
    cout << endl;
}

Huffman:: ~Huffman() {
    delete []root;
    delete []code;
    cout << "The Huffmantree has been destroyed." << endl;
}

int Huffman:: getMin(int n) {
    int Min = 100;
    int flag = 0; //用来记录已遍历过的结点
    for(int i = 1; i <= n; ++i) {
        if ((root + i)->weight < Min && (root + i)->parent == 0) {
            Min = (root + i)->weight;
            flag = i;
        }
    }
    //给选中的结点置 1, 下次不需要再遍历
    (root + flag)->parent = 1;
    return flag;
}

void Huffman:: select(int n, int &s1, int &s2) {
    s1 = getMin(n);
    s2 = getMin(n);
    //目的是 s1 的权值要不大于 s2 的权值
    if ((root + s1)->weight > (root + s2)->weight) {
        swap(s1, s2);
    }
}

int main() {
    int n;
    cin >> n;
    int w[5];
    for (int i = 1; i <= n; ++i) {
        cin >> w[i];
    }
    Huffman h_test(n, w);
    h_test.HuffmanCode(n);
    h_test.Decode(n, "10011");
    return 0;
}


上一篇:设计模式之工厂模式(大话设计模式C++实现)


下一篇:enums