实验报告
1、实验目的：
(1)理解哈夫曼树的含义和性质。
(2)掌握哈夫曼树的存储结构以及描述方法。
(3)掌握哈夫曼树的生成方法。
(4)掌握哈夫曼编码的一般方法，并理解其在数据通讯中的应用。
2、实验内容：
哈夫曼树与哈弗曼编码、译码
a.问题描述：
哈夫曼问题的提出可以参考教材P.145.
利用哈弗曼编码进行通信可以大大提高通信利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码。
b.算法提示：
参见教材P.147-148算法6.12、6.13的描述。
3、实验要求：
建立哈夫曼树，实现编码，译码。
○1.初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。
○2.编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
○3.译码（Decoding )。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
○4.输出代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。
○5.输出哈夫曼树（TreePrinting）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
测试数据：
设权值 c= (a, b, c, d , e, f, g, h)
w=（5，29，7，8，14，23，3，11），n=8。
按照字符‘0’或‘1’确定找左孩子或右孩子，则权值对应的编码为：
5：0001，29：11，7：1110，8：1111
14：110，23：01，3：0000，11：001
。
四实验代码
#include #include #include #include #include typedef struct {
int weight,K;
int parent,lchild,rchild;
}HTNode,* HuffmanTree;
typedef char **HuffmanCode;
char str[50];
int wa[50];
HuffmanTree HT;
HuffmanCode HC;
int w[50],i,j,n=8;
char z[50];
int flag=0;
int numb=0;
// -----------------求哈夫曼编码-----------------------
struct cou {
char data;
int count;
}cou[50];
void select(HuffmanTree HT,int j,int *s1,int *s2)
{
int i;
//找weight最小的结点
for (i=1;i<=j;i++)
if (HT[i].parent==0)
{*s1=i;break;}
for (;i<=j;i++)
if
((HT[i].parent==0)&&(HT[i].weight*s1=i;
HT[*s1].parent=1;
//找weight次小的结点
for (i=1;i<=j;i++)
if (HT[i].parent==0)
{*s2=i;break;} for (;i<=j;i++)
if
((HT[i].parent==0)&&(i!=*s1)&&(HT[i].weight *s2=i;
}
// --------------算法6.12--------------------------
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{
int m,i,s1,s2,start;
int c,f;
HuffmanTree p;
char *cd;
if(n<=1)
return;//检测结点数是否可以构成树
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode) );
for(p=HT+1,i=1;i<=n;i++,p++)
{
p->weight=wa[i-1];
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(;i<=m;++i,++p)
p->parent=0;
for(i=n+1;i<=m;++i) // 建哈夫曼树
{
select(HT,i-1,&s1,&s2);
