哈夫曼树及其应用(完美版)

数据结构课程设计设计主题：赫夫曼树及其应用研究所：计算机科学和技术专业化：网络工作路径类别：网路131学号：学生姓名：谢谢导师：叶芝2015年7月12日设计目的：赫夫曼编码被广泛使用，使用赫夫曼树获得的通信的二进制编码称为赫夫曼编码。从树的根到每个树叶，路径的每个分支都有一个路径。指向左侧子树的分支表示代码“0”；右侧子树的分支表示代码“1”；将每个路径的序列“0”或“1”作为对应于单独树叶的字符导入。这就是赫夫曼编码。海夫曼可以将输入字符串编译为二进制代码，并在输入二进制代码时将其编译为字符串。1、熟悉树的二叉树存储结构和特性。2，掌握如何构建霍夫曼树和赫夫曼编码。设计内容：Aabbcab.要发送(a、b、c、d、e、f等共100个字符)的内容，请输入消息中出现的6个字符(共100次)，并将6个字符编码为huff。设计要求：Hefman编码实现输入的消息字符字符串，解码hefman编码生成的代码字符串以输出消息字符串。数据压缩过程通常称为编码，解压缩过程称为解码。电报通信是传递字符的二进制代码形式的字符串。但是，在传递信息时，我总是希望总长度尽可能短，即最短的代码。如果每个字符在通信中有Wi、Li编码长度和n个字符，则假定消息编码总长度为WiLi。映射到二进制树时，Wi是叶节点的权重，Li是从根点到叶节点的路径长度。然后WiLi是二叉树的加权路径长度。因此，设计消息总长度的最短二进制前缀编码是以n个字符出现的频率构造huff man树，此配置过程称为huff man编码。设计实施功能：1.另存为辅助列表。赫夫曼树的建立；查找并显示每个字符的Huffman代码。答：霍夫曼树的结构(1)给定n个加权值W1，W2，Wn配置的n个二进制树集f=t1，T2，Tn。其中，每个二进制树Ti只有一个权限为Wi的根节点，左侧和右侧的子树为空。(2)在f中，选择根节点权重最小、权重最低的两个二进制树作为左右子树，以构建新的二进制树。此新二叉树根节点的权重是左和右子根节点权重的总和。(3)删除集合f中的两个子树(左和右)，并将新创建的二进制树添加到集合f中。(4)重复两个步骤(2)(3)，如果f只剩下一个二叉树，则只有创建这个二叉树的哈夫会成为树。”他说第二：设计概述赫夫曼编制解码器的主要功能是先创建赫夫曼树，然后使用生成的赫夫曼树生成赫夫曼代码，最后对其进行解码。在数据通信中，通常需要将传递的文本转换为由二进制字符0，1组成的二进制字符串(称为编码)。如果配置仅半高树，使仅半高树的左分支表示0，右分支表示1，则由从根节点到每个叶节点的路径分支组成的0和1序列，通过编码对应于该节点的字符称为半高代码。最简单的二进制编码方法是等长编码。对于长度不同的编码，高频率字符的编码缩短，低频率字符的编码延长，发送的总消息长度缩短。霍夫曼树课程用于构建消息的编码长度最短的编码体系。(1)主要流程图如图所示。开始节点数是否大于-1为Ht分配data和权重根节点和权重输出调用SELECT函数根节点函数计算父节点是两个子节点的总和两个子节点和配置的节点输出是根节点吗？左边的儿子是空的吗？编码为0I2*N？I编码为1结束否否否右子项是否为空是是否否是是是(2)设计中包含的几个方面：赫夫曼树的建立Huffman树构造由hufman算法定义，在初始树系中有n个仅包含根节点的二进制树。算法的第二步是将当前树系中两个根节点权重最小的二进制树合并为新的二进制树。每次合并后，森林中的一棵树就会减少，从而生成新节点。显然需要n-1合并，因此生成了n-1个新节点。都是具有两个子节点的分支节点。结果，生成的Huffman树总计有2n-1个节点，其中n个节点是初始森林中的n个孤立节点。而且，霍夫曼树没有度数为1的分支节点。您可以使用2n-1大小的一维阵列储存Huffman树的节点。赫夫曼编码要求消息的huff man编码。首先必须定义huff man编码类型，根据设计要求和实际需要定义的类型包括：Typed et structChar ch/储存编码文字charbitsn 1；/存储编码位字符串Int len/编码长度 CodeNode/编码结构类型字符串解码解密的基本想法是从文件中读取编码，与原来老师创建的赫夫曼码表比较，将该字符放入新字符串中。三、详细设计(1)赫夫曼树的存储结构描述如下。#define N 50 /叶节点数# define M 2 * N-1/Huffman树中的节点总数Typedef structInt weight/叶节点权重Int lchild、rchild、parent/左右儿童和父母指针 HTNode/树的节点类型typedef HTNode HuffmanTreeM 1；霍夫曼树算法调用Void create ht (htnode ht，int n)/输入的数组ht和节点数nInt i、k、lnode、rnodeInt min1、min2for(I=0)；I2 * n-1；I)Ht I。parent=ht I。lchild=ht I。rchild=-1；/所有节点的相关域设置初始值-1for(I=n)；I2 * n-1；I) /仅半树配置Min1=min2=32767/int的范围为-32768-327