c语言哈夫曼编码贪心,[C++]哈夫曼树(最优满二叉树) / 哈夫曼编码(贪心算法)

迷南。 2023-01-22 15:51 13阅读 0赞

一 哈夫曼树

1.1 基本概念

算法思想

贪心算法(以局部最优，谋求全局最优)

适用范围

1 【(约束)可行】：它必须满足问题的约束

2 【局部最优】它是当前步骤中所有可行选择中最佳的局部选择

3 【不可取消】选择一旦做出，在算法的后面步骤中，就无法再改变。

示例

【树论：最优(二叉)数=带权路径最短的树】

【图论：单源最短路径=从某一结点出发至其他结点的带权路径之和最小 / 多源最短路径=某一对结点之间的带权路径之和最小】

定义

哈夫曼树 = 最优((满)二叉)树 = 带权路径之和最短的树

哈夫曼树所产生的哈夫曼编码 = (最优)前缀编码

一种最基本的、数据压缩的编码方法

![524bca63dc91a47d74e074cf7e307d1d.png][]

1.2 算法描述/构造过程

![0655fe258bb0f455364eb45e568eb888.png][]

1.3 算法实现

![9db2d768389c5e335f857005bd1eefbe.png][]

1> 定义存储结构

\# define MAXNEGATIVE -9999 //最大负值

\# define MAXPOSITIVE 9999 //最大正值

typedef struct HuffmanNode\{ // 加 typedef : 避免发生编译错误 " variable or field 'functionName' declared void "

double weight;

int parent, lchild, rchild; //当前节点的双亲结点、左右孩子结点

\}\*HuffmanTree;

2> 确定最小的两个结点的选择策略(贪婪策略)【次核心】

/\*\*

\* 选择权值结点最小的两个结点 s1、s2

\*/

void Select(HuffmanTree &HT,int k,int \*s1,int \*s2)\{

int min\[2\]=\{0, 0\}; // 升序排名， 保留 HT中 权重值最小的两个结点的下标

cout<

HT\[0\].weight = MAXPOSITIVE; // 初始化为最大正值，方便被 初始结点比最小而比下去

for(int i=1;i<=k;i++)\{

//cout<

if( HT\[i\].parent==0 && (HT\[i\].weight

if(HT\[i\].weight

min\[1\] = min\[0\]; min\[0\] = i; cout<

\} else \{

min\[1\] = i;cout<

\*s1 = min\[0\]; // 最小者下标

\*s2 = min\[1\]; // 次小者下标

//cout<

3> 创建 Huffman 树【核心】

/\*\*

\* 创建 Huffman 树

\* n : 初试结点(待编码结点)数

\*/

void CreateHuffmanTree(HuffmanTree &HT, int n)\{

int m = 2\*n-1;

HT = new HuffmanNode\[m+1\]; // 0 位空余

cout<

for(int i=1;i<=n;i++)\{

cin>>HT\[i\].weight;

for(int k=1;k<=m;k++)\{ // 初始化所有结点

HT\[k\].lchild = 0;

HT\[k\].rchild = 0;

HT\[k\].parent = 0;

for(int j=n+1;j<=m;j++)\{

int s1,s2;

Select(HT, j-1, &s1, &s2); // 选择权值结点最小的两个结点s1、s2

HT\[s1\].parent = j; // 合并左右结点

HT\[s2\].parent = j;

HT\[j\].lchild = s1;

HT\[j\].rchild = s2;

HT\[j\].weight = HT\[s1\].weight + HT\[s2\].weight;

4> 输出哈夫曼树

void OutputHuffmanTree(HuffmanTree &HT, int n)\{ // 输出 哈夫曼树 中 结点情况

int m = 2\*n-1;

for(int i=1;i<=m;i++)\{

cout< weight: "<

cout<

5> 执行：Main函数

int main()\{

HuffmanTree HT;

int n;

cout<

int s1, s2;

cin>>n;

CreateHuffmanTree(HT, n);

OutputHuffmanTree(HT, n);

return 0;

![a08c850679debc542c625a475cf1cce5.png][]

二 哈夫曼编码

2.1 哈夫曼编码的主要思想

![28eb210b91499c9527cedc52ca8c4d3b.png][]

2.2 【前缀编码】

![45dfada1f84a6cd7899af1e85e485b7d.png][]

2.3 【哈夫曼编码】

![e4f5eafb847403dde6155b9145bb47e2.png][]

2.4 应用：文件的编码与译码

![093c3b52bd31fa65a22473758143a528.png][]

2.5 哈夫曼编码的算法实现 (根据哈夫曼树，求哈夫曼编码)

![0edf8f9b9cf3f1741021ed56a0f3870c.png][]

1> 定义存储结构

//由于 每个哈夫曼编码是变长编码；因此，使用指针数组来存储每个字符编码串的首地址

typedef char \*\*HuffmanCode; // 动态分配数组，存储哈夫曼编码表 (char 前面不能随意加 struct 关键字)

2> 生成哈夫曼编码(表)(借助于哈夫曼树)

/\*\*

\* 根据哈夫曼树，求哈夫曼编码

\*/

void CreateHuffmanCodeByHuffmanTree(HuffmanTree HT, HuffmanCode &HC,int n)\{//从叶子到根，逆向求每个字符的哈夫曼编码

HC = new char \*\[n+1\]; // 分配存储n个字符编码的编码表空间

char \*cd = new char \[n\]; // 分配临时存放每个字符编码的动态数组空间

cd\[n-1\] = '\\0'; // 编码结束符

for(int i=1;i<=n;i++)\{ // 逐个字符求哈夫曼编码

int start = n-1; // start 初始化指向最后位置 即 编码结束符位置，逆向存储 从叶子到根结点路径的0/1编码

int c = i;

int f = HT\[i\].parent; // f 指向结点C 的双亲结点

while(f!=0)\{ // 直到 f 滑动到根节点为止

\--start; // 编码表游标向前滑动

if(HT\[f\].lchild == c)\{

cd\[start\] = '0';

\} else \{

cd\[start\]= '1';

c = f;

f = HT\[f\].parent; // 逆向， 自(树)底向(树)上

HC\[i\] = new char \[n-start\]; //为第i个字符编码分配存储空间

strcpy(HC\[i\], &cd\[start\]); // 头文件： \#include 、

delete cd;

3> 输出哈夫曼编码(表)

void OutputHuffmanCodes(HuffmanCode &HC,int n)\{

for(int i=1;i<=n;i++)\{

cout<

for(int j=0,size=sizeof(HC\[i\])/sizeof(char);j

cout<

4> 执行：Main函数

int main()\{

HuffmanTree HT;

int n;

cout<

int s1, s2;

cin>>n;

CreateHuffmanTree(HT, n);

OutputHuffmanTree(HT, n);

HuffmanCode HC;

CreateHuffmanCodeByHuffmanTree(HT, HC, n);

OutputHuffmanCodes(HC, n);

return 0;

![aca057db86b8cc058c6b61d17e348020.png][]

三 哈夫曼译(解)码

四 文献

4.1 参考文献

《数据结构(C语言版)：严蔚敏/吴伟民》

《算法设计与分析基础(\[美\] Anany Levitin. 潘彦 译)》

贪心算法思想的适用范围

4.2 推荐文献

五 二叉树 补充：红黑树

![5bc58fd4af294d20c3d088a0197e7ed0.png][]

树形结构&lowbar;红黑树&colon;平衡2X 哈夫曼树&colon;最优2X

红黑树:平衡2X 哈夫曼树:最优2X 红黑树 :TreeSet.TreeMap 哈夫曼树 1. 将w1.w2.…,wn看成是有n 棵树的森林(每棵树仅有一个结点): 2. 在森林中选出根结点的权值最小 ...

采用C&plus;&plus;实现哈夫曼树的创建并输出哈夫曼编码

一.这篇随笔来自一道信息论的作业题,因为手动编码过于复杂,所以想到了编程解决,原题目如下图所示: 二.源代码如下: \#include \#include

【algo&amp&semi;ds】【吐血整理】4&period;树和二叉树、完全二叉树、满二叉树、二叉查找树、平衡二叉树、堆、哈夫曼树、B树、字典树、红黑树、跳表、散列表

本博客内容耗时4天整理,如果需要转载,请注明出处,谢谢. 1.树 1.1树的定义 在计算机科学中,树(英语:tree)是一种抽象数据类型(ADT)或是实作这种抽象数据类型的数据结构,用来模拟具有树状结 ...

哈夫曼树——c&plus;&plus;

哈夫曼树的介绍 Huffman Tree,中文名是哈夫曼树或霍夫曼树,它是最优二叉树. 定义:给定n个权值作为n个叶子结点,构造一棵二叉树,若树的带权路径长度达到最小,则这棵树被称为哈夫曼树. 这个定 ...

数据结构-哈夫曼树(python实现)

好,前面我们介绍了一般二叉树.完全二叉树.满二叉树,这篇文章呢,我们要介绍的是哈夫曼树. 哈夫曼树也叫最优二叉树,与哈夫曼树相关的概念还有哈夫曼编码,这两者其实是相同的.哈夫曼编码是哈夫曼在1952年 ...

数据结构之C语言实现哈夫曼树

1.基本概念 a.路径和路径长度 若在一棵树中存在着一个结点序列 k1,k2,……,kj, 使得 ki是ki+1 的双亲(1<=i

C&plus;&plus;哈夫曼树编码和译码的实现

一．背景介绍: 给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree).哈夫曼树是带权路径长度最短的树,权值较大的 ...

哈夫曼树&lpar;三&rpar;之 Java详解

前面分别通过C和C++实现了哈夫曼树,本章给出哈夫曼树的java版本. 目录 1. 哈夫曼树的介绍 2. 哈夫曼树的图文解析 3. 哈夫曼树的基本操作 4. 哈夫曼树的完整源码 转载请注明出处:htt ...

哈夫曼树&lpar;二&rpar;之 C&plus;&plus;详解

上一章介绍了哈夫曼树的基本概念,并通过C语言实现了哈夫曼树.本章是哈夫曼树的C++实现. 目录 1. 哈夫曼树的介绍 2. 哈夫曼树的图文解析 3. 哈夫曼树的基本操作 4. 哈夫曼树的完整源码 转载 ...

随机推荐

K-均值聚类算法

K-均值聚类算法 聚类是一种无监督的学习算法,它将相似的数据归纳到同一簇中.K-均值是因为它可以按照k个不同的簇来分类,并且不同的簇中心采用簇中所含的均值计算而成. K-均值算法 算法思想 K-均值是 ...

curl毫秒超时使用的坑

升级后的libcurl已经支持了毫米级别的超时.但是使用的时候还有一个坑需要注意跨过去 . libcurl如果检查到设置的timeout < 1s 那么会直接发出一个信号说 "已经超时 ...

hdu 5673 Robot 卡特兰数&plus;逆元

Robot Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Problem D ...

js中给函数传参函数时，函数加括号与不加括号的区别

模式识别与机器学习—bagging与boosting

声明:本文用到的代码均来自于PRTools(http://www.prtools.org)模式识别工具箱,并以matlab软件进行实验. (1)在介绍Bagging和Boosting算法之前,首先要简 ...

32位汇编第三讲&comma;RadAsm&comma;IDE的配置和使用&comma;以及汇编代码注入方式

32位汇编第三讲,RadAsm,IDE的配置和使用,以及汇编代码注入方式 一丶RadAsm的配置和使用 用了怎么长时间的命令行方式,我们发现了几个问题 1.没有代码提醒功能 2.编写代码很慢,记不住各 ...

Eclipse配置tomcat程序发布到哪里去了？

今天帮同事调一个问题,明明可以main函数执行的,他非要固执的使用tomcat执行,依他.但是发布到tomcat之后我想去看看发布后的目录,所以就打开了tomcat中的webapps目录,可是并没有发 ...

django项目实现中文检索

在settings.py中设置 EMAIL\_USE\_SSL = True EMAIL\_HOST = 'smtp.qq.com'  \# 如果是 163 改成 smtp.163.com EMAIL\_POR ...

PHP随机浮点数

function randomFloat($min = 0, $max = 1) \{ $rand = mt\_rand(); $lmax = mt\_getrandmax(); return $min + ...

shell 提取mysql指定数据库下表创建语句为单文件

dbcn="mysql -h172.16.1.194 -uroot -p123456"; db=dsp\_ad\_center; ii=0; ct=\`$dbcn -N -e &quot ...

[524bca63dc91a47d74e074cf7e307d1d.png]: /images/20221020/120eb30815f9479187950aa5eef7ec9c.png
[0655fe258bb0f455364eb45e568eb888.png]: /images/20221020/c2e78d4ba7ae41d98e7e4f24303f8cc0.png
[9db2d768389c5e335f857005bd1eefbe.png]: /images/20221020/512e8b2fb0bf4064b4b1ea13f9de30b7.png
[a08c850679debc542c625a475cf1cce5.png]: /images/20221020/69637b0f7d474ca784ebb7a8af6fe45a.png
[28eb210b91499c9527cedc52ca8c4d3b.png]: /images/20221020/921d9f542fdc48eabcdb80a8214b6e9d.png
[45dfada1f84a6cd7899af1e85e485b7d.png]: /images/20221020/9573aa058aba4bfdb01c2d454155f4ce.png
[e4f5eafb847403dde6155b9145bb47e2.png]: /images/20221020/bcb01c5a1a374538a4ff02f50ca9c987.png
[093c3b52bd31fa65a22473758143a528.png]: /images/20221020/a71fcd607c09472597383302162b1412.png
[0edf8f9b9cf3f1741021ed56a0f3870c.png]: /images/20221020/394f4a383ca342e8b93c6b0796b76828.png
[aca057db86b8cc058c6b61d17e348020.png]: /images/20221020/8d732ee951c04d1189d9156f1d96525c.png
[5bc58fd4af294d20c3d088a0197e7ed0.png]: /images/20221020/b1e9370ad37a49d1a323ed98d8e77991.png