《数据结构C语言哈夫曼编码译码》由会员分享，可在线阅读，更多相关《数据结构C语言哈夫曼编码译码（16页珍藏版）》请在装配图网上搜索。
1、实训报告题 目： 哈夫曼树编码译码院 系： 信息工程系专 业： 计算机科学与技术（网络方向）姓 名： 梁展荣 学 号： 1151220115 指导教师： 赵莹莹 刘欣 日 期： 2013年7月3日 桂林电子科技大学信息科技学院目 录一、设计思想1 1.1建立哈夫曼树的思想1 1.2建立哈夫曼编码表2 1.3对文件进行编码21.4对文件进行解码2二、算法流程图3三、运行结果8四、遇到的问题及解决10五、心得体会13一、设计思想要完成哈夫曼的编码和解码需要首先建立哈夫曼树，之后对所有字符根据权重进行编码，最后再对文件内容进行编码和解码。1.1建立哈夫曼树的思想。首先定义适合哈夫曼树的节点类型，需要
2、定义的有当前节点的字符，当前节点的左子、右子和父亲指针。在建立哈夫曼树之前还需要对出现的字符和权重进行统计和记录，并且定义一个可以筛选出最小权重的函数。初始化树节点之后开始建立哈夫曼树。先在所有可能出现的字符中筛选出当前权重最小的两个字符，将这两个字符分别作为新节点的左子和右子建立一个小的二叉树，并将两个字符的权重之和赋值给新节点，将新二叉树放入筛选字符中，再将筛选过的两个字符从筛选列表中淘汰掉。依次对列表中剩下的字符进行权重最小的筛选，直到根节点（如果编码表共有N个字符，则2*N-1就为最终根节点）为止，也就是当筛选列表为空的时候，哈夫曼树即建立完成。对于哈夫曼编码树来说，由于哈夫曼编码是前
3、缀码，所以所有要编码的字符最终都将是这颗树的叶子节点，而其它节点并没有真正的字符意义。即当哈夫曼编码树建立之后，对树的所有叶子节点进行打印可知道是否有字符遗漏或多余。1.2建立哈夫曼编码表。建立编码表时要根据每个出现的字符的权重对建立的哈夫曼树的每个叶子节点进行编码。编码时要从叶子节点出发向根节点进行逆向编码。判断如果当前节点为左子则对其编码0，如果当前节点为右子则对其编码1。以此类推进行编码直到根节点为止。此时的编码是逆向的，所以需要将码值逆向存储。依次对每一个叶子节点进行编码操作，即可得到当前哈夫曼树的编码表。对于码值的逆向存储可以使用栈结构，先将一个码的每一步编码存入栈，再在一个码结束后
4、出栈至空。当然也可以定义一个字符型数组，将值从后向前存入数组，再将数组有值部分粘贴到新的数组中进行存储。本次采用了后者，因为个人认为为此一步操作建立栈结构不划算，而且前一个设计也已经熟练掌握了栈的方法，此处进行新的尝试会更好。1.3对文件进行编码。首先需要建立一个原始文件，在文件中输入需要编码的内容。之后将文件打开，将其中的内容存储到字符串中以便程序编码调用。开始对需要编码的字符进行编码，将字符逐一读取与刚刚建立的编码表中的每个叶子节点代表的字符进行比较，找出相同的对象，并将当前节点的编码打印到屏幕，并将编码存入到新建的密码文件当中。1.4对文件进行解码。先打开密码文件，将之前编码后得到的密文
5、内容存储到字符串中以便解码调用。开始对密文的字符串进行解码，树索引从根节点开始走，当密文中的当前字符是0的时候，则索引走向左子节点；当是1的时候，则走向右子节点。以此类推，一直走到叶子节点为止，则当前叶子节点所代表的字符即为前一段密文的解码结果，。再对下一个字符依次从根节点开始解码，如此循环对每一段密文进行解码直到解码结束。将解码打印到屏幕，并将解码结果存入到新的解码文件当中。在解码之前，还应该先确认之前是否建立了哈夫曼树并且是否构建了编码表。不过由于本次将a到z都进行了编码，所以此步省略了，因为编码表是唯一的。需要的时候可以在Encoder 函数中先进行判定。将编码和解码写在了一起，可以在运
6、行时进行选择调用。二、算法流程图第一步：建立哈夫曼树。图1建立哈夫曼树的算法流程图第二步：构建哈夫曼编码表。图2构建哈夫曼编码表的算法流程图第三步：编码。图3 编码算法流程图第四步：解码。图4 解码算法流程图四、运行结果原文文件：图5 中缀转后缀运行结果图编码图：图6 编码图密文文件：图7 密文文件图解码图：图8 解码图译文文件：图9 译文文件图整体运行图：图10 编码解码整体运行图五、遇到的问题及解决这部分我主要遇到了如下两个问题，其内容与解决方法如下所列：l 第一个问题是权重的筛选部分出现了错误解决办法：一开始对于筛选最小权重的代码编写如下：void SelectMin(HFMT T,in
7、t i,int *p1,int *p2) int j, min=999; for(j=0;jTj.weight) min=Tj.weight; *p1=j; min=999; for(j=0;jTj.weight&j!=(*p1) min=Tj.weight; *p2=j; 因为权重中最大的就是字符e的权重103，所以为初始值min赋值时觉得999就已经是无限大了。但是后来发现编码不知确，就开始思考是什么问题。发现每次筛选都将会把最小的两个权重进行相加，所以很快就会超过999，编码自然就出现了问题。所以后来将min定义成了long型，并赋值999999，问题就解决了。l 第二个问题是生成编码表
8、的时候如何将逆向编码正向存储解决办法：对于求编码的时候，由于是从叶子节点向根顺次而求，所以编码结果将是逆向的。一开始想到的办法是利用栈的结构，将编码依次存入栈中，再在一个字符编码结束时将栈倒空，这样就可以将编码正向存储了。但是又在考虑如果不用栈时候也可以做到。后来想到了strcpy函数对字符数组进行链接。所以就可以定义一个数组，从后向前存储编码，再在一个字符编码结束时将这个数组有值的重新存入新数组中，即可以成为正向编码了。最终实现编码如下：HFCode hfEn(HFMT T) int i,f,c,start; HFCode hc; char *cd; hc=(char *)malloc(N+
9、1)*sizeof(char*); cd=(char)malloc(N*sizeof(char); cdN-1=0; for(i=0;iN;i+) start=N-1; for(c=i,f=Ti.parent;f!=-1;c=f,f=Tf.parent) if(Tf.left=c) cd-start=0; else cd-start=1; hci=(char *)malloc(N-start)*sizeof(char); strcpy(hci,&cdstart); return hc;六、心得体会 通过对本次的编写，使我掌握了哈夫曼编码的特点、存储方法和基本原理，培养了我运用C语言正确编写程序
10、以及调试程序的能力。哈夫曼编码的结构取决于可能出现的字符的个数和其所对应的权值，权值大的编码短，权值小的编码长。这样的结构会利用比较小的空间存储数据。而且，利用树的结构对其编码和对其解码，也是比较规格话，比较方便的。本次编程还运用了结构体，便捷的对树节点和树以及编码表进行定义和调用。并且了解到当求解一个算法时，不是拿到问题就不假思索去做，而应该首先对它有个整体的概念，再一步步对其进行分析。在分析的过程中也应该学会随时总结问题，将遇到的问题融会贯通，以便在将来需要的时候能够应用自如。本次设计中也存在一些一开始不容易解决的问题，但当对算法的进一步分析和对相关信息的查阅，也比较顺利的完成了设计。虽然路途比较艰辛，但奋斗的经历却成为了最宝贵的人生经验。
数据结构C语言哈夫曼编码译码
