自底向上的哈夫曼编码

哈夫曼编码原理：哈夫曼编码原理

练习题目：哈夫曼编码

其中第一个即是自底向上的，另外还有几个练习题，可以进行相应练习。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>


using namespace std;
//输入数字个数 
const int maxn = 110;
//输入的需编码的数字数组 
int w[maxn];

//哈夫曼树节点定义
//每个节点包括其权值，父亲节点指针以及左右孩子结点指针 
typedef struct{
    int wt;
    int parent, lchild, rchild;
}hftree;

/***************************************************************
/*从已有的节点中选出权值最小的两个结点
/*参数：hftree，根据节点权值建立后的哈夫曼树，n当前已有节点个数
/*      a第一小的节点，b第二小的节点 
*****************************************************************/
void min_two(hftree* tree, int n, int &a, int &b){
    //m初始设置为一个很大的数 
    int m = 0x3fffffff;
    //在已有的节点中寻找两个权值最小的节点 
    for(int i = 1; i <= n; i++){
        if(tree[i].parent == 0 && m > tree[i].wt){
            m = tree[i].wt;
            a = i;
        }
    }
    //寻找第二个 
    m = 0x3fffffff;
    for(int i = 1; i <= n; i++){
        if(tree[i].parent == 0 && m > tree[i].wt && i != a){
            m = tree[i].wt;
            b = i;
        }
    }
    //由于当选出两个最小的节点之后，我们将两个节点所放的左右顺序不同时
    //得到的编码顺序也是不同的，为了得到一个固定的编码，同时为了能够
    //AC题目，将两个中更小的放在左边
    /****若无此步得到的编码将是不唯一的 ***/
    if(a > b)
        swap(a, b);
}
/*********************************************************************************
/*         哈夫曼树的建立以及编码过程
/* 根据输入的n个权值初始化n个叶子节点，再依次选择未合并的节点（包括新节点）中的最小
/*的两个权值节点进行合并，直到只剩下一个未合并的节点即根结点时结束，
/* 然后则进行自底向上的编码，每次都从某一个叶子节点出发，如果是其父节点的左孩子则添0 
/*如果是右孩子则添1，直到碰到根结点结束 
/********************************************************************************/
void HuffmanCode(hftree* &t, char** &code, int w[], int n){
    //当输入的n为1或者0时无需编码 
    if(n <= 1)
        return ;
    //由于每次在找两个节点并合成时，都会生成一个新的节点，而n个结点则会生成n-1个
    //而生成的节点是哈夫曼树中的非叶子节点，因此需要定义足够的数组空间 
    int m = 2 * n - 1;
    //根据得到的节点个数为哈夫曼树分配空间，0号空间不使用 
    t = (hftree *)malloc((m+1)*sizeof(hftree));
    //使用初始的n个数初始化哈夫曼树，相当于初始化叶子节点 
    for(int i = 1; i <= n; i++){
        t[i].wt = w[i];
        t[i].parent = t[i].lchild = t[i].rchild = 0;
    }
    //对非叶子节点初始化信息，由于它们是之后生成的，因此没有初始化权值信息 
    for(int i = n+1; i <= m; i++)
        t[i].parent = t[i].lchild = t[i].rchild = 0;
    //生成n-1个非叶子节点，每次都选择已经存在的且未合并的节点中的两个最小节点
    //选出后将其合并，生成新的节点（此处当parent为0时可以代表还未合并） 
    for(int i = n+1; i <= m; i++){
        int a, b;
        min_two(t, i-1, a, b);
        //对合并的节点进行信息修改，包括权值，父节点指向，左右孩子指向 
        t[i].wt = t[a].wt + t[b].wt;
        t[i].lchild = a;
        t[i].rchild = b;
        t[a].parent = t[b].parent = i;
    }
    
    //以下进行编码操作
    //申请n个节点需要的编码串的空间，由于一个编码串可用一维指针表示
    //而n个时，便可用一个二维指针表示，它的每一维都对应一个数的编码 
    code = (char **)malloc((n+1)*sizeof(char *));
    //临时存储某个数的编码串 
    char *cd = (char *)malloc(n*sizeof(char));
    //由于是自底向上的，所以进行逆向编码，首先初始化末尾为字符串结束符 
    cd[n-1] = '\0';
    //对n个数进行编码
    for(int i = 1; i <= n; i++){
        int index = n - 1;
        //从每一个i所在的叶子节点开始向上，如果当前节点是其父节点的左孩子则添加一个0
        //否则添加1，当回溯到根结点则i所在的叶子节点编码完成 
        for(int c=i, f=t[i].parent; f != 0; c=f, f=t[f].parent){
            if(t[f].lchild == c)
                cd[--index] = '0';
            else
                cd[--index] = '1';
        }
        code[i] = (char*)malloc((n-index)*sizeof(char));
        //将i叶子节点的编码串赋值到code中，存储起来 
        strcpy(code[i], cd+index);
    }
    //释放空间 
    delete cd;
}


int main() {
    int n, a;
    while(scanf("%d", &n) != EOF){
        for(int i = 1; i <= n; i++)
            scanf("%d", &w[i]);
        hftree *ht;
        char** code;
        HuffmanCode(ht, code, w, n);
        for(int i = 1; i <= n; i++)
            printf("%s\n", code[i]);
        delete ht;
        delete code;
    }
    return 0;
}