数据结构和算法-哈夫曼树以相关代码实现
文章目录
- 总览
- 带权路径长度
- 哈夫曼树的定义
- 哈夫曼树的构造
- 法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 哈夫曼编码英文字母频次总结实验内容: 哈夫曼树一、上机实验的问题和要求(需求分析):二、程序设计的基本思想,原理和算法描述:三、调试和运行…...

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

三极管在数字电路中的应用
一、认识三极管 三极管拥有3个引脚,分别对应3个级:基极(Base)、发射极(Emitter)、集电极(Collector),如下图所示;下图横向左侧的是基极,带箭头的那个引脚就是发射极,另一个就是集电…...

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

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

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

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

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的时候,只有播放状态下的 Game 面板能看到Shader 顺畅的动态效果,不方便。 想要带有动态效果的 Shader 在 Scene 面板持续更新动画,只需要打开一个开关就能让 Scene 持续刷新动画了。 感谢大家的观看,您的点赞和关…...

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

solidity实现ERC721代币标准发布NFT
文章目录 1、非同质化货币(NFT)- 维基百科2、IERC1653、IERC7214、IERC721Receiver5、IERC721Metadata6、ERC7217、ERC721 NFT 的实现8、编译部署 1、非同质化货币(NFT)- 维基百科 非同质化代币(英语:Non-F…...

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

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

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

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

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

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

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

【开源】基于Vue+SpringBoot的音乐平台
项目编号: S 055 ,文末获取源码。 \color{red}{项目编号:S055,文末获取源码。} 项目编号:S055,文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块三、系统展示 四、核心代码4.1 查询单首…...

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

Git Bash环境下用perl脚本获取uuid值
在Linux环境下,比如在ubuntu就直接有uuidgen命令直接获取uuid值。在Windows环境下常用的git bash中没有对应的命令,略有不便。这里用脚本写一个uuidgen,模拟Linux环境下的uuidgen命令。 #! /usr/bin/perl use v5.14; use Win32;sub uuidGen {…...

linux安装部署redis
1、下载redis包2、解压3、进入解压路径编译安装4、修改配置文件使redis后台运行5、启动 1、下载redis包 https://redis.io/download/ 2、解压 tar -zxvf redis-7.2.3.tar.gz3、进入解压路径编译安装 cd redis-7.2.3 make && make install默认安装路径: …...

Redis 数据结构详解
分类 编程技术 Redis 数据类型分为:字符串类型、散列类型、列表类型、集合类型、有序集合类型。 Redis 这么火,它运行有多块?一台普通的笔记本电脑,可以在1秒钟内完成十万次的读写操作。 原子操作:最小的操作单位&a…...

03-IDEA集成Git,初始化本地库,添加远程仓库,提交,拉取,推送,分支的快捷操作
IDEA集成Git 创建Git忽略文件 不同的IDE开发工具有不同的特点文件,这些文件与项目的实际功能无关且不参与服务器上的部署运行, 把它们忽略掉能够屏蔽之间的差异 局部忽略配置文件: 在本地仓库的根目录即项目根目录下直接创建.gitignore文件, 以文件后缀或目录名的方式忽略指定…...

Python---格式化输出与%百分号----涉及转义符 \ 反斜杠的使用
相关链接Python--格式化输出中的转义符号----\t 制表符(空格的)和\n(换行的)_唯元素的博客-CSDN博客 Python---字符串(用单、双引号、 三单/双引号定义。反斜杠 \ 转义,单在双内/双在单内 )-CS…...

大华技术GIS开发工程师24届秋招三场面试Offer面经
本文介绍2024届秋招中,大华技术股份有限公司的GIS开发工程师岗位的3场面试基本情况、提问问题等。 10月投递了大华技术股份有限公司的GIS开发工程师岗位,所在部门为研发中心。目前完成了一面、二面与三面等全部流程,并有幸获得Offerÿ…...

前端三大MV*模式:MVC、mvvm、mvp模式介绍
MVC(同步通信为主):Model、View、Controller MVP(异步通信为主):Model、View、Presenter MVVM(异步通信为主):Model、View、ViewModel mvc模式介绍 MVC(Model–View–Controller)模式是软件…...

分享一些Git的常用命令
常用命令 命令名称作git config —global user.name 用户名设置用户签名git config —global user.email 邮箱设置用户签名git init初始化本地库git status查看本地库状态git add 文件名添加到暂存区git commit -m “日志信息” 文件名提交到本地库git reflog查看历史记录git r…...

C语言第四十二弹---使用多种方法实现字符串左旋转
使用多种方法实现字符串左旋转 一、 左移法 思路:每一次通过移动第一个字符,然后把后面的字符前移,然后再进行移动第一个字符再前移。故需要使用嵌套循环,外层循环控制移动第一个字符的次数,第二个循环进行字符前移 …...

REST-Assured--JAVA REST服务自动化测试的Swiss Army Knife
什么是REST-Assured REST Assured是一套基于 Java 语言实现的开源 REST API 测试框架 Testing and validation of REST services in Java is harder than in dynamic languages such as Ruby and Groovy. REST Assured brings the simplicity of using these languages into t…...