/*
题意：给你一个字符串，首先是计算出一个按正常编码的编码长度，
其次是计算出一个用霍夫曼编码的编码长度，最后求正常编码的长度除以霍夫曼编码长度的值，保留一位小数。
*/
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cstdio>
using namespace std;
const int MAXN=250;
struct node
{
    int weight;//权值
    int lchild;//左孩子
    int rchild;//右孩子
    int parent;//父亲
}hufftree[MAXN];
int w[MAXN];
bool vis[MAXN];
//这个函数自我感觉比网上好，容易理解
int WPL(int rt,int tep)//rt为根，tep为深度
{
    if(hufftree[rt].lchild==-1&&hufftree[rt].rchild==-1)
    {
        return hufftree[rt].weight*tep;
    }
    else
    {
        return WPL(hufftree[rt].lchild,tep+1)+WPL(hufftree[rt].rchild,tep+1);
    }
}
void select(int &s1,int &s2,int n)
{
    int i;
    s1=s2=0;
    for(i=1;i<=n;i++)  //随便给s1,s2赋一个初值
    {
        if(hufftree[i].parent==-1)
        {
            if(s1==0)
            {
                s1=i;
            }
            else
            {
                s2=i;
                break;
            }
        }
    }
    if(hufftree[s1].weight>hufftree[s2].weight)
    {
        swap(s1,s2);
    }
    for(i=i+1;i<=n;i++)//i点就是s2或者s1中的其中一个，所以要跳过
    {
        if(hufftree[i].parent==-1)
        {
            if(hufftree[s1].weight>hufftree[i].weight)
            {
                s2=s1;
                s1=i;
            }
            else
            {
                if(hufftree[s2].weight>hufftree[i].weight)
                {
                   s2=i;
                }
            }
        }
    }
}
void Build_Tree(int n)//n个节点
{
    for(int i=1;i<=2*n-1;i++)//第一步，初始化为-1
    {
        hufftree[i].lchild=-1;
        hufftree[i].rchild=-1;
        hufftree[i].parent=-1;
    }
    for(int i=1;i<=n;i++)   //第二步，存放权值
    {
        hufftree[i].weight=w[i];
    }
    int num=n;//现在有n个节点赋值了
    for(int i=n+1;i<=2*n-1;i++)
    {
        int i1,i2;
        select(i1,i2,num);//第三步，找两个最小值
        num++;//找到一个加一
        hufftree[i].weight=hufftree[i1].weight+hufftree[i2].weight;
        hufftree[i].lchild=i1;
        hufftree[i].rchild=i2;
        hufftree[i1].parent=i;
        hufftree[i2].parent=i;
    }
}
int main()
{
    string s;
    while(1)
    {
        cin>>s;
        if(s=="END")break;
        memset(w,0,sizeof(w));
        memset(vis,false,sizeof(vis));
        int len=s.length();
        int k=1;
        for(int i=0;i<len;i++)
        {
            int cnt=0;
            for(int j=0;j<len;j++)
            {
                if(!vis[s[j]])
                {
                    if(s[i]==s[j])
                        cnt++;
                }
            }
            if(cnt!=0)
            {
                w[k++]=cnt;
                vis[s[i]]=true;
            }
        }
        k--;
        if(k==1)
        {
            printf("%d %d 8.0\n",8*len,len);
        }
        else
        {
            Build_Tree(k);
            /*int i=2*k-1;//这里是找根，不过没必要，因为根就是2*k-1
            for(i=1;i<=2*k-1;i++)
            {
                if(hufftree[i].parent==-1)break;
            }*/
            int lenWPL=WPL(2*k-1,0);
            printf("%d %d %.1lf\n",len*8,lenWPL,len*8.0/lenWPL);
        }
    }
    return 0;
}

• Re:哈夫曼模板，0MS水过 (3524) 204300604 2021-10-27 23:19:56
  • Re:哈夫曼模板，0MS水过 (2) adidde 2022-10-02 19:18:52
• Re:哈夫曼模板，0MS水过 (3524) agirl17 2021-12-22 23:50:58