文章

4

粉丝

0

获赞

2

访问

5673

头像
记录一下,哈夫曼编码1562
经验总结
发布于2021年2月24日 12:29
阅读数 488

#include<iostream>
#include<queue>
#include<string>
#include<stdio.h>
#include<cstring>

using namespace std;
int a[30];
int main()
{
    int len;
    int ans;
    int tmp;
    double cpsn;
    string s;

    while (cin >> s)
    {
        ans = 0;
		if (s == "END")  break;
        len = s.size();
        memset(a, 0, sizeof(a));

        for (int i = 0; i < len; i++)
        {

            if (s[i] == '_')
            {
                a[27]++;
            }else
            {
                a[s[i] - 'A']++;
            }
        }
        priority_queue<int, vector<int>, greater<int> > q;

        for (int i = 0; i <= 27; i++)
        {
            if (a[i] > 0)
                q.push(a[i]);
        }
		if (q.size() == 1) ans = q.top();  //考虑单一字符的字符串的特殊情况处理
        while (q.size() > 1)
        {
            tmp = q.top();
            q.pop();
            tmp += q.top();
            q.pop();
            q.push(tmp);
            ans += tmp;
        }
        q.pop();

        printf("%d %d ",len*8,ans);
        cpsn = (len * 8.00) / ans;
        printf("%0.1lf\n",cpsn);

    }

    return 0;
}

要记得考虑单一字符组成一个字符串的特殊情况处理

另外,注意等号赋值和判断的区别,避免再犯这种低级错误



登录后发布评论

暂无评论,来抢沙发