Question

哈弗曼编码与译码问题 在发送端根据输入的内容构造哈夫曼树并编码，在接收端怎么译码呢

Answer 1

Huffman 编码

一、实验目的
熟悉Huffman编码方法。
了解并弄懂Huffman编码实现信息的无损压缩原理。

二、实验要求
熟悉C语言编程。

三、实验内容
1.根据给定的n个权值(w1, w2, …, wn)构成n棵二叉树的集合F=，其中每棵二叉树Ti中只有一个带树为Ti的根结点
2.在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置其根结点的权值为其左右子树权值之和
3.在F中删除这两棵树，同时将新得到的二叉树加入F中
4.重复2, 3，直到F只含一棵树为止

四、实验步骤
1．用C语言实现二叉树的说明
2．输入n个权值，并生成n个二叉树
3．对n个二叉树逐步生成Huffman树
4．对Huffman树的每个叶子结点生成编码

附：实验程序
#include <stdio.h>
#define M 10
#define MAX 100

typedef struct
{
int data;
int pa,lc,rc;
}JD;

void huffman(int n,int w[],JD t[])
{ int i,j,k,x1,x2,m1,m2;
for(i=1;i<(2*n);i++)
{ t[i].pa=t[i].lc=t[i].rc=0;
if(i<=n)
t[i].data=w[i-1];
else
t[i].data=0;
}
for(i=1;i<n;i++)
{ m1=m2=MAX;
x1=x2=0;
for(j=1;j<(n+i);j++)
{ if((t[j].data<m1)&&(t[j].pa==0))
{ m2=m1; x2=x1;
m1=t[j].data; x1=j;
}
else if((t[j].data<m2)&&(t[j].pa==0))

}
k=n+i;
t[x1].pa=t[x2].pa=k;
t[k].data=m1+m2;
t[k].lc=x1;
t[k].rc=x2;
}
}

void main()
{ int i,j,n=4;
static int w[]=;
JD t[M];
huffman(n,w,t);
for(i=1;i<=2*n-1;i++)
printf("%d ,%d ,%d ,%d \n",t[i].lc,t[i].data,t[i].rc,t[i].pa);
printf("\n\n");
getch();
}