C语言实现哈夫曼树的方法
本文实例为大家分享了C语言实现哈夫曼树的具体代码,供大家参考,具体内容如下
准备工作:
1、定义一个结构体,表示一个节点。其中,这个结构体有4个成员变量,分别表示是这个节点的权值,父节点及左右子节点的下标
2、定义一个整形数组,用于存放各个节点的权值
3、定义一个整形数组,用于存放哈夫曼编码,当然也可以定义一个整形数组来存放哈夫曼编码
构建哈夫曼树:
1、给这个哈夫曼树创建一个结构体数组,其中分配的空间是2 * n - 1,因为我们都知道哈夫曼树的性质有一个是:给定n个叶子节点,那么由这n个叶子节点构成 的哈夫曼树一共含有2 * n - 1个节点。
2、结构体数组前面n个用于存放n个叶子节点,然后后面的n - 1个节点用于存放父节点。这时候,我们需要遍历这个结构体数组,将所有的节点的进行初始化,即节点的权值就是结构体数组各个下标对应的值,然后节点的父节点及子节点的下标为-1,表示的是这个节点没有父节点,同时也没有子节点。
3、遍历数组,将获取数组中两个最小的叶子节点,然后将他们的权值合并构成一个新节点。在这一步中,我们同时需要知道这两个最小节点在结构体数组中的下标,只有这样,我们才可以知道它的父节点的左右子节点的下标,在初始化父节点的时候需要用到。
4、如果已经进行了n - 1次数操作,表明已经构建完成了。
获取哈夫曼编码:
1、由于我们将所有节点的权值都赋值给了一个数组,并且哈夫曼树中的节点的下标和这个数组的下标是一一对应的,那么我们只需要首先在数组中获取这个数字的下标,就表示他在哈夫满树中的下标也是这个,然后往它的父节点方向走,如果当前节点时它父节点的右子节点,那么就将1存放到数组arr2中,否则字符将0存放到数组arr2中。重复这一步,直到当前的节点的父节点为空,及已经遍历到了根节点。
2、重复步骤一,存放数字的数组已经遍历完了,这时候已经将所有数字的哈夫曼编码都已经输出了
#include<stdio.h> #define MAX_SIZE 1000 typedef struct NODE Node; struct NODE{ int weight;//节点的权值 int parent,lchild,rchild; }; /* 初始化或者更改节点的信息,比如,如果这个节点是一个新节点,那么 就需要将这个节点初始化成一个叶子节点,否则需要修改这个节点的父节点 */ void initNode(Node &node,int weight,int parent,int lchild,int rchild){ node.weight = weight; node.lchild = lchild; node.rchild = rchild; node.parent = parent; } /* 1、有n个叶子节点,那么构建哈夫曼树的时候,需要分配n * 2 - 1个内存空间,前n 个表示的是新输入的叶子节点,后面n - 1表示的是叶子节点的父节点 2、遍历这个数组,将进行初始化,即给这些节点的权值赋值,并且将他的左右子节 点、父节点赋初始值为-1,从而构建了n个叶子节点 3、遍历数组,从而将从这个数组中跳出两个值最小的叶子节点,同时需要标记他们的下标,从而可以知道当前最小值节点的父节点的左右子节点的下标,方便下次寻找 最小值的叶子结点的时候不会再找到已经找过的叶子节点 4、将新节点插入到数组的最后。 5、重复3,4的操作,直到只有一个节点,那么这个节点就是哈夫曼树的根节点 */ void createHuffmanTree(Node *node,int *arr,int n){ //n表示有n个叶子节点,arr数组存放的是所有叶子节点的值 int i,j,min1,min2,x1,x2,total;//min1:第一个最小值,min2:第二个最小值,x1:第一个最小值的下标,x2:第二个最小值的下标 for(i = 0; i < n; i++){ initNode(node[i],arr[i],-1,-1,-1);//调用initNode方法,从而将节点进行初始化 } total = n * 2 - 1;//total表示的是哈夫曼所有节点的个数 for(i = n; i < total; i++){ //i之所以从n开始,是因为第一个父节点这个下标(前n个节点是叶子节点) min1 = 65432;//定义两个最小值 min2 = min1; x1 = x2 = 0;//假设两个最小值的下标都是0 for(j = 0; j < i; j++){ //判断当前下标的节点是否为叶子节点 if(node[j].parent == -1){ //如果当前节点的parent等于-1,表示这个节点是一个叶子节点,那么我们需要判断他是否一个最小节点 if(node[j].weight < min1){ //如果当前这个节点的值比min1小,那么我们需要更新min2,min1,同时需要更新两者对应的下标 min2 = min1; x2 = x1; min1 = node[j].weight; x1 = j; }else if(node[j].weight < min2){ /* 如果当前这个节点比第一个最小值要大,那么我们需要判断 他是否比第二个最小值小,如果是,那么更新min2,并且更新x2 */ min2 = node[j].weight; x2 = j; } } } /* 找到两个最小节点之后,我们需要将这两个节点的父节点指向i, 然后将i这个节点进行初始化,并且新节点的左子节点比右子节点小 从而构建唯一的哈夫曼树 */ node[x1].parent = i; node[x2].parent = i; initNode(node[i],min1 + min2,-1,x1,x2);//初始化合并之后的新节点 } } void huffmanCode(Node *node,int child,int *str){ //str表示的是这个叶子节点的哈夫曼编码 int i,parent,j = 0,e; parent = node[child].parent;//获取当前这个叶子节点的父节点 while(parent != -1){ if(node[parent].lchild == child){ //如果当前这个节点是父节点的左子节点,那么就将0压入到数组中,否则将1压入数组中 str[j++] = 0; }else{ str[j++] = 1; } child = parent; parent = node[child].parent; } e = j;//当退出循环的时候,j表示的是这个数的哈夫曼编码的长度,所以需要从下标为j - 1开始逆序输出,才是这个数的哈夫曼编码 for(j = e - 1; j>= 0; j--) printf("%d",str[j]); printf("\n"); } int main(){ Node node[MAX_SIZE]; int arr[MAX_SIZE];//定义一个整形数组,用于存放所有叶子节点的权值 int arr2[MAX_SIZE];//arr2用于存放一个数字的哈夫曼编码 int n,i,j,e; printf("请输入叶子节点的个数:"); scanf("%d",&n); for(i = 0; i < n; i++) scanf("%d",&arr[i]); createHuffmanTree(node,arr,n);//构建哈夫曼树 /* 获取哈夫曼编码: 1、将遍历数组arr,从而获得各个叶子节点的权值以及下标 2、通过这个下标,我们从这个节点向根节点走去,如果当前节点是父节点的左子 节点,那么将0压入到数组中,否则将1压入到数组arr2中 3、逆序输出arr2 */ for(i = 0; i < n; i++){ huffmanCode(node,i,arr2);//调用这个方法,将当前下标对应的数字的哈夫曼编码输出 } return 0; }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持猪先飞。
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中查找字符在字符串中出现的位置的方法,分别是strchr()函数和strrchr()函数的使用,需要的朋友可以参考下...2020-04-25
- 很多同学在学习c语言的时候是不是会碰到a++和++a都有甚么作用啊。今天我们就来探讨下...2020-04-25
- 这篇文章主要对C语言中const关键字的用法进行了详细的分析介绍,需要的朋友可以参考下...2020-04-25
- 下面小编就为大家带来一篇C语言实现时间戳转日期的算法(推荐)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25
- 文中详细讲了关于Java哈夫曼树的概述以及用Java实现的方法,对各位正在学习java数据结构的小伙伴们有很大的帮助哟,需要的朋友可以参考下...2021-05-14
- 这篇文章主要介绍了C语言之整数划分问题(递归法)实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 本文给大家简单介绍下c实现linux下的数据库备份的方法和具体的源码,十分的实用,有需要的小伙伴可以参考下。...2020-04-25
C语言正则表达式详解 regcomp() regexec() regfree()用法详解
C语言处理正则表达式常用的函数有regcomp()、regexec()、regfree()和regerror(),这里就为大家介绍一下,需要的朋友可以参考一下啊...2020-04-25