《数据结构 实验7》由会员分享，可在线阅读，更多相关《数据结构 实验7（11页珍藏版）》请在金锄头文库上搜索。
1、本文格式为Word版，下载可任意编辑数据结构 实验7 119 测验七 哈夫曼编/译码器测验指导书 一、测验目的 通过哈夫曼树的构造，深刻理解二叉树的构造。通过哈夫曼编/译码过程，深刻领会二叉 树的根本操作和二叉树的应用，扶助学生纯熟掌管二叉数组织数据的根本原理和对二叉数操 作的实现方法。 二、测验内容 本测验的主要内容是： 1、由文本字符及字符在文本文件中展现的频率，构造带权路径最短的最优二叉树（哈夫 曼树），并依此为根基构造字符的前缀编码（哈夫曼编码）； 2、编码：从文本文件中读入文本字符，按照已知的字符哈夫曼编码将文本字符转换为二 进制串的哈夫曼编码形式。 3、译码：从文件中读入二进制串字
2、符，按照哈夫曼树将其转换为文本字符。 4、输出哈夫曼树：以凹入表（层次表）的形式显示哈夫曼树。 四、测验原理 1、哈夫曼树的定义 哈夫曼树（最优二叉树）：设有个权值w1,w2,.,wn，试构造一棵有个叶结点的二 叉树，第个叶结点的权值为 wi，那么其中带权路径长度为最小的二叉树被称为最优二叉树或 哈夫曼树。 2、哈夫曼算法 哈夫曼算法要点是： (1)根据给定的个权值w1,w2,.,wn构成棵二叉树的集合T1,T2,.,Tn，其中每 棵二叉树 Ti 只有一个带权为 Wi 的根结点，左右子树为空。 (2)在中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的 二叉树根结点的权值为
3、左右子树根结点权值之和。 (3)在中删除这两棵树，同时将新得到的树参与到中。 (4)重复(2)和(3)，直到只剩下一棵二叉树为止。这棵二叉树便是哈夫曼树。 3、哈夫曼编码 对于字符的二进制编码，若任一字符的二进制编码都不是另一个字符的二进制编码的前 缀。这种编码叫做前缀编码。 以 n 种字符展现的频率作权，设计一棵哈夫曼树，并用二叉树的叶结点分别表示待编码 120 的字符，并商定左分支表示字符?0?，右分支表示字符?1?。那么对每个叶结点，都有唯一的 一条从根结点启程的路径，那么该路径上分支字符组成的字符串作为该叶子结点的编码。由此 得到的编码必为二进制的前缀编码，而且是编码总长最短的二进制前
4、缀编码，这种编码即为 哈夫曼编码。 例：设有 8 个字符A，B，C，D，E，F，G，H，其概率为0.05，0.29，0.07，0.08， 0.14，0.23，0.03,0.11,设其权值用整数表示为 5，29，7，8，14，23，3，11，其哈夫曼树 如图 1 所示。 100 42 58 19 23 29 29 8 11 14 15 3 5 7 图 7-1 哈夫曼树示意图 8 那么字符的哈夫曼编码为： A 0001 B 10 C 1110 D 1111 E 110 F 01 G 0000 H 001 四、实现 1、哈夫曼树的存储布局 根据哈夫曼树的构造算法，哈夫曼树除叶结点外，其余结点的度均为
5、 2。对于具有 n 个 权值构造的哈夫曼树，根据二叉树的性质 3，哈夫曼树的结点总数为 m=2n-1,即哈夫曼树所需 存储空间是由文本中不同字符的个数唯一确定的。为了便于对多棵二叉树举行组织和便于查 找各二叉树的根结点，采用静态链表作为二叉树的存储布局。其存储布局描述如下： typedef struc char ch; unsigned int weight; unsigned int parent,lchild,rchild; 121 HTNode,*HuffmanTree; 0 1 2 3 4 A 5 B C D 8 E F G 3 H * * * 11 10 8 15 19 29 42
6、58 100 14 23 29 7 8 13 9 9 11 -1 12 8 10 11 2 12 13 14 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 3 7 9 5 11 13 5 6 7 -1 -1 -1 6 8 4 10 1 12 8 9 10 11 * 12 * 13 14 * * 2、哈夫曼编码的存储布局 若要编码的文本文件的字符集不变，那么其哈夫曼编码不变。字符的哈夫曼编码一旦确定， 可以长期使用。因此，需要用文件同时保存字符的哈夫曼编码和字符。哈夫曼编码的表示形 式既要考虑存储空间的效率，也要考虑文件读取的便当。 文本字符的哈夫曼编码是
7、不等长的二进制码，用不等长的二进制字符串表示，节省存储 空间，但用文件读取不便当。若用等长的布局体表示，可能要滥用一点存储空间，但文件存 取便当。为了便于文件存取，采用等长布局体表示哈夫曼具有可取之处，其存储布局描述如 下： #define NODENUM 26 /字符集 struct HuffmanCoding char ch; /字符 char codingNODENUM; /字符编码 ; 3、字符及权值的输入形式 为了制止字符及其权值的手工键盘输入带来的错误，可以将字符及其权值组织成文本文件 的形式。文本文件的格式为： 字符 例如： 权值 122 A 5 B 19 C 7 D 8 E 1
8、4 F 23 G 3 H 11 一般读入单个字符很不便当，格式化输入字符串和数值型数据很便当，所以字符数据可 以采用读串的方式读入，然后把它赋给字符变量。 4、文件的设置 （1）字符权值文件 const char *WeighFileName = 存放需构造哈夫曼树的字符和权值数据，为文本数据，见“字符及权值的输入形式”。 （2）哈夫曼树数据文件 const char *TableFileName = 存放哈夫曼树数据，二进制 HTNode 布局型。格式为： 数据个数哈夫曼树的结点数，M=2n-1,n 为权值个数 记录 i-二进制 HTNode 布局型数据 （3）字符编码数据文件 const
9、char *CodeFileName = 存放字符编码数据，二进制 struct HuffmanCoding 布局型。格式为： 数据个数权值个数 记录 i-二进制 struct HuffmanCoding 布局型数据 （4）文本文件 const char *SourceFileName = 存放需编码的文本字符串数据，其中的字符属于编码字符集。 （5）编码数据文件 const char *EnCodeFileName = 存放对文本文件编码后的数据，其中的数据为“0”和“1”的字符串。 （6）译码字符文件 const char *DecodeFileName = 存放译码后的字符文件 5、程序
10、根本功能 （1）初始化：输入编码字符和其权值，生成哈夫曼树和字符的哈夫曼编码，并用文 123 件保存哈夫曼树和字符的哈夫曼编码。 （2）编码：把文本字符串转换为“0”和“1”表示的哈夫曼编码。 （3）译码：把“0”和“1”表示的哈夫曼编码串转换为文本字符串 （4）显示哈夫曼树：以凹入形式显示哈夫曼树。 （5）显示哈夫曼表：以表格形式显示哈夫曼树 （6）显示字符编码 6、辅佐功能 （1）菜单项选择择：将上述功能通过“菜单”形式罗列出来，通过菜单项选择择举行交互式 操纵程序运行。 （2）读文件：把哈夫曼树数据读入内存。 （3）选择结点：选择两个具有最小权值的根结点。 7、程序布局 本程序可以由 10 个函数组成，其中主函数 1 个，根本功能函数 6 个，辅佐功能函数 3 个。函数间的调用关系图 2 所示。 main nemu Initialization Encode Decode PrintHuffman PrintHuff bl PrintCha Select ReadFromFile 图 7-2 程序布局示意图 8、程序函数 （1）主函数：main 功能：通过菜单项选择择操纵对系统功能的操作 （2）菜单项选择择函数：menu 函数格式： int menu(void) 函数功能：构造功能菜单，并选择下一步要操作的功能。 函数参数：无参数。 11
