codeup|問題 A: 算法6-12：自底向上的赫夫曼編碼

題目描述

在通訊領域，經常需要将需要傳送的文字轉換成由二進制字元組成的字元串。在實際應用中，由于總是希望被傳送的内容總長盡可能的短，如果對每個字元設計長度不等的編碼，且讓内容中出現次數較多的字元采用盡可能短的編碼，則整個内容的總長便可以減少。另外，需要保證任何一個字元的編碼都不是另一個字元的編碼字首，這種編碼成為字首編碼。

而赫夫曼編碼就是一種二進制字首編碼，其從葉子到根（自底向上）逆向求出每個字元的算法可以表示如下：

在本題中，讀入n個字元所對應的權值，生成赫夫曼編碼，并依次輸出計算出的每一個赫夫曼編碼。

輸入

輸入的第一行包含一個正整數n，表示共有n個字元需要編碼。其中n不超過100。

第二行中有n個用空格隔開的正整數，分别表示n個字元的權值。

輸出

共n行，每行一個字元串，表示對應字元的赫夫曼編碼。

樣例輸入 Copy

8

5 29 7 8 14 23 3 11

樣例輸出 Copy

0110

10

1110

1111

110

00

0111

010

提示

赫夫曼樹又名最優二叉樹，它是一類帶權路徑長度最小的二叉樹。通過構造赫夫曼樹，我們可以得到赫夫曼編碼，進而使得通信能夠得到更高的效率。在本題中，構造赫夫曼樹的過程使用了從葉子到根的逆向順序，另外，還有一種從根出發直到葉子的赫夫曼編碼構造算法，這将在下一題中進行讨論。

代碼

#include<iostream>
#include<limits.h>

using namespace std;
const int maxn = 110;
int n, w[maxn];//結點個數 和 權值數組
string code[maxn];//存放編碼  順序就是元素輸入權值的順序(不是權值排序後的順序)
struct huffManNode {
    int weight, lchild, rchild, parent;//需要知道父親 以判斷是否是葉子結點
} HMNode[2 * maxn - 1];

void Min(int index, int &s1, int &s2) {//查找範圍[1,index]
    int minw = INT_MAX;
    for (int i = 1; i <= index; i++) {
        if (HMNode[i].parent == 0 && HMNode[i].weight < minw) {
            minw = HMNode[i].weight;
            s1 = i;
        }
    }
    minw = INT_MAX;
    for (int i = 1; i <= index; i++) {
        if (HMNode[i].parent == 0 && HMNode[i].weight < minw && i != s1) {
            minw = HMNode[i].weight;
            s2 = i;
        }
    }
    if (s1 > s2) swap(s1, s2);//此句必要,保證樹的結構的唯一性
}

void HuffManEncoding() {
    if (n < 1) return;//一個結點 随便編碼
    int m = 2 * n - 1;//Huffman樹總結點數
    for (int i = 1; i <= n; i++) {
        HMNode[i].weight = w[i];
        HMNode[i].parent = HMNode[i].lchild = HMNode[i].rchild = 0;
    }
    int s1, s2;
    for (int i = n + 1; i <= m; i++) {
        Min(i - 1, s1, s2);
        HMNode[i].lchild = s1;
        HMNode[i].rchild = s2;
        HMNode[i].parent = 0;
        HMNode[s1].parent = HMNode[s2].parent = i;
        HMNode[i].weight = HMNode[s1].weight + HMNode[s2].weight;
    }
    char *temp = new char[n];
    int start;
    for (int i = 1; i <= n; i++) {
        start = n;
        temp[--start] = '\0';      //f==0到根了
        for (int j = i, f = HMNode[j].parent; f != 0; f = HMNode[j].parent) {//j是孩子 f是父親 一直往上走 直到走到根
            if (HMNode[f].lchild == j) temp[--start] = '0';//左0
            else temp[--start] = '1';//右1
            j = f;
        }
        code[i] = temp + start;
    }
    delete temp;
}

int main() {
    while (cin >> n) {
        for (int i = 1; i <= n; i++)cin >> w[i];
        HuffManEncoding();
        for (int i = 1; i <= n; i++) cout << code[i] << endl;
    }
    return 0;
}