用哈弗曼树对字符串(可能包括空格)编码,返回压缩后占用的最小位数,OJ显示答案错误。
自己尝试了一些例子,在字符串长度不是非常长的时候,输出数值是没有问题的。然后当字符串长度为好几百时会有问题。
代码如下,请教各位我的代码错在哪里,是哪里的思路出现了问题?
#include <iostream>
#include <string>
using namespace std;
int main()
{
string input;
getline(cin, input);
int length = (int)input.length();
int freq[256];
for (int i = 0; i < 256; i++) freq[i] = 0;
for (int i = 0; i < length; i++) freq[int(input[i]) + 128]++;
int a[256];
for (int i = 0; i < 256; i++) a[i] = 0;
int n=0;
for(int i=0;i<256;i++){
if(freq[i]!=0){
a[n]=freq[i];
n++;
}
}
int temp;
for(int i=1; i<=n-1; i++)
{
for(int j=1;j<=n-i;j++)
{
if(a[j-1]>a[j])
{temp=a[j-1];
a[j-1]=a[j];
a[j]=temp;
}
}
}
int B=0;
int sum=0;
while(n>1){
a[0]=a[0]+a[1];
a[1]=257;
sum=sum+a[0];
for(int i=1; i<=n-1; i++){
for(int j=1;j<=n-i;j++){
if(a[j-1]>a[j]){
temp=a[j-1];
a[j-1]=a[j];
a[j]=temp;
}
}
}
n--;
}
cout<<sum;
return 0;
}