数据结构课程设计：哈夫曼编码器.doc

摘要
哈夫曼(huffman)树是一种带权路径长度最小的二叉树,也称最优二叉树,它有着极为广泛的应用。而我今天做的课程设计就是其中的一个应用---哈夫曼编码器。其实它的思想很简单,显示根据输入的权值建立一棵哈夫曼树,然后根据哈夫曼数求出各个叶结点的编码。这样就构成了一个最简单的哈夫曼编码器。
关键词:哈夫曼树编码器最优二叉树带权路径长度
目录
1 课题分析 1
设计目的 1
设计要求 1
1
2 总体设计与分析 3
3
3
3
3
3 程序说明 4
结构图 4
4 程序调试 5
菜单 5
输入叶结点和权值 6
输出哈夫曼编码 7
5 设计问题 8
8
8
8
6 小结 9
参考文献 10
源代码 11
1 课题分析
在当今信息爆炸时代,如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视,哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码是一种编码方式,以哈夫曼树—即最优二叉树,带权路径长度最小的二叉树,经常应用于数据压缩。哈夫曼编码使用一张特殊的编码表将源字符(例如某文件中的一个符号)进行编码。这张编码表的特殊之处在于,它是根据每一个源字符出现的估算概率而建立起来的(出现概率高的字符使用较短的编码,反之出现概率低的则使用较长的编码,这便使编码之后的字符串的平均期望长度降低,从而达到无损压缩数据的目的)。赫夫曼编码的应用很广泛,利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径,对路径上的各分支约定:指向左子树的分支表示“0”码,指向右子树的分支表示“1”码,取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码,这就是哈夫曼编码。
设计目的
(1)复****并灵活掌握二叉树的各种储存结构和遍历方法。
(2)了解静态链表,并掌握其构造方法。
(3)掌握哈夫曼树的构造过程和哈夫曼编码的求解方法。
(4)复****掌握文件读写的基本方法。
设计要求
(1)求得的哈夫曼编码及WPL必须写入编码文件。
(2)哈夫曼树的存储可以采用静态链表或二叉链表。

我在实验中采用的是静态链表作为存储结构,其数据类型可以定义为:
#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)求出所有叶子的哈夫曼编码,并将编码写入文件。
2 总体设计与分析
通常我们把数据压缩的过程称为编码,解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。构造一棵赫夫曼树,此构造过程称为赫夫曼编码。设计实现的功能: (1) 赫夫曼树的建立; (2) 赫夫曼编码的生成; (3) 编码文件的译码。


void HuffmTree(huffm HT[m+1]);
我用的是手动输入,首先提醒用户输入8个叶结点,即8个字母,输入完毕后提醒用户输入8个权值。以上的两个输入的输入格式都用空格隔开,以回车结束。哈夫蛮树建立成功。
其基本算法是:
①由给定的8个权值,构造由空二叉树扩充得到的扩充二叉树,每个数只有一个外部结点。
②在已经构造的扩充二叉树中,选取根结点权值最小和次小的两个。将它们作为左子树、右子树,构造成一颗新的扩充二叉树,它的根结点的权值为两子树的权值之和。
③重复执行步骤②,每次都使扩充的二叉树的个数减一,当只剩下一棵扩充二叉树时,它便是所要构造的哈夫曼树。

void Huffmcode(ctype code[n+1]);
从根结点开始,寻找每一个叶结点,在寻找过程中,经过左子树时,编码增加“0”,经过右子树时,编码增加“1”,当每一个