哈夫曼編碼原理：哈夫曼編碼原理

練習(xí)題目：哈夫曼編碼

其中第一個即是自底向上的硕舆，另外還有幾個練習(xí)題惋增，可以進行相應(yīng)練習(xí)补胚。

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


using namespace std;
//輸入數(shù)字個數(shù) 
const int maxn = 110;
//輸入的需編碼的數(shù)字?jǐn)?shù)組 
int w[maxn];

//哈夫曼樹節(jié)點定義
//每個節(jié)點包括其權(quán)值壹哺，父親節(jié)點指針以及左右孩子結(jié)點指針 
typedef struct{
    int wt;
    int parent, lchild, rchild;
}hftree;

/***************************************************************
/*從已有的節(jié)點中選出權(quán)值最小的兩個結(jié)點
/*參數(shù)：hftree倾剿，根據(jù)節(jié)點權(quán)值建立后的哈夫曼樹鸳吸，n當(dāng)前已有節(jié)點個數(shù)
/*      a第一小的節(jié)點熏挎，b第二小的節(jié)點 
*****************************************************************/
void min_two(hftree* tree, int n, int &a, int &b){
    //m初始設(shè)置為一個很大的數(shù) 
    int m = 0x3fffffff;
    //在已有的節(jié)點中尋找兩個權(quán)值最小的節(jié)點 
    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;
        }
    }
    //由于當(dāng)選出兩個最小的節(jié)點之后，我們將兩個節(jié)點所放的左右順序不同時
    //得到的編碼順序也是不同的晌砾，為了得到一個固定的編碼坎拐，同時為了能夠
    //AC題目，將兩個中更小的放在左邊
    /****若無此步得到的編碼將是不唯一的 ***/
    if(a > b)
        swap(a, b);
}
/*********************************************************************************
/*         哈夫曼樹的建立以及編碼過程
/* 根據(jù)輸入的n個權(quán)值初始化n個葉子節(jié)點，再依次選擇未合并的節(jié)點（包括新節(jié)點）中的最小
/*的兩個權(quán)值節(jié)點進行合并哼勇，直到只剩下一個未合并的節(jié)點即根結(jié)點時結(jié)束都伪，
/* 然后則進行自底向上的編碼，每次都從某一個葉子節(jié)點出發(fā)积担，如果是其父節(jié)點的左孩子則添0 
/*如果是右孩子則添1陨晶，直到碰到根結(jié)點結(jié)束 
/********************************************************************************/
void HuffmanCode(hftree* &t, char** &code, int w[], int n){
    //當(dāng)輸入的n為1或者0時無需編碼 
    if(n <= 1)
        return ;
    //由于每次在找兩個節(jié)點并合成時，都會生成一個新的節(jié)點帝璧，而n個結(jié)點則會生成n-1個
    //而生成的節(jié)點是哈夫曼樹中的非葉子節(jié)點先誉，因此需要定義足夠的數(shù)組空間 
    int m = 2 * n - 1;
    //根據(jù)得到的節(jié)點個數(shù)為哈夫曼樹分配空間，0號空間不使用 
    t = (hftree *)malloc((m+1)*sizeof(hftree));
    //使用初始的n個數(shù)初始化哈夫曼樹的烁，相當(dāng)于初始化葉子節(jié)點 
    for(int i = 1; i <= n; i++){
        t[i].wt = w[i];
        t[i].parent = t[i].lchild = t[i].rchild = 0;
    }
    //對非葉子節(jié)點初始化信息褐耳，由于它們是之后生成的，因此沒有初始化權(quán)值信息 
    for(int i = n+1; i <= m; i++)
        t[i].parent = t[i].lchild = t[i].rchild = 0;
    //生成n-1個非葉子節(jié)點渴庆，每次都選擇已經(jīng)存在的且未合并的節(jié)點中的兩個最小節(jié)點
    //選出后將其合并铃芦，生成新的節(jié)點（此處當(dāng)parent為0時可以代表還未合并） 
    for(int i = n+1; i <= m; i++){
        int a, b;
        min_two(t, i-1, a, b);
        //對合并的節(jié)點進行信息修改，包括權(quán)值襟雷，父節(jié)點指向刃滓，左右孩子指向 
        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個節(jié)點需要的編碼串的空間，由于一個編碼串可用一維指針表示
    //而n個時耸弄，便可用一個二維指針表示咧虎，它的每一維都對應(yīng)一個數(shù)的編碼 
    code = (char **)malloc((n+1)*sizeof(char *));
    //臨時存儲某個數(shù)的編碼串 
    char *cd = (char *)malloc(n*sizeof(char));
    //由于是自底向上的，所以進行逆向編碼叙赚，首先初始化末尾為字符串結(jié)束符 
    cd[n-1] = '\0';
    //對n個數(shù)進行編碼
    for(int i = 1; i <= n; i++){
        int index = n - 1;
        //從每一個i所在的葉子節(jié)點開始向上老客，如果當(dāng)前節(jié)點是其父節(jié)點的左孩子則添加一個0
        //否則添加1，當(dāng)回溯到根結(jié)點則i所在的葉子節(jié)點編碼完成 
        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葉子節(jié)點的編碼串賦值到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;
}