1761 Problem B 算法6-13：自頂向下的赫夫曼編碼

問題 B: 算法6-13：自頂向下的赫夫曼編碼

時間限制: 1 Sec  記憶體限制: 32 MB

送出: 15  解決: 13

題目描述

在本題中，我們将要讨論的是自頂向下的赫夫曼編碼算法。從根出發，周遊整棵赫夫曼樹進而求得各個葉子結點所表示的字元串。算法的關鍵部分可以表示如下：

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

輸入

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

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

輸出

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

樣例輸入

8
5 29 7 8 14 23 3 11      

樣例輸出

0110
10
1110
1111
110
00
0111
010      

提示

經驗總結

正确代碼

#include <cstdio>
#include <climits>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=110;
struct HuffNode
{
    int w,parent,lchild,rchild;
}Node[maxn*2];
void SearchMin(int &a,int &b,int n)
{
    int min=INT_MAX;
    for(int i=1;i<=n;++i)
    {
        if(Node[i].parent==0&&Node[i].w<min)
        {
            min=Node[i].w;
            a=i;
        }
    }
    min=INT_MAX;
    for(int i=1;i<=n;++i)
    {
        if(Node[i].parent==0&&Node[i].w<min&&i!=a)
        {
            min=Node[i].w;
            b=i;
        }
    }
    if(a>b)
    {
        swap(a,b);
    }
}
void HuffmanCode(int n,int * w,char * * &ans)
{
    int m=2*n-1;
    for(int i=1;i<=n;++i)
    {
        Node[i].parent=Node[i].lchild=Node[i].rchild=0;
        Node[i].w=w[i];
    }
    for(int i=n+1;i<=m;++i)
    {
        int a,b;
        SearchMin(a,b,i-1);
        Node[i].lchild=a;
        Node[i].rchild=b;
        Node[i].w=Node[a].w+Node[b].w;
        Node[i].parent=0;
        Node[a].parent=Node[b].parent=i;
    }
    int c,f,index=0;
    char temp[n];
    ans=new char * [n+1];
    for(int i=1;i<=m;++i)
        Node[i].w=0;
    while(m)
    {
        if(Node[m].w==0)
        {
            Node[m].w=1;
            if(Node[m].lchild!=0)
            {
                m=Node[m].lchild;
                temp[index++]='0';
            }
            else if(Node[m].rchild==0)
            {
                ans[m]=new char[index+1];
                temp[index]='\0';
                strcpy(ans[m],temp);
            }
        }
        else if(Node[m].w==1)
        {
            Node[m].w=2;
            if(Node[m].rchild!=0)
            {
                m=Node[m].rchild;
                temp[index++]='1';
            }
        }
        else
        {
            Node[m].w=0;
            m=Node[m].parent;
            --index;
        }
    }
}
int main()
{
    int n,w[maxn];
    char * * ans;
    while(~scanf("%d",&n))
    {
        for(int i=1;i<=n;++i)
        {
            scanf("%d",&w[i]);
        }
        HuffmanCode(n,w,ans);
        for(int i=1;i<=n;++i)
        {
            printf("%s\n",ans[i]);
        }
    }
    delete ans;
    return 0;
}