huffman编码

//摘自网络

#include
#include

#define MAXSIZE 50

struct code{
        int c;
        int w;
        char code[MAXSIZE];
};

struct node{
        int w;
        int l,r,p;
};

//寻找最小和次小节点

void select_ht_node(node *ht, int n, int &min1, int &min2)
{
        int i;
        min1 = min2  = 0;
        for(i=1; i                if(ht[i].p == -1) {
                        if(ht[min1].w >= ht[i].w) {
                                min2 = min1;
                                min1 = i;
                        } else if(ht[min2].w > ht[i].w) {
                                min2 = i;
                        }
                }
        }
}

//创建huffman树

void creat_huff_tree(node *ht, int length, code *hc)
{
        int i,min1,min2;
        ht[0].w = 65536;
        for(i=1; i<=length; ++i) {
                ht[i].w = hc[i].w;
                ht[i].l = ht[i].r = ht[i].p = -1;
        }
        for(; i<2*length; ++i) {
                ht[i].l = ht[i].r = ht[i].p = -1;
        }
        for(i=length+1; i<2*length; ++i) {
                select_ht_node(ht, i, min1, min2);
                ht[min1].p = ht[min2].p = i;
                ht[i].l = min1;
                ht[i].r = min2;
                ht[i].w = ht[min1].w + ht[min2].w;
        }
}

创建huffman编码

void creat_huff_code(node *ht, int n, code *hc)
{
        for(int i=1; i<=n; ++i) {
                node th = ht[i];
                int tc = i;
                int top = -1;
                int flag[MAXSIZE];
                while(th.p != -1) {
                        top++;
                        if(ht[th.p].l == tc) { flag[top] = 'L'; tc = th.p; }
                        if(ht[th.p].r == tc) { flag[top] = 'R'; tc = th.p; }
                        th = ht[th.p];
                }
                int j = 0;
                while(top != -1) {
                        if(flag[top] == 'L') hc[i].code[j++] = '0';
                        if(flag[top] == 'R') hc[i].code[j++] = '1';
                        top--;
                }
                hc[i].code[j] = '\0';
        }
}

int main()
{
        code huff_code[MAXSIZE];
        node huff_tree[MAXSIZE];

//一般权值是通过计算得出的，这里简化了
        huff_code[1].c = 'A';
        huff_code[1].w = 4;
        huff_code[2].c = 'B';
        huff_code[2].w = 5;
        huff_code[3].c = 'C';
        huff_code[3].w = 6;
        huff_code[4].c = 'D';
        huff_code[4].w = 7;
        huff_code[5].c = 'E';
        huff_code[5].w = 10;
        huff_code[6].c = 'F';
        huff_code[6].w = 12;
        huff_code[7].c = 'G';
        huff_code[7].w = 18;

        creat_huff_tree(huff_tree, 7, huff_code);
        creat_huff_code(huff_tree, 7, huff_code);
        for(int i=1; i<=7; ++i) {
                printf("%c %s\n", huff_code[i].c, huff_code[i].code);
        }

        return 0;
}