数据结构实验—哈夫曼树编码.doc

中南大学物理学院（数据结构课程）实验报告实验名称： 哈弗曼编码和译码专业班级： 电子信息科学与技术 0904姓 名： 秦杰学 号： 1404090506指导教师： 胡志坤2011 年 11 月 27 日实验四：哈夫曼编码和译码一、 实验目的和要求（1） 掌握哈夫曼树的基本概念及其存储结构2） 掌握哈夫曼树的建立算法3） 掌握哈夫曼树的应用（哈夫曼编码和译码） 二、 实验内容和原理1.实验内容用下表给出的字符集和频度的数据建立哈曼树,并实现以下报文的编码和译码：“this*program*is*my*favourite” 字符 * a b c d e f g h i频度 186 64 13 22 32 103 21 15 47 57字符 j k l m n o p q r s频度 1 5 32 20 57 63 15 1 48 51字符 t u v w x y z频度 80 23 8 18 1 16 12.实验原理首先规定构建哈夫曼树，再去进行哈夫曼树的编码，接着设计函数进行字符串的编码过程，最后进行哈夫曼编码的译码定义一个结构体，用于存放构建哈夫曼树所需要的所有变量，开辟一块地址空间，用于存放数组，数组中每个元素为之前定义的结构体。

输入 n 个字符及其权值构建哈夫曼树：在上述存储结构上实现的哈夫曼算法可大致描述为： 1.初始化:将 ht[0…m-1]中 2n-1 个结点里的三个指针均置为空，权值置为 0 2.输入:读入 n 个叶子的权值存于向量的前 n 个分量中它们是初始森林中 n 个孤立的根结点上的权值 3.合并:对森林中的树共进行 n-1 次合并，所产生的新结点依次放入向量ht 的第 i 个分量中每次合并分两步： ①在当前森林 ht[0…i-1]的所有结点中，选取权最小和次小的两个根结点[s1]和 [s2]作为合并对象，这里 0≤s1，s2≤i-1 ② 将根为 ht[s1]和 ht[s2]的两棵树作为左右子树合并为一棵新的树，新树的根是新结点 ht[i]具体操作： 将 ht[s1]和 ht[s2]的 parent 置为 i， 将 ht[i]的 lchild 和 rchild 分别置为 s1 和 s2 .新结点 ht[i]的权值置为 ht[s1]和 ht[s2]的权值之和 4.哈夫曼的编码：约定左子为 0，右子为 1，则可以从根结点到叶子结点的路径上的字符组成的字符串作为该叶子结点的编码当用户输入字母时就在已经找好编码的编码结构体中去查找该字母。

查到该字母就打印所存的哈夫曼编码接着就是完成用户输入 0、1 代码时把代码转成字母的功能这是从树的头结点向下查找，如果当前用户输入的 0、1 串中是 0 则就走向该结点的左子如果是 1 这就走向该结点的右结点，重复上面步骤直到发现该结点属于输入了字母的结构体则打印该结构体的字母重复上面步骤直到找完用户输入 0、1 串为止则就完成了程序所有的译码过程三、 实验环境硬件：（1）学生用微机（2）多媒体教室或远程教学（3）局域网环境软件：（1）Windows XP 中文操作系统 （2）VC++6.0四、 算法描述及实验步骤(1)建立哈夫曼树的算法：定义各结点类型其中应包含两类数据一是权重域 weight;一是应该包括指向左右孩子和指向双亲的指针这里分别用 lchild、rchild 和 parent 来表示，因此可用静态三叉链表来实现在实际构造中由于是叶子结点来构造新的根结点其构造过程中仅与叶子结点的权重有关而与其数据域无关，所以构造过程中不用考虑其数值域，并且在链表中从叶子开始存放，然后不断的将两个最小权值的子树合并为一个权值为其和的较大的子树，逐步生成各自内部结点直到树根2）编码的算法将建立的哈夫曼树从每个叶子结点开始沿着双亲回到根结点，每走一步进行编码得到的一个编码值，由于每个叶子结点的哈夫曼编码是从根结点到相应的叶子的路径的各个分支的代码组成的 0 和 1 序列，所以先得到了低位编码后得到高位编码因此可用一维数组从后向前来存放各位编码值，并用 start 来记录编码的起始位置。

开始i=0start=n-1i 结点的父结点子结点为左子YN编码为 0编码为 1start=start-1把父结点作为当前结点根结点？NYstart=start+1start=start+1start#include //数组头文件#include#define MAX 1000 //宏定义typedef struct{ //定义哈夫曼编码的结构数组char data;int weight; //定义权值int parent;int lchild;int rchild;}huffmannode;typedef struct{ //定义保存哈夫曼结构体char bits[50];int start;}huffmancode ;void main() {huffmannode ht[100]; //定义储存权值的空间huffmancode cd[100];char string[100]; //定义数组存储空间char hcd[100];int i,j,x,y,s1,s2,m1,m2,n,c,f,k;printf("please input the n="); //输入字符的个数scanf("%d",printf("\n==============================\n");for(i=0;i

如下图示：第四步，得到哈夫曼编码后输入哈夫曼编码进行译码过程，得到输出为“this*program*is*my*favourite”，译码正确！，输出如下图所示：六、 总结通过编程，我进一步学习了哈弗曼编码的特点、存储方法和基本原理，提高了自己运用 C 语言正确编程及调试的能力，运用数据结构解决简单的实际问题的能力，为后续数据结构课程的学习打下基础在 此 次 实 验 中 遇 到 了 很 多 语 句 赋 值 的 错 误 ， 还 有 for 语 句 使 用 的 不 熟练 ， 以 及 自 己 的 粗 心 而 造 成 的 标 点 符 号 使 用 错 误 ， 宏 语 句 的 定 义 等 等 ， 主 要的 解 决 方 案 是 ， 看 一 些 关 于 C 语 言 编 程 的 书 籍 ， 请 教 其 他 同 学 ， 使 得 编 译 成功 自 己 的 程 序 这次的设计可以看作是一次理论与实践相结合的桥梁，通过这次的设计，我学习到了许多的知识，也认识到了自己目前的不足，那就是缺乏相应的知识与经验，所以在运用和操作方面体现了不足我还明白了在编写程序的时候，应该尽量使界面简洁大方，布局统一变量类型的定义，一定要够用就好，这样程序就可以尽可能的减少对系统资源的占用。

在设计时也免不了存在着一些不足，所以在今后的学习中我会努力取得更大的进步。