2008级数据结构课程设计实验报告
实验课题：（1）利用树进行赫夫曼编码（2）查找和排序
学生姓名：学号：班级：指导老师：
日期：201079
1
f一、利用树进行赫夫曼编码1、实验目的：
（1）、使得学生在学习编程的过程中学会用树进行赫夫曼编码与译码。（2）、使得学生在变成中充分领会排序的实质过程，计算机的运行情况，对程序的运行、调试，以及对赫夫曼编码与译码的算法的熟悉。
2、实验内容：
文件co
ftxt中保存了若干字母及其出现的频度，要求所有频度加起来要为1，否则载入时报错。字母及其频度保存的格式为：a01b02c03……界面上，首先出现一个按钮，点击，载入co
ftxt。然后输入一个字符串，由这些字母组成。点击按钮，显示哈夫曼编码的结果。同时，界面上如果输入哈夫曼编码，也能被翻译成相应的字母。如果输入格式错误，要求给予提示。
3、程序分析：
31存储结构
存储结构二叉树示意图如下
2
f32关键算法分析核心算法思想：
1哈夫曼编码Huffma
Codi
g是可变字长编码。编码时借助哈夫曼树，也即带权路径长度最小的二叉树，来建立编码。2哈夫曼编码可以实现无损数据压缩。单个字符用一个特定长度的位序列替代：在字符串中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。关键算法1：统计字符出现的频度，记录出现的字符及其权值，对未出现的字符不予统计编码。将统计的叶子节点编制成数组。为创建哈夫曼树作准备。
3
fC实现：
fori
ti0stri0ifreque
cyshortstri
统计频度
此处以一个一维的下标表示ascII编码，以元素之表示字符频度，解决统计字符的问题。fori
tj0j128jiffreque
cyj0leaf此处扫描一遍上面建立的数组得到叶子节点的个数，则由leaf21得到总的节点个数。
关键算法2：建立哈弗曼树即最优二叉树。这里实现时：每建立一个父节点就需要扫描权值序列得到两个最小的权值。由于节点个数逐渐增多，因而扫描次数动态变化，程序里设置计数变量来控制扫描次数的变化。另外设置标记来标识节点是否已经被取出。由于前面得出了总的叶子节点个数，根据哈弗曼树建立的规律可以知道总的节点数和建立哈弗曼树过程中的父子节点间的对应关系，因而可以通过下标准确定位节点，动态建立哈弗曼树。具体C实现参看源代码中的CreateTree函数。关键算法3：建立字符编码表。这里采用从叶子节点到根节点的顺序逆序编码，然后字符串转置得到最终编码。C实现：
统计叶子节点个r