哈夫曼编译码实验指导书

实验七哈夫曼编/译码器一、实验目的通过哈夫曼树的构造，深刻理解二叉树的构造。通过哈夫曼编/译码过程，深刻领会二叉树的基本操作和二叉树的应用，帮助学生熟练掌握二叉数组织数据的基本原理和对二叉数操作的实现方法。二、实验内容本实验的主要内容是：1、由文本字符及字符在文本文件中出现的频率，构造带权路径最短的最优二叉树（哈夫曼树），并依此为基础构造字符的前缀编码（哈夫曼编码）；2、编码：从文本文件中读入文本字符，按照已知的字符哈夫曼编码将文本字符转换为二进制串的哈夫曼编码形式。3、译码：从文件中读入二进制串字符，按照哈夫曼树将其转换为文本字符。4、输出哈夫曼树：以凹入表（层次表）的形式显示哈夫曼树。三、实验仪器微型计算机实验用编程语言：TurboC2.0，BorlandC3.0等以上版本四、实验原理1、哈夫曼树的定义哈夫曼树（最优二叉树）：设有ｎ个权值｛w1,w2,...,wn｝，试构造一棵有ｎ个叶结点的二叉树，第ｉ个叶结点的权值为wi，则其中带权路径长度为最小的二叉树被称为最优二叉树或哈夫曼树。2、哈夫曼算法：哈夫曼算法要点是：(1)根据给定的ｎ个权值{w1,w2,...,wn}构成ｎ棵二叉树的集合Ｆ＝{T1,T2,...,Tn}，其中每棵二叉树Ti只有一个带权为Wi的根结点，左右子树为空。(2)在Ｆ中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树根结点的权值为左右子树根结点权值之和。(3)在Ｆ中删除这两棵树，同时将新得到的树加入到Ｆ中。(4)重复(2)和(3)，直到只剩下一棵二叉树为止。这棵二叉树便是哈夫曼树。3、哈夫曼编码对于字符的二进制编码，若任一字符的二进制编码都不是另一个字符的二进制编码的前缀。这种编码叫做前缀编码。以n种字符出现的频率作权，设计一棵哈夫曼树，并用二叉树的叶结点分别表示待编码的字符，并约定左分支表示字符‘0’，右分支表示字符‘1’。则对每个叶结点，都有唯一的一条从根结点出发的路径，则该路径上分支字符组成的字符串作为该叶子结点的编码。由此得到的编码必为二进制的前缀编码，而且是编码总长最短的二进制前缀编码，这种编码即为哈夫曼编码。例：设有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}●100●42●58●23●19●29●29●11●8●14●15●5●3●7●8则字符的哈夫曼编码为：A0110B10C1110D1111E110F00G0111H010五、实现1、哈夫曼树的存储结构根据哈夫曼树的构造算法，哈夫曼数除叶结点外，其余结点的度均为2。对于具有n个权值构造的哈夫曼树，根据二叉树的性质3，哈夫曼树的结点总数为m=2n-1,即哈夫曼树所需存储空间是由文本中不同字符的个数唯一确定的。为了便于对多棵二叉树进行组织和便于查找各二叉树的根结点，采用静态链表作为二叉树的存储结构。其存储结构描述如下：typedefstruc{charch;unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;A58-1-1B2913-1-1C79-1-1D89-1-1E1411-1-1F2312-1-1G38-1-1H1110-1-1*81060*151123*191287*291349*421410501234567891011121314*581111*100-112132、哈夫曼编码的存储结构若要编码的文本文件的字符集不变，则其哈夫曼编码不变。字符的哈夫曼编码一旦确定，可以长期使用。因此，需要用文件同时保存字符的哈夫曼编码和字符。哈夫曼编码的表示形式既要考虑存储空间的效率，也要考虑文件读取的方便。文本字符的哈夫曼编码是不等长的二进制码，用不等长的二进制字符串表示，节省存储空间，但用文件读取不方便。若用等长的结构体表示，可能要浪费一点存储空间，但文件存取方便。为了便于文件存取，采用等长结构体表示哈夫曼具有可取之处，其存储结构描述如下：#defineNODENUM26//字符集structHuffmanCoding{charch;//字符charcoding[NODENUM];//字符编码};3、字符及权值的输入形式为了避免字符及其权值的手工键盘输入带来的错误，可以将字符及其权值组织成文本文件的形式。文本文件的格式为：字符权值例如：A5B19C7D8E14F23G3H11一般读入单个字符很不方便，格式化输入字符串和数值型数据很方便，所以字符数据可以采用读串的方式读入，然后把它赋给字符变量。4、文件的设置（1）字符权值文件constchar*WeighFileName=Weight.txt;存放需构造哈夫曼树的字符和权值数据，为文本数据，见“字符及权值的输入形式”。（2）哈夫曼树数据文件constchar*TableFileName=HfmTbl.txt;存放哈夫曼树数据，二进制HTNode结构型。格式为：数据个数M记录1记录2……记录M数据个数—哈夫曼树的结点数，M=2n-1,n为权值个数记录i--二进制HTNode结构型数据（3）字符编码数据文件constchar*CodeFileName=CodeFile.txt;存放字符编码数据，二进制structHuffmanCoding结构型。格式为：数据个数n记录1记录2……记录n数据个数—权值个数记录i--二进制structHuffmanCoding结构型数据（4）文本文件constchar*SourceFileName=SrcText.txt;存放需编码的文本字符串数据，其中的字符属于编码字符集。（5）编码数据文件constchar*EnCodeFileName=EnCodeFile.txt;存放对文本文件编码后的数据，其中的数据为“0”和“1”的字符串。（6）译码字符文件constchar*DecodeFileName=DecodeFile.txt;存放译码后的字符文件5、程序基本功能（1）初始化：输入编码字符和其权值，生成哈夫曼树和字符的哈夫曼编码，并用文件保存哈夫曼树和字符的哈夫曼编码。（2）编码：把文本字符串转换为“0”和“1”表示的哈夫曼编码。（3）译码：把“0”和“1”表示的哈夫曼编码串转换为文本字符串（4）显示哈夫曼树：以凹入形式显示哈夫曼树。（5）显示哈夫曼表：以表格形式显示哈夫曼树（6）显示字符编码6、辅助功能(1)菜单选择：将上述功能通过“菜单”形式罗列出来，通过菜单选择进行交互式控制程序运行。（2）读文件：把哈夫曼树数据读入内存。（3）选择结点：选择两个具有最小权值的根结点。7、程序结构本程序可以由10个函数组成，其中主函数1个，基本功能函数6个，辅助功能函数3个。函数间的调用关系图2所示。mainnemuInitializationEncodeDecodePrintHuffmanTreePrintCharCodingReadFromFilePrintHuffmanTableSelect图1：程序结构示意图8、程序函数（1）主函数：main功能：通过菜单选择控制对系统功能的操作（2）菜单选择函数：menu函数格式：intmenu(void)函数功能：构造功能菜单，并选择下一步要操作的功能。函数参数：无参数。函数返回值：1～7中的一个序号。可供选择的功能如下：1---Initialization2---Encode3---Decode4---Printhuffmantree5---PrinthuffmanTable6---PrintcharCoding7---Quit(3)初始化函数：Initialization函数格式：voidInitialization()函数参数：无参数函数功能：输入编码字符和权值，生成哈夫曼树和字符编码，并用文件TableFileName和CodeFileName保存哈夫曼树和字符编码数据。函数返回值：无(4)文本串编码函数：Encode函数格式voidEncode(void)函数功能：从文本串文件SourceFileName中读入文本字符，按照CodeFileName文件中字符的编码将其转换为“0”和“1”表示的哈夫曼编码，并把编码结果写入文件EnCodeFileName中。函数参数：无函数返回值：无(5)译码函数：Decode函数格式voidDecode()函数功能：从文件EnCodeFileName中读入“0”和“1”表示的哈夫曼编码数据，将其转换为文本字符，并将译码结果写入文件DecodeFileName中。函数参数：无函数返回值：无(6)显示哈夫曼树函数：PrintHuffmanTree函数格式voidPrintHuffmanTree()函数功能：以凹式形式显示哈夫曼树函数参数：无函数返回值：无(7)显示哈夫曼树表函数：PrintHuffmanTable函数格式voidPrintHuffmanTable()函数功能：以表格形式显示哈夫曼树函数参数：无函数返回值：无(8)显示字符哈夫曼编码函数：PrintCharCoding函数格式voidPrintCharCoding()函数功能：显示字符的哈夫曼编码函数参数：无函数返回值：无(9)读文件函数：ReadFromFile函数格式intReadFromFile()函数功能：从文件TableFileName中读哈夫曼树数据函数参数：无函数返回值：0—读数据失败0--读入的数据个数(10)选择根界点函数：Select函数格式voidSelect(structnodeht[],intn,int*s1,int*s2)函数功能：从多棵树中选择两个权值最小的根结点函数参数：structnodeht[]—哈夫曼树intn—选择结点的范围，即只能在0～n中选择结点int*s1—指向第一个权值最小的结点的指针int*s2—指向第二个权值最小的结点的指针函数返回值：无六、主要算法描述1、初始化函数Initialization算法描述功能：读入字符及其权值，生成哈夫曼树和字符哈夫曼编码。字符输入的处理：C语言输入字符的处理很不方便，任何一个字符都当作有效字符处理，包括空格字符和回车符。而用格式读函数读字符串很方便，空格字符和回车符都当作字符串数据的分隔。因此，可以先把字符用格式读函数把字符读入字符数组中，再将其赋值给字符变量，这样处理更简单。算法步骤：（1）输入：读入n个叶结点的字符和权值存放于静态树T中的前n个分量中。（2）初始化：将树T的其余结点的三个指针均置为空（-1），权值置为0，字符为“*”。（3）合并：进行n-1次合并，将产生的新结点i依次放入T的第i个分量中（n≤i≤m-1）。合并分两步进行：①在当前森林T[0..i-1]的所有结点中，选取权最小和次小的两个根结点T[p1]和T[p2]作为合并对象。（0≤p1,p2≤i-1）②将根为T[p1]和T[p2]的两棵树作为左右子树合并为一棵新的树。新树的根为T[i]，权值为T[p1]和T[p2]的权值之和。并且T[p1]和T[p2]的parent为i，T[i]的lchild和rchild分别为p1和p2。（4）保存哈夫曼树数据。（5）生成字符编码。（6）保存字符编码数据。算法描述如下：接口参数：(无)输入权值个数ndo-While(n=1)*p&&*p==‘’把哈夫曼树数据存储到文件中把字符和编码数据数据保存到文件中计算结点个数m=2n-1,申请存储空间ht输入字符和权值for(i=0;in;i++)ht[i].parent=ht[i].lchild=ht[i].rchild=-1ht[i].ch='*';ht[i].weight=0for(i=n;im;i++)ht[i].parent=ht[i].lchild=ht[i].rchild=-1Select(ht,i-1,&s1,&s2)for(i=n;im;i++)ht[s1]