摘  要
哈夫曼（huffman）树是一种带权路径长度最小的二叉树，也称最优二叉树，它有着极为广泛的应用。而我今天做的课程设计就是其中的一个应用---哈夫曼编码器。其实它的思想很简单，显示根据输入的权值建立一棵哈夫曼树，然后根据哈夫曼数求出各个叶结点的编码。这样就构成了一个最简单的哈夫曼编码器。
关键词：哈夫曼树  编码器  最优二叉树  带权路径长度

1 课题分析
在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。哈夫曼编码使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起
来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。赫夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码。
1.1 设计目的
（1）复习并灵活掌握二叉树的各种储存结构和遍历方法。
（2）了解静态链表，并掌握其构造方法。
（3）掌握哈夫曼树的构造过程和哈夫曼编码的求解方法。
（4）复习掌握文件读写的基本方法。
1.2 设计要求
（1）求得的哈夫曼编码及WPL必须写入编码文件。
（2）哈夫曼树的存储可以采用静态链表或二叉链表。
1.3设计内容
我在实验中采用的是静态链表作为存储结构，其数据类型可以定义为：
#define m 2*n-1                /*m为哈夫曼树的结点*/      /*具有n个叶结点的哈夫曼树共有2n-1个结点*/
typedef struct
{int wi;                    /*定义权值*/
char data;                /*定义叶结点*/
int Parent,Lchild,Rchild;    /*定义父结点、左孩子、右孩子*/
}huffm;
huffm  HT[m+1];        /*静态链表HT[m+1]*/
(1)从文件中读取所有结点的权值，将读取的权值放到静态链表中，并初始化静态链表。
（2）依据给定的权值，不断生成各分支结点，直到生成树根结点为止，得到生成
哈夫曼树后的静态链表。
（3）规定所有的左分支为0，右分支为1，从树根到叶子所经过的分支构成的01编码，即是对应叶子的哈夫曼编码。
哈夫曼编码树的带权路径长度
（4）求出所有叶子的哈夫曼编码，并将编码写入文件。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。