问题 R: 赫夫曼编码

63 阅读 0 评论 42 点赞

我是靠谱客的博主鲜艳雪碧，最近开发中收集的这篇文章主要介绍问题 R: 赫夫曼编码，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题 R: 赫夫曼编码
时间限制: 1 Sec
内存限制: 128 MB
提交: 438
解决: 117
[提交][状态][讨论版]
题目描述
赫夫曼编码能够产生最短的报文。以报文“ABCDABCDABCABDABAA”为例，A编为0，B对应10，C对应110，D对应111，整体的报文长度为35位二进制。相比于定长的ASCII码，压缩比达到了18*8/35=4.1。
输入
输入有一系列的字符串组成，每个字符串占据一行。字符串仅包含大写字母和下划线。字符串“END” 表示处理结束，不应对其处理。
输出
对每一个字符串，输出其ASCII编码的比特位长度，赫夫曼编码的比特位长度，以及二者之比，精确到小数点后一位。
样例输入
ABCDABCDABCABDABAA
AAAAAAAAAAAAAAAAAA
END
样例输出
144 35 4.1
144 18 8.0
提示
要求书中算法取权值最小的部分使用堆来实现

RE了好久，后来被提醒叶子深度就是编码长度才意识到，直接判断叶子深度总算AC了，但是堆那里还可以优化（因为学的不精，这里只是一次次的重新建树，而不是调整堆-_-)

#include <bits/stdc++.h>
using namespace std;
char String[10000];
int P[700];
typedef struct
{
int weight,order;
int parent,Lchild,Rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
//!--------------------------------------------------------------------------------
int cmp(const void *a,const void *b)
{
return (*(HTNode *)a).order - (*(HTNode *)b).order;
}
int CMP(const void *a,const void *b) { return *(int *)b - *(int *)a;}
//!--------------------------------------------------------------------------------
void HeapAdjust(HuffmanTree &Judge,int s,int m)
{
HTNode rc = Judge[s];
for(int i = 2*s;i<=m;i*=2)
{
if(i<m && Judge[i].weight<Judge[i+1].weight) i++;
if(rc.weight >= Judge[i].weight) break;
Judge[s]= Judge[i]; s = i;
}
Judge[s]= rc;
}
void CreatHeap(HuffmanTree &Judge,int n)
{//把[1..n]建成大根堆
for(int i = n/2;i>0;i--)
HeapAdjust(Judge,i,n);
}
void HeapSort(HuffmanTree &Judge,int n)
{
CreatHeap(Judge,n);
for(int i = n;i > 1;i--)
{
HTNode x = Judge[1];
Judge[1] = Judge[i];
Judge[i] = x;
HeapAdjust(Judge,1,i-1);
}
}
//!--------------------------------------------------------------------------------
void Select(HuffmanTree &HT,int n,int &s1,int &s2)
{
HuffmanTree Copy = new HTNode[n+1];
for(int i=1;i<=n;i++)
{
Copy[i].weight = HT[i].weight;
Copy[i].parent = HT[i].parent;
Copy[i].order = i;
}
HeapSort(Copy,n);///!确定序列
int I=0;
for(int i=1;i<=n;i++) if(!Copy[i].parent) {s1 = Copy[i].order;I=i;break;}
for(int i=I+1;i<=n;i++) if(!Copy[i].parent) {s2 = Copy[i].order;break;}
}
void CreateHuffmanTree(HuffmanTree &HT,int n)
{
if(n<=1) return;
int m = 2*n-1;
HT = new HTNode[m+1];
for(int i=1;i<=m;i++)
{
HT[i].parent = 0;
HT[i].Lchild = 0;
HT[i].Rchild = 0;
}
for(int i=1;i<=n;i++) HT[i].weight = P[i];
for(int i = n+1;i<=m;i++)
{
int s1,s2;Select(HT,i-1,s1,s2);
HT[s1].parent = i;HT[s2].parent = i;
HT[i].Lchild = s1;HT[i].Rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
}
int Cal(int len)
{
memset(P,0,sizeof(P));
int Label = 0;
for(int i=1;i<=len;i++)
{
int value =
String[i] - 'A' + 50;
if(!P[value]) Label++;
P[value]++;
}
qsort(P+1,600,sizeof(P[0]),CMP);///!确定序列
sort(P+1,P+1+Label);///!确定序列
return Label;
}
//!--------------------------------------------------------------------------------
void CreateHuffmanCode(HuffmanTree &HT,HuffmanCode &HC,int n)
{
HC = new char*[n+1];
if(n==1) {HC[1][0] = '0';HC[1][1] = '';return;}
char *cd = new char[n];
cd[n-1]='';
for(int i=1;i<=n;i++)
{
int start = n-1;
int c = i,f = HT[i].parent;
while(f)
{
--start;
if(HT[f].Lchild == c) cd[start] = '0';
else
cd[start] = '1';
c = f;f = HT[f].parent;
}
HC[i] = new char[n-start];
strcpy(HC[i],&cd[start]);
}
}
int Handle(HuffmanTree HT,int n)
{
if(n==1) return P[1];
int ans = 0;
for(int i=1;i<=n;i++)
{
int Parent;int deep = 0;
Parent = HT[i].parent;
while(Parent)
{
deep++;
Parent = HT[Parent].parent;
}
ans += P[i]*deep;
}
return ans;
}
/*
//!------------------test-----------------------------------------------------
void Print_Huffman(HuffmanTree HT,int n)
{
printf("-----------------------------------------------------n");
for(int i=1;i<=2*n-1;i++)
printf("结点序号: %2d
权值: %2d
父亲: %2dn",i,HT[i].weight,HT[i].parent);
}
//!--------------------------------------------------------------------------------
*/
int main(void)
{
//freopen("E:\test.txt","r",stdin);
//freopen("E:\tsst.txt","w",stdout);
while(gets(String+1)!=NULL)
{
if(!strcmp("END",String+1)) break;
int len = strlen(String+1);
int Label = Cal(len);
HuffmanTree HT;HuffmanCode HC;
CreateHuffmanTree(HT,Label);
//Print_Huffman(HT,Label);
int ans = Handle(HT,Label);
printf("%d %d %.1lfn",8*len,ans,(double)8*len/(double)ans);
}
}