Huffman编译码程序的分析与设计-源代码+流程图 第6页

根据给定的权值构成二叉树森林，在森林中任意选取两棵根节点权值最小的树，将这两棵树合并为新的树，为保证新树仍为二叉树，需要增加一个新的结点作为根将这两个孩子的权值之和作为新树根的权值。对新的森林重复上述步骤直到森林中只剩下一棵树为止。此树即为哈夫曼树。
算法的流程图
 图3.1 哈夫曼算法图
3.1.3 哈夫曼树的构造
①哈夫曼树是指对于一组带有确定权值的叶子结点，构造的具有最小带权路径长度的二叉树。首先，将n个权值分别是w1，w2，…,wn-1，wn的结点按权值递增排列。将每个权值作为一颗二叉树，构成n颗二叉树的森林F={T1，T2，…，Tn-1，Tn}，其中每颗二叉树Ti都只有一个权值为wi的根结点，其左、右子树均为空。
②在森林F中选取两颗根结点权值最小的二叉树，作为左、右子树构造一颗新的二叉树，并使得新二叉树根结点的权值为其左、右子树上根结点的权值之和。
③在森林F中，删除这两棵树，同时将新得到的二叉树代替者两棵树加入森林F中。因此，森林F中二叉树的个数将比以前少一颗。
④对新的森林F重复②和③，直到森林F中只有一棵树为止。这棵树就是哈夫曼树。构造出的哈夫曼树如下图所示：
 
图3.2 最优二叉树构造

3.1.4  哈夫曼树的存储
  对哈夫曼树的存储我们可以采用带双亲的孩子链表作为结点的存储结构。由哈夫曼算法可知，如果哈夫曼树有n个叶结点，则最终生成的哈夫曼树共有2n-1个结点。因此可用一个长为2n的一文数组存放哈夫曼树中所以结点，存储结构如表3-1；本文来自辣.文,论-文·网原文请找腾讯324.9114
表3-1哈夫曼书存储结构
name weight parent lchild rchild

#define leafnum 27
#define hufnum 2*leafnum
typedef char datatype;
typedef struct node
{
 datatype name;
 int weight;
 int parent,lchild,rchild;
}huftree;
huftree tree[hufnum+1];
其中，name表示结点数据的名称,weight表示结点的权值,lchild,rchild分别表示结点的左右孩子在数组中的下标值，叶结点的左右孩子下标值均为0；parent表示结点的双亲在数组中的位置。利用parent=0得知该结点为树的根结点，否则为非根结点。在把森林中的两棵二叉树合并成一棵树时，必须选取两个根结点的权值最小的结点，此时就是根据parent来区分根与非根结点。

3.2 哈夫曼编、译码
3.2.1 哈夫曼编码 国际会计和金融认证的英文文献和翻译
在电报通信中，电文是以二进制数0、1序列传送的。在发送端将电文中的字符序列转换为二进制数0、1序列，这就是编码。哈弗曼编码就是为了得到最短的二进制前缀编码，用来缩短传送电文的总长度L。为了得到总厂最短的二进制前缀编码，可用该字符出现的频率作为叶子结点的权赋给该结点，求出此树的最小带权路径长度。用哈夫曼树得到的编码就成为哈弗曼编码。其实现算法如下：

上一页  [1] [2] [3] [4] [5] [6] [7] [8] [9] 下一页

Huffman编译码程序的分析与设计-源代码+流程图 第6页下载如图片无法显示或论文不完整，请联系qq752018766