北京邮电大学信息与通信工程学院
4. 总结
本次实验题目为哈夫曼树。
本次实验是在期末考试后进行了，经过了一学期的学习与期末复习，感觉对于数据结构的认识深刻了很多。
哈夫曼树是在学习第五章树的时候最后讲到的数据结构。相比于普通的树来说，海夫曼树的性质更为优良，首先它有权值，其次可以通过节点中编码域进行访问（例如0为左子树，1为右子树），最重要的是，哈夫曼树可以做到权值和最小。这一优良的性质使得其可以用于数据压缩，将权值看作字符出现的次数，而路径长度则是编码的路径。这样可以达到一种理想式的压缩效果。但是，如果压缩的字符串比较多的情况下，每个字符的哈夫曼编码会增加（因为树的层数在增加），这样压缩比会下降。虽然这个下降的趋势是逐渐减小的（因为每层具有的树节点的数量也在不断地增加）
本次编码的过程中一开始参考了教材上的代码，一些函数的实现是原创的。但是由于对于上界的理解不到位（n个叶子节点则一共有2n-1个节点）所以造成了原创代码的错误。后来在参考了教学辅导书后，发现了错误，更改了主函数与类函数的声明后，又加上了一些选作内容的代码，最后终于完成了本次实验。在完成之后还进行了一个有趣的测试：
在输入测试字符串后，发现随着字符串中字符种类的增加，压缩比在下降。最开始的只有两个字符的时候，压缩比（原串码长/编码串长）高达8。后来随着字符串种类的增加，压缩比下降明显，但是下降趋势是趋缓的。这就如我在前文中提到了一样，和哈夫曼树的结构有关。在之后的一次测试中，我输入了键盘上所有的字符，压缩比则跌到了1.2左右。这和相比最开始的压缩比已经很小了，此时压缩效果已经比较差了。这个测试说明，哈夫曼树编码的压缩效率很有限，无法适应于一般的编码情况。在压缩效率如此有限的情况下，却要额外付出时间和空间成本，并不是一种很好的压缩方法。
在浏览知乎的时候发现了一个很有意思的说法，要解决问题比如剔牙，只用基本的编程语言相当于用手抠，而数据结构则相当于用牙签，更加高效（各种数据结构留下了接口，使得操作变得多样化，比如二向链表可以极其方便的访问前驱后后继，普通的链表只能遍历），更加卫生（可以通过各种方式检测溢出，超限等等）。本学期的学习使我了解了很多的编程知识，比如一些基本的算法分析方法（时间复杂度，空间复杂度），很多的数据结构（线性表，栈串队列，树，图，多维数组），以及数据结构的使用方法（先定义存储结构，之后定义数据结构类）。本学期的学习也算是一次愉快的经历，虽然实验中的各种BUG不断，但是课程目标整体上还是脱离了普通的编程细节，而追求对算法和数据结构的宏观理解。在实验过程中，大量在网站上（CSDN，coDing）查找资料也让我们体验了一下程序员的生活。程序员并非是人形的编程语言字典，他对于算法和程序有一个整体的把握，同时直到各种数据结构的使用，通过合理应用各种已有的模板解决问题。
第5页
相关推荐：
loading