Question

关于哈夫曼编码的一道题

假定用于通信的报文仅由8个字母：a，b，c，d，e，f，g，h组成，各字母在电文中出现的频率分别为5，25，3，6，10，11，36，4.试为这8个字母设计哈夫曼编码，给出相应的哈夫曼树，原电文压缩存储的总空间？并给出报文“abefhgeadcbb”的总码数？

Answer 1

下面是我写的一个程序，希望能满意。
#include<iostream>
using namespace std;

struct htnode
{
char ch;
int weight;
int parent;
int lchild,rchild;
};

class huffmantree
{
public:
void code(char str1[],int w[],int n);
void uncode(char str1[],char str2[],int n);
private:
htnode ht[3000];
void creathuffmantree(char str1[],int w[],int n);
void select(int pos,int &r1,int &r2);
};

void huffmantree::select(int pos,int &r1,int &r2)
{
r1=r2=0;
for(int i=1;i<=pos;i++)
{
if(ht[i].parent!=0)
continue;
if(r1==0)
r1=i;
else if(r2==0)
r2=i;
else if(ht[i].weight<ht[r1].weight)
r1=i;
else if(ht[i].weight<ht[r2].weight)
r2=i;
}
}

void huffmantree::creathuffmantree(char str1[],int w[],int n)
{
int pos;
for(pos=1;pos<=n;pos++)
{
ht[pos].weight=w[pos-1];
ht[pos].ch=str1[pos-1];
ht[pos].parent=ht[pos].lchild=ht[pos].rchild=0;
}
for(pos=n+1;pos<=2*n-1;pos++)
{
int r1,r2;
select(pos-1,r1,r2);
ht[r1].parent=ht[r2].parent=pos;
ht[pos].lchild=r1;
ht[pos].rchild=r2;
ht[pos].weight=ht[r1].weight+ht[r2].weight;
ht[pos].parent=0;
}
}

void huffmantree::code(char str1[],int w[],int n)
{
creathuffmantree(str1,w,n);
int start,c,i,f,j;
char *cd;
cd=new char[n];
cd[n-1]='\0';
for(i=1;i<=n;i++)
{
start=n-1;
for(c=i,f=ht[i].parent;f!=0;c=f,f=ht[c].parent)
{
if(ht[f].lchild==c)
cd[--start]='0';
else
cd[--start]='1';
}
cout<<"结点"<<str1[i-1]<<"的编码为："<<endl;
for(j=start;j<n;j++)
cout<<cd[j];
cout<<endl;
}
delete []cd;
}

void huffmantree::uncode(char str1[],char str2[],int n)
{
int i,f;
char c;
for(i=0;i<strlen(str2);)
{
for(f=2*n-1;ht[f].lchild!=0&&ht[f].rchild!=0;)
{
c=str2[i];
if(c=='1')
{
f=ht[f].rchild;
i++;
}
else
{
f=ht[f].lchild;
i++;
}
}
cout<<ht[f].ch;
}
cout<<endl;
}

int main()
{
char str[27],str2[3000],c;
char ch[]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
int cd[27],s,len,i,w[27];
sb1:
cout<<"请输入要编码的字符串"<<endl;
cin>>str;
huffmantree obj;
s=0;
memset(cd,0,sizeof(cd));
len=strlen(str);
for(i=0;i<len;i++)
{
cd[str[i]-'a']++;
}
for(i=0;i<26;i++)
{
if(cd[i])
{
str[s]=ch[i];
w[s]=cd[i];
s++;
}
}
cout<<"各节点编码如下："<<endl;
obj.code(str,w,s);
sb2:
cout<<"请输入要解码的01串"<<endl;
cin>>str2;
cout<<"解码结果如下："<<endl;
obj.uncode(str,str2,s);
cout<<"是否继续解码?(Y/N)"<<endl;
getchar();
c=getchar();
if(c=='Y')
goto sb2;
cout<<"是否继续编码?(Y/N)"<<endl;
getchar();
c=getchar();
if(c=='Y')
goto sb1;
return 0;
}
其中的哈夫曼树同一层上左边的权值比右边的小。

Answer 2

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>

#define ERROR 0;
#define OK 1;

typedef int Status;

typedef struct{
unsigned int weight;
int key;
int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char * * HuffmanCode;

int **KEY;
int N;

Status GetData(){
FILE *fp;
int key[100][2];
int ch,k,i,tem;
char str[16];
fp=fopen("data.txt","r");
k=0;

while(!feof(fp)){

ch=fgetc(fp);
i=0;
while(ch!=' '){
str[i]=ch;
i++;
ch=fgetc(fp);
}
str[i]='\0';
//printf("%d\n",strcmp(str,"空格"));
if(!strcmp(str,"空格")){

key[k][0]=' ';
}
else{
key[k][0]=str[0];

}

ch=fgetc(fp);
tem=0;
while(ch!='\n'&&ch!=EOF){
tem=tem*10+ch-'0';
ch=fgetc(fp);
}
key[k][1]=tem;
//printf("%c,%d\n",key[k][0],key[k][1]);
k++;

}
KEY=(int * *)malloc(k*sizeof(int *));
if(!KEY){
return ERROR;
}
for(i=0;i<k;i++){
KEY[i]=(int*)malloc(2*sizeof(int));
if(!KEY[i]){
return ERROR;
}
KEY[i][0]=key[i][0];
KEY[i][1]=key[i][1];
}
N=k;
fclose(fp);
return OK;
}

Status InitHuffmanTree(HuffmanTree &HT){
int i;
HT=(HTNode *)malloc((2*N-1)*sizeof(HTNode));
if(!HT){
return ERROR;
}

for(i=0;i<N;i++){

HT[i].weight=KEY[i][1];
HT[i].key=KEY[i][0];
HT[i].parent=-1;
HT[i].lchild=-1;
HT[i].rchild=-1;
}

for(;i<2*N-1;i++){
HT[i].parent=-1;
}

return OK;
}

void Select(HuffmanTree &HT,int n,int &fi,int &si){
int i=0,tem;
if(n>=2){
while(((HT+i)->parent)!=-1){
i++;
}
fi=i;

i++;
while((HT+i)->parent!=-1){
i++;
}
si=i;

if((HT+fi)->weight>(HT+si)->weight){
tem=fi;
fi=si;
si=tem;
}

for(i++;i<n;i++){
if((HT+i)->parent==-1){
if((HT+i)->weight<(HT+fi)->weight){
si=fi;
fi=i;

}
else{
if((HT+i)->weight<(HT+si)->weight){
si=i;
}
}
}
}
}

}

int HuffmanTreeAllReady(HuffmanTree HT,int m){
int sum=0,i;
for(i=0;i<m;i++){
if((HT+i)->parent==-1){
sum++;
}
if(sum>1){
return 0;
}

}
return 1;
}

void CreateHuffmanTree(HuffmanTree &HT,int n){
int s1,s2;
while(!HuffmanTreeAllReady(HT,n)){
Select(HT,n,s1,s2);

HT[n].parent=-1;
HT[n].lchild=s1;
HT[n].rchild=s2;
HT[n].weight=HT[s1].weight+HT[s2].weight;
HT[s1].parent=n;
HT[s2].parent=n;
n++;

}

}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int n){
char * str;
int len=0,tem,i,j;
unsigned int p;
str=(char *)malloc(n*sizeof(char));

for(i=0;i<n;i++){
p=i;
len=0;
while((tem=HT[p].parent)!=-1){

if(HT[tem].lchild==p){
str[len]='0';
}
else{
str[len]='1';
}
len++;
p=tem;
}

HC[i]=(char *)malloc((len+1)*sizeof(char));

if(HC[i]){
for(j=0;j<len;j++){
HC[i][j]=str[len-1-j];
}
HC[i][len]='\0';
str[len]='\0';
}
//printf("%d,%d\n",HC[i][0],len);
}
}

void OutputHuffmanCode(HuffmanCode HC){
int i;
for(i=0;i<N;i++){
printf("%c -> %s\n",KEY[i][0],HC[i]);
}
}

void Coding(HuffmanCode HC){
FILE *fp,*fq;
int ch,t;
fp=fopen("加密明文.txt","r");
fq=fopen("加密密文.txt","w+");
ch=fgetc(fp);
while(ch!=EOF){

if(ch==' '){
t=0;
}
else{
t=ch-'A'+1;
}
fputs(HC[t],fq);
//printf("%c",ch);
//printf("%s",HC[t]);
ch=fgetc(fp);
}
fclose(fp);
fclose(fq);
printf("OK\n");
}

void Decoding(HuffmanTree HT,int N){
FILE *fp,*fq;
int ch,t;
fq=fopen("解密明文.txt","w+");
fp=fopen("解密密文.txt","r");
ch=fgetc(fp);
while(ch!=EOF){
t=2*N-2;

while(HT[t].lchild!=-1&&HT[t].rchild!=-1){

if(ch=='0'){
t=HT[t].lchild;
}
else{
t=HT[t].rchild;
}
//printf("%c",ch);
ch=fgetc(fp);
}
//printf("%c",ch);
fputc(HT[t].key,fq);
//printf("%c",HT[t].key);
//printf("%s",HC[t]);
//ch=fgetc(fp);
}
fclose(fp);
fclose(fq);
printf("OK\n");
}

int main(){
HuffmanTree HT;
HuffmanCode HC;
int n,i,j,a,b,x;

GetData();

HC=(char * *)malloc((N)*sizeof(char *));

InitHuffmanTree(HT);

CreateHuffmanTree(HT,N);

HuffmanCoding(HT,HC,N);
//for(i=0;i<2*N-1;i++){
// printf("%d,%d,%d,%c,%d,%d\n",i,HT[i].parent,HT[i].weight,HT[i].key,HT[i].lchild,HT[i].rchild);
//}

printf("选项:1.输出哈夫曼编码 2.输入明文得到密文 3.输入密文得到明文 0.退出\n");
printf("输入选项:");

while(scanf("%d",&x),x){
switch(x){

case 1 :{
OutputHuffmanCode(HC);
break;
}

case 2 :{
Coding(HC);
}

case 3 :{
Decoding(HT,N);
}

}
printf("输入： 1.输出哈夫曼编码 2.输入明文得到密文 3.输入密文得到明文 0.退出\n");
printf("输入选项：");

}

return 0;
}

//我很少做注释，抱歉；
//data。txt中最后不要加回车！！！
//输入要规范
//认真琢磨吧

Answer 3

Huffman编码：数据通信用的二进制编码
编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列.
例 要传输的字符集 D={C,A,S,T, ; }
字符出现频率 w={ 2,4, 2, 3, 3}

T : 00
; : 01
A : 10
C : 110
S : 111

例 电文是{CAS;CAT}
其编码 “11010111011101000”

Answer 4

始终用权值最小的两个数相加的双亲结点权值.
以此类推可很容易得出哈夫曼树的编码。