C++哈夫曼树+哈夫曼编码的实现(双完整版)

2024-06-21 17:38

本文主要是介绍C++哈夫曼树+哈夫曼编码的实现(双完整版),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

注释详解哈夫曼Tree和哈夫曼Code

  • 一、哈夫曼Tree
  • 二、哈夫曼Code

  本文是根据B站视频👉青岛大学 - 王卓老师的数据结构来实现的,涉及到哈夫曼Tree 和 哈夫曼Code的C++版完整实现,若有不足欢迎大佬斧正-(/▽\)

一、哈夫曼Tree

  具体理论请配合👉B站视频来学习,构造哈夫曼Tree主要的方法如下:
  第一步:构造森林全是根
  第二步:选用两小造新树
  第三步:删除两小添新人(parent设置为 n+1 到 2n-1 中的下标)
  第四步:重复2、3步剩单根
  话不多说,我们只需要记住这四步,把下面代码的框架敲熟了,就能运用自如了。
  PS:代码有详细注解 和 引导思考,喜欢的话可以收藏一波~

#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;typedef struct HFT
{int weight;int parent, LTree, RTree;
}HFT, *PHFT;void Select(PHFT HFT, int n, int &s1, int &s2)    //选取权值最小的两个结点
{for(int i = 1; i < n; i++){         //初始化s1,s1的双亲为0if(HFT[i].parent == 0){     /**  思考:为什么不是 i <= n  **/s1 = i;					//解答:因为我们第 2n-1  个元素的parent是0break;                          /**  思考:为什么要加上 break  **/}}for(int i = 1; i < n; i++){         //s1为权值最小的下标if(HFT[i].parent == 0 && HFT[s1].weight > HFT[i].weight)s1 = i;}for(int j = 1; j < n; j++){         //初始化s2,s2的双亲为0if(HFT[j].parent == 0 && j != s1){s2 = j;break;}}for(int j = 1; j < n; j++){         //s2为另一个权值最小的下标if(HFT[j].parent == 0 && HFT[s2].weight > HFT[j].weight && j != s1)s2 = j;}
}void initHFT(PHFT &H, int n)
{if(n <= 1) return;int m = 2*n - 1;            //数组共2n - 1个元素H = new HFT[m + 1];	//0号单元未用,H[m]表示根节点for(int i = 1; i <= m; i++){H[i].parent = 0;H[i].LTree = 0;H[i].RTree = 0;}cout << "please input the weight of nodes:" << endl;for(int i = 1; i <= n; i++)cin >> H[i].weight;cout << endl;for(int i = n + 1; i <= m; i++)         //产生的新结点要放在从n+1开始,一直到2n-1的位置{int s1, s2;Select(H, i, s1, s2);H[s1].parent = i;H[s2].parent = i;   //相当于从表F中删除s1, s2H[i].LTree = s1;H[i].RTree = s2;H[i].weight = H[s1].weight + H[s2].weight;}
}void showHFT(PHFT &H, int n)
{cout << "index  weight  parent  LTree  RTree" << endl;cout << left;     //左对齐输出int m = 2*n - 1;for(int i = 1; i <= m; i++){cout << setw(5) << i << "  ";                       /** 思考: 为什么是setw(5) 和 setw(6)   **/cout << setw(6) << H[i].weight << "  ";     // 解答:当后面紧跟着的输出字段长度小于n的时候,在该字段前面用空格补齐;当输出字段长度大于n时,全部整体输出cout << setw(6) << H[i].parent << "  ";cout << setw(6) << H[i].LTree << "  ";cout << setw(6) << H[i].RTree << "  " << endl;}
}int main()
{PHFT HFT;int n = 0;cout << "please input the number of nodes: ";cin >> n;initHFT(HFT, n);showHFT(HFT, n);system("pause");return 0;
}

  我们可以对应下面这张图来看代码,弄懂思路。
在这里插入图片描述
Input
please input the number of nodes: 7
please input the weight of nodes:
7
19
2
6
32
3
21

Output
index weight parent LTree RTree
1  7   0   0   0
2  19  11   0   0
3  2   8   0   0
4  6   9   0   0
5  32  12   0   0
6  3   8   0   0
7  21  12   0   0
8  5   9   3   6
9  11  10   8   4
10  18  11  1   9
11  37  13  10   2
12  53  13  7   5
13  90  0  11   12
  

二、哈夫曼Code

  该代码在实现哈夫曼编码核心算法时既使用了C++的string类来实现,也使用了C的方式实现。这是在学会构造哈夫曼树之后的进一步提升,在这里给需要提高的同学抛出一个思考问题,“C++如何处理模板类template实现自动根据用户输入的 weight 值类型来分配内存”。
在这里插入图片描述
  首先先看图,根据图来实现以下步骤(用char动态数组):
  第一步:构建哈夫曼树表、HC表(动态二维数组)、cd表(一维)
  第二步:一般规定左子树路径为0,右子树路径为1,按哈夫曼树表寻找parent结点直到为0。
  与第二步同时进行:先将临时cd表最后一个元素定为’\0’,创建临时结点记录当前处理的结点。
  第三步:将cd表值赋值给HC表,同时销毁cd表的临时内存。

在这里插入代码片```cpp
#include <iostream>
#include <string.h>
#include <iomanip>
#include <stack>
#include <algorithm>using namespace std;typedef struct HFT
{float weight;int parent, LTree, RTree;string name;
}HFT, *PHFT;void Select(const PHFT& H, const int& n, int& s1, int& s2){for(int i = 1; i < n; i++){if(H[i].parent == 0){s1 = i;break;}}for(int i = 1; i < n; i++){if(H[i].parent == 0 && H[s1].weight > H[i].weight)s1 = i;}for(int j = 1; j < n; j++){if(H[j].parent == 0 && j != s1){s2 = j;break;}}for(int j = 1; j < n; j++){if(H[j].parent == 0 && H[s2].weight > H[j].weight && j != s1)s2 = j;}
}void initHFC(PHFT& HT, const int& n)
{if(n <= 1) return;int m = 2*n - 1;HT = new HFT[m + 1];for(int i = 1; i <= m; i++){HT[i].parent = 0;HT[i].LTree = 0;HT[i].RTree = 0;}cout << "please input the weight of nodes and nodes' name as 0.23 A: " << endl;for(int i = 1; i <= n; i++){cin >> HT[i].weight >> HT[i].name;}cout << endl;for(int i = n+1; i <= m; i++){int s1, s2;Select(HT, i, s1, s2);HT[s1].parent = i;HT[s2].parent = i;HT[i].LTree = s1;HT[i].RTree = s2;HT[i].weight = HT[s1].weight + HT[s2].weight;}
}/**      char 类型解决方案   */
void ch_CreateHFMcode(const PHFT& HT, char** HC, const int& n)
{char* temp = new char[n];temp[n-1] = '\0';int  start = 0, c = 0, father = 0;for(int i = 1; i <= n; i++){start = n - 1;c = i;                      //记录正在处理的当前位置father = HT[i].parent;while(father != 0)   //从叶子节点向上回溯{                //回溯一次 start指向前一个位置一个if(HT[father].LTree == c) temp[--start] = '0';else temp[--start] = '1';c = father;             //当前位置移到父节点father = HT[father].parent;    //更新父节点,继续向上回溯}HC[i] = new char[n-start];            // 为第 i 个字符串编码分配空间strcpy(HC[i], &temp[start]);             // 将求得的编码从临时空间cd复制到HC的当前行中,strcpy遇到 \0 拷贝就会结束}delete temp;
}/**   string 类型的解决方案   **/
void str_CreateHFMcode(PHFT& H, string *HC, const int& n)
{string temp;stack<string> st;		//利用栈实现上一个char类型strcpy的方法int cur = 0, father = 0;for(int i = 1; i <= n; i++){cur = i;father = H[i].parent;while(father != 0){if(H[father].LTree == cur) st.push("0");else st.push("1");cur = father;father = H[father].parent;}while(!st.empty()){temp += st.top();st.pop();}HC[i] = temp;temp.erase();	//擦除内存}
}void showdata(const PHFT& HFT, char** HC, const int& n){cout << "index  weight  parent  LTree  RTree" << endl;cout << left;int m = 2*n - 1;for(int i = 1; i <= m; i++){cout << setw(5) << i << "  ";cout << setw(6) << HFT[i].weight << "  ";cout << setw(6) << HFT[i].parent << "  ";cout << setw(6) << HFT[i].LTree << "  ";cout << setw(6) << HFT[i].RTree << "  " << endl;}cout << endl;cout << "Name  HFMCode" << endl;for(int i = 1; i <= n; i++){cout << setw(5) << HFT[i].name << "  ";cout << setw(7) << HC[i] << "  " << endl;}
}int main()
{PHFT HFT;int n = 0;cout << "please intput the number of vertices: ";cin >> n;char** HC = new char*[n];initHFC(HFT, n);ch_CreateHFMcode(HFT, HC, n);showdata(HFT, HC, n);return 0;
}

Input
please intput the number of vertice: 7
what value do you want to give them?
0.4
0.3
0.15
0.05
0.04
0.03
0.03

Output
index HC[i]
1  0
2  10
3  110
4  11111
5  11110
6  11100
7  11101
  
路曼曼其修远兮,吾将上下而求索

这篇关于C++哈夫曼树+哈夫曼编码的实现(双完整版)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1081891

相关文章

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片,默认是输出到项目文件夹中,可以自己选择其他的文件夹,选择需要拆分的行数和列数,可以通过

Python中将嵌套列表扁平化的多种实现方法

《Python中将嵌套列表扁平化的多种实现方法》在Python编程中,我们常常会遇到需要将嵌套列表(即列表中包含列表)转换为一个一维的扁平列表的需求,本文将给大家介绍了多种实现这一目标的方法,需要的朋... 目录python中将嵌套列表扁平化的方法技术背景实现步骤1. 使用嵌套列表推导式2. 使用itert

Python使用pip工具实现包自动更新的多种方法

《Python使用pip工具实现包自动更新的多种方法》本文深入探讨了使用Python的pip工具实现包自动更新的各种方法和技术,我们将从基础概念开始,逐步介绍手动更新方法、自动化脚本编写、结合CI/C... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

在Linux中改变echo输出颜色的实现方法

《在Linux中改变echo输出颜色的实现方法》在Linux系统的命令行环境下,为了使输出信息更加清晰、突出,便于用户快速识别和区分不同类型的信息,常常需要改变echo命令的输出颜色,所以本文给大家介... 目python录在linux中改变echo输出颜色的方法技术背景实现步骤使用ANSI转义码使用tpu

Python使用python-can实现合并BLF文件

《Python使用python-can实现合并BLF文件》python-can库是Python生态中专注于CAN总线通信与数据处理的强大工具,本文将使用python-can为BLF文件合并提供高效灵活... 目录一、python-can 库:CAN 数据处理的利器二、BLF 文件合并核心代码解析1. 基础合

Python使用OpenCV实现获取视频时长的小工具

《Python使用OpenCV实现获取视频时长的小工具》在处理视频数据时,获取视频的时长是一项常见且基础的需求,本文将详细介绍如何使用Python和OpenCV获取视频时长,并对每一行代码进行深入解析... 目录一、代码实现二、代码解析1. 导入 OpenCV 库2. 定义获取视频时长的函数3. 打开视频文

golang版本升级如何实现

《golang版本升级如何实现》:本文主要介绍golang版本升级如何实现问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录golanwww.chinasem.cng版本升级linux上golang版本升级删除golang旧版本安装golang最新版本总结gola

SpringBoot中SM2公钥加密、私钥解密的实现示例详解

《SpringBoot中SM2公钥加密、私钥解密的实现示例详解》本文介绍了如何在SpringBoot项目中实现SM2公钥加密和私钥解密的功能,通过使用Hutool库和BouncyCastle依赖,简化... 目录一、前言1、加密信息(示例)2、加密结果(示例)二、实现代码1、yml文件配置2、创建SM2工具

Mysql实现范围分区表(新增、删除、重组、查看)

《Mysql实现范围分区表(新增、删除、重组、查看)》MySQL分区表的四种类型(范围、哈希、列表、键值),主要介绍了范围分区的创建、查询、添加、删除及重组织操作,具有一定的参考价值,感兴趣的可以了解... 目录一、mysql分区表分类二、范围分区(Range Partitioning1、新建分区表:2、分

MySQL 定时新增分区的实现示例

《MySQL定时新增分区的实现示例》本文主要介绍了通过存储过程和定时任务实现MySQL分区的自动创建,解决大数据量下手动维护的繁琐问题,具有一定的参考价值,感兴趣的可以了解一下... mysql创建好分区之后,有时候会需要自动创建分区。比如,一些表数据量非常大,有些数据是热点数据,按照日期分区MululbU