大数据结构哈夫曼编译码器.docx

东北大学秦皇岛分校计算机与通信工程学院计算机科学与技术 数据结构课设 哈夫曼编译码器 学 号： 姓 名： 提交日期： 成 绩： 实验名称 哈夫曼编/译码器的实现 实验要求 【问题描述】 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传来数据预先编码，在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道)，每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。 【基本要求】 一个完整的系统应具有以下功能： (1)I：初始化(Initialization)。从终端读入字符集大小n , 以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。 (2)E：编码(Encoding)。利用已建好的哈夫曼树(如不在内存，则从文件hfmTree中读人)，对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 (3)D: 译码(Decoding)。利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码，结果存入文件TextFile中。 (4)P：打印代码文件(Print)。将文件CodeFile以紧凑格式显示在终端上，每行 50 个代码。同时将此字符形式的编码文件写入文件 CodePrin 中。 (5)T：打印哈夫曼树(Tree printing)。将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。 【测试数据】 (1)利用教科书例 6-2 中的数据调试程序。 (2)用下表给出的字符集和频度的实际统计数据建立哈夫曼树 , 并实现以下报文的编码和译码：THIS PROGRAM IS MY FAVORITE。 字符 A B C D E F G H I J K L M 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 需求分析 Huffman编码是一种可变长编码方式，是由美国数学家David Huffman创立的，是二叉树的一种特殊转化形式。编码的原理是：将使用次数多的代码转换成长度较短的代码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。Huffman算法的最根本的原则是：累计的(字符的统计数字*字符的编码长度)为最小，也就是权值(字符的统计数字*字符的编码长度)的和最小。 3.1设计简介 本设计是通过对给定字符及其使用频度构造哈夫曼树再根据哈夫曼树进行哈夫曼编码，在此之前，首先要理解哈夫曼树、哈夫曼算法、哈夫曼编译码的概念和原理。 3.1.1哈夫曼树 从树的根结点到树的每个结点的路径长度之和即为该树的路径长度。而在实际应用中，常将树的结点赋予一个有某种含义的数值，这个数值就称为结点的权。从树的根结点到该结点之间的路径长度与结点权的乘积称为该结点的带权路径长度，树中所有叶结点的带权路径长度之和称为树的带权路径长度。通常记作： WPL = 式中，n表示树中叶子结点的数目，wi表示叶结点ki的权，li表示根结点到叶结点Ki之间的路径长度。 在n个权值为w1,w2,……wn的带权叶结点构成的所有二叉树中，其带权路径长度WPL最小的二叉树即为哈夫曼树或最优二叉树。 3.1.2哈夫曼算法 给定n个带权叶结点，如何构造一棵n个带有给定权值的叶结点的二叉树，使其带权路径长度最小？哈夫曼首先给出了构造最有二叉树的方法，故称其为哈夫曼算法，其基本的算法思想如下： = 1 \* GB3 ①将n个权值分别是w1,w2,…,wn的结点按权值递增排列。将每个权值作为一个二叉树，构成n棵二叉树的森林F={T1,T2,…,Tn}，其中每棵二叉树都只有一个权值为wi的根结点，其左右子树均为空。 = 2 \* GB3 ②在森林F中选两棵根结点权值最小的二叉树，作为左右子树构造一棵新的二叉树，并使得新二叉树根结点的权值为其左右子树上根结点权值之和。 = 3 \* GB3 ③在森林F中，删除这两棵树，同时将新得到的二叉树代替这两棵树加入到森林F中去， 因此，森林F中二叉树的个数比以前少一棵。 = 4 \* GB3 ④对新的森林F重复 = 2 \* GB3 ②和 = 3 \* GB3 ③，直到森林中只有一棵树为止。这棵树就是哈夫曼树。 3.1.3哈夫曼编码 用哈夫曼树得到的二进制前缀编码就是哈夫曼编码。具体做法是：对于给定的字符集C={