实验二：用Huffman树进行编码与解码算法

实验：哈夫曼树编码及译码的实现一．实验题目给定字符集的HUFFMANN编码与解码，这里的字符集及其字符频数自己定义，要求输出个字符集的哈夫曼编码及给定的字符串的哈夫曼码及译码结果。

二．实验原理首先规定构建哈夫曼树，然后进行哈夫曼树的编码，接着设计函数进行字符串的编码过程，最后进行哈夫曼编码的译码。

首先定义一个结构体，这个结构体定义时尽可能的大，用来存放左右的变量，再定义一个地址空间，用于存放数组，数组中每个元素为之前定义的结构体。

输入n个字符及其权值。

构建哈夫曼树：在上述存储结构上实现的哈夫曼算法可大致描述为：1.首先将地址空间初始化，将ht[0…n-1]中所有的结点里的指针都设置为空，并且将权值设置为0.2.输入:读入n个叶子的权值存于向量的前n个分量中。

它们是初始森林中n个孤立的根结点上的权值。

3.合并:对森林中的树共进行n-1次合并，所产生的新结点依次放入向量ht的第i个分量中。

每次合并分两步：①在当前森林ht[0…i-1]的所有结点中，选取权最小和次小的两个根结点[s1]和 [s2]作为合并对象，这里0≤s1，s2≤i-1。

②将根为ht[s1]和ht[s2]的两棵树作为左右子树合并为一棵新的树，新树的根是新结点ht[i]。

具体操作：将ht[s1]和ht[s2]的parent置为i，将ht[i]的lchild和rchild分别置为s1和s2 .新结点ht[i]的权值置为ht[s1]和ht[s2]的权值之和。

4.哈夫曼的编码：约定左子为0，右子为1，则可以从根结点到叶子结点的路径上的字符组成的字符串作为该叶子结点的编码。

当用户输入字母时。

就在已经找好编码的编码结构体中去查找该字母。

查到该字母就打印所存的哈夫曼编码。

接着就是完成用户输入0、1代码时把代码转成字母的功能。

这是从树的头结点向下查找，如果当前用户输入的0、1串中是0则就走向该结点的左子。

如果是1这就走向该结点的右结点，重复上面步骤。

这个是代码是昨天写完的，一开始的时候还出了点小bug，这个bug在晚上去吃饭的路上想明白的，回来更改之后运行立刻完成最后一步，大获成功。

简单说下huffman编码和文件压缩主要的技术。

Huffman编码，解码：I 创建Huffman树II 根据Huffman树实现编码，并将编码结果和要编码的数据建立映射关系。

III Huffman解码，也就是根据获取的Huffman码来逆向获取解码信息，而且你从解压文件中一次性获取的数据是一个很长的字符串，没有预处理好的成段字符串式Huffman码。

1I 首先，如何创建Huffman树？在这个我在前天的那篇文章中简单的提了一下，现在好好说一下。

如果你不知道什么是Huffman树，请google之~对于获取到的文件，首先要做的就是，建立一个长度为256的int数组，全部置零，然后以字节流的形式读取文件，并对字节流中的字节出现次数进行统计，方法就是以字节数值为数组偏移地址，对应的数组元素进行+1操作。

另外这里需要提一下的就是，用于存储文件字节流的缓冲区最好是unsigned char类型，因为这样能直接使用，如果是char的，在转化为int类型的时候，一旦数值大于127，因为补码问题，你就直接乘上了通往未知数值的高铁~完成统计之后，将这个数组中出现次数不为0的元素添加对应大小的二叉树节点数组中，然后以出现次数为Key值，进行排序。

在排序完成之后，就能开始构建Huffman树了。

操作如下：1 如果数组中元素个数不为1，将前两个元素构造为一个临时节点的子树，此时临时节点的Key值为两个元素Key值之和，然后删除数组中的第一个元素（从数组中删除），再将临时节点赋值给当前数组的第一个元素。

（其实就是将前两个元素添加到一个临时节点的左右根节点，然后在原数组中删除这两个元素，，接着再将这个临时节点插入到数组头部，充当新的节点。

上面的那段描述我觉得说的不是很清楚，但是那个是我在代码中发现的一个可以优化的地方，减少了一个元素的删除操作）2 此时数组依据key值的排序很有可能已经不再有序，而又因为仅有一个乱序元素，所以专门设计了一个函数，一次完成排序，效率，应该是最高的了。

Huffman编解码实验报告⽂本⽂件的⼆进制预统计Huffman编解码⼀、实验⽬的(1) 熟悉Huffman编解码算法；(2) 理解Huffman编码的最佳性。

⼆、实验内容1、编程思想霍夫曼（Huffman）编码是1952年为⽂本⽂件⽽建⽴，是⼀种统计编码。

属于⽆损压缩编码。

霍夫曼编码的码长是变化的，对于出现频率⾼的信息，编码的长度较短；⽽对于出现频率低的信息，编码长度较长。

这样，处理全部信息的总码长⼀定⼩于实际信息的符号长度。

计算机编程实现时，⾸先统计带编码的⽂本⽂件中各个字符出现的概率，然后将概率作为节点的权值构建huffman树。

编码时从叶⼦节点出发，如果这个节点在左⼦树上，则编码0，否则编码1，直到根节点为⽌，所得到的01序列即为该叶⼦节点的编码。

所有叶⼦节点的编码构成⼀个码本。

有两种译码⽅法：(1)按位读⼊码字，从已建好的Huffman树的根节点开始，若码字为“0”，则跳到左⼦树，若为“1”则跳到右⼦树，直到叶⼦结点为⽌，输出叶⼦接点所表⽰的符号。

（2）由于Huffman编码是唯⼀码，还有另⼀种译码⽅法，每读⼊⼀位编码就去码本中去匹配相应的码字，若匹配不成功，则继续读⼊下⼀个编码，直到匹配成功为⽌。

显然前⼀种⽅法⽐较简便，本程序采⽤便是该⽅法。

2、程序流程图3、编程实现本实验采⽤⽤C 语⾔程序语⾔，VC++ 6.0编程环境。

(1)数据结构构造存放符号及其权值的存储结构如下 typedef struct {unsigned char symbol; //符号的ASCII 码值 int sweight; //权值}syml_weit;syml_weit *sw;构造huffman 树存储结构如下：typedef struct {int weit; //权值int lchd; //左孩⼦地址 int rchd; //右孩⼦地址 int part; //双亲地址 }hufmtree;hufmtree *htree;(2)函数本程序共包含5个函数：⼀个主函数：void main()， 4个⼦函数：void CountWeight(unsigned char *DataBuf,int FileLen); void BuildTree();void HufmCode(unsigned char *DataBuf,int FileLen); void HufmDCode(unsigned char *CDataBuf,int CDataLen); 其功能分别CountWeight----计算⽂本⽂件中各符号的权值； BuildTree-------构建Huffman 树，形成码本； HufmCode---------对⽂本⽂件进⾏编码； HufmDCode-------进⾏译码。

一、实验目的1. 理解哈夫曼树的概念及其在数据结构中的应用。

2. 掌握哈夫曼树的构建方法。

3. 学习哈夫曼编码的原理及其在数据压缩中的应用。

4. 提高编程能力，实现哈夫曼树和哈夫曼编码的相关功能。

二、实验原理哈夫曼树（Huffman Tree）是一种带权路径长度最短的二叉树，又称为最优二叉树。

其构建方法如下：1. 将所有待编码的字符按照其出现的频率排序，频率低的排在前面。

2. 选择两个频率最低的字符，构造一棵新的二叉树，这两个字符分别作为左右子节点。

3. 计算新二叉树的频率，将新二叉树插入到排序后的字符列表中。

4. 重复步骤2和3，直到只剩下一个节点，这个节点即为哈夫曼树的根节点。

哈夫曼编码是一种基于哈夫曼树的编码方法，其原理如下：1. 从哈夫曼树的根节点开始，向左子树走表示0，向右子树走表示1。

2. 每个叶子节点对应一个字符，记录从根节点到叶子节点的路径，即为该字符的哈夫曼编码。

三、实验内容1. 实现哈夫曼树的构建。

2. 实现哈夫曼编码和译码功能。

3. 测试实验结果。

四、实验步骤1. 创建一个字符数组，包含待编码的字符。

2. 创建一个数组，用于存储每个字符的频率。

3. 对字符和频率进行排序。

4. 构建哈夫曼树，根据排序后的字符和频率，按照哈夫曼树的构建方法，将字符和频率插入到哈夫曼树中。

5. 实现哈夫曼编码功能，遍历哈夫曼树，记录从根节点到叶子节点的路径，即为每个字符的哈夫曼编码。

6. 实现哈夫曼译码功能，根据哈夫曼编码，从根节点开始，按照0和1的路径，找到对应的叶子节点，即为解码后的字符。

7. 测试实验结果，验证哈夫曼编码和译码的正确性。

五、实验结果与分析1. 构建哈夫曼树根据实验数据，构建的哈夫曼树如下：```A/ \B C/ \ / \D E F G```其中，A、B、C、D、E、F、G分别代表待编码的字符。

2. 哈夫曼编码根据哈夫曼树，得到以下字符的哈夫曼编码：- A: 00- B: 01- C: 10- D: 11- E: 100- F: 101- G: 1103. 哈夫曼译码根据哈夫曼编码，对以下编码进行译码：- 00101110111译码结果为：BACGACG4. 实验结果分析通过实验，验证了哈夫曼树和哈夫曼编码的正确性。

哈夫曼树的编码和解码是哈夫曼编码算法的重要部分，下面简要介绍其步骤：
1. 编码：
哈夫曼编码是一种变长编码方式，对于出现频率高的字符使用较短的编码，而对于出现频率低的字符使用较长的编码。

具体步骤如下：（1）根据字符出现的频率，构建哈夫曼树。

频率相同的字符，按照它们在文件中的出现顺序排列。

（2）从哈夫曼树的叶子节点开始，从下往上逐步进行编码。

对于每个节点，如果该节点有左孩子，那么左孩子的字符编码为0，右孩子的字符编码为1。

如果该节点是叶子节点，则该节点的字符就是它的编码。

（3）对于哈夫曼树中的每个节点，都记录下它的左孩子和右孩子的位置，以便后续的解码操作。

2. 解码：
解码过程与编码过程相反，具体步骤如下：
（1）从哈夫曼树的根节点开始，沿着路径向下遍历树，直到找到一个终止节点（叶节点）。

（2）根据终止节点的位置信息，找到对应的字符。

（3）重复上述步骤，直到遍历完整个编码序列。

需要注意的是，哈夫曼编码是一种无损压缩算法，解压缩后的数据与原始数据完全相同。

此外，由于哈夫曼编码是一种变长编码方式，因此在解码时需要从根节点开始逐个解码，直到解码完成。

（规格为A4纸或A3纸折叠）佛山科学技术学院（用四号宋体）实验报告（用小二号黑体）课程名称数据结构实验实验项目用Huffman树进行编码和解码算法专业班级姓名学号指导教师成绩日期（用小四号宋体）一、目的和要求1、通过本实验，熟悉二叉树、Huffman树的基本概念，掌握二叉树的存储结构及各种算法。

2、熟悉用Huffman树进行电文的加密与解密算法。

二、实验原理Huffman树是一种特殊的二叉树，其叶结点的编码是一种前缀码，同时，通过统计字符的频度，能够达到编码电文的最小化。

三、实验步骤1、统计电文中字符的出现频率。

2. 用统计频率建立Hffman树。

3．生成前缀码；4．建立huffman树的解码算法．5．用随机输入的电文完成编码与解码过程。

四、源程序#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX 100struct HTNode{char a;int weight;int parent,lchild,rchild;}*HT; //动态分配数组存储赫夫曼树char **HC;int n=0,m=0;char *write()//存储输入的电文{char *p,*q;printf("请输入电文(结束输入请按enter）：\n");p=(char *)malloc(MAX*sizeof(char));//申请存储输入的电文的空间if(!p) exit(0);q=p;scanf("%c",q);while(*q!='\n'){//******录入电文，每录入一个字符同时给电文长度计数器n加一*******//*****************遇到换行符时结束录入***************n=n+1;if(n>=MAX)//判断已申请的空间是否足够录入，不足则追加空间{p=(char *)realloc(q,(MAX+10)*sizeof(char));if(!p) exit(0);}q++;scanf("%c",q);}return(p);}void weight(char *p)//求电文中各字符的概率，并将该概率当作各字符的权值{char *q,*q1,temp;struct HTNode *q2;int i,j,t;q1=q=(char *)malloc(n*sizeof(char));for(;*p!='\n';p++,q1++) *q1=*p;//将电文存放到q1指向的空间中q1=q;for(i=0;i<n-1;i++){//*****对电文中的字符进行排序，使得相同的字符地址连续，方便统计***** t=i;for(j=i+1;j<n;j++)if(*(q1+t)>*(q1+j)) t=j;temp=*(q1+i);*(q1+i)=*(q1+t);*(q1+t)=temp;}temp=*q1;//标记当前为何种字符m=1;for(i=1;i<n;i++)//统计电文中出现过不同的字符的个数{q1++;if(temp!=*q1){m++;//字符种类计数器加一temp=*q1;}}q1=q;HT=(struct HTNode *)malloc(2*m*sizeof(struct HTNode));/*申请赫夫曼树HT的空间，其中0号单元不用*/q2=HT+1;//*****************初始化赫夫曼树HT*********************for(i=1;i<=n;){t=0;for(q2->a=*q1;*q1==q2->a;q1++){t++;i++;}q2->weight=(int)(t*100/n);q2->lchild=0;q2->parent=0;q2->rchild=0;q2++;}for(i=m+1;i<=2*m-1;i++,q2++){q2->lchild=0;q2->parent=0;q2->rchild=0;q2->weight=0;}free(q);}void Select(int t,int *s1,int *s2){/************在HT[1，t]选择parent为0且weight最小的两个结点，其序号分别为s1和s2。

哈夫曼编码与解码
哈夫曼编码（Huffman coding）和哈夫曼解码（Huffman decoding）是一种用于数据压缩的技术，由美国计算机科学家 David A. Huffman 于 1952 年提出。

哈夫曼编码的基本思想是根据字符在文本中出现的频率来分配二进制编码的长度。

出现频率较高的字符将被分配较短的编码，而出现频率较低的字符将被分配较长的编码。

这样，通过使用较短的编码来表示常见字符，可以实现更有效的数据压缩。

哈夫曼编码的过程包括以下步骤：
1. 统计字符出现频率：对要编码的文本进行分析，统计每个字符出现的次数。

2. 构建哈夫曼树：根据字符出现频率构建一棵二叉树，其中频率较高的字符靠近树的根节点，频率较低的字符位于树的叶子节点。

3. 分配编码：从根节点开始，根据字符出现频率为每个字符分配二进制编码。

左子节点表示 0，右子节点表示 1。

4. 编码文本：将文本中的每个字符替换为其对应的哈夫曼编码。

哈夫曼解码是哈夫曼编码的逆过程，用于将已编码的数据还原为原始文本。

解码过程根据哈夫曼树的结构和编码规则，从编码中解析出原始字符。

哈夫曼编码与解码在数据压缩领域具有广泛的应用，例如图像、音频和视频压缩。

它通过有效地利用字符频率分布的不均匀性，实现了较高的压缩率，从而减少了数据传输和存储的开销。

需要注意的是，哈夫曼编码是一种无损压缩技术，意味着解码后可以完全还原原始数据。

但在实际应用中，可能会结合其他有损压缩技术来进一步提高压缩效果。

福建农林大学金山学院实验报告系（教研室）：专业：计算机科学与技术年级：08 实验课程：姓名：学号：实验室号：_______ 计算机号：实验时间：指导教师签字：成绩：实验二：哈夫曼树及哈夫曼编码译码的实现（验证性、4学时）一、实验目的和要求构建哈夫曼树及哈夫曼编码，输出哈夫曼树及哈夫曼编码，完成编码与译码的算法。

（1）掌握树的有关操作算法（2）熟悉树的基本存储方法（3）学习利用树求解实际问题二、实验内容和原理定义哈夫曼树的存储结构；输入要编码的字符权重，根据权重建立哈夫曼树，并进行编码，最后输出哈夫曼编码。

三、实验环境硬件：（1）学生用微机（2）多媒体教室或远程教学（3）局域网环境软件：（1）Windows XP中文操作系统（2）Turbo C 3.0四、算法描述及实验步骤1．算法描述(1).建立哈夫曼树的算法定义各节点类型其中应包含两类数据一是权重域weight；一是指针域而指针域中应该包括指向左右孩子和指向双亲的指针这里分别用lchild、rdhild和parent来表示因此可用静态三叉链表来实现，在实际构造中由于是叶子节点来构造新的根节点其构造过程中仅与叶子节点的权重有关而与其数据域无关所以构造过程中不用考虑其数值域，并且在链表中从叶子开始存放，让后不断的将两颗最小权值的子树合并为一颗权值为其和的较大的子树，逐步生成各自内部节点直到树根。

(2).哈夫曼编码的算法将建立的哈夫曼树从每个叶子节点开始沿着双亲域回到根节点，梅走一步进行编码得到一位编码值；由于每个叶子节点的哈夫曼编码是从根节点到相应的叶子的路径的各个分支的代码组成的0和1序列，所以先得到了低位编码后得到高位编码因此可用一维数组从后向前来存放各位编码值，并用start来记录编码的起始位置。

2．算法流程图构建哈夫曼树算法流程哈夫曼编码算法流程3．代码仅作参考--redbatzero#include <stdio.h>#include <malloc.h>#define maxvalue 10000 //定义最大权值常量#define maxnodenumber 100 //定义节点最大数#define maxbit 10 //定义哈弗曼编码最大长度typedef struct //定义新数据类型即节点结构{int weight; //权重域int parent,lchild,rchild; //指针域}htnode; //节点类型标识符//typedef htnode * huffmanstree; //定义哈弗曼数类型htnode ht[maxnodenumber]; //定义三叉链表存储数组typedef struct //定义保存一个叶子节点哈弗曼编码的结构{int bit[maxbit]; //定义一维数组为编码域int start; //定义位置域}hcnodetype; //定义编码类型htnode * creatstree(int n) //huffmanstree creatstree(int n) //建立哈夫曼树算法实现函数{int i,j,m1,m2,k1,k2; //局部变量for(i=0;i<2*n-1;i++) //初始化各节点{ht[i].weight=0; //权重初始化为0ht[i].parent=-1; //根节点和给左右孩子初始化为-1ht[i].lchild=-1;ht[i].rchild=-1;}for(i=0;i<n;i++) //权重赋初值，由用户输入{scanf("%d",&ht[i].weight);}for(i=0;i<n-1;i++) //生成新节点构造哈夫曼树{m1=maxvalue; //预置最小权值变量为最大权值m2=maxvalue; //预置次小权值变量为最大权值k1=0; //预置最小权值节点位置为下标为0处k2=0; //预置次小权值节点位置为下标为0处for(j=0;j<n+i;j++) //循环找出每趟最下权值和所在位置if(ht[j].parent==-1&&ht[j].weight<m1){m2=m1;k2=k1;m1=ht[j].weight;k1=j;}else //当小于当前次小m2则更新m2及其位置if(ht[j].parent==-1&&ht[j].weight<m2){m2=ht[j].weight;k2=j;}ht[k1].parent=n+i; //修改最小权值节点的双亲为刚生成的新节点ht[k2].parent=n+i; //修改次小权值节点的双亲为刚生成的新节点ht[n+i].weight=ht[k1].weight+ht[k2].weight; //将新生成的权重值填入新的根节点ht[n+i].lchild=k1; //新生节点左孩子指向k1ht[n+i].rchild=k2; //新生节点右孩子指向k2}return ht; //返回哈夫曼树指针}void getstree(htnode * ht,int n) //哈夫曼编码算法及打印函数的实现{int i,j,c,p; //局部变量的定义hcnodetype cd[maxnodenumber]; //定义存储哈夫曼编码的数组for(i=0;i<n;i++) //循环控制对每一个节点进行编码{c=i; //为编码各节点初始化c和jj=maxbit;do{j--; //j指向bit中存放编码为的正确位置p=ht[c].parent; //p指向c的双亲节点if(ht[p].lchild==c) //如果c是p的左孩子cd[i].bit[j]=0; //编码为赋值0else //否则即c是p的右孩子cd[i].bit[j]=1; //编码赋值1c=p;//更新当前指针，为下一节点编码做准备}while(ht[p].parent!=-1); //判断是否编码结束即循环至最终根节点cd[i].start=j; //编码完成,记下编码开始位置}for(i=0;i<n;i++) //循环打印各节点哈夫曼编码{for(j=cd[i].start;j<maxbit;j++)//循环逐一输出printf("%d",cd[i].bit[j]);printf("\n"); //每输出一编码后换行}}int main() //主函数{int n;printf("请输入节点数:"); //用户输入节点数scanf("%d",&n);htnode * p; // huffmanstree p //定义哈夫曼树类型pp=(htnode * )malloc(sizeof(htnode *));//p=(huffmanstree)malloc(sizeof(huffmanstree))//分配内存空间p=creatstree(n);//调用建立哈夫曼树函数赋返回值给pgetstree(p,n); //调用编码函数读入建立的哈夫曼树p进行编码return 0;}五、调试过程出现该错误是因为type识别不了，即定义哈夫曼树时确切的说是type并不能定义htnode *标识符为huffmanstree：type htnode * huffmanstree这个小错误可以通过连个方法来修改一是将type改为typedef，当然直接删除该定义完全不会影响程序的执行，但在定义建立哈夫曼树函数时返回值应直接用htnode *；该错原因是参数未能成功传递，其中的ht[p]系统当做是未定义的类型可知，在getstree（htnode ht，int n）时正确的应当是传递哈夫曼树的头指针即数组首地址ht因此改为getstree（htnode * ht，int n）六、实验结果通过改正后成功编译连接，进行数据测试{5,20,12,7,47，9}当然编码因为定义时大小的左右排序是不同的所以编码也不唯一，但在这里是以左小右大来分布的，所以编码结果符合预期的。

一、问题描述1. 实验题目：huffman编解码2. 基本要求：初始化（I nitialization）。

从终端读入字符集大小n，以及n个字符和n个权值，建立Huffman 树，并将它存入hfmTree 中。

编码（E ncoding）。

利用已经建好的Huffman树（如果不在内存，则应从文件hfmTree 中读取），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。

解码（D ecoding）。

利用已经建立好的Huffman树将文件CodeFile中的代码进行解码，结果存入TextFile中。

打印代码文件（Print）。

将文件CodeFile以紧凑的格式显示在终端上，每行 50 个代码。

同时将此字符形式的编码文件写入文件CodePrint中。

打印Huffman树（T ree Printing）。

将已经在内存中的Huffman树以直观的形式（树或者凹入的形式）显示在终端上，同时将此字符形式的Huffman 树写入文件TreePrint中。

3. 测试数据：用下表给出的字符集和频度的实际统计数据建立Huffman树，并对以下报文进行编字符集大小 n，n个字符和 n个权值均从终端读入，初始化后的huffman树存储在hfmTree文件中，待编码文件为ToBeTran,编码结果以文本的方式存储在文件CodeFile中，解码文件存在TextFile中,打印的编码和赫夫曼树分别存储在CodePrint和TreePrint文件中。

用户界面可以设计为“菜单”方式：显示上述功能符号，再加上一个退出功能“Q”，表示退出（quit）。

用户键入一个选择功能符，此功能执行完毕后再显示此菜单，直至某次用户选择了Q为止。

二、需求分析1. 本程序可以根据输入字符集和频度建立huffman树并且对给定文本进行编解码，还可以直接读入建立好的huffman树再对给定文本编解码，打印编码、解码结果、表格形式及树形的huffman树。