【c++哈夫曼树代码实现】

哈夫曼树是不定长编码方式，由于是将权值大的元素放在离根结点近的地方 ，权值小的放在离根远的地方，哈夫曼树效率很高，并且一个编码不会以另一个编码作为前缀，避免了编码的歧义性，本文将带大家探索如何创建和使用哈夫曼树。

在这里插入图片描述

构造哈夫曼树

n个元素构造哈夫曼树需要2n-1个结点，为什么是这个结果呢？接下来我们看一下哈夫曼树的构造原理

  1. 从所有（未确定双亲结点）元素中选出两个权值最小的元素
  2. 选出来的元素的权值的和为新的元素的权值（新的元素将是这两个元素的双亲结点），再将新的元素放入原来的元素集合中（已经确定双亲结点则不用放回集合中），现在集合中元素数量-1，但总元素个数+1，因为新生成了一个元素。
  3. 重复 1，2过程，直到元素集合中只有1个元素。

很容易看出总共要重复n-1次1，2操作（因为每次操作后集合元素数量要-1，当集合元素的数量为2时就是最后一次操作，此时总共进行了n-1次操作）每进行一次操作都会生成一个新元素，所以总共生成了n-1个新元素，再加上原来的元素，总共2*n-1个。
这里我们用结构体数组维护哈夫曼树，清楚原理后我们来看下具体代码：
在这里插入图片描述

#include <iostream>
using namespace std;
//最大元素个数
const int N=1e5;

typedef struct{
    int parent;
    int lchild,rchild;
    int weight;
}HuffNode,*HUffTree;

//第0个位置不使用，下标从1开始
HuffNode tree[N*2];
void HuffMan(HuffNode tree[],int w[],int n){
    //p1最小的权值的结点索引，p2第二小的结点的索引
    int i,j,p1,p2;
    int small1,small2;
    //要求最小值，所以初始化要赋很大的值
    small1=small2=0x3fff;

    //初始化每个结点
    for(i=1;i<=n;i++){
        tree[i].weight=w[i];
        tree[i].parent=0;
        tree[i].lchild=0;
        tree[i].rchild=0;
    }
    //初始化其他结点
    for(;i<2*n;i++){
        tree[i].parent=0;
        tree[i].lchild=0;
        tree[i].rchild=0;
    }
    for(i=n+1;i<2*n;i++){
        for(j=1;j<i;j++){
            //如果结点的双亲结点为0，说明改结点还在元素集合中
            if(tree[i].parent==0){
                if(tree[i].weight<small1){
                    //已经找到一个比原来最小的元素还小的元素，那原来最小的现在成了第二小
                    small2=small1;
                    p2=p1;
                    //更新最小元素
                    small1=tree[i].weight;
                    p1=j;
                }
                else if(tree[i].weight<small2){
                    small2=tree[i].weight;
                    p2=j;
                }
            }
        }
        //找到权值最小的两个结点后，要生成新的结点
        tree[i].weight=small1+small2;
        tree[i].lchild=p1;
        tree[i].rchild=p2;
        //更新最小的两个结点的双亲为新结点
        tree[p1].parent=tree[p2].parent=i;
    }
    
}

哈夫曼树编码

在已经建好的哈夫曼树上，从叶子结点开始沿着双亲结点找根，每退回一步就到了一个分支，从而得到一位哈夫曼编码的值。因为每一个字符的哈夫曼编码都是根结点到叶子结点的路径分支上的0、1序列，所以先得到的编码是低位码，后得到的是高位码，可以设置二维字符数组来保存每个哈夫曼编码。

char HuffManCode[N][N];
void huffmancodding(HuffNode tree[],int n){
    //存储每次循环后字符的哈夫曼编码
    char * tem = (char*)malloc(n*(sizeof(char)));
    int  parent;

    //结束标志
    tem[n-1] = '\0';

    //叶子结点是前n个结点
    for(int i =1;i<=n;i++){
           int idx=n-1;
        for(int j =i;tree[j].parent!=0;j=tree[j].parent){
            //得到双亲结点
            parent = tree[j].parent;
            //左分支为 0，右分支为 1
            if(tree[parent].lchild==j){
                tem[--idx]='0';
            }
            else{
                tem[--idx]='1';
            }

        }
        //在C语言中，数组是一个连续存储的数据结构，其中每个元素都有一个固定的地址。数组名实际上是指向数组第一个元素的指针。
        //对于二维数组b[n][m]，它实际上是按行优先或列优先的方式在内存中进行存储的一维数组。
        // 因此，b[i]实际上是代表了第i+1行（如果从0开始计数）的首地址，也就是指向这一行第一个元素的指针。
        strcpy(HuffManCode[i],&tem[idx]);

    }
    free(tem);

    for(int i =1;i<=n;i++)
        printf("%d:   %s\n",i,HuffManCode[i]);
}

测试

按照这个图来检验一下我们的代码
请添加图片描述
请添加图片描述

#include <iostream>
#include <cstring>
using namespace std;
//最大元素个数
const int N=100;

typedef struct{
    int parent;
    int lchild,rchild;
    int weight;
}HuffNode;

//第0个位置不使用，下标从1开始
HuffNode tree[N*2];
void HuffMan(HuffNode tree[],int w[],int n){
    //p1最小的权值的结点索引，p2第二小的结点的索引
    int i,j,p1,p2;
    int small1,small2;
    //要求最小值，所以初始化要赋很大的值
    small1=small2=0x3fff;

    //初始化每个结点
    for(i=1;i<=n;i++){
        tree[i].weight=w[i];
        tree[i].parent=0;
        tree[i].lchild=0;
        tree[i].rchild=0;
    }
    //初始化其他结点
    for(;i<2*n;i++){
        tree[i].parent=0;
        tree[i].lchild=0;
        tree[i].rchild=0;
    }
    for(i=n+1;i<2*n;i++){
        small1=small2=0x3fff;
        for(j=1;j<i;j++){
            //如果结点的双亲结点为0，说明改结点还在元素集合中
            if(tree[j].parent==0){
                if(tree[j].weight<small1){
                    //已经找到一个比原来最小的元素还小的元素，那原来最小的现在成了第二小
                    small2=small1;
                    p2=p1;
                    //更新最小元素
                    small1=tree[j].weight;
                    p1=j;
                }
                else if(tree[j].weight<small2){
                    small2=tree[j].weight;
                    p2=j;
                }
            }
        }
        //找到权值最小的两个结点后，要生成新的结点
        tree[i].weight=small1+small2;
        tree[i].lchild=p1;
        tree[i].rchild=p2;
        //更新最小的两个结点的双亲为新结点
        tree[p1].parent=tree[p2].parent=i;
    }

}
char HuffManCode[N][N];
void huffmancodding(HuffNode tree[],int n){
    //存储每次循环后字符的哈夫曼编码
    char * tem = (char*)malloc(n*(sizeof(char)));
    int  parent;

    //结束标志
    tem[n-1] = '\0';

    //叶子结点是前n个结点
    for(int i =1;i<=n;i++){
           int idx=n-1;
        for(int j =i;tree[j].parent!=0;j=tree[j].parent){
            //得到双亲结点
            parent = tree[j].parent;
            //左分支为 0，右分支为 1
            if(tree[parent].lchild==j){
                tem[--idx]='0';
            }
            else{
                tem[--idx]='1';
            }

        }
        //在C语言中，数组是一个连续存储的数据结构，其中每个元素都有一个固定的地址。数组名实际上是指向数组第一个元素的指针。
        //对于二维数组b[n][m]，它实际上是按行优先或列优先的方式在内存中进行存储的一维数组。
        // 因此，b[i]实际上是代表了第i+1行（如果从0开始计数）的首地址，也就是指向这一行第一个元素的指针。
        strcpy(HuffManCode[i],&tem[idx]);

    }
    free(tem);

    for(int i =1;i<=n;i++)
        printf("%d:   %s\n",i,HuffManCode[i]);
}
int main(){
    int w[7]={0,6,2,3,9,10,8};
    HuffMan(tree,w,6);
   huffmancodding(tree,6);

}

请添加图片描述

总结

本文介绍了哈夫曼树的创建和如何编码，希望本文能帮助到正在学习哈夫曼树的读者。在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/187511.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【Apache Doris】一键实现万表MySQL整库同步 | 快速体验

【Apache Doris】一键实现万表MySQL整库同步 | 快速体验

【Apache Doris】一键实现万表MySQL整库同步 | 快速体验&#xff09; 一、 环境信息1.1 硬件信息1.2 软件信息 二、 流程介绍三、 前提概要3.1 安装部署3.2 JAR包准备3.2.1 数据源3.2.2 目标源 3.3 脚本模版 四、快速体验五、常见问题5.1 Mysql通信异常5.2 MySQL无Key同步异常5…
阅读更多...
excel一个单元格换行方法

excel一个单元格换行方法

要是在同一个单元格内输入文字输入不下的话&#xff0c;我们是可以进行同一个单元格换行设置的&#xff0c;而且换行的方法也是有很多种&#xff0c;下面我们就一起来看一下有哪些方法吧。 excel一个单元格换行方法&#xff1a; 方法一&#xff1a; 1、我们可以直接按下alte…
阅读更多...
2-10岁女童穿搭 I 看的见的时尚感

2-10岁女童穿搭 I 看的见的时尚感

分享女儿的时尚穿搭—连帽加绒卫衣 简单易搭怎么穿都好看的卫衣 红色吸睛又显肤色&#xff0c;不挑人穿 面料亲肤柔软&#xff0c;保暖性也很棒 单穿内搭都能轻松打造时尚造型&#xff01;&#xff01;
阅读更多...
广州华锐互动：AR可视化展示昆虫让教学过程更直观生动

广州华锐互动：AR可视化展示昆虫让教学过程更直观生动

随着科技的不断发展&#xff0c;AR&#xff08;增强现实&#xff09;技术已经逐渐走进我们的生活。通过AR技术&#xff0c;我们可以将虚拟的信息叠加到现实世界中&#xff0c;让现实世界变得更加丰富多彩。在这篇文章中&#xff0c;我们将以昆虫为主题&#xff0c;探讨AR增强现…
阅读更多...
破案现场：Docker容器资源限制导致的oom问题

破案现场：Docker容器资源限制导致的oom问题

破案现场&#xff1a;Docker容器资源限制导致的oom问题 01 事故现场02 问题定位03 对症下药04 后记 原文来自于微信公众号“运维之美” https://mp.weixin.qq.com/s?__bizMzA5NDY1MTM3MA&mid2247484902&idx1&sn8394aefd884ee09ea546fcd400dd233c&chksm904a136…
阅读更多...
想当老师应该去学什么专业

想当老师应该去学什么专业

专业选择是决定未来职业发展的重要步骤&#xff0c;如果你也想成为一名老师&#xff0c;那么这五个专业可能会适合你&#xff01; 教育学专业 教育学专业是培养教育理论和方法的学科&#xff0c;这些理论知识将帮助你理解教学过程、学生发展、课程设计和评估。该专业将让你全面…
阅读更多...
人工智能教程（二）：人工智能的历史以及再探矩阵

人工智能教程（二）：人工智能的历史以及再探矩阵

目录 前言 更多矩阵的知识 Pandas 矩阵的秩 前言 在上一章中&#xff0c;我们讨论了人工智能、机器学习、深度学习、数据科学等领域的关联和区别。我们还就整个系列将使用的编程语言、工具等做出了一些艰难的选择。最后&#xff0c;我们还介绍了一点矩阵的知识。在本文中&am…
阅读更多...
机器学习第14天：KNN近邻算法

机器学习第14天：KNN近邻算法

☁️主页 Nowl &#x1f525;专栏《机器学习实战》 《机器学习》 &#x1f4d1;君子坐而论道&#xff0c;少年起而行之 文章目录 介绍 实例 回归任务 缺点 实例 分类任务 如何选择最佳参数 结语 介绍 KNN算法的核心思想是&#xff1a;当我们要判断一个数据为哪一类时…
阅读更多...
CMD - ping

CMD - ping

文章目录 前言参数 前言 ping 命令主要测试到达指定 IP 或主机的连通性. 参数 -t: ping 指定的计算机直到中断 -a: 将地址解析为主机名 -n count: 要发送的回显请求数
阅读更多...
教师编制缩减是为什么

教师编制缩减是为什么

老师们有没有注意到一个趋势&#xff1f;那就是教师编制正在逐步缩减。不知道你们发现没有&#xff0c;我最近在研究教育领域的新闻&#xff0c;发现这两年教师编制缩减的消息越来越多。这是为什么呢&#xff1f;今天就来跟大家聊一聊。 原因一&#xff1a;资金压力 第一个原因…
阅读更多...
【华为OD题库-038】支持优先级的对列-java

【华为OD题库-038】支持优先级的对列-java

题目 实现一个支持优先级的队列&#xff0c;高优先级先出队列&#xff0c;同优先级时先进先出。 如果两个输入数据和优先级都相同&#xff0c;则后一个数据不入队列被丢弃。 队列存储的数据内容是一个 整数。 输入描述 一组待存入队列的数据(包含内容和优先级)。 输出描述 队列…
阅读更多...
ubuntu 使用webrtc_ros 编译linux webrtc库

ubuntu 使用webrtc_ros 编译linux webrtc库

ubuntu 使用webrtc_ros 编译linux webrtc库 webrtc_ros 使用WebRTC流式传输ROS图像主题 该节点提供了一个WebRTC对等方&#xff0c;可以将其配置为流ROS图像主题并接收发布到ROS图像主题的流。 该节点托管一个提供简单测试页面的Web服务器&#xff0c;并提供可用于创建和配置W…
阅读更多...
基于springboot实现学生成绩管理系统项目【项目源码+论文说明】

基于springboot实现学生成绩管理系统项目【项目源码+论文说明】

基于springboot实现学生成绩管理系统演示 摘要 随着信息技术和网络技术的飞速发展&#xff0c;人类已进入全新信息化时代&#xff0c;传统管理技术已无法高效&#xff0c;便捷地管理信息。为了迎合时代需求&#xff0c;优化管理效率&#xff0c;各种各样的管理系统应运而生&am…
阅读更多...
【从浅识到熟知Linux】基本指令之基本权限

【从浅识到熟知Linux】基本指令之基本权限

&#x1f388;归属专栏&#xff1a;从浅学到熟知Linux &#x1f697;个人主页&#xff1a;Jammingpro &#x1f41f;每日一句&#xff1a;用博客整理整理之前学过的知识&#xff0c;是个不错的选择。 文章前言&#xff1a;本文介绍Linux中的基本权限及相关指令用法并给出示例和…
阅读更多...
互联网+智慧工地系统源码

互联网+智慧工地系统源码

智慧工地以施工现场风险预知和联动预控为目标&#xff0c;将智能AI、传感技术、人像识别、监控、虚拟现实、物联网、5G、大数据、互联网等新一代科技信息技术植入到建筑、机械、人员穿戴设施、场地进出关口等各类设备中&#xff0c;实现工程管理与工程施工现场的整合&#xff0…
阅读更多...
快速压缩：迅速减小PDF文件大小的步骤与技巧

快速压缩：迅速减小PDF文件大小的步骤与技巧

虽然png图片格式是一种无损压缩格式&#xff0c;但是png图片的内存大小也是比较大的&#xff0c;而且兼容性上也没有jpg图片好&#xff0c;许多平台推荐的也都是jpg格式&#xff0c;所以当我们需要把png转jpg格式的时候&#xff0c;就需要用到图片格式转换器&#xff0c;今天推…
阅读更多...
JAVA创建线程方式有几种

JAVA创建线程方式有几种

方式1&#xff1a;继承Thread类 步骤&#xff1a; 创建一个继承于Thread类的子类重写Thread的run()方法创建当前Thread子类的对象通过实例对象调用start()方法&#xff0c;启动线程----》JAVA虚拟机会调用run()方法 实现&#xff1a; public class TestMyThread {public sta…
阅读更多...
怎样禁止邮件发送涉密信息

怎样禁止邮件发送涉密信息

数字化时代&#xff0c;电子邮件已成为人们生活和工作中不可或缺的通讯工具。然而&#xff0c;随着互联网的普及&#xff0c;涉密信息的泄露风险也随之增加。为了保护敏感数据&#xff0c;禁止邮件发送涉密信息显得尤为重要。以下是一些建议&#xff0c;帮助你实现这一目标。 1…
阅读更多...
buuctf web [极客大挑战 2019]PHP

buuctf web [极客大挑战 2019]PHP

提示有备份,dirsearch扫描网站备份 GitHub - maurosoria/dirsearch: Web path scanner下载.zip格式文件 解压到python目录下 在上图位置cmd打开窗口 输入python setup.py install安装dirseach 安装好后输入命令使用dirseach python dirseach.py -u http://44296191-973d-448…
阅读更多...
在CentOS 7.9上搭建高性能的FastDFS+Nginx文件服务器集群并实现外部远程访问

在CentOS 7.9上搭建高性能的FastDFS+Nginx文件服务器集群并实现外部远程访问

文章目录 引言第一部分&#xff1a;FastDFS介绍与安装1.1 FastDFS简介1.2 FastDFS安装1.2.1 安装Tracker Server1.2.2 安装Storage Server 1.3 FastDFS配置1.3.1 配置Tracker Server1.3.2 配置Storage Server1.3.3 启动FastDFS服务 第二部分&#xff1a;Nginx配置2.1 Nginx安装…
阅读更多...
最新文章

Copyright @ 2022~2023