赫夫曼树的实现数据结构实验报告

《赫夫曼树的实现数据结构实验报告》由会员分享，可在线阅读，更多相关《赫夫曼树的实现数据结构实验报告（11页珍藏版）》请在装配图网上搜索。

1、精品范文模板 可修改删除撰写人：_日 期：_软件学院设计性实验报告专业：.NET 年级/班级： 20122013学年第一学期课程名称数据结构指导教师本组成员学号姓名实验地点实验时间第十二、十三、十四周项目名称哈夫曼编/译码系统的设计与实现实验类型设计性1问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编/译码系统。2一个完整的系统应具有以下功能：1）初始

2、化（Initialzation）。从数据文件DataFile.data中读入字符及每个字符的权值，建立哈夫曼树HuffTree；2）编码（EnCoding）。用已建好的哈夫曼树，对文件ToBeTran.data中的文本进行编码形成报文，将报文写在文件Code.txt中；3）译码（Decoding）。利用已建好的哈夫曼树，对文件CodeFile.data中的代码进行解码形成原文，结果存入文件Textfile.txt中；4）输出（Output）: 输出DataFile.data中出现的字符以及各字符出现的频度（或概率）；输出ToBeTran.data及其报文Code.txt；输出CodeFile.

3、data及其原文Textfile.txt；要求：所设计的系统应能在程序执行的过程中，根据实际情况（不同的输入）建立DataFile.data、ToBeTran.data和CodeFile.data三个文件，以保证系统的通用性。一、实验目的1、 掌握哈夫曼编码原理；2、 熟练掌握哈夫曼树的生成方法； 3、理解数据编码压缩和译码输出编码的实现。二、实验要求实现哈夫曼编码和译码的生成算法。三、实验内容先统计要压缩编码的文件中的字符字母出现的次数，按字符字母和空格出现的概率对其进行哈夫曼编码，然后读入要编码的文件，编码后存入另一个文件；接着再调出编码后的文件，并对其进行译码输出，最后存入另一个文件中。

4、四、实验原理1、哈夫曼树的定义：假设有n个权值，试构造一颗有n个叶子节点的二叉树，每个叶子带权值为wi，其中树带权路径最小的二叉树成为哈夫曼树或者最优二叉树；2、哈夫曼树的构造：weight为输入的频率数组，把其中的值赋给依次建立的HT Node对象中的data属性，即每一个HT Node对应一个输入的频率。然后根据data属性按从小到大顺序排序，每次从data取出两个最小和此次小的HT Node，将他们的data相加，构造出新的HTNode作为他们的父节点，指针parent，leftchild，rightchild赋相应值。在把这个新的节点插入最小堆。按此步骤可以构造构造出一棵哈夫曼树。 通

5、过已经构造出的哈夫曼树，自底向上，由频率节点开始向上寻找parent,直到parent为树的顶点为止。这样，根据每次向上搜索后，原节点为父节点的左孩子还是右孩子，来记录1或0，这样，每个频率都会有一个01编码与之唯一对应，并且任何编码没有前部分是同其他完整编码一样的。五、实验流程 初始化，统计文本文件中各字符的个数作为权值,生成哈夫曼树； 根据符号概率的大小按由大到小顺序对符号进行排序； 把概率最小的两个符号组成一个节点； 重复步骤（2）（3），直到概率和为1； 从根节点开始到相应于每个符号的“树叶”，概率大的标“0”，概率小的标“1”； 从根节点开始，对符号进行编码； 译码时流程逆向进行，从

6、文件中读出哈夫曼树,并利用哈夫曼树将编码序列解码。六、 实验程序数据结构：下面是编译码系统中所用的数据结构。在这个系统中，哈夫曼树的存储结构采用顺序存储；其结点结构为：程序中用到的头文件、类型定义及主要的函数原型如下：#include#include#include#includetypedef struct unsigned int weight;unsigned int parent,lchild,rchild;unsigned char ch;HTNode,*HuffmanTree; /动态分配数组存储赫夫曼树typedef char *HuffmanCode;/动态分配数组存储赫夫曼编

7、码表char str9= ,a,b,c,d,e,f,g,h;int m;void Select(HuffmanTree &HT,int i,int &s1,int &s2)int j,min1,min2;for(j=1;j=i;j+)if(HTj.parent=0)if(HTj.weights1|HTj.weight=s2) s1=HTj.weight; min1=j; else s2=HTj.weight; min2=j; s1=min1; s2=min2;void Print1(HuffmanTree HT)int i;printf(建立好的赫夫曼树的存储情况：n);printf(存储单元

8、字符权值双亲左孩子右孩子n); for(i=1;i=m;i+)printf( %-4d %c %-4d %-4d %d %dn,i,HTi.ch,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild);void Print2(HuffmanCode HC)int i;printf(各个字符的编码如下：n);for(i=1;i=8;i+)printf(%c的编码：%sn,stri,HCi);void Initialzation(int *w)FILE *fp;char a;int i;int n=0;if(fp=fopen(DataFile.data,wb)=N

9、ULL)printf(cannot open flien);return;printf(请输入数据字符（a-h）以#结束:n);a=getchar();for(i=0;a!=#;i+)fprintf(fp,%c,a); n+;switch(a)case a: w1+; break;case b: w2+; break;case c: w3+; break;case d: w4+; break;case e: w5+; break;case f: w6+; break;case g: w7+; break;case h: w8+; a=getchar();fclose(fp); printf(输

10、入的字符及其权值：n);for(i=1;i=8;i+)printf( ,stri,wi);printf(n);void EnCoding(HuffmanCode HC)printf(原文为：n);char s100,a; int i,n=0;a=getchar();for(i=0;a!=#;i+)si=a; n+;a=getchar();printf(报文为：n);for(i=0;in;i+)switch(si)case a: printf(%s ,HC1); break;case b: printf(%s ,HC2); break;case c: printf(%s ,HC3); break

11、;case d: printf(%s ,HC4); break;case e: printf(%s ,HC5); break;case f: printf(%s ,HC6); break;case g: printf(%s ,HC7); break;case h: printf(%s ,HC8); printf(n);void De(HuffmanTree HT) printf(报文为：n);char s100,a;int i,j,n=0;a=getchar();for(i=0;a!=#;i+)si=a; n+;a=getchar();for(i=1;i=m;i+)if(HTi.parent=

12、0) j=i;HT0=HTj; printf(译文为：n);for(i=0;i0），构造赫夫曼树HT，并求出n个字符的赫夫曼编码HCint i,start,c,f;int n=8;int s1,s2;HuffmanTree p;char *cd;if(n=1) return;m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /0号单元未用for(i=1,p=HT+1,w=w+1;iweight=*w;p-parent=0;p-lchild=0;p-rchild=0;p-ch=stri;for(;iweight=0;p-parent=0;p-

13、lchild=0;p-rchild=0;p-ch= ;p+;printf(初始化后的赫夫曼树的存储情况：n);printf(存储单元字符权值双亲左孩子右孩子n); for(i=1;i=m;i+)printf( %-4d %c %-4d %-4d %d %dn,i,HTi.ch,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild);for(i=n+1;i=m;i+) /建立赫夫曼树/在HT1.i-1选择parent为0且weight最小的两个结点，其序号分别为s1和s2s1=100;s2=100;Select(HT,i-1,s1,s2); HTs1.paren

14、t=i; HTs2.parent=i;HTi.lchild=s1; HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/*从叶子到根逆向求每个字符的赫夫曼编码*/ HC=(HuffmanCode)malloc(n+1)*sizeof(char *); /分配n个字符编码的头指针向量cd=(char*)malloc(n*sizeof(char); /分配求编码的工作空间cdn-1=0; /编码结束符for(i=1;i=n;i+)start=n-1; /编码结束符位置for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent

15、) /从叶子到根逆向求编码if(HTf.lchild=c) cd-start=0;else cd-start=1;HCi=(char *)malloc(n-start)*sizeof(char); /为第i个字符编码分配空间strcpy(HCi,&cdstart); /从cd复制编码（串）到HCfree(cd);/HuffmanCodingvoid main()HuffmanTree HT;HuffmanCode HC;int w9=0,x;/存放权值for(;)printf(n*n); printf(1.*输入字符及其权值n); printf(2.*初始化赫夫曼树n); printf(3.*

16、输出赫夫曼树n); printf(4.*输出各个字符及其对应的编码n); printf(5.*编码n); printf(6.*译码n); printf(7.*退出n);printf(n*n);scanf(%d,&x);switch(x) case 1: Initialzation(w); break;case 2: HuffmanCoding(HT,HC,w); break;case 3: Print1(HT); break;case 4: Print2(HC); break;case 5: EnCoding(HC); break;case 6: De(HT); break;case 7: exit(0); 七、运行的结果八、实验总结 在做时应该注意注释好有什么作用，还有实验时要细心，信心和细心是成功的基础所以一定要认真。我的心里还是认为要学会一定要听老师的话。自信心使人勇敢，自信的人总能轻松的度过困难，勇敢的面对生活中的挫折和挑战，学好每门语言都要有自信，才能真正的做好，学好！通过这次实验，我对哈夫曼编码都有一定的了解，掌握了它的构造方法，学会了从理论到实践的转换。在实验中也加强了与同学们的交流，分析能力有所提高，希望再接再厉！第 11 页 共 11 页免责声明：图文来源于网络搜集，版权归原作者所以若侵犯了您的合法权益，请作者与本上传人联系，我们将及时更正删除。