《哈夫曼树及哈夫曼编码译码的实现》由会员分享，可在线阅读，更多相关《哈夫曼树及哈夫曼编码译码的实现（13页珍藏版）》请在金锄头文库上搜索。
1、福建农林大学计算机与信息学院（程序设计类课程）实验报告课程名称：数据结构姓名：邓建国系：计算机与信息学院专业：网络工程年级：09级学号：091154050指导教师：黄思先职称：副教授福建农林大学计算机与信息学院实验报告系：计算机与信息专业:网络工程年级:09级姓名： 邓建国 学号: 091154050 实验室号： 计算机号： 实验二哈夫曼树及哈夫曼编码译码的实现一、实验目的和要求1, 掌握树及二叉树的基本概念2, 熟悉二叉树的运算和应用3, 理解哈夫曼树的概念及哈夫曼编码译码的实现二、实验内容和原理实验内容：输入一个电文字符串，构造出哈夫曼树并实现该字符串的二进制输出，并统计该字 符串中的字符
2、总数目及二进制编码的总长度。实验原理：哈夫曼树是由n个带权叶子结点构成的所有二叉树中带权路径长度WPL最小的二 叉树。本实验中，要输入电文字符以及它的权值，用Hunffman算法构建哈夫曼树。定 义一个存储哈夫曼编码结果的二维数组。为使每一个字符编码都不是另一个字符编码的 前缀，规定哈夫曼树中左分枝以“0”编码，右分枝以“1”编码。三、实验环境硬件环境：多媒体实验室学生用微机 局域网环境软件环境:Windows xp professionalTurbo C/C+ for windows四、算法描述及实验步骤1,算法描述inti, j;4 i=lprintf( %c： jhufftnancode
3、i. ch);j二huffmanucide i. wtart-lp工intf(、huffm血匚口己已i cod.LIp工in妊 tRnd;htlchrchparentQQQ59193261545657673, 4 , 2, 10为叶子权值。0123456abcd3231011000101chcodestar2,算法描述及实验步骤starstar star在Turbo C/C+ for windows新建名为huffman.c的c程序项目，然后进行编译调试，若编译链接都通过，则运行程序，得出正确结果。正确的程序代码如下所示:#include stdio.h#include conio.h#inc
4、lude string.h#define NO 10typedef struct nodel int w,lch,rch,parent;HFT2*N0-1+1;/哈夫曼树结点的数据类型HFT ht;struct node2 char ch;int start;int codeN0;hcN0+1;/字符的哈夫曼编码信息的数据类型int n,m;void select(int t, int *s1, int *s2)选择一个权值最小和次小的结点作为叶子结点 int w1=32767,w2=w1,i;for(i=1; i=t; i+)if( hti.parent=0 )先找出前面2个无双亲(即未合并
5、的)结点的位置if( hti.w w1 )选择权值最小和次小的数w2=w1;*s2=*s1;w1=hti.w;*s1=i;s1指向最小的数 else if( hti.w w2 ) w2=hti.w;*s2=i;s2指向次小的数void creat_ht_hc() /建立哈夫曼树的函数 int s1,s2,i,child,parent;freopen(huffman.in, r, stdin);读取文件信息，文件名为 huffman.infreopen(huffman.out, w, stdout); 写入文件信息，文件名为 huffman.out scanf(%d, &n);输入叶子个数nm=
6、2*n-1;总结点数m为2*n-1for(i=l; iv=n; i+)分别输入叶子字符以及它的权值scanf(n%c%d, &hci.ch, &hti.w);for(i=n+1; i=m; i+)建树 select( i-1, &sl, &s2 );调用 select。函数hti.w = hts1.w+hts2.w;hti.lch=s1;hti左孩子指向最小的数hti.rch=s2;hti右孩子指向次小的数hts1.parent=hts2.parent=i;for(i=1; i=n; i+)/生成哈夫曼编码的函数 child=i;/从叶子开始parent=htchild.parent;whil
7、e(child!=m) /查找直到哈夫曼树根结点的路径 if( child=htparent.lch )hci.codehci.start=0; / 左分枝编码为 0elsehci.codehci.start=1; / 右分枝编码为 1 hci.start+; /校正编码的指针位置 child=parent;parent=htchild.parent;void showtree(int root, int tab)哈夫曼树的显示 if(root)从根开始，如果根结点不为空 int i;for(i=1; i=tab; i+) printf(); 输出空格 printf(%d,htroot.w);
8、/ 输出根结点权值if(htroot.lch=0)如果左孩子为 0printf(%c), hcroot.ch);输出根字符printf(n);showtree(htroot.lch, tab+3);沿左链下降showtree(htroot.rch, tab+3);沿右链下降void showcode() int i,j；显示哈夫曼编码for(i=l; i=0； j-)依次输出结点的编码printf(%d, hci.codej);printf(n);void char2bit(char Sin, char Sout)加密，把字符转化为编码 int i,j,k,p=0;i=0;while( Sin
9、i) for(j=1; j=0; k-)Soutp+=hcj.codek+48; /*Soutl里面存储的是字符，code存储的是数字，字符0,1,2.9 的 ASCII是 48, 49.57*/break;i+;Soutp=0;void bit2char(char Sin, char Sout)解密把哈夫曼编码转化为字符 int i=0,k=m,p=0;while( Sini) if( htk.lch=0 ) Soutp+=hck.ch; k=m;else if( Sini=0)k=htk.lch;如果结点左孩子为0/把字符存入Sout里否则结点左孩子不为0如果Simi是字符0沿左链下降el
10、se k=htk.rch;否则沿右链下降i+;Soutp+=hck.ch;把字符存入 Sout 里Soutp=0;main() char Sin2*N0+l, Sout2*N0+l;定义两个字符数组clrscr();清屏creat_ht_hc();调用creat_ht_hc()创建哈夫曼树showtree(m,1);调用showtree(m,1)显示哈夫曼树showcode();调用showcode()显示哈夫曼编码gets(Sin); gets(Sin);char2bit(Sin, Sout);加密，把字符转化为编码puts(Sout);输出gets(Sin);bit2char(Sin, S
11、out);解密，把编码转化为字符puts(Sout);输出五、调试过程调试过程前面建树过程没错，当输入caabd，和01001001110111进行加密和解密却错了,错误如下：经排除在主函数用gets(Sin);输入字符串是少写了一个gets(Sin);改正如上程序的主函数第7行, 改正之后运行正确.六、实验结果最后的运行结果如下:七、总结通过实验，使我对树的结构有了新的认识。在今后学习数据结构的过程中有很大的帮助，也在 编程的过程中掌握了更多编程上的技巧,如使用文件进行输入输出。参考文献：1 宁正元，王秀丽一一算法与数据结构清华大学出版社 20062 严蔚敏 吴伟民 数据结构（C语言版）清华大学出版社 2006宁正元，王秀丽算法与数据结构习题精解和实验指导 清华大学2007
