哈夫曼编码与解码(C语言实现) - Touch的博客 - ITeye技术网站
博客分类：
#include&stdio.h&
#include&stdlib.h&
#include&string.h&
#include&conio.h&
#define MAXNUM 60
typedef struct
//权值，这个字符出现的频率
typedef struct
char code[MAXNUM];
HuffNode ht[MAXNUM*2]; //存放哈夫曼树
HuffCode hcd[MAXNUM];
//存放ht数组中对应的字符的编码
//字符的个数
//初始化哈夫曼树ht
void initHt()
//从文件document/character.txt中读出要编码的字符和权值
if((fp=fopen("document/character.txt","r"))==NULL){
printf("can not open the file character.txt");
ht[i].left=ht[i].right=ht[i].parent=-1;
while((ch=fgetc(fp))!=EOF){
if(ch=='\n'){
ht[i].left=ht[i].right=ht[i].parent=-1;
else if((ch&='a' && ch&='z')||(ch&='A' && ch&='Z'))
else if(ch&='0'&&ch&='9')
ht[i].weight=ht[i].weight*10+ch-'0';
if(fclose(fp)){
printf("can not close the file character.txt");
//构造哈夫曼树,看成有n棵树，选择权值最小的两棵树合并
void createHuffTree()
int i=0,k;
int minI,minJ;
minI=minJ=-1; //minI&minJ
for(k=n;k&2*n-1;k++){
//寻找ht中权值最小且无父结点的两个结点
while(ht[i].ch!='\0'){
if(ht[i].parent==-1){
}else if(f==1){
if(ht[i].weight&ht[minI].weight){
minJ=minI;
if(ht[i].weight&ht[minI].weight){
minJ=minI;
}else if(ht[i].weight&ht[minJ].weight)
//合并两个结点
ht[k].ch='#';
ht[k].left=minI;
ht[k].right=minJ;
ht[k].weight=ht[minI].weight+ht[minJ].
ht[k].parent=-1;
ht[minI].parent=ht[minJ].parent=k;
//将一个字符串反转
void reverse(char *str)
for(i=0,j=strlen(str)-1;i&j;i++,j--){
ch=str[i];
str[i]=str[j];
//哈夫曼编码，通过父节点从下往上找
void createHuffCode()
for(i=0;i&n;i++){
//给每个字符进行编码
while(ht[j].parent!=-1){
if(ht[ht[j].parent].left==j){
hcd[i].code[length++]=0+'0';
hcd[i].code[length++]=1+'0';
hcd[i].start=hcd[i].code[length-1]-'0';
hcd[i].code[length]='\0';
reverse(hcd[i].code);
//把hcd字符编码写入文件document/code.txt中
if((fp=fopen("document/code.txt","w"))==NULL){
printf("can not open the file character.txt");
for(i=0;i&n;i++){
fputc(ht[i].ch,fp);
fputs(hcd[i].code,fp);
fputc('\n',fp);
if(fclose(fp)){
printf("can not close the file character.txt");
//哈夫曼解码，每次都从根节点开始搜索
int releaseHuffCode(char *str,char* code)
int root=2*n-2;
int length=0,i=0;
while(code[i]){
if(code[i]=='0'+0)
root=ht[root].
else if(code[i]=='0'+1)
root=ht[root].
if(ht[root].left==-1 && ht[root].right==-1){
str[length++]=ht[root].
root=2*n-2;
str[length]='\0';
if(root==2*n-2)
//用户输入编码字符
void encode()
int i=0,j,f=1;
char str[50];
char code[500]={'\0'};
printf("\n请输入要编码的字符串(length&50)\n");
scanf("%s",str);
while(str[i]){
if((str[i]&='a'&&str[i]&='z')||(str[i]&='A'&&str[i]&='Z')){
for(j=0;j&n;j++)
if(str[i]==ht[j].ch){
strcat(code,hcd[j].code);
puts(code);
printf("你输入的字符串错误！\n");
printf("按任意键后重新选择！\n");
//用户输入解码字串
char str[50];
char code[500];
printf("\n请输入要解码的字串(用0和1表示)\n");
scanf("%s",code);
if(releaseHuffCode(str,code))
puts(str);
printf("你输入的字串错误！\n");
printf("按任意键后重新选择！\n");
void main()
int choice=1;
createHuffTree();
createHuffCode();
while(choice){
system("cls");
printf("/****************哈夫曼编码与解码*********************/\n");
printf(" 在document/character.txt 文件中存放着各个字母的权值\n");
printf(" 程序从中读出各个字母的权值构造哈夫曼树并进行编码\n");
printf(" 各个字符的编码存在document/code.txt文件中\n");
printf("/*****************************************************/\n");
printf("\n请输入你的选择：1 ---- 编码
2 ---- 解码
0 ---- 退出\n");
scanf("%d",&choice);
switch(choice){
printf("谢谢使用！\n");
printf("你的输入错误！按任意键后重新输入！\n");
下载次数: 75
浏览 13419
Touch_2011
浏览: 129123 次
来自: 武汉
大侠，你这个程序的递归部分看不懂，能不能麻烦解释一下递归的思路 ...
我是一楼的神马_CS哦 再次表示感谢！！
好 万分感谢 ！！
shenma_CS 写道你好！ 我看了你的代码 有好多让我佩服 ...
乘法是模拟数学上两个数相乘，但在处理进位方面可能有点不同。比如 ...哈夫曼编码（最优前缀码） - 推酷
哈夫曼编码（最优前缀码）
作为哈夫曼树的一个重要应用，我们来介绍哈夫曼编码。在我的上一篇博文《树之哈夫曼树》中已经介绍了建立哈夫曼树的过程，而由哈夫曼树求得的编码为最优前缀码。 每个叶子表示的字符的编码，就是 从根到叶子的路径上的标号依次相连所形成的编码，显然这就是该字符的最优前缀码。 所谓 前缀码 是指，对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀，比如常见的等长编码就是前缀码。所谓 最优前缀码 是指，平均码长或文件总长最小的前缀编码称为最优的前缀码（这里的平均码长相当于码长的期望值）。
我们知道，变长编码可能使解码产生二义性，而前缀码的出现很好地解决了这个问题。而平均码长相当于二叉树的加权路径长度，从这个意义上说，由哈夫曼树生成的编码一定是最优前缀码，故通常不加区分的将哈夫曼编码也称作最优前缀码。
需要注意的是，由于哈夫曼树建立过程的不唯一性可知，生成的哈夫曼编码也是不唯一的，并且在本文中，将树中左分支和右分支分别标记为0和1也造成了哈夫曼编码的不唯一性（当然也可以反过来，将左分支记为1，右分支记为0）。
在实际应用中，我们通常采用下列做法：根据各个字符的权值建立一颗哈夫曼树，求得每个字符的哈夫曼编码，有了每个字符的哈夫曼编码，我们就可以制作一个该字符集的哈夫曼编码表。有了字符集的哈夫曼编码表之后，对数据文件的
是：依次读人文件中的字符c，在哈夫曼编码表H中找到此字符，将字符c转换为对应的哈夫曼编码串。对压缩后的数据文件进行
则必须借助于哈夫曼树，其过程是：依次读人文件的二进制码，从哈夫曼树的根结点出发，若当前读入0，则走向左孩子，否则走向右孩子。一旦到达某一叶子时便译出相应的字符。然后重新从根出发继续译码，直至文件结束。下面给出制作哈夫曼编码表的过程的代码，通过以上的分析，读者不难写出文件编码过程和解码过程的代码。
#include&cstdio&
#include&cstdlib&
#include&cstring&
#include&algorithm&
#define n 6
//叶子数目
#define m 2*n-1
//树中结点总数
typedef struct{
//结点类型
//结点的权值
int parent,lchild,//双亲指针及左右孩子
typedef HTNode HuffmanTree[m];//HuffmanTree是向量类型
typedef struct{
//用于SelectMin函数中排序的结点类型
//保存根结点在向量中的序号
//保存根结点的权值
typedef struct{
//编码结点
//存储字符
char bits[n+1];
//存放编码位串
typedef CodeNode HuffmanCode[n];
void InitHuffmanTree(HuffmanTree T){
//初始化哈夫曼树
//将2n-1个结点里的三个指针均置为空(即置为-1)，权值置为0
for(int i=0;i&m;i++){
T[i].lchild=-1;
T[i].rchild=-1;
T[i].parent=-1;
T[i].weight=0;
void InputWeight(HuffmanTree T){
//输入叶子权值
//读人n个叶子的权值存于向量的前n个分量中
for(int i=0;i&n;i++){
scanf(&%lf&,&x);
T[i].weight=x;
bool cmp(temp a,temp b){
//用于排序的比较函数
return a.weight&b.
void SelectMin(HuffmanTree T,int k,int *p1,int *p2){
//在前k个结点中选择权值最小和次小的根结点，其序号分别为p1和p2
temp x[m];
//x向量为temp类型的向量
for(i=0,j=0;i&=k;i++){
//寻找最小和次小根节点的过程
if(T[i].parent==-1){//如果是根节点,则进行如下操作
x[j].id=i;
//将该根节点的序号赋值给x
x[j].weight=T[i].//将该根节点的权值赋值给x
//x向量的指针后移一位
sort(x,x+j,cmp);
//对x按照权值从小到大排序
//排序后的x向量的第一和第二个位置中存储的id是所找的根节点的序号值
void CreateHuffmanTree(HuffmanTree T){
//构造哈夫曼树，T[m-1]为其根结点
int i,p1,p2;
InitHuffmanTree(T); //将T初始化
InputWeight(T);
//输入叶子权值
for(i=n;i&m;i++){
//在当前森林T[0．．i-1]的所有结点中，选取权最小和次小的
//两个根结点T[p1]和T[p2]作为合并对象
//共进行n-1次合并，新结点依次存于T[i]中
SelectMin(T,i-1,&p1,&p2);//选择权值最小和次小的根结点，其序号分别为p1和p2
//将根为T[p1]和T[p2]的两棵树作为左右子树合并为一棵新的树
//新树的根是新结点T[i]
T[p1].parent=T[p2].parent=i;//T[p1]和T[p2]的两棵树的根结点指向i
T[i].lchild=p1;
//最小权的根结点是新结点的左孩子
T[i].rchild=p2;
//次小权的根结点是新结点的右孩子
T[i].weight=T[p1].weight+T[p2].//新结点的权值是左右子树的权值之和
void CharSetHuffmanEncoding(HuffmanTree T,HuffmanCode H){
//根据哈夫曼树T求哈夫曼编码表H
int c,p;//c和p分别指示T中孩子和双亲的位置
char cd[n+1];//临时存放编码
//指示编码在cd中的起始位置
cd[n]='\0';//编码结束符
getchar();
for(int i=0;i&n;i++){//依次求叶子T[i]的编码
H[i].ch=getchar();//读入叶子T[i]对应的字符
start=n;//编码起始位置的初值
c=i;//从叶子T[i]开始上溯
while((p=T[c].parent)&=0){//直至上溯到T[c]是树根为止
//若T[c]是T[p]的左孩子，则生成代码0；否则生成代码1
if(T[p].lchild==c)
cd[--start]='0';
cd[--start]='1';
c=p;//继续上溯
strcpy(H[i].bits,&cd[start]);//复制编码位串
//*************************测试函数**********************************
int main(){
HuffmanTree T;
HuffmanCode H;
printf(&请输入%d个叶子结点的权值来建立哈夫曼树：\n&,n);
CreateHuffmanTree(T);
printf(&请输入%d个叶子结点所代表的字符：\n&,n);
CharSetHuffmanEncoding(T,H);
printf(&哈夫曼树已经建好，哈夫曼编码已经完成，输出如下：\n&);
printf(&哈夫曼树：\n&);
for(int i=0;i&m;i++){
printf(&id:%d
weight:%.1lf
parent:%d&,i,T[i].weight,T[i].parent);
lchild:%d rchild:%d\n&,T[i].lchild,T[i].rchild);
printf(&哈夫曼编码：\n&);
double wpl=0.0;
for(int i=0;i&n;i++){
printf(&id:%d
code:%s\n&,i,H[i].ch,H[i].bits);
wpl+=strlen(H[i].bits)*T[i].
printf(&平均码长为：%.2lf\n&,wpl);
} 测试样例及预测运行结果：（表中和图中的权重数值weight均需要乘以0.01）
运行结果：
已发表评论数()
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见
正文不准确
标题不准确
排版有问题
主题不准确
没有分页内容
图片无法显示
视频无法显示
与原文不一致}