> /*
> 题意：给你一个字符串，首先是计算出一个按正常编码的编码长度，
> 其次是计算出一个用霍夫曼编码的编码长度，最后求正常编码的长度除以霍夫曼编码长度的值，保留一位小数。
> */
> #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水过 (2) adidde 2022-10-02 19:18:52