对字符串进行哈夫曼编码

对字符串进行哈夫曼编码【数据结构】哈夫曼树及哈夫曼编码实现(C语言)目录 1. 哈夫曼树 1.1 基本概念 1.2 构造哈夫曼树 1.3 哈夫曼树的类型定义

【数据结构】哈夫曼树及哈夫曼编码实现(C语言)   目录 1. 哈夫曼树 1.1 基本概念 1.2 构造哈夫曼树 1.3 哈夫曼树的类型定义 1.4 哈夫曼树创建的算法实现 2. 哈夫曼编码实现 2.1 哈夫曼编码 2.2 完整代码 2.3 运行结果   1. 哈夫曼树   1.1 基本概念   路径:指从根结点到该结点的分支序列。   路径长度:指根结点到该结点所经过的分支数目。   结点的带权路径长度:从树根到某一结点的路径长度与该结点的权的乘积。   树的带权路径长度(WPL):树中从根到所有叶子结点的各个带权路径长度之和。   
树的带权路径长度哈夫曼树是由 n 个带权叶子结点构成的所有二叉树中带权路径长度最短的二叉树,又称最优二叉树。如上图中第三棵树就是一棵哈夫曼树。 1.2 构造哈夫曼树   构造哈夫曼树的算法步骤:   ① 初始化:用给定的 n 个权值{w1,w2,…,wn}构造 n 棵二叉树并构成的森林F={T1,T2,…,Tn},其中每一棵二叉树Ti(1<=i<=n)都只有一个权值为 wi 的根结点,其左、右子树为空。   ② 找最小树:在森林 F 中选择两棵根结点权值最小的二叉树,作为一棵新二叉树的左、右子树,标记新二叉树的根结点权值为其左、右子树的根结点权值之和。   ③ 删除与加入:从 F 中删除被选中的那两棵二叉树,同时把新构成的二叉树加入到森林 F 中。   ④ 判断:重复②、③操作,直到森林中只含有一棵二叉树为止,此时得到的这棵二叉树就是哈夫曼树。   简单的说就是先选择权小的,所以权小的结点被放置在树的较深层,而权较大的离根较近,这样一来所构成的哈夫曼树就具有最小带权路径长度。   例如给定5个权值{2,3,5,7,8},构造过程如下:   
构造哈夫曼树注意:由于未规定左右子树顺序,因此哈夫曼树不唯一,但树的最小带权路径长度唯一。如下图两棵树都是根据5个权值{2,3,5,7,8}构造的哈夫曼树:   
哈夫曼树不唯一 1.3 哈夫曼树的类型定义   哈夫曼树是一种二叉树,其中没有度为1的结点,因此一棵有 n 个叶子的哈夫曼树共有 2n-1 个结点,可以用一个大小为 2n-1 的一维数组来存放哈夫曼树的各个结点。由于每个结点同时还包含其双亲信息和孩子结点的信息,所以构成一个静态三叉链表。   
结点结构   1.4 哈夫曼树创建的算法实现   基于上文中的构造哈夫曼树的步骤,代码如下:

2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/82924.html

(0)
上一篇 2024年 7月 28日 下午3:43
下一篇 2024年 7月 28日

相关推荐

关注微信