哈夫曼树试验报告

1、哈夫曼树实验报告北京邮电大学信息与通信工程学院2009级数据结构实验报告 实验名称 : 实验三哈夫曼树 学生姓名 : 袁彬班 级 : 2009211119 班班内序号 : 09学 号 : 09210552日 期: 2010 年 12 月 10 日1( 实验要求1.1 程序要求(1) 、初始化 (Init):能够对输入的任意长度的字符串 s 进行统计，统计每个字符的频度，并建立哈夫曼树。(2) 、建立编码表 (CreateTable): 利用已经建好的哈夫曼树进行编码，并将每 个字符的编码输出。(3) 、编码 (Encoding): 根据编码表对输入的字符串进行编码，并将编码后的字 符输出。 (

2、4) 、译码 (Decoding): 利用已经建好的哈夫曼树对编码后的字符串进行 译码，并输出译码结果。(5) 、计算输入的字符串编码前后的长度，并进行长度分析，讨论哈夫曼树的 压缩效果。 测试数据如下 :I love data structure,I love computer.I will try my best to study data structure.1.2 代码要求(1) 、必须要有异常处理，比如删除空链表时要抛出异常(2) 、保持良好的编程风格 :a. 代码之间要有空行和缩进 ;b. 标识符名称应该与其代表意义一致 ;c. 函数名称之间应该添加注释说明该函数的功能 ;d. 关

3、键代码应说明其功能 ;(3) 、递归程序注意调用的过程，防止栈溢出。2. 程序分析第1页北京邮电大学信息与通信工程学院2.1 存储结构a. 哈夫曼树的存储结构该程序使用一个静态三叉链表来存储哈夫曼树 :weight LChild RChild Parent2 -1 -1 4 01 3 -1 -1 42 6 -1 -1 53 9 -1 -1 64 5 1 1 55 11 2 2 66 20 5 5 -1 b.哈夫曼编码表的存储结构把每个字符 data 及对应的编码 code 用一个结点存储，将所有的结点存储在数 组中:data CodeZ 100 0C 101 1B 11 23 A 0c. 录入

4、字符串以及存储字符的数组 a 、b 的获取 : 先将录入的字符串存在一个字符数组 S 中，然后遍历数组 S ，先建立一个 空的循环链表，然后再遍历数组 S 的同时往链表里插入新的结点或者修改相应结点中的域 值:data weight next rear空循环链表rear2.2 关键算法分析a. 初始化哈夫曼树 : 用数组 a 初始化哈夫曼树 :从 0 到 n-1 循环，分别对树中结点赋值 :HTreei.weight=ai;HTreei.lchild=-1;HTreei.rchild=-1; HTreei.parent=-1;b. 创建哈夫曼树 :(1) 、从 1 i 中选择两个最小的结点 :

5、SelectMin(x,y,0,i);(2) 、将选中的两个结点插入到树中 : HTreex.parent=HTreey.parent=ii;HTreeii.weight=HTreex.weight+HTreey.weight;HTreeii.lchild=x;第2页北京邮电大学信息与通信工程学院HTreeii.rchild=y;HTreeii.parent=-1; d. 创建编码表 :(1) 、自下而上从叶子节点找到根节点，左孩子标识为 0'，右孩子标识为 1'，将 0'、1'储存在编码表的 code 中;(2) 、将 code 中的 0'、 1

6、9;进行倒序 ; e. 编码: 根据编码表，进行编码 :for(int i=0;i<n;i+) if(*s=HCodeTablei.data) cout<<HCodeTablei.code;s+;f. 译码:输入一串 0'、 1'代码，根据编码表进行译码 :(1) 、如果是 0'，则转到当前结点的左孩子 :if(*s='0') parent=HTreeparent.lchild;(2) 、如果是 1'，则转到当前结点的右孩子 :else parent=HTreeparent.rchild;3. 程序运行结果开始输入一串字符输出编

7、码表否输入字符 a'否输入一串 0'、1'是是否合法是译码结束第3页北京邮电大学信息与通信工程学院4总结(1)、出现的问题及调试的方法由于本程序书上有一部分可借鉴的代码，自己只需要编写几个函数即可，但是 这几个函数也不是很简单。首先要解决输入字符串的问题，录入字符串之后要获取 存储字符串的数组 a 和存储不同字符权值的数组 b 。我先将从键盘上录入的字 符串储存在字符数组 s 中，然后遍历数组，建立循环链表，接着再遍历链表获得 数组 a 和 b 。还有一个选择权值最小的两个结点函数，看似简单，实际很复 杂。刚开始我编了很长时间，测试结果老是不正确，最第4页北京邮电大学信

8、息与通信工程学院后通过单步调试成功了，虽然实现了相应的功能，但是代码还是很冗长，我很 想改进一下，但鉴于时间原因也就只能这样了。最后是异常处理，这这点上我也花 费了很长时间，最终勉强地编出了还算比较完整的异常处理。(2) 、心得体会虽然最终顺利的编完了程序，但是总的来说哈夫曼树还是很不容易的。书上已 经有了许多关键算法的代码，只需要自己编写几个函数而已，我想如果课本上没有 这些关键代码，那么肯定是十分困难的。每一次数据结构实验总是痛苦纠结的，总 要花费很长时间、很多精力来编写程序，能编出来还好，如果花费了很长时间没变 出来心里肯定很不是滋味。但是总的来说，数据结构实验对我们的编程能力还是有 很大的