《数据结构 实验7》由会员分享，可在线阅读，更多相关《数据结构 实验7（23页珍藏版）》请在金锄头文库上搜索。
1、实验七哈夫曼编/译码器实验指导书一、实验目的通过哈夫曼树的构造，深刻理解二叉树的构造。通过哈夫曼编/译码过程，深刻领会二叉 树的基本操作和二叉树的应用，帮助学生熟练掌握二叉数组织数据的基本原理和对二叉数操 作的实现方法。二、实验内容本实验的主要内容是：1、由文本字符及字符在文本文件中出现的频率，构造带权路径最短的最优二叉树(哈夫 曼树)，并依此为基础构造字符的前缀编码(哈夫曼编码)；2、编码：从文本文件中读入文本字符，按照已知的字符哈夫曼编码将文本字符转换为二 进制串的哈夫曼编码形式。3、译码：从文件中读入二进制串字符，按照哈夫曼树将其转换为文本字符。4、输出哈夫曼树：以凹入表(层次表)的形式
2、显示哈夫曼树。四、实验原理1、哈夫曼树的定义哈夫曼树(最优二叉树)：设有n个权值 wl,w2,.,wn ，试构造一棵有n个叶结点的二 叉树，第i个叶结点的权值为wi,则其中带权路径长度为最小的二叉树被称为最优二叉树或 哈夫曼树。2、哈夫曼算法哈夫曼算法要点是：(1) 根据给定的n个权值w1,w2,.,wn构成n棵二叉树的集合卩=T1,T2,.,Tn，其中每 棵二叉树 Ti 只有一个带权为 Wi 的根结点，左右子树为空。(2) 在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的 二叉树根结点的权值为左右子树根结点权值之和。(3) 在F中删除这两棵树，同时将新得到的树加入到
3、F中。(4) 重复(2)和(3)，直到只剩下一棵二叉树为止。这棵二叉树便是哈夫曼树。3、哈夫曼编码对于字符的二进制编码，若任一字符的二进制编码都不是另一个字符的二进制编码的前 缀。这种编码叫做前缀编码。以 n 种字符出现的频率作权，设计一棵哈夫曼树，并用二叉树的叶结点分别表示待编码的字符，并约定左分支表示字符0，右分支表示字符T。则对每个叶结点，都有唯一的一条从根结点出发的路径，则该路径上分支字符组成的字符串作为该叶子结点的编码。由此得到的编码必为二进制的前缀编码，而且是编码总长最短的二进制前缀编码，这种编码即为 哈夫曼编码。例：设有 8 个字符A, B，C, D, E，F, G, H,其概率
4、为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 所示。则字符的哈夫曼编码为：A000lBl0Clll0D llllEll0F0lG0000H00l四、实现1、哈夫曼树的存储结构根据哈夫曼树的构造算法，哈夫曼树除叶结点外，其余结点的度均为2。对于具有 n 个 权值构造的哈夫曼树，根据二叉树的性质3,哈夫曼树的结点总数为m=2n-l即哈夫曼树所需 存储空间是由文本中不同字符的个数唯一确定的。为了便于对多棵二叉树进行组织和便于查 找各二叉树的根结点，采用静态链表作为二叉树的存储结构
5、。其存储结构描述如下： typedef struc char ch;unsigned int weight;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;91011121314A 58-1-1B2913-1-1C79-1-1D 89-1-1E1411 -1-1F2312-1-1G 38-1-1H11 10-1-1*81060*1511 23*191287*291349*4214105*581111*100-112132、哈夫曼编码的存储结构若要编码的文本文件的字符集不变，则其哈夫曼编码不变。字符的哈夫曼编码一旦确定， 可以长期使用。
6、因此，需要用文件同时保存字符的哈夫曼编码和字符。哈夫曼编码的表示形 式既要考虑存储空间的效率，也要考虑文件读取的方便。文本字符的哈夫曼编码是不等长的二进制码，用不等长的二进制字符串表示，节省存储 空间，但用文件读取不方便。若用等长的结构体表示，可能要浪费一点存储空间，但文件存 取方便。为了便于文件存取，采用等长结构体表示哈夫曼具有可取之处，其存储结构描述如 下：#define NODENUM 26/字符集struct HuffmanCoding char ch;/ 字符char codingNODENUM; /字符编码;3、字符及权值的输入形式为了避免字符及其权值的手工键盘输入带来的错误，可以
7、将字符及其权值组织成文本文件 的形式。文本文件的格式为：字符 权值例如：A5B 19C7D8E 14F 23G3H 11 一般读入单个字符很不方便，格式化输入字符串和数值型数据很方便，所以字符数据可 以采用读串的方式读入，然后把它赋给字符变量。4、文件的设置（1）字符权值文件const char *WeighFileName = Weight.txt; 存放需构造哈夫曼树的字符和权值数据，为文本数据，见“字符及权值的输入形式”。（2）哈夫曼树数据文件const char *TableFileName = HfmTbl.txt; 存放哈夫曼树数据，二进制 HTNode 结构型。格式为：数据个数一
8、哈夫曼树的结点数，M=2n-l,n为权值个数记录 i-二进制 HTNode 结构型数据（3）字符编码数据文件const char *CodeFileName = CodeFile.txt; 存放字符编码数据，二进制 struct HuffmanCoding 结构型。格式为：数据个数权值个数记录 i-二进制 struct HuffmanCoding 结构型数据（4）文本文件const char *SourceFileName = SrcText.txt; 存放需编码的文本字符串数据，其中的字符属于编码字符集。（5）编码数据文件const char *EnCodeFileName = EnCode
9、File.txt; 存放对文本文件编码后的数据，其中的数据为“0”和“1”的字符串。（6）译码字符文件const char *DecodeFileName = DecodeFile.txt;存放译码后的字符文件5、程序基本功能1）初始化：输入编码字符和其权值，生成哈夫曼树和字符的哈夫曼编码，并用文 件保存哈夫曼树和字符的哈夫曼编码。（2）编码：把文本字符串转换为“0”和“1”表示的哈夫曼编码。（3）译码：把“0”和“1”表示的哈夫曼编码串转换为文本字符串（4）显示哈夫曼树：以凹入形式显示哈夫曼树。（5）显示哈夫曼表：以表格形式显示哈夫曼树（6）显示字符编码6、辅助功能（1）菜单选择：将上述功能
10、通过“菜单”形式罗列出来，通过菜单选择进行交互式 控制程序运行。（2）读文件：把哈夫曼树数据读入内存。（3）选择结点：选择两个具有最小权值的根结点。7、程序结构本程序可以由 10 个函数组成，其中主函数 1 个，基本功能函数 6 个，辅助功能函数 3 个。函数间的调用关系图 2 所示。图 7-2 程序结构示意图8、程序函数（1）主函数：main功能：通过菜单选择控制对系统功能的操作（ 2）菜单选择函数： menu函数格式： int menu（void） 函数功能：构造功能菜单，并选择下一步要操作的功能 函数参数：无参数。函数返回值：17中的一个序号。可供选择的功能如下：1- - Initial
11、ization2- -Encode3- -Decode4- -Print huffmantree5- -Print huffman Table6- -Print char Coding7- -Quit(3) 初始化函数： Initialization函数格式： void Initialization()函数参数：无参数函 数 功 能 ： 输 入 编 码 字 符 和 权 值 ， 生 成 哈 夫 曼 树 和 字 符 编 码 并用文件TableFileName 和 CodeFileName 保存哈夫曼树和字符编码数据。函数返回值：无(4) 文本串编码函数： Encode函数格式 void Encod
12、e(void)函数功能：从文本串文件 SourceFileName 中读入文本字符，按照 CodeFileName 文件中字符的编码将其转换为“0”和“1”表示的哈夫曼编码，并把编码 结果写入文件 EnCodeFileName 中。函数参数：无函数返回值：无(5)译码函数： Decode函数格式 void Decode()函数功能：从文件EnCodeFileName中读入“0”和T”表示的哈夫曼编码数 据，将其转换为文本字符，并将译码结果写入文件DecodeFileName中。函数参数：无函数返回值：无(6) 显示哈夫曼树函数： PrintHuffmanTree函数格式 void PrintH
13、uffmanTree()函数功能：以凹式形式显示哈夫曼树函数参数：无函数返回值：无(7) 显示哈夫曼树表函数： PrintHuffmanTable函数格式 void PrintHuffmanTable()函数功能：以表格形式显示哈夫曼树函数参数：无函数返回值：无(8) 显示字符哈夫曼编码函数：PrintCharCoding函数格式 void PrintCharCoding() 函数功能：显示字符的哈夫曼编码 函数参数：无函数返回值：无(9) 读文件函数： ReadFromFile函数格式 int ReadFromFile()函数功能：从文件 TableFileName 中读哈夫曼树数据 函数参
14、数：无函数返回值： 0读数据失败0-读入的数据个数(10) 选择根界点函数： Select函数格式 void Select(struct node ht,int n, int *s1,int *s2) 函数功能：从多棵树中选择两个权值最小的根结点 函数参数：struct node ht哈夫曼树int n选择结点的范围，即只能在0n中选择结点int *sl指向第一个权值最小的结点的指针int *s2指向第二个权值最小的结点的指针 函数返回值：无五、主要算法描述1、初始化函数 Initialization 算法描述功能：读入字符及其权值，生成哈夫曼树和字符哈夫曼编码。字符输入的处理： C 语言输入字符的处理很不方便，任何一个字符都当作有效字符处理， 包括空格字符和回车符。而用格式读函数读字符串很方便，空格字符和回车符都当作字符串 数据的分隔。因此，可以先把字符用格式读函数把字符读入字符数组中，再将其赋值给字符 变量，这样处理更简单。算法步骤：(1) 输入：读入n个叶结点的字符和权值存放于静态树T中的前n个分量中。(2) 初始化
