问题: 哈夫曼编码,英文名称 Huffman Coding，有时也翻译为霍夫曼编码，在1952年提出的，是最好的编码方式。哈夫曼编码在电子通讯方面有着重要的应用，同时也广泛应用于数据压缩，其压缩率通常在20% 90%之间 赫夫曼码是可变字长编码(VLC)的一种。哈夫曼树是最优二叉树， 带权路径长度最小的二叉树。
原理:
假设有几个数字40,10,20,16,14。
首先将这五个数字按照从小到大的顺序排列：10, 14，16，20, 40。
构建哈夫曼树：
1.首先选取10,14
2.重新排序：16,20,24,40
3.重新排序24,36,40,60
4.按照二叉树左0右1，构建哈夫曼树
所以最终得到数字10的编码为100，数字14的编码为101，数字16的编码为110，数字20的编码为111，数字40的编码为0。
代码：
运行结果:
#include <stdio.h>#include <string.h>
#include <stdlib.h>
#define TRUE 1
#define ERROR 0
#define OK 1
#define FALSE 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define Status int
#define MAXLENGTH 128
typedef struct HTnode
{
long weight
int parent
int lchild
int rchild
}HTNode, *HuffmanTree
typedef struct CTnode
{
long weight
char *coded_string
}CharacterTable
typedef char * *HuffmanCode
FILE *fp=NULL
void Analyse (CharacterTable * *character_table, long * *w, char * *chara, int &n)//分析所有不同的字符的权值
{
long *tmpw
char ch, *tmpchara
int i
(*character_table)=(CharacterTable *)malloc(128*sizeof(CharacterTable))//定义存放字母的数组
for(i=0i<128i++)
{
(*character_table)[i].weight=0 //初始化
(*character_table)[i].coded_string=NULL
}
ch=fgetc(fp)
while(!feof(fp))//诺到文件末尾，函数值为真
{
//m=ch
if(ch<128 &&ch>=0)
(*character_table)[ch].weight++//获得各个字母在文件中出现的次数
ch=fgetc(fp)
}
for(i=0, n=0i<128i++)
if((*character_table)[i].weight)
n++//统计有多少不同的字符数
(*w)=(long *)malloc(n*sizeof(long))//deliver the character and the weight to main
(*chara)=(char *)malloc(n*sizeof(char))
tmpw=(*w)
tmpchara=(*chara)
for(i=0i<128i++)
if((*character_table)[i].weight)
{//将权值放入*w数组中
*(*w)=(*character_table)[i].weight
*(*chara)=i//这里i是字符
(*w)++
(*chara)++
}
(*w)=tmpw
(*chara)=tmpchara//指针返回数组头
}
void Select (HuffmanTree *HT, int i, int *Min1, int *Min2)
{
int j, n, tmp1=-1, tmp2=-2
for(n=0n<in++)
{
if(!(*HT)[n].parent)
{
if(tmp1 == -1)
{
tmp1=n
continue
}
if(tmp2 == -2)
{
tmp2=n
if((*HT)[tmp1].weight >(*HT)[tmp2].weight)
{
j=tmp1
tmp1=tmp2
tmp2=j
}
continue
}
if((*HT)[n].weight <(*HT)[tmp2].weight) //scan and change
if((*HT)[n].weight <(*HT)[tmp1].weight)
tmp1=n
else
tmp2=n
}
}
*Min1=tmp1
*Min2=tmp2//tmp[Min2].weight >= tmp[Min1].weight
}
Status Huffman(HuffmanTree *HT, HuffmanCode *HC,long *w, int n)
{
int m, i, Min1, Min2, p1, p2, start, *M1, *M2
char *cd
HuffmanTree *HTp
if(n<1) return ERROR
m=2*n-1
(*HT)=(HTNode *)malloc(m*sizeof(HTNode)) //intialise Hc in main
HTp=HT
for(i=0i<ni++, w++)
{
(*HTp)[i].weight=*w
(*HTp)[i].parent=0
(*HTp)[i].lchild=0
(*HTp)[i].rchild=0
}
for(i<mi++)
{
(*HTp)[i].weight=0
(*HTp)[i].parent=0
(*HTp)[i].lchild=0
(*HTp)[i].rchild=0
}
M1=&Min1
M2=&Min2
for(i=ni<mi++)
{
Select(HT, i, M1, M2)
(*HTp)[Min1].parent=i
(*HTp)[Min2].parent=i
(*HTp)[i].lchild=Min1//左孩子要小一些
(*HTp)[i].rchild=Min2
(*HTp)[i].weight=(*HTp)[Min1].weight + (*HTp)[Min2].weight
}
//coded the weight below
(*HC)=(HuffmanCode)malloc(n*sizeof(char *))
cd=(char *)malloc(n*sizeof(char))
cd[n-1]='\0'
for(i=0i<ni++)
{
start=n-1
for(p1=i, p2=(*HTp)[p1].parentp2!=0p1=p2, p2=(*HTp)[p1].parent)
{
if( (*HTp)[p2].lchild ==p1) //编码, 左孩子为0, 右孩子为1
cd[--start]='0'
else
cd[--start]='1'
}
(*HC)[i]=(char *)malloc((n-start)*sizeof(char))
strcpy((*HC)[i],&cd[start])
} //over
return OK
}
void Weinumber_to_stringnumber(char * *stringnumber, long *w, int leaves)
{//将权值以字符数组形式存放在上米的数组中
char tmp[30]
long i, j, k
int start
for(i=0i<leavesi++)
{
start=29
tmp[start--]='\0'
for(k=w[i], j=k%10k!=0k=k/10, j=k%10)
tmp[start--]=j+'0'
stringnumber[i]=(char *)malloc((29-start)*sizeof(char))
strcpy(stringnumber[i], &tmp[start+1])
}
}
void Save_huffman_weight_dictionary(long *w, char *character, int leaves, HuffmanCode *HC)
{
char * *stringnumber
int i
FILE *fp1
fp1=fopen("weight.txt", "w")
stringnumber=(char * *)malloc(leaves * sizeof(char *))
Weinumber_to_stringnumber(stringnumber, w, leaves)
for(i=0i<leavesi++)
{
fputc(' ', fp1) // for unhuffman add '
fputc(character[i], fp1)
fputc('\t', fp1)
fputs(stringnumber[i], fp1)
fputc('\t', fp1)
fputc('\'', fp1)
fputs((*HC)[i], fp1)
fputc('\'', fp1)
fputc('\n', fp1)
}
fclose(fp1)
}
void Huffman_file_convert(HuffmanCode *HC, CharacterTable *character_table) //fp had opened
{
int i
char ch
FILE *fp2=fopen("coded.txt","w")
for( i=0i<128i++)
if(character_table[i].weight)
{
character_table[i].coded_string=*(*HC)
(*HC)++
}
ch=fgetc(fp)
while(!feof(fp))
{
if( (ch>=0 &&ch<128) &&(character_table[ch].weight) )//it is very importan to add (ch>=0 &&ch<128)
fputs(character_table[ch].coded_string,fp2)
ch=fgetc(fp)
}
fclose(fp2)
}
void fileopen1() //通过指针fp传递信息
{
char filename[100]
do{
printf("\n\n\t请输入要编码的文件:")
scanf("%s", filename)
if ((fp=fopen(filename,"r"))==NULL)
printf("\n\t不能打开此文件! 请重新输入!\n")
}while(!fp)
}
void main()
{
HuffmanTree Ht, *ht//three level pointer
HuffmanCode Hc, *hc
CharacterTable *CT, * *character_table
long *weight, * *w
char * character, * *chara
int leave //the all leaves number
ht=&Ht
hc=&Hc
w=&weight
chara=&character
character_table=&CT
fileopen1()
Analyse(character_table, w, chara, leave)
fseek(fp, 0, 0)//将文件指针还原
Huffman(ht, hc, weight, leave)//构建哈弗曼树！
Save_huffman_weight_dictionary(weight, character, leave, hc)
Huffman_file_convert(hc, CT)
fclose(fp)
}
#include <stdio.h>#include <stdlib.h>
#include <string.h>
//////////////////////////////////////////////////////////////////////////////
/*定义赫夫曼树结点的结构体变量，存放结点的权值、字符、双亲、坐孩子和右孩子*/
typedef struct{
int weight
char ch//增加一个域用于存放该节点的字符
int parent,lchild,rchild
}HTNode,*HuffmanTree
typedef char **HuffmanCode//指向赫夫曼编码的指针
//////////////////////////////////////////////////////////////////////////////
/*本程序用到的函数原型*/
void welcome() //打印 *** 作选择界面
void HuffmanCoding(HuffmanTree &,char *,int *,int)//建立赫夫曼树的算法
void select(HuffmanTree HT,int j,int *s1,int *s2)//从目前已建好的赫夫曼树中选择parent为0且weight最小的两个结点
void Init()//输入n个字符及其对应的权值，根据权值建立哈夫曼树
void Coding()//编码
void Decoding()//译码
void Print_code()//打印译码好的代码文件
void Print_tree()//以凹凸表形式打印哈夫曼树
int Read_tree(HuffmanTree &)//从文件中读入赫夫曼树
void find(HuffmanTree &HT,char *code,char *text,int i,int m)//译码时根据01字符串寻找相应叶子节点的递归算法
void Convert_tree(unsigned char T[100][100],int s,int *i,int j)//将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树
HuffmanTree HT//全局变量，指向存放赫夫曼树的存储空间
int n=0//全局变量，存放赫夫曼树叶子结点的数目
int main()
{
char select
while(1)
{
welcome()
scanf("%c",&select)
switch(select)
{
case 'i':
case 'I':Init()break
case 'c':
case 'C':Coding()break
case 'd':
case 'D':Decoding()break
case 'p':
case 'P':Print_code()break
case 't':
case 'T':Print_tree()break
case 'e':
case 'E':exit(1)
default :printf("Input error!\n")
}
getchar()
}
return 0
}
void welcome() //打印 *** 作选择界面
{
printf("*-----------------------------------------------------*\n")
printf("|What do you want to do? |\n")
printf("|-----------------------------------------------------|\n")
printf("| |\n")
printf("| I--------------------------Init the Huffman tree. |\n")
printf("| C--------------------------Code your file. |\n")
printf("| D--------------------------Decode the code.|\n")
printf("| P--------------------------Print the codefile. |\n")
printf("| T--------------------------Print the Huffman tree. |\n")
printf("| |\n")
printf("*-----------------------------------------------------*\n")
}
//////////////////////////////////////////////////////////////////////////////////////
/*初始化函数，输入n个字符及其对应的权值，根据权值建立哈夫曼树，并将其存于文件hfmtree中*/
void Init()
{
FILE *fp
int i,n,w[52]//w数组存放n个字符的权值
char character[52]//存放n个字符
printf("\n输入字符个数 n:")
scanf("%d",&n) //输入字符集大小
printf("输入%d个字符及其对应的权值:\n",n)
for (i=0i<ni++)
{
char b=getchar()
scanf("%c",&character[i])
scanf("%d",&w[i]) //输入n个字符和对应的权值
}
HuffmanCoding(HT,character,w,n) //建立赫夫曼树
if((fp=fopen("hfmtree.txt","w"))==NULL)
printf("Open file hfmtree.txt error!\n")
for (i=1i<=2*n-1i++)
{
if(fwrite(&HT[i],sizeof(HTNode),1,fp)!=1) //将建立的赫夫曼树存入文件hfmtree.txt中
printf("File write error!\n")
}
printf("\n建立赫夫曼树成功，已将其存于文件hfmtree.txt中\n")
fclose(fp)
}
///////////////////////////////////////////////////////////////////////////////////
//////建立赫夫曼树的算法///////////////////////////////////////////////////////////
void HuffmanCoding(HuffmanTree &HT,char *character,int *w,int n)
{
int m,i,s1,s2
HuffmanTree p
if(n<=1) return
m=2*n-1
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode))
for(p=HT+1,i=1i<=n++i,++p,++character,++w)
{p->ch=*characterp->weight=*wp->parent=0p->lchild=0p->rchild=0}
for(i<=m++i,++p) {p->ch=0p->weight=0p->parent=0p->lchild=0p->rchild=0}
for(i=n+1i<=m++i)
{
select(HT,i-1,&s1,&s2)
HT[s1].parent=iHT[s2].parent=i
HT[i].lchild=s1HT[i].rchild=s2
HT[i].weight=HT[s1].weight+HT[s2].weight
}
}
///////////////////////////////////////////////////////////////////////////////
/*从HT[1]到HT[j]中选择parent为0且weight最小的两个结点，用s1和s2返回其序号*/
void select(HuffmanTree HT,int j,int *s1,int *s2)
{
int i
//找weight最小的结点
for (i=1i<=ji++)
if (HT[i].parent==0)
{*s1=ibreak}
for (i<=ji++)
if ((HT[i].parent==0)&&(HT[i].weight<HT[*s1].weight))
*s1=i
HT[*s1].parent=1
//找weight次小的结点
for (i=1i<=ji++)
if (HT[i].parent==0)
{*s2=ibreak}
for (i<=ji++)
if ((HT[i].parent==0)&&(i!=*s1)&&(HT[i].weight<HT[*s2].weight))
*s2=i
}
///////////////////////////////////////////////////////////////////////////////
/*对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中*/
void Coding()
{
FILE *fp,*fw
int i,f,c,start
char *cd
HuffmanCode HC
if(n==0)
n=Read_tree(HT)//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数
/////以下程序段求赫夫曼树中各叶子节点的字符对应的的编码，并存于HC指向的空间中
{
HC=(HuffmanCode)malloc((n+1)*sizeof(char*))
cd=(char *)malloc(n*sizeof(char))
cd[n-1]='\0'
for(i=1i<=n++i)
{
start=n-1
for(c=i,f=HT[i].parentf!=0c=f,f=HT[f].parent)
if(HT[f].lchild==c)
cd[--start]='0'
else cd[--start]='1'
HC[i]=(char *)malloc((n-start)*sizeof(char))
strcpy(HC[i],&cd[start])
}
free(cd)
}
/////////////////////////////////////////////////////////////////////////////////////
if((fp=fopen("tobetrans.txt","rb"))==NULL)
printf("Open file tobetrans.txt error!\n")
if((fw=fopen("codefile.txt","wb+"))==NULL)
printf("Open file codefile.txt error!\n")
char temp
fscanf(fp,"%c",&temp)//从文件读入第一个字符
while(!feof(fp))
{
for(i=1i<=ni++)
if(HT[i].ch==temp) break //在赫夫曼树中查找字符所在的位置
for(int r=0HC[i][r]!='\0'r++) //将字符对应的编码存入文件
fputc(HC[i][r],fw)
fscanf(fp,"%c",&temp) //从文件读入下一个字符
}
fclose(fw)
fclose(fp)
printf("\n对文件hfmtree.txt编码成功,结果已存入codefile.txt中。\n\n")
}
/////////////////////////////////////////////////////////////////////////
/*将文件codefile中的代码进行译码，结果存入文件textfile中*/
void Decoding()
{
FILE *fp,*fw
int m,i
char *code,*text,*p
if(n==0)
n=Read_tree(HT)//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数
if((fp=fopen("codefile.txt","rb"))==NULL)
printf("Open file codefile.txt error!\n")
if((fw=fopen("textfile.txt","wb+"))==NULL)
printf("Open file textfile.txt error!\n")
code=(char *)malloc(sizeof(char))
fscanf(fp,"%c",code) //从文件读入一个字符
for(i=1!feof(fp)i++)
{
code=(char *)realloc(code,(i+1)*sizeof(char))//增加空间
fscanf(fp,"%c",&code[i])//从文件读入下一个字符
}
code[i-1]='\0'
/////////到此codefile.txt文件中的字符已全部读入，存放在code数组中
text=(char *)malloc(100*sizeof(char))
p=text
m=2*n-1
if(*code=='0')
find(HT,code,text,HT[m].lchild,m) //从根节点的左子树去找
else
find(HT,code,text,HT[m].rchild,m) //从根节点的右子树去找
for(i=0p[i]!='\0'i++) //把译码好的字符存入文件textfile.txt中
fputc(p[i],fw)
fclose(fp)
fclose(fw)
printf("\n对codefile.txt文件译码成功，结果已存入textfile.txt文件。\n\n")
}
//////////////////////////////////////////////////////////////////////////////////////////////////////
/*将文件codefi1e以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。*/
void Print_code()
{
FILE *fp,*fw
char temp
int i
if((fp=fopen("codefile.txt","rb"))==NULL)
printf("Open file codefile.txt error!\n")
if((fw=fopen("codeprint.txt","wb+"))==NULL)
printf("Open file codeprint.txt error!\n")
printf("\n文件codefi1e以紧凑格式显示如下:\n")
fscanf(fp,"%c",&temp) //从文件读入一个字符
for (i=1!feof(fp)i++)
{
printf("%c",temp)
if(i%50==0) printf("\n")
fputc(temp,fw) //将该字符存入文件codeprint.txt中
fscanf(fp,"%c",&temp) //从文件读入一个字符
}
printf("\n\n此字符形式的编码已写入文件codeprint.txt中.\n\n")
fclose(fp)
fclose(fw)
}
//////////////////////////////////////////////////////////////////////////////////////////////////
/*将已在内存中的哈夫曼树以凹凸表形式显示在屏幕上，同时将此字符形式的哈夫曼树写入文件treeprint中。*/
void Print_tree()
{
unsigned char T[100][100]
int i,j,m=0
FILE *fp
if(n==0)
n=Read_tree(HT)//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数
Convert_tree(T,0,&m,2*n-1)//将内存中的赫夫曼树转换成凹凸表形式的树，存于数组T中
if((fp=fopen("treeprint.txt","wb+"))==NULL)
printf("Open file treeprint.txt error!\n")
printf("\n以凹凸表形式打印已建好的赫夫曼树：\n")
for(i=1i<=2*n-1i++)
{
for (j=0T[i][j]!=0j++)
{
if(T[i][j]==' ') {printf(" ")fputc(T[i][j],fp)}
else
{printf("%d",T[i][j])fprintf(fp,"%d\n",T[i][j])}
}
printf("\n")
}
fclose(fp)
printf("\n此字符形式的哈夫曼树已写入文件treeprint.txt中.\n\n")
}
//////////////////////////////////////////////////////////////////////////////////
/*从文件hfmtree.txt中读入赫夫曼树，返回叶子节点数*/
int Read_tree(HuffmanTree &HT)
{
FILE *fp
int i,n
HT=(HuffmanTree)malloc(sizeof(HTNode))
if((fp=fopen("hfmtree.txt","r"))==NULL)
printf("Open file hfmtree.txt error!\n")
for (i=1!feof(fp)i++)
{
HT=(HuffmanTree)realloc(HT,(i+1)*sizeof(HTNode))//增加空间
fread(&HT[i],sizeof(HTNode),1,fp)//读入一个节点信息
}
fclose(fp)
n=(i-1)/2
return n
}
////////////////////////////////////////////////////////////////
/*译码时根据01字符串寻找相应叶子节点的递归算法*/
void find(HuffmanTree &HT,char *code,char *text,int i,int m)
{
if(*code!='\0') //若译码未结束
{
code++
if(HT[i].lchild==0&&HT[i].rchild==0) //若找到叶子节点
{
*text=HT[i].ch//将叶子节点的字符存入text中
text++
if((*code=='0'))
find(HT,code,text,HT[m].lchild,m)//继续从根节点的左子树找
else
find(HT,code,text,HT[m].rchild,m)//继续从根节点的右子树找
}
else //如果不是叶子节点
if(*code=='0')
find(HT,code,text,HT[i].lchild,m) //从该节点的左子树去找
else
find(HT,code,text,HT[i].rchild,m) //从该节点的右子树去找
}
else
*text='\0'//译码结束
}
////////////////////////////////////////////////////////////////////////
/*将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树*/
void Convert_tree(unsigned char T[100][100],int s,int *i,int j)
{
int k,l
l=++(*i)
for(k=0k<sk++)
T[l][k]=' '
T[l][k]=HT[j].weight
if(HT[j].lchild)
Convert_tree(T,s+1,i,HT[j].lchild)
if(HT[j].rchild)
Convert_tree(T,s+1,i,HT[j].rchild)
T[l][++k]='\0'
}
自己改改吧！
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）