哈夫曼树编码的实现+图解(含全部代码)

这篇具有很好参考价值的文章主要介绍了哈夫曼树编码的实现+图解(含全部代码)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录


哈夫曼树的基本概念

------------哈夫曼树的构造方法 

------------------------哈夫曼编码

------------------------------------全部代码 


哈夫曼树的基本概念

        哈夫曼树通常以二叉树的形式出现,所以也称最优二叉树,是一类带权路径长度最短的树

首先得知道下以下几个术语:

        路径:从树中的一个结点到另一个结点之间的分支构成这两点之间的路径

        路径长度:路径上的分支数目称作路径长度

        树的路径长度:从树根到每一个结点的路径长度之和

        :赋予某个实体的一个量

        结点的带权路径长度:从该结点到树根之间的路径长度与结点上权的乘积

        树的带权路径长度:树中所有叶子结点的带权路径长度之和

哈夫曼树编码,acwing,数据结构

哈夫曼树的构造方法 

        哈夫曼树的实现利用了贪心算法的理念,就是先给定的若干结点的权进行分割,让它们变为单个的森林或者说是单个的树,因为树肯定是森林,而后在其中选择两个权值最小的结点生成新的结点,而后删除被选择的结点,让生成的结点参与森林中进行选拔,直至无结点进行选拔。

哈夫曼树编码,acwing,数据结构

哈夫曼树编码,acwing,数据结构哈夫曼树编码,acwing,数据结构

        不好意思结点搞的太多了。。。 每次生成都是到最后的原因是因为后面的代码,不然最后的结果不是一样的,当然哈夫曼树并不唯一,但是为了让最后答案一样,我选择这样画,这个过程也是后面构建哈夫曼树代码的过程,后面代码看不懂的可以结合这个图一起理解。

        接下来就是哈夫曼树的存储结构了,因为每个结点需要权值,孩子结点与双亲结点的地址和结点的数据,所以我们需要用一个结构体来存储。而且这是二叉树的顺序存储。

typedef struct 
{
    char data;             //结点的数据
    int parent,lch,rch;    //双亲结点和孩子结点的下标
    int weight;            //结点的权值
}htNode,*HuffmanTree;

                         哈夫曼树编码,acwing,数据结构

        这个就是这个结构体的内部图,有了存储结构后,我们要做的就是初始化,因为是顺序存储,所以我们要知道给的这些结点构成哈夫曼树需要多少空间,因为我们要节省空间,所以需要用动态分配的方法来解决。

        而我们知道,假设有n个结点构成哈夫曼树则会生成2n-1个结点,这是因为每个结点都会有个双亲,而根结点没有双亲,生成结点和边数相同为n-1,所以为2n-1,而我们在构成哈夫曼树时0下标是不用的,所以我们真正要申请的空间为2n个。

        知道这些后我们就可以来初始化哈夫曼树了,我们在各自输入权值和结点数据后还需把各个结点的孩子与双亲的值置为-1(置为-1的好处就是能当个flag,也就是现在都没有双亲,都是森林,而且在生成的过程中不会出现和它相同的值):以下是初始化的代码

int initHuffmanTree(huffmanTree& HT)
{
	HT = (htNode*)malloc(sizeof(htNode) * (2 * NODENUM));			//给HT分配2 * NODENUM个htNOde大小的htNode类型的数组
	for (int i = 1; i <= 2 * NODENUM - 1; i++)						//下标从1开始到2 * NODENUM
	{
		HT[i].parent = HT[i].lch = HT[i].rch = -1;					//双亲和孩子的值都置为-1
	}
	printf("please input some weight!\n");
	for (int i = 1; i <= NODENUM; i++)								//权值只有1-n个
	{
		scanf("%d",&HT[i].weight);									//给每个结点赋予权值
	}
		char c = getchar();											//这个来接收上面的回车
	printf("please input some data!\n");
	for (int i = 1; i <= NODENUM; i++)
	{
			//scanf("%c ",&HT[i].data);
			char a = getchar();
		if(a == '\n')												//遇到回车就结束
			break;
		else
			HT[i].data = a;											//给每个结点赋予数据
	}
	
	return 1;
}

        哈夫曼树编码,acwing,数据结构

          这是初始化后的结果。初始化完后我们就可以开始构建哈夫曼树啦,构建的思想和刚才那张图一样,就是找到最小的两个结点,然后权值相加,然后最小的两个结点的parent的值为新生成结点的下标,新生成结点的孩子的值为两个最小结点的下标。举个例子你就懂了

          eq:现在最小的为1,4,则它们相加的结果要放在下标为11的位置,并且parent的值改为11,而11的孩子的值为1,2。更新后如下:

哈夫曼树编码,acwing,数据结构

        经过n-1次操作后,最终就成了哈夫曼树 ,下面为最终结果,有颜色的为生成结点部分:

哈夫曼树编码,acwing,数据结构

         可以直观的看到,在最后一个结点,下标为19parent值为-1,所以这个就是根结点,表示没有双亲。

        现在的问题是,我们知道是怎么回事,那怎么用代码来实现它呢

        首先先设置2个变量存储最小值,2个变量存储最小值的下标,因为要生成n-1个结点,所以我们要操作n-1次,且生成一次我们要比较的次数就会增加1,而且不难看出来最后一次不用比较了,所以我们比较的次数要比现总结点数小1,按我们的例子来说,我们要生成19个结点,且比较18次,那我们剩下的工作就是如何找最小值并且生成新的结点,我们的逻辑思维应该是利用4个变量去记住值和下标

        并且只合并parent为-1的结点,parent不为-1的我们就不用再去判断了,代码如下:

#define MAXVALUE 32767	

void creatHuffmanTree(huffmanTree& HT, int n)
{
	if (n <= 1)															//如果结点数小于等于1,不创建
		return;
	int min1, min2;														//定义两个数,来存储每次选取最小两个结点的权值
	int rnode, lnode;													//定义两个下标值,来存储每次选取最小两个结点的下标
	for (int i = n + 1; i <= 2 * n -1; i++)								//要生成n-1个结点,所以要操作n—1次且从下标为n+1开始存储
	{
		int min1 = MAXVALUE; int lnode = -1;							//让最小值初始化为极大值,这样叶子结点的最大值再大也不会超过这个值了							
		int min2 = MAXVALUE; int rnode = -1;
		for (int j = 1; j <= i - 1; j++)								//因为起先是在前n个中选择最小的两个结点的权值,但新生成一个后就得在前n+1个中选择最小的两个结点的权值							
		{																//假设n = 10 总结点数就得为19,那我们就只要比较18次就可以得出结果了,记住比较的次数比生成的总结点数少1
				if (HT[j].weight < min1 && HT[j].parent == -1)			//这个小于就使得当出现相同的权值时优先考虑先出现的值,可以假设下
				{
					min2 = min1;	rnode = lnode;						//碰到比min1小的,那min1的值就给第二小的min2,下标也给它
					min1 = HT[j].weight; lnode = j;						//然后最小的给min1,下标同理
				}
				else if (HT[j].weight < min2 && HT[j].parent == -1)		//这是第二小的判断
				{
					min2 = HT[j].weight;
					rnode = j;
				}
		}
		HT[lnode].parent = HT[rnode].parent = i;						//最小两个结点的parent变为生成结点的下标
		HT[i].lch = lnode; HT[i].rch = rnode;							//生成结点的左孩子为最小的min1的下标,右孩子同理
		HT[i].weight = HT[lnode].weight + HT[rnode].weight;				//生成结点的权值等于最小结点的权值相加
	}
		
}

         在此我给出第一次循环的图示,接下来就是同理了:

哈夫曼树编码,acwing,数据结构

         构成哈夫曼树就在此结束并完成了,而后就是编码。

哈夫曼编码

        哈夫曼编码基于哈夫曼树而产生的一种好编码,具体干嘛的我不说了,百度一下你就知道,因为现在已经很晚了,我想一夜干完,哈哈哈

        上面已经完成哈夫曼树的构成了,那么编码就是左子树上的为0,右子树上的为1,再自根结点扫描下来到叶子结点,输出的值就为哈夫曼编码。

        哈夫曼树编码,acwing,数据结构

        那我们第一步得确定装编码的存储结构,可以从图中看出,需要一个大数组装很多装编码的小数组,那我们就选择指针数组,因为指针变量就类似一个数组,指针数组是装指针的数组,那就符合我们的需求了。

typedef char** huffmanCode;	//第一个*是代表它是指针变量,说明它是数组
							//第二个*说明它是指针数组,代表这个char类型数组里每个元素都是*huffmanCode变量
					

         哈夫曼树编码,acwing,数据结构

        

哈夫曼树编码,acwing,数据结构

         那我们的思路就是搞个临时数组把编码记录下来,然后再给这个大数组里的小数组,那我们怎么求编码呢,这就用到刚才看到那个最后一个结点的parent了,因为它的值是-1,所以它被我们定义为根结点,所以我们只要顺着parent存着的下标一步一步找上去就行了,而后就是左孩子为0,右孩子为1。下面为代码:

void createHuffmanCode(huffmanTree HT, huffmanCode& HC, int n)
{
	HC = (huffmanCode)malloc(sizeof(huffmanCode) * n + 1);				//申请n + 1个huffmanCode大小huffmanCode类型的临时空间
																		//因为下标是从一开始,所以我们要申请比结点多一个的结点,和哈夫曼树的结构对应,方便输出
	char* cd = (char*)malloc(sizeof(char) * n);							//申请n个char大小char类型的临时空间,这个临时数组记录每次遍历出来的编码
	int start = 0,c = 0,f = 0;											//start为cd数组记录下标,c初始为叶子结点下标,而后就是孩子结点的下标,f记录双亲结点的下标
	cd[n - 1] = '\0';													//这个就是给printf留着的,因为printf不会生成'\0',如果用puts就不用这句语句了
	for (int i = 1; i <= n; i++)										//只要叶子结点的编码
	{
		start = n - 1;													//这句要赋值n的话,start--要写在判断后方
		c = i;
		f = HT[c].parent;
		while (f != -1)													//根节点没有双亲
		{
			start--;
			if (HT[f].lch == c)											//是左孩子就是0,右孩子就为1
				cd[start] = '0';
			else
				cd[start] = '1';
			c = f; f = HT[c].parent;									//向根结点接近
		}
		HC[i] = (char*)malloc(sizeof(char) * (n - start));				//给数组里的数组申请n - start个char大小的char*类型的临时空间
		strcpy(HC[i], &cd[start]);										//cd里记录的编码给HC的第i个数组
	}
	free(cd);															//释放临时空间
}

         出一个循环的图,这图画的我累死。

哈夫曼树编码,acwing,数据结构

        全部代码 

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#define MAXVALUE 32767		//极大值相当于无穷大
#define NODENUM 10			//叶子结点数
typedef struct
{
	char data;				//数据域
	int weight;				//结点的权值
	int parent, lch, rch;	//双亲与孩子的下标
}htNode,*huffmanTree;		

typedef char** huffmanCode;	//第一个*是代表它是指针变量,说明它是数组
							//第二个*说明它是指针数组,代表这个char类型数组里每个元素都是*huffmanCode变量

int initHuffmanTree(huffmanTree& HT);								//初始化哈夫曼树
void creatHuffmanTree(huffmanTree& HT, int n);						//构建哈夫曼树
void createHuffmanCode(huffmanTree HT, huffmanCode &HC, int n);		//编写哈夫曼编码
int main()
{
	huffmanTree HT ;
	initHuffmanTree(HT);
	huffmanCode HC;
	creatHuffmanTree(HT,NODENUM);
	createHuffmanCode(HT,HC,NODENUM);
	/*for (int i = NODENUM + 1; i <= 2 * NODENUM - 1; i++)
		printf("%d ", HT[i].weight);*/
	for (int i = 1; i <= NODENUM; i++)								//遍历输出编码
	{
		printf("%c:\t",HT[i].data);
		printf("%s\n", HC[i]);
	}
	return 0;
}
int initHuffmanTree(huffmanTree& HT)
{
	HT = (htNode*)malloc(sizeof(htNode) * (2 * NODENUM));			//给HT分配2 * NODENUM个htNOde大小的htNode类型的数组
	for (int i = 1; i <= 2 * NODENUM - 1; i++)						//下标从1开始到2 * NODENUM
	{
		HT[i].parent = HT[i].lch = HT[i].rch = -1;					//双亲和孩子的值都置为-1
	}
	printf("please input some weight!\n");
	for (int i = 1; i <= NODENUM; i++)								//权值只有1-n个
	{
		scanf("%d",&HT[i].weight);									//给每个结点赋予权值
	}
		char c = getchar();											//这个来接收上面的回车
	printf("please input some data!\n");
	for (int i = 1; i <= NODENUM; i++)
	{
			//scanf("%c ",&HT[i].data);
			char a = getchar();
		if(a == '\n')												//遇到回车就结束
			break;
		else
			HT[i].data = a;											//给每个结点赋予数据
	}
	
	return 1;
}

void creatHuffmanTree(huffmanTree& HT, int n)
{
	if (n <= 1)															//如果结点数小于等于1,不创建
		return;
	int min1, min2;														//定义两个数,来存储每次选取最小两个结点的权值
	int rnode, lnode;													//定义两个下标值,来存储每次选取最小两个结点的下标
	for (int i = n + 1; i <= 2 * n -1; i++)								//要生成n-1个结点,所以要操作n—1次且从下标为n+1开始存储
	{
		int min1 = MAXVALUE; int lnode = -1;							//让最小值初始化为极大值,这样叶子结点的最大值再大也不会超过这个值了							
		int min2 = MAXVALUE; int rnode = -1;
		for (int j = 1; j <= i - 1; j++)								//因为起先是在前n个中选择最小的两个结点的权值,但新生成一个后就得在前n+1个中选择最小的两个结点的权值							
		{																//假设n = 10 总结点数就得为19,那我们就只要比较18次就可以得出结果了,记住比较的次数比生成的总结点数少1
				if (HT[j].weight < min1 && HT[j].parent == -1)			//这个小于就使得当出现相同的权值时优先考虑先出现的值,可以假设下
				{
					min2 = min1;	rnode = lnode;						//碰到比min1小的,那min1的值就给第二小的min2,下标也给它
					min1 = HT[j].weight; lnode = j;						//然后最小的给min1,下标同理
				}
				else if (HT[j].weight < min2 && HT[j].parent == -1)		//这是第二小的判断
				{
					min2 = HT[j].weight;
					rnode = j;
				}
		}
		HT[lnode].parent = HT[rnode].parent = i;						//最小两个结点的parent变为生成结点的下标
		HT[i].lch = lnode; HT[i].rch = rnode;							//生成结点的左孩子为最小的min1的下标,右孩子同理
		HT[i].weight = HT[lnode].weight + HT[rnode].weight;				//生成结点的权值等于最小结点的权值相加
	}
		
}

void createHuffmanCode(huffmanTree HT, huffmanCode& HC, int n)
{
	HC = (huffmanCode)malloc(sizeof(huffmanCode) * n + 1);				//申请n + 1个huffmanCode大小huffmanCode类型的临时空间
																		//因为下标是从一开始,所以我们要申请比结点多一个的结点,和哈夫曼树的结构对应,方便输出
	char* cd = (char*)malloc(sizeof(char) * n);							//申请n个char大小char类型的临时空间,这个临时数组记录每次遍历出来的编码
	int start = 0,c = 0,f = 0;											//start为cd数组记录下标,c初始为叶子结点下标,而后就是孩子结点的下标,f记录双亲结点的下标
	cd[n - 1] = '\0';													//这个就是给printf留着的,因为printf不会生成'\0',如果用puts就不用这句语句了
	for (int i = 1; i <= n; i++)										//只要叶子结点的编码
	{
		start = n - 1;													//这句要赋值n的话,start--要写在判断后方
		c = i;	
		f = HT[c].parent;
		while (f != -1)													//根节点没有双亲
		{
			start--;
			if (HT[f].lch == c)											//是左孩子就是0,右孩子就为1
				cd[start] = '0';
			else
				cd[start] = '1';
			c = f; f = HT[c].parent;									//向根结点接近
		}
		HC[i] = (char*)malloc(sizeof(char) * (n - start));				//给数组里的数组申请n - start个char大小的char*类型的临时空间
		strcpy(HC[i], &cd[start]);										//cd里记录的编码给HC的第i个数组
	}
	free(cd);															//释放临时空间
}

哈夫曼树编码,acwing,数据结构

         还得加紧学习,只能写到这了,有问题的请指出,问问题的可以评论哦,然后我有空再在有问题的地方再讲细点。

        从严老师的教材中学来------------------------------------------------------------------------------------------文章来源地址https://www.toymoban.com/news/detail-777234.html

到了这里,关于哈夫曼树编码的实现+图解(含全部代码)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法】哈夫曼编码(最优二叉树)实现

    哈夫曼编码 等长编码:占的位置一样 变长编码(不等长编码):经常使用的编码比较短,不常用的比较短 最优:总长度最短 最优的要求:占用空间尽可能短,不占用多余空间,且不能有二义性 这里给出哈夫曼二叉树的实现: HuffmanTree.h: 测试数据(主函数): 运行结果截图

    2024年02月16日
    浏览(47)
  • 哈夫曼树与哈夫曼编码及等长编码

    哈夫曼树的构造:就是将给定的数据中选择最小的两个权值进行合并,然后重复该操作,构造出一个 二叉树。使其带权路径长度WPL最小的二叉树称为哈夫曼树或最优二叉树。 例如:给定几个数值:0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.01 可以将其扩大一百倍,以方便计

    2024年02月06日
    浏览(43)
  • 15哈夫曼树/哈夫曼编码

    哈夫曼树又称为 最优树 ,作用是找到一种效率最高的判断树。 路径 :从树中一个结点到另一个结点之间的 分支 构成这两个结点之间的路径。 结点的路径长度 :两结点间路径上的分支树 如图 a :从 A - D 的路径长度就是是 2。从 A 到 B C D E F G F I 的路径长度分别为 1 1 2 2 3

    2024年02月05日
    浏览(45)
  • 哈夫曼树、哈夫曼编码/解码

    哈夫曼树的基本介绍 哈夫曼树构建步骤图解 创建哈夫曼树代码实现 基本介绍 哈夫曼编码原理剖析 哈夫曼编码的实例 思路分析 代码实现 使用哈夫曼编码压缩文件的注意事项(代码胜省略)

    2024年02月08日
    浏览(42)
  • 【数据结构与算法】哈夫曼编码(最优二叉树实现

    哈夫曼编码 等长编码:占的位置一样 变长编码(不等长编码):经常使用的编码比较短,不常用的比较短 最优:总长度最短 最优的要求:占用空间尽可能短,不占用多余空间,且不能有二义性 这里给出哈夫曼二叉树的实现: HuffmanTree.h: 测试数据(主函数): 运行结果截图

    2024年02月16日
    浏览(45)
  • c++利用哈夫曼编码实现文件的压缩加密和解压缩解密

    需求分析 @1:编码实现哈夫曼树,然后根据数据建立哈夫曼树,然后显示所有的字符的哈夫曼编码 @2:实现哈夫曼编码和解码 并通过编码实现文本文件的压缩 通过解码实现压缩文件的解压缩 概要设计 @1:在二叉树的基础上实现哈夫曼树的数据结构 @2:读取文本文件--对字符频

    2024年02月03日
    浏览(43)
  • 哈夫曼树与哈夫曼编码

    哈夫曼树:结点中赋予一个某种意义的值,称为结点的权值,从根结点开始,到目标结点经过的边数,称为路径长度,路径长度乘以权值,称为带权路径长度; 例如:根结点代表着快递集散点,一个叶子结点权值是5,在业务逻辑中代表着重量是5斤的货物📦,路径长度是3,

    2024年02月05日
    浏览(49)
  • 哈夫曼树详解及其应用(哈夫曼编码)

    一,哈夫曼树的基本概念 路径: 从树中一个结点到另一个结点之间的 分支 构成这两个结点间的路径 结点的路径长度 :两结点之间路径上的 分支数 树的路径长度: 从 树根 到每一个结点的 路径长度之和 . 记作:TL 权(weight): 将树中结点赋给一个有着某种含义的数值

    2024年02月04日
    浏览(50)
  • 哈夫曼树、哈夫曼编码和字典树

    目录 哈夫曼树 树的带权路径长度(wpl) 哈夫曼编码 代码实现哈夫曼树 封装哈夫曼树的节点 构建哈夫曼树 字典树 执行流程 代码实现字典树 封装字典树的节点 构建字典树         哈夫曼树(Huffman Tree)是一种带权路径长度最短的二叉树。哈夫曼树常常用于数据压缩,其压

    2023年04月09日
    浏览(51)
  • 哈夫曼树,哈夫曼编码及解码详解

    🌍新人小白的博客 ⌛️希望大家多多关注 🌱一起加油,共同成长 🎃以后会经常更新哒~🙈 ⭐️个人主页: 收藏加关注,永远不迷路~⭐️ 一: 顺序表的操作,你真的学会了吗? 二: 顺序栈的基本操作 三: 循环队列的基本操作,你学会了吗? 四: 单链表的操作(超详细

    2024年02月05日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包