【数据结构】基于c++的哈夫曼树构造、编码、译码算法实现 ※这篇是以前投在CSDN上的,现在搬来b站。别的写过的一些文章也会陆续搬过来,以后会主要考虑在b站发文章 创建哈夫曼树的描述: 数据结构: 数据的逻辑结构是树状结构;采用静态的三叉链表存放。 算法思想: 1.先把三叉链表中N个素进行初始化,存放叶子节点,他们都没有孩子和双亲。 2.再初始化后n-1个非叶子节点素。 3.从当前森林中(在森林中树的根节点的双亲为0)选择两棵根的权值最小的树;删除合并是将选到的两棵树的根权和存入数组当前最前面的空闲素中,并置入相应的双亲与孩子的位置。 4.重复上述步骤直到森林中只含有一棵二叉树为止。 哈夫曼树编码的描述: 数据结构: 数据的逻辑结构是树状结构;采用静态的三叉链表存放。 算法思想: 1.申请存储哈夫曼编码串的指针数组,申请一个字符型指针,用来存放临时的编码串。 2.从叶子节点开始向上倒退,若其为它双亲节点的左孩子则编码标0,否则标1;直到根节点为止,最后把临时存储编码复制到对应的指针数组所指向的内存中。 3.重复上述步骤,直到所有的叶子节点都被编码完。 哈夫曼树译码的描述: 数据结构: 数据的逻辑结构是树状结构;采用静态的三叉链表存放。 算法思想: 1.从根结点开始向下递推,若其编码当前的数值为0,则到该节点的左孩子,否则转到其右孩子;重复上述步骤直到该编码中全部访问完,则树中对应的叶子节点则为所求。 2.依据上述步骤,对编码数组中所有编码全部进行译码。 算法流程: 1.选择两个权值最小的结点; 2.创建哈夫曼树; 3.打印哈夫曼树; 4.哈夫曼编码; 5.哈夫曼译码。 程序代码: 运行结果:
2024最新激活全家桶教程,稳定运行到2099年,请移步至置顶文章:https://sigusoft.com/99576.html
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处:https://sigusoft.com/39900.html