当前位置: 首页 > news >正文

数据结构和算法-哈夫曼树以相关代码实现

文章目录

  • 总览
  • 带权路径长度
  • 哈夫曼树的定义
  • 哈夫曼树的构造
    • 法1
    • 法2
  • 哈夫曼编码
  • 英文字母频次
  • 总结
  • 实验内容: 哈夫曼树
    • 一、上机实验的问题和要求(需求分析):
    • 二、程序设计的基本思想,原理和算法描述:
    • 三、调试和运行程序过程中产生的问题及采取的措施:
    • 四、源程序及注释
    • 五、运行结果

总览

在这里插入图片描述

带权路径长度

在这里插入图片描述

哈夫曼树的定义

一个含n个带权叶节点的二叉树对应形式有多种(左右也不是两种的形式),可自己去画画
在这里插入图片描述

哈夫曼树的构造

即权值最小的叶子节点作为最长路径的叶子节点

法1

在这里插入图片描述

法2

在这里插入图片描述
二者本质相同,都是每次从节点中找最小的两个合并为一个新节点

哈夫曼编码

在这里插入图片描述

在这里插入图片描述
前缀编码就是不存在部分编码为其他编码的开头某部分
或者说不存在编码为其他编码的子集
在这里插入图片描述
在这里插入图片描述

英文字母频次

即各频率为权重,然后去构造对应的哈夫曼树,最后得出各自的编码
数据压缩率可以认为是 对应哈夫曼树的WPL / 用原来的固定长度编码对应的WPL
在这里插入图片描述

总结

在这里插入图片描述

实验内容: 哈夫曼树

一、上机实验的问题和要求(需求分析):

[ 题目 ] (1)哈夫曼树问题。(2)利用哈夫曼编码进行通讯可以大大提高信道利用率,缩
短信息传输时间,降低传输成本,但是,这要求在发送端通过一个编码系统对待传数据进行
预先编码;在接受端将传来的数据进行解码(复原)对于双工信道(即可以双向传输的信道),
每端都要有一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编译码系统。

二、程序设计的基本思想,原理和算法描述:

1.实现哈夫曼编码首先需要构建最优二叉树,权值越大的叶节点越靠近根节点,其算法为:键盘输入的字符串长度决定最优二叉树的节点数,遍历这个字符串长度,创建具有字符长度n的单节点树。选取根节点权值最小和次小的两个根节点合成一棵树,重复这个过程——把根节点最小和次小的结合直到每个节点都出现在最优二叉树上。

2.构造哈夫曼编码:

左分支为0,右分支为1,各结点所对应的二进制编码为该节点的哈夫曼编码。采用叶节点向上回溯的方法,每退回一个就记录一位数字。将所得编码存入code[]。

3.编码:

根据所得哈夫曼树对比字符串,根据左分支为0右分支为1输出其对应编码。

4.解码:根据哈夫曼树回溯编码。

三、调试和运行程序过程中产生的问题及采取的措施:

使用printf打印相关内容,从而观察变化

四、源程序及注释

#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#define status int
#define OK 1
#define Maxvalue 100
#define Maxleaf 30 
typedef struct
{ int weight;int parent ,lchild,rchild ;
}HTNode,*HuffmanTree;typedef char * *HuffmanCode; //指向字符指针的指针status Select(HuffmanTree HT,int n,int &s1, int &s2) //选择最小的两个节点
{HuffmanTree p;int i;int lnode= Maxvalue,mnode= Maxvalue;for(p=HT,i=1;i<=n;i++){ //lnode小于始终会小于mmnode,因为if的匹配顺序if(p[i].weight<lnode&&p[i].parent==0)// 判断该节点的权重是否小于当前的lnode并且已经有父节点的不要{ mnode=lnode;         //此时mmode更新为lnodelnode=p[i].weight;  //lnode更新为当前节点的权重s2=s1;          //S2为mmnode对应节点的索引 S1为lnode对应节点的索引 此时将mnode的索引更新s1=i;      //更新lnode的索引更新}else if(p[i].weight<mnode&&p[i].parent==0) //当该节点的权重大于lnode时并判断是否小于当前的mnode并且已经有父节点的不要{mnode=p[i].weight;   //更新mnode的为当前节点的权重s2=i;           //更新mnode此时的索引}}return OK;
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC, int *w,int n)
{   int i,m,start,f,s1=0,s2=0 ,c;char *cd;HuffmanTree p;if(n<=1)return;//叶子节点判断m=2*n-1;  //求出叶子节点对应的二叉树的节点个数 合并次数+节点个数=对应二叉树的节点个数HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(p=HT+1,i=1;i<=n;++i,++p,++w){ (*p).weight=*w;// 刚开始的节点赋权值(*p).parent=0; (*p).lchild=0;(*p).rchild=0;}for(i=1;i<=n;i++){ printf("刚开始的第%d个叶子节点weight:%d ,parent:%d ,lchild:%d ,rchild:%d ",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);printf("\n");  //刚开始的}for(;i<=m;i++)  { (*p).weight=0; //其他节点初始化为0(*p).parent=0;(*p).lchild=0;(*p).rchild=0;p++; }for(i=1;i<=m;i++){   printf("初始化完成的哈夫曼树的第%d节点:%d ,%d ,%d ,%d ",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);printf("\n");}for(i=n+1;i<=m;++i){Select(HT,i-1,s1,s2);  //传入的是原来的和新建的节点范围,返回的是对应节点中权重最小的两个HT[s1].parent=i;      //然后建立父子关系HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight; //父节点的权重等于两个孩子的权重和}for(p=HT+1,i=1;i<=m;i++,p++){printf("编码完成后的哈夫曼树的第%d个节点:%d,%d,%d,%d",i,(*p).weight,(*p).parent,(*p).lchild,(*p).rchild); printf("\n");} //从叶子到根逆向求每个字符的赫夫曼编码HC=(HuffmanCode )malloc((n+1) *sizeof(char *)); //编码的字符串地址数组 大小为(n+1)*8 但类型为HuffmanCode,即单位为八个字节 指向char* cd=(char*)malloc(n*sizeof(char));// n个字符的指针,对应编码结果cd[n-1]='\0'; //结束符for(i=1;i<=n;++i) //遍历初始的叶子的节点{start=n-1;    //编码从后往前一个一个字符的赋值for(c=i,f=HT[i].parent; f!=0; c=f,f=HT[f].parent) //从初始叶子节点遍历父节点,直到对应父节点为0时停止{if(HT[f].lchild==c) cd[--start]='0'; //如果父节点的左孩子为当前节点则此时编码为0else cd[--start]='1'; //如果父节点的右孩子为当前节点则此时编码为1}//则当前叶子节点对应的编码转换完成HC[i]=(char *)malloc((n-start)*sizeof(char));//赋予满足编码长度的字符串地址strcpy(HC[i],&cd[start]); //赋值给当前节点的编码printf("当前第%d个叶子的编码为:%s\n",i,HC[i]); }free(cd);
}int main()
{HuffmanTree HT;HuffmanCode HC;int n,i; int w[8]={5,29,7,8,14,23,3,11};printf("%d",sizeof(char *));printf("请输入叶子节点的个数:\n");scanf("%d",&n); //输入叶子节点的个数HuffmanCoding(HT,HC, w,n); //生成哈夫曼树并输出对应各个叶子节点的编码return 0;
}

五、运行结果

在这里插入图片描述

相关文章:

数据结构和算法-哈夫曼树以相关代码实现

文章目录 总览带权路径长度哈夫曼树的定义哈夫曼树的构造法1法2 哈夫曼编码英文字母频次总结实验内容&#xff1a; 哈夫曼树一、上机实验的问题和要求&#xff08;需求分析&#xff09;&#xff1a;二、程序设计的基本思想&#xff0c;原理和算法描述&#xff1a;三、调试和运行…...

Kafka 的起源和背景

Apache Kafka 是一个分布式流处理平台&#xff0c;被广泛用于构建实时数据流应用程序和大数据处理系统。本文将深入探讨 Kafka 的起源、设计原则以及它在大数据领域中的重要作用。 大数据和实时数据处理背景 在大数据时代&#xff0c;处理海量数据和实时数据成为了一项关键挑…...

三极管在数字电路中的应用

一、认识三极管 三极管拥有3个引脚&#xff0c;分别对应3个级&#xff1a;基极(Base)、发射极&#xff08;Emitter&#xff09;、集电极(Collector)&#xff0c;如下图所示&#xff1b;下图横向左侧的是基极&#xff0c;带箭头的那个引脚就是发射极&#xff0c;另一个就是集电…...

java后端自学错误总结

java后端自学错误总结 MessageSource国际化接口总结 MessageSource国际化接口 今天第一次使用MessageSource接口,比较意外遇到了一些坑 messageSource是spring中的转换消息接口&#xff0c;提供了国际化信息的能力。MessageSource用于解析 消息&#xff0c;并支持消息的参数化…...

CLion安装与配置教程

目录 一、下载并安装CLion1、下载1、官网&#xff1a;2、注意&#xff1a; 2、安装1、下载完成后&#xff0c;直接点击安装包安装&#xff0c;即可。2、开始安装&#xff0c;然后下一步3、可以在此处自定义地址&#xff0c;然后下一步4、根据系统版本选择&#xff0c;然后下一步…...

初识主力投资者

在股票市场中&#xff0c;真正赚钱的散户并不多。“七亏二平一赚”似乎已经成为了大家公认的一个股市定律。 为什么散户炒股赚的人少呢&#xff1f;原因很简单&#xff0c;就是因为市场上除了散户之外&#xff0c;还存在着一个重要的投资主体——主力。股市交易的过程&#xff…...

vue项目报错及解决npm run build:prod打包错误

vue项目报错及解决npm run build:prod打包错误 执行dev环境时加载失败了该变量&#xff0c;在package.json文件中 删掉 解决方法&#xff1a; 打包成功&#xff1a;...

Go连接mysql数据库

package main import ("database/sql""fmt"_ "github.com/go-sql-driver/mysql" ) //go连接数据库示例 func main() {// 数据库信息dsn : "root:roottcp(192.168.169.11:3306)/sql_test"//连接数据库 数据库类型mysql,以及数据库信息d…...

⭐ Unity 里让 Shader 动画在 Scene 面板被持续刷新

写 Unity Shader的时候&#xff0c;只有播放状态下的 Game 面板能看到Shader 顺畅的动态效果&#xff0c;不方便。 想要带有动态效果的 Shader 在 Scene 面板持续更新动画&#xff0c;只需要打开一个开关就能让 Scene 持续刷新动画了。 感谢大家的观看&#xff0c;您的点赞和关…...

面试--各种场景问题总结

1.在开发过程中&#xff0c;你是如何保证机票系统的正常运行的&#xff1f; 用户、测试、监控和日志、安全措施、数据备份、系统设计、需求分析 2.在机票系统开发过程中&#xff0c;你最有成就的事情&#xff0c;为什么&#xff1f; 用户体验感、高可用和稳定性、客户满意度、系…...

solidity实现ERC721代币标准发布NFT

文章目录 1、非同质化货币&#xff08;NFT&#xff09;- 维基百科2、IERC1653、IERC7214、IERC721Receiver5、IERC721Metadata6、ERC7217、ERC721 NFT 的实现8、编译部署 1、非同质化货币&#xff08;NFT&#xff09;- 维基百科 非同质化代币&#xff08;英语&#xff1a;Non-F…...

Failed building wheel for opencv-python which use PEP 517

这主要是opencv-python版本更新以后wheels也更新了&#xff0c;但是相关安装软件没有及时适配&#xff0c;所以不管是使用pip直接安装还是换源其实效果都是报错&#xff0c;解决方法就是直接指定安装旧版opencv-python完事儿&#xff0c;例如&#xff1a; pip3 install opencv…...

HTML5 的全局属性 hidden 和 display:none 的关系

目录 1&#xff0c;hidden 和 display:none 的关系2&#xff0c;其他隐藏元素的方式2.1&#xff0c;语意上的隐藏2.2&#xff0c;视觉上的隐藏 1&#xff0c;hidden 和 display:none 的关系 hidden - MDN 参考 一句话总结&#xff1a;hidden 是HTML5 新增的全局布尔属性&…...

CCKS2023-面向上市公司主营业务的实体链接评测-亚军方案

赛题分析 大赛地址 https://tianchi.aliyun.com/competition/entrance/532097/information 任务描述 本次任务主要针对上市公司的主营业务进行产品实体链接。需要获得主营业务中的产品实体&#xff0c;将该实体链接到产品数据库中的某一个标准产品实体。产品数据库将发布在竞赛…...

关于我离破500粉丝感受

嘿嘿快破500粉丝啦&#xff0c;加油喔&#xff0c;感谢支持 首先&#xff0c;恭喜我在CSDN上的粉丝数量即将突破500大关&#xff01;这说明你在这个平台上的内容受到了很多人的关注和认可。 1. 保持高质量的内容输出&#xff1a;粉丝数量的增长与你在CSDN上发布的内容质量密切…...

锁表的原因及解决办法

引言 作为开发人员&#xff0c;我们经常会和数据库打交道。 当我们对数据库进行修改操作的时候&#xff0c;例如添加字段&#xff0c;更新记录等&#xff0c;没有正确评估该表在这一时刻的使用频率&#xff0c;直接进行修改&#xff0c;致使修改操作长时间无法响应&#xff0…...

Kettle 安装配置

文章目录 Kettle 安装配置Kettle 安装Kettle 配置连接 Hive Kettle 安装配置 Kettle 安装 在安装Kettle之前&#xff0c;需要确定已经安装Java运行环境。Kettle需要Java的支持才能运行&#xff0c;JDK的版本最好是8.x的太新的也会出现bug。Kettle的7.1版本的太旧了&#xff0…...

Webgis学习总结

前言&#xff1a; 作者跟随视频学习了webgis内容进行如下学习复习总结 参考&#xff1a;新中地学习笔记 WebGIS第一课&#xff1a;测试高德API并通过&#xff1a; 注册申请高德API成为开发者&#xff0c;创建自己的项目和key进行项目初始化&#xff0c;可以使用JS API官方文…...

【开源】基于Vue+SpringBoot的音乐平台

项目编号&#xff1a; S 055 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S055&#xff0c;文末获取源码。} 项目编号&#xff1a;S055&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块三、系统展示 四、核心代码4.1 查询单首…...

20、Resnet 为什么这么重要

(本文已加入“计算机视觉入门与调优”专栏,点击专栏查看更多文章信息)r esnet 这一网络的重要性,上一节大概介绍了一下,可以从以下两个方面来有所体现:第一是 resnet 广泛的作为其他神经网络的 back bone;第二是 resnet 是 AI 芯片厂家对标性能时,在视觉领域尤其是图像…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

Caliper 配置文件解析:config.yaml

Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...