哈夫曼树 实验报告

《数据结构》实验报告书实验内容：哈夫曼树与哈夫曼编码201100814***计科111 ***前言计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习计算机编程仅仅了解计算机语言是不够的，还必须掌握数据的组织、存储和运算的一般方法，这便是数据结构课程中所研究的内容，也是我们编写计算机程序的重要基础，由于它对计算机学科起到承前启后的作用，因此本课程被列为计算机等相关专业最重要的专业基础课；同时数据结构是计算机专业教学的一门核心课程。

计算机各领域都要用到各种数据结构，而且要从事计算机科学与技术工作，尤其是计算机领域的软件开发工作，必须具备较强的数据结构基础。

数据结构课程内容丰富、学习量大，实践性强；隐含在各部分内容中的方法和技术多；算法设计具有动态性和抽象性等特点，看懂听明白与掌握会应用之间有相当大的一段距离。

所以学生必须多实践才能进一步加深对课程的理解，理解和掌握算法设计所需的方法和技术，为整个专业学习打下良好的基础。

一、实验目的1、使学生熟练掌握哈夫曼树的生成算法。

2、熟练掌握哈夫曼编码的方法。

二、实验内容[问题描述]已知n个字符在原文中出现的频率，求它们的哈夫曼编码。

[基本要求]1. 初始化：从键盘读入n个字符，以及它们的权值，建立Huffman树。

（具体算法可参见教材P147的算法 6.12）2. 编码：根据建立的Huffman树，求每个字符的Huffman编码。

对给定的待编码字符序列进行编码。

[选作内容]１. 译码：利用已经建立好的Huffman树，对上面的编码结果译码。

译码的过程是分解电文中的字符串，从根结点出发，按字符’0’和’1’确定找左孩子或右孩子，直至叶结点，便求得该子串相应的字符。

4. 打印 Huffman树。

［测试数据］利用教材P.148 例6－2中的数据调试程序。

可设8种符号分别为A,B,C,D,E,F,G,H。

编/译码序列为“CFBABBFHGH”(也可自己设定数据进行测试)。

数据结构课程设计设计题目：哈夫曼树编码译码目录第一章需求分析1第二章设计要求1第三章概要设计2（1）其主要流程图如图1-1所示。

3（2）设计包含的几个方面4第四章详细设计4（1）①哈夫曼树的存储结构描述为：4（2）哈弗曼编码5（3）哈弗曼译码7（4）主函数8（5）显示部分源程序：8第五章调试结果10第六章心得体会12第七章12附录：12第一章需求分析在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。

哈夫曼编码是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。

哈弗曼编码使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。

这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。

哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。

树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码。

哈弗曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。

第二章设计要求对输入的一串电文字符实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译码，输出电文字符串。

通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。

电报通信是传递文字的二进制码形式的字符串。

但在信息传递时，总希望总长度能尽可能短，即采用最短码。

假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为∑WiLi。

若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。

目录第一章哈夫曼树的基本术语 (1)1．1路径和路径长度 (1)1.2树的带权路径长度 (1)1．3哈夫曼树的定义 (1)第二章哈夫曼树的构造 (2)2.1哈夫曼树的构造 (2)第三章哈夫曼树的存储结构及哈夫曼算法的实现 (3)3.1哈夫曼树的存储结构 (3)3.2 哈夫曼算法的简要描述 (3)第四章哈夫曼树的应用 (5)4.1哈夫曼编码 (5)4.2求哈夫曼编码的算法 (5)4.21思想方法 (5)4.22字符集编码的存储结构及其算法描述 (6)4.3哈夫曼树和编码程序实现： (6)4.4程序运行结果： (9)心得体会 (10)参考文献 (10)第一章哈夫曼树的基本术语1．1路径和路径长度在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。

通路中分支的数目称为路径长度。

若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

1.2结点的权及带权路径长度若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。

结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

1.2树的带权路径长度树的带权路径长度(Weighted Path Length of Tree)：也称为树的代价，定义为树中所有叶结点的带权路径长度之和，通常记为：其中：n表示叶子结点的数目wi和li分别表示叶结点ki的权值和根到结点ki之间的路径长度。

1．3哈夫曼树的定义在权为wl ，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树。

[例]给定4个叶子结点a，b，c和d，分别带权7，5，2和4。

构造如下图所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别为：(a)WPL=7*2+5*2+2*2+4*2=36(b)WPL=7*3+5*3+2*1+4*2=4(c)WPL=7*1+5*2+2*3+4*3=35其中(c)树的WPL最小，可以验证，它就是哈夫曼树。

数据结构实验报告实验名称：实验三哈夫曼树学生姓名：班级：班内序号：学号：日期：程序分析：2.1 存储结构：二叉树2.2 程序流程：template <class T>class BiTree{public:BiTree(); //构造函数，其前序序列由键盘输入 ~BiTree(void); //析构函数BiNode<T>* Getroot(); //获得指向根结点的指针protected:BiNode<T> *root; //指向根结点的头指针};//声明类BiTree及定义结构BiNodeData：二叉树是由一个根结点和两棵互不相交的左右子树构成二叉树中的结点具有相同数据类型及层次关系哈夫曼树类的数据域，继承节点类型为int的二叉树class HuffmanTree:public BiTree<int>data:HCode* HCodeTable;//编码表int tSize; //编码表中的总字符数二叉树的节点结构template <class T>struct BiNode //二叉树的结点结构{T data; //记录数据T lchild; //左孩子T rchild; //右孩子T parent; //双亲};编码表的节点结构struct HCode{char data; //编码表中的字符char code[100]; //该字符对应的编码};待编码字符串由键盘输入，输入时用链表存储，链表节点为struct Node{char character; //输入的字符unsigned int count;//该字符的权值bool used; //建立树的时候该字符是否使用过Node* next; //保存下一个节点的地址};示意图：2.3 关键算法分析：1.初始化函数（void HuffmanTree::Init(string Input)）算法伪代码：1.初始化链表的头结点2.获得输入字符串的第一个字符，并将其插入到链表尾部,n=1(n记录的是链表中字符的个数)3.从字符串第2个字符开始，逐个取出字符串中的字符3.1 将当前取出的字符与链表中已经存在的字符逐个比较，如果当前取出的字符与链表中已经存在的某个字符相同，则链表中该字符的权值加1。

哈夫曼树的实验报告1一、需求分析1、本演示程序实现Haffman编/译码器的作用，目的是为信息收发站提供一个编/译系统，从而使信息收发站利用Haffman编码进行通讯，力求达到提高信道利用率，缩短时间，降低成本等目标。

系统要实现的两个基本功能就是：①对需要传送的数据预先编码；②对从接收端接收的数据进行译码；2、本演示程序需要在终端上读入n个字符（字符型）及其权值（整形），用于建立Huffman树,存储在文件hfmanTree.txt中；如果用户觉得不够清晰还可以打印以凹入表形式显示的Huffman树；3、本演示程序根据建好的Huffman树，对文件的文本进行编码，结果存入文件CodeFile中；然后利用建好的Huffman树将文件CodeFile中的代码进行译码，结果存入文件TextFile中；最后在屏幕上显示代码（每行50个），同时显示对CodeFile中代码翻译后的结果；4、本演示程序将综合使用C++和C语言；5、测试数据：(1)教材例6-2中数据：8个字符，概率分别是0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，可将其的权值看为5，29，7，8，14，23，3，11(2)用下表给出的字符集和频度的实际统计数据建立Haffman树，并实现以下报文的编码和一、概要设计1、设定哈夫曼树的抽象数据类型定义ADT Huffmantree{数据对象：D={a i| a i∈Charset,i=1,2,3,……n,n≥0}数据关系：R1＝{< a i-1, a i >| a i-1, a i∈D, i=2,3,……n}基本操作：Initialization(&HT，&HC,w，n,ch)操作结果：根据n个字符及其它们的权值w[i],建立Huffman树HT,用字符数组ch[i]作为中间存储变量，最后字符编码存到HC中；Encodeing(n)操作结果：根据建好的Huffman树，对文件进行编码，编码结果存入到文件CodeFile 中Decodeing(HT,n)操作结果：根据已经编译好的包含n个字符的Huffman树HT，将文件的代码进行翻译，结果存入文件T extFile中} ADT Huffmantree1）主程序模块void main(){输入信息，初始化；选择需要的操作；生成Huffman树；执行对应的模块程序；输出结果；}2）编码模块——根据建成的Huffman树对文件进行编码；3）译码模块——根据相关的Huffman树对编码进行翻译；各模块的调用关系如图所示二、详细设计1、树类型定义typedef struct {unsigned int weight; //权值char ch1; //储存输入的字符unsigned int parent,lchild,rchild;}HTNode,*HuffmanTree;2、编码类型定义typedef char **HuffmanCode;哈夫曼编译器的基本操作设置如下Initialization(HuffmanTree &HT，HuffmanCode &HC,int *w，int &n,char *ch) //根据输入的n个字符及其它们的权值w[i],建立Huffman树HT,用字符数组ch[i]作为中间存储变量存储编码，最后转存到HC中；Encodeing(int n)//根据建好的包含n个字符的Huffman树，对文件进行编码，编码结果存入到文件CodeFile中Decodeing(HuffmanTree HT,int n)//根据已经编译好的包含n个字符的Huffman树HT，对文件的代码进行翻译，结果存入文件TextFile中基本操作操作的算法主函数及其他函数的算法void select(HuffmanTree HT,int n,int &s1,int &s2){ //依次比较，从哈夫曼树的中parent为0的节点中选择出两个权值最小的if(!HT[i].parent&&！HT[S1]&&!HT[S2]){if(HT[i].weight<ht[s1].weight){< p="">s2=s1; s1=i;}else if(HT[i].weight<ht[s2].weight&&i!=s1)< p=""> s2=i;}3、函数的调用关系图三、调试分析Encodeing Decoding Print PrintTreeInitialization1、本次实习作业最大的难点就是文件的读和写，这需要充分考虑到文件里面的格式，例如空格，换行等等，由于不熟悉C++语言和C语言的文件的输入和输出，给编程带来了很大的麻烦；2、原本计划将文本中的换行格式也进行编码，也由于设计函数比较复杂，而最终放弃；3、一开始考虑打印哈夫曼树的凹入表时是顺向思维，希望通过指针的顺序变迁来实现打印，但问题是从根结点到叶子结点的指针不是顺序存储的，所以未能成功，后来查找相关资料，最终利用递归的方法解决问题；4、程序中的数组均采用了动态分配的方法定义，力求达到减少空间的浪费；5、时间的复杂度主要是由查树这个步骤决定，因为无论是编码还是译码都需要对Huffman树进行查找和核对，但考虑到英文字母和空格也就是27个字符，影响不是很大；6、程序无论在屏幕显示还有文件存储方面都达到了不错的效果；7、程序不足的地方就是在文件文本格式方面处理得还是不够，或许可以通过模仿WORD的实现来改善。

哈夫曼树实验报告需求分析：从终端读入一串字符，利用建立好的哈夫曼树对其进行编码，储存到文件当中去，然后从文件读入哈夫曼编码，针对每个字母对其进行译码，翻译为原来的信息。

二、概要设计程序分为以下几个模块：1、从终端读入字符集大小，n个字符和n个权值，建立哈夫曼树，写入文件hfmTree中去。

2、对hfmTree进行编码，建立hfm编码表。

3、从文件ToTran读入信息，根据hfm编码表对其进行hfm编码，将编码后的信息写入文件Codefile 中去4、对Codefile文件反向译码，结果储存在Textfile中去。

5、将建立的hfmTree打印在终端上，并储存于相应的Treeprint文件中去。

抽象的数据定义如下：哈夫曼树结构typedef struct //定义哈夫曼树的结构{int weight; //权值int parent; //双亲int lchild; //左孩子int rchild; //右孩子}htnode,huffmantree[M+1];建立哈夫曼树void crthuffmantree(huffmantree ht,int w[],int n) //初始化哈夫曼树{int i,s1,s2,m;for(i=1;i<=n;i++){ht[i].weight=w[i];ht[i].parent=0;ht[i].lchild=0;ht[i].rchild=0;}m=2*n-1;for(i=n+1;i<=m;i++){ht[i].weight=0;ht[i].parent=0;ht[i].lchild=0;ht[i].rchild=0;}for(i=n+1;i<=m;i++){select(ht,i-1,&s1,&s2);ht[i].weight=ht[s1].weight+ht[s2].weight;ht[s1].parent=i;ht[s2].parent=i;ht[i].lchild=s1;ht[i].rchild=s2;}}typedef char *huffmancode[N+1]; //建立哈夫曼树编码表void crthuffmancode(huffmantree ht,huffmancode hc,int n){char *cd; //新建立一个指针int start,i,c,p;cd=(char*)malloc(n*sizeof(char))；//分配求一个字符的哈夫曼编码的空间cd[n-1]='\0'; //编码结束符for(i=1;i<=n;i++){start=n-1;c=i;p=ht[i].parent;while(p!=0){--start;if(ht[p].lchild==c)cd[start]='0';elsecd[start]='1';c=p;p=ht[p].parent;}hc[i]=(char *)malloc((n-start)*sizeof(char));strcpy(hc[i],&cd[start]);}free(cd);}select(huffmantree ht,int pos,int *s1,int *s2) //取最小和次小权值{int j,m1,m2;m1=m2=maxint;for(j=1;j<=pos;j++){if(ht[j].weight<m1&&ht[j].parent==0) //定义为双亲为零时才开始求，这样就做到了防止筛选过的重新加入比较列表里{m2=m1;*s2=*s1;*s1=j;m1=ht[j].weight;}else if(ht[j].weight<m2&&ht[j].parent==0){m2=ht[j].weight;*s2=j;}}}主程序模块int main(){初始化参数printf("请输入：初始化 I;编码 E;译码 D;印代码文件 P;印哈弗曼树 T\n");printf("结束请输入Q\n");while(1){ //这就是用户输入scanf("%c",&q);if(q=='Q'){break;}if(q=='I'){fpw=fopen("hfmtree.txt","w");ftest=fopen("date.txt","r");printf("请输入密码表，第一位表示密码表大小，之后按空格键开始以紧凑的格式输入编码字母和权值。

霍夫曼树实验目的：掌握结构体、指针及二叉树的生成、遍历等操作掌握霍夫曼编码/译码的原理。

基本要求：熟练掌握树的操作。

程序实现：程序第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并把树的信息保存起来，以便解压时创建同样的哈夫曼树进行解压；第二遍，根据第一遍扫描得到的哈夫曼树进行编码，并把编码后的码字存储。

要点分析:题目中涉及的主要知识点：1、本程序参考霍夫曼算法（由给定的权值构造赫夫曼树）：（1）由给定的n个权值{w0, w1, w2, …, wn-1}，构造具有n棵二叉树的集合F ={T0, T1, T2, …, Tn-1}，其中每一棵二叉树Ti只有一个带有权值wi的根结点，其左、右子树均为空。

（2）重复以下步骤, 直到F中仅剩下一棵树为止:①在F中选取两棵根结点的权值最小的二叉树, 做为左、右子树构造一棵新的二叉树。

置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。

②在F中删去这两棵二叉树。

③把新的二叉树加入F。

2、用构造赫夫曼树以完成赫夫曼编码:把d1,d2,…, dn 作为叶子结点，把w1,w2,…,wn作为叶子结点的权，构造赫夫曼树。

在赫夫曼树中结点的左分支赋0，右分支赋1，从根结点到叶子结点的路径上的数字拼接起来就是这个叶子结点字符的编码。

3、译码的过程是分解电文中的字符串，从根出发，按字符‘0’或‘1’确定找左孩子或右孩子，直至叶子节点，便求得该子串相应的字符。

心得体会：通过本次实验，我熟练掌握了结构体、指针及二叉树的生成、遍历等操作，掌握了霍夫曼编码和译码的原理，熟练掌握树的操作，尤其是对霍夫曼树有了更深刻的理解。

同时，在编写代码的过程中方，对字符串的相关知识进行了回顾。

代码#include<stdio.h>#include<stdlib.h>#include<string.h>typedef struct{int weight;int parent,lchild,rchild;int sign;}HTNode,*HuffmanTree;typedef char * *HuffmanCode;void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n,char *s);void select(HuffmanTree &HT,int i,int &s1,int &s2);void creatHuffmanTree(int *w,char *s,char *r);void pr(HuffmanCode &HC,char r[],char s,char a[]);void HuffmanYM(HuffmanCode &HC,char r[],char a[],int n,HuffmanTree &HT);void HuffmanPass(HuffmanCode &HC,char r[],int n,HuffmanTree &HT);int main(){char s[100];char r[100];char a[100]="a";int w[100];int n,p;HuffmanTree HT;HuffmanCode HC;printf("请输入进行编码的字符串\n");scanf("%s",s);p=strlen(s);if(p!=1)creatHuffmanTree(w,s,r);printf("进行编码......\n");if(p!=1)HuffmanCoding(HT,HC,w,strlen(r)-1,r);else printf("%c的霍夫曼编码是: %c\n",s[0],'0');printf("霍夫曼码序列为：\n");if(p!=1)for(int i=0;i<strlen(s);i++)pr(HC,r,s[i],a);printf("\n");n=strlen(r)-1;if(p==1)printf("0\n");printf("霍夫曼编码进行译码:\n");if(p==1)printf("%c",s[0]);else HuffmanYM(HC,r,a,n,HT);printf("\n");printf("先序遍历输出叶子节点\n");if(p==1){printf("%c\n",s[0]);}else HuffmanPass(HC,r,n,HT);return 0;}void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int w[],int n,char s[]) {int s1,s2,f,c;int m,i,l;int start;char cd[101];if(n<1)return;l=strlen(s);m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));HT[0].weight=10000;for (i=1;i<=n;++i){HT[i].weight=w[i-1];HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;HT[i].sign=0;}for(;i<=m+1;++i){HT[i].weight=0;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;HT[i].sign=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;}HC=(HuffmanCode)malloc((n+1)*sizeof(char *));cd[n-1]='\0';for(i=1;i<=n;i++){start=n;c=i;for(f=HT[i].parent;f!=0;f=HT[f].parent){if(HT[f].lchild==c){start--;cd[start]='0';}else{start--;cd[start]='1';}c=f;}HC[i]=(char *)malloc((n-start)*sizeof(char));for(int a=0;a<n-start;a++){HC[i][a]=cd[start+a];}HC[i][a]='\0';printf("%c的霍夫曼编码是: %s\n",s[i],HC[i]);}}void select(HuffmanTree &HT,int i,int &s1,int &s2){s1=0;s2=0;for(int j=1;j<=i;j++){if(HT[j].parent==0)if(HT[j].weight<=HT[s1].weight)s1=j;else continue;}else continue;}for(j=1;j<=i;j++){if(j==s1)continue;elseif(HT[j].parent==0){if(HT[j].weight<=HT[s2].weight)s2=j;else continue;}else continue;}}void creatHuffmanTree(int w[],char s[],char r[]) {int g=1;int q=0;r[0]='0';r[1]=s[0];w[0]=1;for(int e=1;e<strlen(s);e++){for(int k=1;k<=g;k++){if(r[k]==s[e]){w[k-1]++;q=1;}else continue;}if(q==0){r[++g]=s[e];w[g-1]=1;q=0;}r[++g]='\0';}void pr(HuffmanCode &HC,char r[],char s,char a[]){for(int i=1;i<strlen(r);i++){if(r[i]==s){printf("%s",HC[i]);strcat(a,HC[i]);}else continue;}}void HuffmanYM(HuffmanCode &HC,char r[],char a[],int n,HuffmanTree &HT) {int e=strlen(a);int k=0;int f=2*n-1;char b[10]="1";for(int j=1;j<=e;j++){if(HT[f].lchild!=0||HT[f].rchild!=0){b[k]=a[j];k++;if(a[j]=='1')f=HT[f].rchild;else if(a[j]=='0')f=HT[f].lchild;}else{for(int s=1;s<=n;s++){if(strcmp(HC[s],b)==0){printf("%c",r[s]);break;}else continue;}for(int u=0;u<10;u++)b[u]='\0';k=0;f=2*n-1;j=j-1;}}}void HuffmanPass(HuffmanCode &HC,char r[],int n,HuffmanTree &HT) {int f,k=0;char b[10]="a";f=2*n-1;HT[f].sign=0;if(HT[f].lchild==0&&HT[f].rchild==0)return;do{if(HT[f].lchild==0&&HT[f].rchild==0){for(int s=1;s<=n;s++){if(strcmp(HC[s],b)==0){printf("%c",r[s]);break;}else continue;}b[k--]='\0';HT[f].sign=2;f=HT[f].parent;}if(HT[f].sign==0){b[k]='0';HT[f].sign++;f=HT[f].lchild;k++;}elseif(HT[f].sign==1){b[k]='1';HT[f].sign++;f=HT[f].rchild;k++;}elseif(HT[f].sign==2){f=HT[f].parent;b[k--]='\0';}}while(f!=0);printf("%\n");}。