main

#include "Header.h"
#include "typ.h"
#include "func.h"

using namespace std;
const int N = 1e5;
int w[N];
int main()
{
   
    HuffmanTree HT;
    HuffmanCode HC;
    int  n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
   
        cin>>w[i];
    }
    CreatHT(HT,w,n);
    HuffmanCoding(HT,HC, n);
    string s;
    cout<<"请输入编码:"<<endl;
    cin>>s;
    HuffmanDecode(HT,s,2*n-1);
    return 0;
}

func.h

//从1-e的范围内找到双亲为0，而且权值最小的两个节点
void select(HuffmanTree HT,int e,int &s1,int &s2)
{
   
    int mi = 1e9;
    for(int i=1;i<=e;i++)
    {
   
        if(HT[i].p==0&&HT[i].w<mi)
        {
   
            mi = HT[i].w;
            s1 = i;
        }
    }
    mi = 1e9;
    for(int i=1;i<=e;i++)
    {
   
        if(HT[i].p==0&&HT[i].w<mi&&i!=s1)
        {
   
            mi = HT[i].w;
            s2 = i;
        }
    }
}
void CreatHT(HuffmanTree &HT,int w[],int n)
{
   
    if(n<=1) return ;
    int m = n*2-1;
    //动态数组，申请m+1个单元，因为0号单元不使用
    HT = (HuffmanTree)malloc(sizeof(HTNode)*(m+1));
    if(!HT) exit(OVERFLOW);
    else
    {
   
        //初始化HT
        for(int i=1; i<=m; i++)
        {
   
            if(i<=n) HT[i]={
   w[i],0,0,0};
            else HT[i]={
   0,0,0,0};
        }
        for(int i=n+1;i<=m;i++)
        {
   
            //从前i-1个节点中选最小的两个节点来构造新的节点
            int s1,s2;
            select(HT,i-1,s1,s2);
            HT[s1].p = i; HT[s2].p = i;//i个是s1 s2的父亲
            HT[i].lchild = s1; HT[i].rchild = s2;
            HT[i].w = HT[s1].w + HT[s2].w;
        }
    }
    cout<<"HT:"<<endl;
    for(int i=1; i<=m; i++)
    {
   
        cout<<HT[i].w<<" "<<HT[i].p<<" "<<HT[i].lchild<<" "<<HT[i].rchild<<endl;
    }
}
//编码
void HuffmanCoding(HuffmanTree HT,HuffmanCode &HC,int n)
{
   
    //分配n个编码的头指针
    HC = (HuffmanCode)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 start = n-1;
        int j,f;
        //从叶子到根遍历,依次往上
        for(j=i,f=HT[i].p; f!=0; j=f,f=HT[f].p)
        {
   
            if(HT[f].lchild==j) cd[--start] = '0';
            else cd[--start] = '1';
        }
        HC[i] = (char*)malloc((n-start)*sizeof(char));
        strcpy(HC[i],&cd[start]);//把cd数组下标start及其以后的值赋给HT[i]
    }
    free(cd);
    cout<<"HTcode:"<<endl;
    for(int i=1 ;i<=n; i++)
    {
   
        cout<<HT[i].w<<" "<<HC[i]<<endl;
    }
}
//译码
void HuffmanDecode(HuffmanTree HT,string s,int m)
{
   
    for(int i=0,j=m; i<s.size(); i++)
    {
   
        if(s[i]=='0') j = HT[j].lchild;
        else j = HT[j].rchild;
        if(HT[j].lchild==0)
        {
   
            cout<<HT[j].w<<" ";
            j = m;
        }

    }
}