《数据结构哈夫曼编译码器（2020年7月整理）.pdf》由会员分享，可在线阅读，更多相关《数据结构哈夫曼编译码器（2020年7月整理）.pdf（17页珍藏版）》请在金锄头文库上搜索。
1、 东北大学秦皇岛分校计算机与通信工程学院计算机科学与技术 1 数据结构课设数据结构课设 哈夫哈夫曼编译码器曼编译码器 学 号： 姓 名： 提交日期： 成 绩： 一、一、 实验名称实验名称 哈夫曼编/译码器的实现 二、二、 实验要求实验要求 【问题描述】 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。 但是，这要求在发送端通过一个编码系统对待传来数据预先编码，在接收端将传来的数据进 行译码(复原)。对于双工信道(即可以双向传输信息的信道)，每端都需要一个完整的编/译码 系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。 【基本要求】 一个完整的系统应具有以下
2、功能： (1)I： 初始化(Initialization)。 从终端读入字符集大小 n , 以及 n 个字符和 n 个权值， 建立哈夫曼树，并将它存于文件 hfmTree 中。 东北大学秦皇岛分校计算机与通信工程学院计算机科学与技术 2 (2)E： 编码(Encoding)。 利用已建好的哈夫曼树(如不在内存， 则从文件hfmTree中读人)， 对文件 ToBeTran 中的正文进行编码，然后将结果存入文件 CodeFile 中。 (3)D: 译码(Decoding)。利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码， 结果存入文件 TextFile 中。 (4)P：打印代码文件
3、(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
4、 频度 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 算法的最根本的原则是： 累计的(字符的统计数字*字符的编码长度)为最小， 也就是权值(
5、字符的统计数字*字符的编码 长度)的和最小。 3.13.1 设计简介设计简介 本设计是通过对给定字符及其使用频度构造哈夫曼树再根据哈夫曼树进行哈夫曼编码， 在此之前，首先要理解哈夫曼树、哈夫曼算法、哈夫曼编译码的概念和原理。 3.1.13.1.1 哈夫曼树哈夫曼树 从树的根结点到树的每个结点的路径长度之和即为该树的路径长度。而在实际应用中， 常将树的结点赋予一个有某种含义的数值， 这个数值就称为结点的权。 从树的根结点到该结 点之间的路径长度与结点权的乘积称为该结点的带权路径长度， 树中所有叶结点的带权路径 长度之和称为树的带权路径长度。通常记作： 东北大学秦皇岛分校计算机与通信工程学院计算机
6、科学与技术 3 WPL = 1 n i i i wl = 式中，n 表示树中叶子结点的数目，wi 表示叶结点 ki 的权，li 表示根结点到叶结点 Ki 之间的路径长度。 在 n 个权值为 w1,w2,wn 的带权叶结点构成的所有二叉树中，其带权路径长度 WPL 最小的二叉树即为哈夫曼树或最优二叉树。 3.1.23.1.2 哈夫曼算法哈夫曼算法 给定 n 个带权叶结点， 如何构造一棵 n 个带有给定权值的叶结点的二叉树， 使其带权路 径长度最小？哈夫曼首先给出了构造最有二叉树的方法， 故称其为哈夫曼算法， 其基本的算 法思想如下： 将n个权值分别是w1,w2,wn的结点按权值递增排列。 将每个
7、权值作为一个二叉树， 构成 n 棵二叉树的森林F=T1,T2,Tn， 其中每棵二叉树都只有一个权值为 wi的根结点， 其左右子树均为空。 在森林 F 中选两棵根结点权值最小的二叉树， 作为左右子树构造一棵新的二叉树， 并 使得新二叉树根结点的权值为其左右子树上根结点权值之和。 在森林 F 中， 删除这两棵树， 同时将新得到的二叉树代替这两棵树加入到森林 F 中去， 因此，森林 F 中二叉树的个数比以前少一棵。 对新的森林 F 重复和，直到森林中只有一棵树为止。这棵树就是哈夫曼树。 3.1.33.1.3 哈夫哈夫曼编码曼编码 用哈夫曼树得到的二进制前缀编码就是哈夫曼编码。具体做法是：对于给定的字
8、符集 C=c1,c2,cn及字符出现的频率 W=w1,w2,wn，以 c1,c2,cn 作为叶结点，以 w1,w2,wn 作为该结点上的权，利用哈夫曼算法，构造一棵带权路径长度最小的的哈夫曼 树。 然后对哈夫曼树中每个分支结点的左右分支分别用 0 和 1 进行编码， 这样从树的根结点 到每个叶结点之间， 沿途路径上0和1组成的编码序列就是叶结点所代表字符的二进制编码。 3.1.43.1.4 哈夫曼译码哈夫曼译码 哈夫曼译码过程与编码过程相反， 译码过程就是分解电文中字符串的过程， 具体步骤如 下：首先输入要一点问的二进制编码，然后从哈夫曼树的根结点出发，对于电文的二进制编 码，按照二进制位串中
9、的 0 和 1 确定是进入左分支还是右分支：若编码为 0，则进入结点的 左孩子，否则进入结点的右孩子，一旦到达叶结点，就译出该叶子结点所代表字符。 东北大学秦皇岛分校计算机与通信工程学院计算机科学与技术 4 3.23.2 设计方案设计方案 3.2.13.2.1 设计思路设计思路 要编程实现该系统，需逐步实现： 1. 哈夫曼树的建立，即根据所给字符及对应频度构造哈夫曼树，哈夫曼树构造函数包括对 哈夫曼树的初始化、赋值和建立； 2. 哈夫曼编码表的建立，即编写程序实现对所给字符进行哈夫曼编码，将每个字符的哈夫 曼编码存储到一个位串数组中去； 3. 打印输出哈夫曼树和哈夫曼编码表，在终端上显示出哈夫
10、曼树的结构和各字符名称及对 应的哈夫曼编码； 4. 编码，对输入的字符串进行哈夫曼编码，将结果写入文件； 5. 译码，将文件中的哈夫曼编码按照编码表翻译成对应字符串并显示到终端上 3.2.23.2.2 设计流程图设计流程图 图 2.1 总流程图 1. 定义哈夫曼结点存储结构和哈夫曼编码存储结构，之后定义一个结点存储结构数组 用来存放结点信息，和定义一个编码存储结构数组用来存放字符的哈夫曼编码，同 给定字符串及对应频率 结束 创建哈夫曼编码表 输入字符 读取 codefile 文件并译码 构造哈夫曼树 编码并写入文件 codefile 数据输出显示 东北大学秦皇岛分校计算机与通信工程学院计算机科
11、学与技术 5 时定义全局数组存放字符和它的使用频度。 2. 先将已建立好的二叉树初始化，再对其中的叶结点其赋予字符名和对应使用频度作 为结点名和结点权值，最后通过哈夫曼算法构造哈夫曼树，同时在屏幕输出哈夫曼 树。 3. 通过已建立好的哈夫曼树再对字符进行二进制编码，编码结束后，对应每个字符都 有一个二进制编码，此编码即为哈夫曼编码，将字符及其哈夫曼编码存放到哈夫曼 编码存储结构体数组中去，构成哈夫曼编码表，同时在屏幕上输出哈夫曼编码表。 4. 编码函数执行，即对输入的字符串根据哈夫曼编码表进行编码，将字符串的二进制 编码存放到一个字符数组中去。 5. 建立文件，将字符数组中的二进制编码写入文件
12、，这需要定义输出流类的对象并与 文件关联，通过操作对象来操作文件的数据写入。 6. 将文件中的二进制编码进行译码，这需要定义输入流类的对象并与文件关联，将文 件中的编码读取到另一字符数组中去，调用译码函数进行译码。 7. 结束。 四、四、 详细设计详细设计 creattreehuffman creatcodehuffman writecodehuffman main transcodehuffman printtreehuffman printcodehuffman 4.14.1 哈夫曼树的建立哈夫曼树的建立 4.1.14.1.1 哈夫曼树的存储结构哈夫曼树的存储结构 为了实现通过哈夫曼算法建
13、立哈夫曼树， 首先要定义哈夫曼树的存储结构。 由于构造哈 夫曼树之后， 编码时要从叶结点出发走一条从叶结点到根的路径， 而译码时要从根结点出发 走一条从根到叶结点的路径。对于每个结点而言，既需知道双亲的信息，又需知道孩子的信 息。因此，可以使用带双亲的孩子链表作为结点的存储结构。由哈夫曼算法可知，如果哈夫 曼有 n 个叶结点，则最终生成的哈夫曼树共有 2n-1 个结点。因此，可以用一个长度为 2n 的一维数组存放哈夫曼树的所有结点。详细定义如下： #define Leafnum 27 #define Hufnum 2*Leafnum typedef char DataType; typedef
14、 struct Tnode 东北大学秦皇岛分校计算机与通信工程学院计算机科学与技术 6 DataType name; double weight; int lchild, rchild, parent; Huftree; Huftree TreeHufnum; 其中，name 表示结点数据的名称（即字符名称） ，weight 表示结点的权值（即字符使用 频度） ，lchild、rchild 分别是结点的左、右孩子在数组中的下标值，叶结点的左右孩子的 下标值均为 0；parent 表示结点双亲在数组中的位置。它的主要作用有两点：第一，区分根 结点和非根结点；第二，使得查找某个结点的双亲变的更为简
15、单。若 parent=0，则该结点 是树的根结点，否则为非根结点。因为把森林中的两棵二叉树合并成一棵二叉树时，必须从 森林的所有结点中选取两个根结点的权值为最小的结点，此时就是根据 parent 来区分根与 非根结点的。 4.1.24.1.2 建立哈夫曼树建立哈夫曼树 本设计只对 26 个英文大写字符及空格进行了哈夫曼编码，各字符及对应使用频度如下 表所示： 表 4.1 字符及其使用频度 字符 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 需要定义全局数组来存放这些字符名称和对应频度： char ch = 0, ,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S, T,U,V,W,X,Y,Z; float w = 0
