哈弗曼编码实验报告.doc

1、掌握哈夫曼树的构造和应用
2、利用哈夫曼方法及其编/译码技术实现对传输信息编码/译码系统.

1、哈夫编码/译码器简介
本例说明,先前快速远距离通信的主要手段是电报,即将需传送的文字转换成由二进制的字符组成的字符串。在传送电文时,希望总长尽可能地短,如果对每个字符设计长度不等的编码,且让电文中出现次数较多的字符采用尽可能短的编码,以减少经费。哈夫曼树就是根据此原理设计出来的一种存储结构。
2、问题描述
哈夫曼树很易求出给定字符集及其概率(或频度)分布的最优前缀码。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。该技术一般可将数据文件压缩掉20%至90%,其压缩效率取决于被压缩文件的特征。
利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时,降低传输成本。但是,这要求在发送端通过一个编码系统对待传送电文须预先编码,在接收须将传送来的数据进行译码。请自行设计实现一个具有初始化、编码、译码、输入/输出等功能的哈夫曼码的编码/译码系统。并实现以下报文的编码和译码:“this program is my favorite”。

某通信的电文字符集为26个英文字母及空格字符,其出现频度如下表所示:

4、设计思想描述
(1)问题分析。
(2) 哈夫曼树中各结点的结构描述(如上图)。
(3) 哈夫曼树的存储结构描述。
5、主要算法设计与实现
(1)哈弗曼树的定义(动态分配数组存储哈夫曼树)
typedef struct{
char ch;//键值
int weight;//权值
int selected;//编码值
int parent,lchild,rchild;//各节点的值
}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树
(2)定义用于译码的树
typedef struct TreeNode{
struct TreeNode * lchild;//结构指针
struct TreeNode * rchild;
char code;
char data;
}TreeNode,*Tree;
(3) 哈夫曼树函数的设计
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int * &w,int n){//建立哈弗曼树
int m=2*n-1,i,j,s1,s2,start,f;
char * cd;
HuffmanTree p;
if(n<=1)return;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0号单元未使用
for(p=HT+1,i=1;i<=n;i++,p++,w++){
p->weight=*(w+1);
p->selected=p->lchild=p->rchild=p->parent=0;
}
for(;i<=m;i++,p++)
p->selected=p->parent=p->lchild=p->rchild=0;
for(i=n+1;i<=m;i++){//建立哈弗曼树
Select(HT,i-1,&s1,&s2);
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
printf("\n哈弗曼树表\n");//打印哈弗曼树表
printf(" i weight parent lchild rchild\n");
for(p=HT+1,i=1;i<=m;i++,p++)
printf("%2d %6d %6d %6d %6d\n",i,p->weight,p->parent,p->lchild,p->rchild);
printf("\n");
//从叶子到根逆向求每个字符的哈夫曼编码
HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); //分配n个字符编码的头指针向量
cd=(char *)malloc(n*sizeof(char)); //分配求编码的工作空间
cd[n-1]='\0'; //编码结束符
for(i=1;i<=n;i++){ //逐个字符求哈夫曼编码
start=n-1; //编码结束位置 for(j=i,f=HT[i].parent;f!=0;j=f,f=HT[f].parent){//从叶子到根逆向求编码
if(HT[f].lchild==j)
cd[