精华内容
下载资源
问答
  • 哈夫曼树的构建及哈夫曼树编码
    千次阅读
    2021-02-26 13:53:50

    实验题:构造哈夫曼树生成哈夫曼编码
    编写一个程序,构造一棵哈夫曼树,输出对应的哈夫曼编码和平均查找长度,并对下表(所示的数据进行验证。

    单词及出现的频度
    单词: The of a to and in that he is at on for His are be
    频度 :1192 677 541 518 462 450 242 195 190 181 174 157 138 124 123

    #include <iostream>
    #define N 50
    #define M 2*N-1
    using namespace std;
    //哈夫曼树结点定义
    typedef struct
    {
        string data;
        double weight;
        int parent;
        int lchild;
        int rchild;
    }HTNode;
    //哈夫曼编码结点定义
    typedef struct
    {
        char cd[N];
        int start;
    }HCode;
    //创建哈夫曼树
    void CreateHT(HTNode ht[], int n)
    {
        int i, k, lnode, rnode;
        double min1, min2;//min1用于记录较小的那个结点,min2记录较大的那个
        for (i = 0; i < 2 * n - 1; i++)//初始化结点
        {
            ht[i].parent = ht[i].lchild = ht[i].rchild = -1;
        }
        for (i = n; i < 2 * n - 1; i++)//开始构造哈夫曼树
        {
            min1 = min2 = INT_MAX;
            lnode = rnode = -1;//记录可用的最小的两个结点的位置
            for (k = 0; k <= i - 1; k++)//随着过程的进行,会加入两个选用结点构成的新结点,所以判断条件为k<=i-1
            {
                if (ht[k].parent == -1)//可用结点
                {
                    if (ht[k].weight < min1)//比最小的那个结点更小
                    {
                        min2 = min1; rnode = lnode;//将较大结点换为较小结点
                        min1 = ht[k].weight; lnode = k;//较小结点更新
                    }
                    else if (ht[k].weight < min2)//只比较大结点小
                    {
                        min2 = ht[k].weight; rnode = k;//较大结点更新
                    }
                }
            }
            ht[i].weight = ht[lnode].weight + ht[rnode].weight;//产生新节点
            ht[i].lchild = lnode; ht[i].rchild = rnode;//记录新节点的孩子结点
            ht[lnode].parent = i; ht[rnode].parent = i;//记录孩子结点的父亲
        }
    }
    //求哈夫曼编码
    void CreateHCode(HTNode ht[], HCode hcd[], int n)
    {
        int i, f, c;
        HCode hc;
        for (i = 0; i < n; i++)
        {
            hc.start = n; c = i;//从该节点倒着回到根结点,编码长度最大也不会超过n
            f = ht[i].parent;
            while (f != -1)//未回到根结点
            {
                if (ht[f].lchild == c)
                    hc.cd[hc.start--] = '0';
                else
                    hc.cd[hc.start--] = '1';
                c = f; f = ht[f].parent;
            }
            hc.start++;
            hcd[i] = hc;
        }
    }
    //输出哈夫曼编码并求其平均查找长度
    void DispHCode(HTNode ht[], HCode hcd[], int n)
    {
        int i, k;
        int sum = 0, m = 0, j;//sum存储树的带权路径长度,m存储权和,j存储路径长度
        cout << "输出哈夫曼编码:" << endl; //输出哈夫曼编码
        for (i = 0; i < n; i++)
        {
            j = 0;
            cout << ht[i].data << '\t';
            for (k = hcd[i].start; k <= n; k++)//输出哈夫曼编码
            {
                cout << hcd[i].cd[k];
                j++;//路径长度+1
            }
            m += ht[i].weight;
            sum += ht[i].weight * j;
            cout << endl;
        }
        cout << "平均长度=";
        cout << 1.0 * sum / m;
    }
    int main()
    {
        int n = 15, i;
        string str[] = { "The","of","a","to","and","in","that","he","is","at","on","for","His","are","be" };
        int fnum[] = { 1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123 };
        HTNode ht[M];
        HCode hcd[N];
        for (i = 0; i < n; i++)
        {
            ht[i].data = str[i];
            ht[i].weight = fnum[i];
        }
        CreateHT(ht, n);//创建哈夫曼树
        CreateHCode(ht, hcd, n);//求得哈夫曼编码
        DispHCode(ht, hcd, n);//输出哈夫曼编码和平均查找长度
        return 0;
    }
    

    运行结果:
    在这里插入图片描述
    如果本文对你有帮助的话,请👍哦(●ˇ∀ˇ●)

    更多相关内容
  • 利用已建好的哈夫曼树(如不在内存,则从文件hfmTree中读人),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。 (3)D: 译码(Decoding)。利用已建好的哈夫曼树将文件 CodeFile 中的代码进行译码,结果...
  • 第2关根据哈夫曼树构建哈夫曼编码 通过哈夫曼树的构造,深刻理解二叉树的构造。 通过哈夫曼编/译码过程,深刻领会二叉树的基本操作和二叉树的应用,熟练掌握二叉数组织数据的基本原理和对二叉树操作的实现方法。 ...
  • 主要为大家详细介绍了C语言实现哈夫曼树构建,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 秉着能不写就不写的理念,关于哈夫曼树的原理及其构建,还是贴一篇博客吧。 https://www.jb51.net/article/97396.htm 其大概流程 哈夫曼编码代码 # 树节点类构建 class TreeNode(object): def __init__(self, ...
  • 带权路径长度最小的二叉树1,权值越大的叶子结点越靠近根结点,而权值越小的叶子结点越远离根结点2,只有度为0(叶子结点)和度为2(分支结点)的结点,不存在度为1的结点哈夫曼编码就是在哈夫曼树的基础上,从叶子...

    目录

    1.哈夫曼树

    (1)相关概念

    (2)定义

    (3)哈夫曼算法

    2.哈夫曼编码

    (1)相关概念

    (2)定义

    (3)代码实现

    3.完整代码

    4.测试输出


    1.哈夫曼树

    (1)相关概念

    • 叶子结点的权值:对叶子结点赋予的一个有意义的数值量(往往体现了访问的频率)
    • 二叉树的带权路径长度:设二叉树具有n个带权值的叶子结点,从根结点到各个叶子结点的路径长度与相应叶子结点权值的乘积之和(所有的叶子加起来)

    (2)定义

    哈夫曼树:给定一组具有确定权值的叶子结点,带权路径长度最小的二叉树

    特点:

    1,权值越大的叶子结点越靠近根结点,而权值越小的叶子结点越远离根结点
    2,只有度为0(叶子结点)和度为2(分支结点)的结点,不存在度为1的结点

    (3)哈夫曼算法

    1.基本步骤:

    (1)初始化:由给定的n个权值构造n棵只有一个结点的二叉树,构成集合F

    (2)选取与合并:在上述结点二叉树集合F中,选取权值最小的两棵树,分别作为左,右子树构建一棵新的二叉树,其权值为左右子树权值之和

    (3)删除与加入:在集合F中删除作为左右子树的两棵二叉树,并将新二叉树加入F

    (4)重复:(2)(3),直至集合F中只剩下一棵二叉树时,即为哈夫曼树

    基本步骤实现如下图: (图片来自懒猫老师《数据结构》相关课程笔记)

     2.存储结构

    设置一个数组huffTree[2n-1]保存哈夫曼树中各点的信息,数组元素的结点结构如下:

    typedef struct element {
    	int weight;//权值域,保存结点的权值
    	int lchild, rchild, parent;
    	//指针域,分别保存结点的左孩子,右孩子和双亲在数组中的下标
    } element;

    为什么存储数组的元素个数为2n-1呢?

    这里要引入二叉树的性质,推导过程如下:

    3.代码实现

    过程图解:

    每一次进行合并后,将新二叉树加入数组,修改结点的双亲和左右孩子的下标,构建起结点之间的链接关系;并更新合并后结点的权值

    i1 :最小权值结点的下标

    i2 :次小权值结点的下标

    k :合并后的新结点下标

     代码实现: 

    • void HuffmanTree(element *huffTree, int *w, int n) 

    参数分别为,哈曼夫树的数组,存放权值的数组,最初的结点个数(也是权值个数)

    • select(element *huffTree, int k, int *i1, int *i2)

    参数分别为,哈曼夫树的数组,合并后的新结点下标,最小权值结点下标,次小权值结点下标

    void HuffmanTree(element *huffTree, int *w, int n) {
    	int i1, i2;
    	for (int i = 0; i < 2 * n - 1; i++) { //初始化项目结点
    		huffTree[i].parent = -1;
    		huffTree[i].lchild = -1;
    		huffTree[i].rchild = -1;
    	}
    	//初始化前n个结点的权值
    	for (int i = 0; i < n; i++) {
    		huffTree[i].weight = w[i];
    	}
    	for (int k = n; k < 2 * n - 1; k++) { //构建哈夫曼树
    		select(huffTree, k, &i1, &i2);
    		printf("最小下标:%d,次小下标;%d\n", i1, i2);
    		huffTree[k].weight = huffTree[i1].weight + huffTree[i2].weight;//权值相加
    		huffTree[i1].parent = k;//将k下标赋给即将合并的结点的双亲
    		huffTree[i2].parent = k;
    		huffTree[k].lchild = i1;//将合并的两个结点下标赋为k的左右孩子
    		huffTree[k].rchild = i2;
    	}
    }
    void  select(element *huffTree, int k, int *i1, int *i2) {	//寻找parent为-1的权值最小和次小的两个结点
    	int index = 0, count = 0, temp;
    	int arr[k];
    	for (int i = 0; i < k; i++) {
    		if (huffTree[i].parent == -1)
    			arr[count++] = i; //将所有叶子结点的下标保存到arr中
    	}
    	for (int i = 0; i < count; i++) {//冒泡排序
    		for (int j = 0; j < count - i - 1; j++) {
    			if (huffTree[arr[j]].weight > huffTree[arr[j + 1]].weight) {
    				temp = arr[j];
    				arr[j] = arr[j + 1];
    				arr[j + 1] = temp;
    			}
    		}
    	}
    	*i1 = arr[0];
    	*i2 = arr[1];
    }

    (最下面有相关的测试完整代码)

    2.哈夫曼编码

    (1)相关概念

    编码:给每一个对象标记一个二进制位串来表示一组对象

    前缀编码:一组编码中任一编码都不是其它任何一个编码的前缀(前缀编码保证了在解码时不会有多种可能)

    (2)定义

    哈夫曼编码就是在哈夫曼树的基础上,从叶子结点开始向上遍历,左孩子记录码为0;右孩子记录码为1。

    哈夫曼编码:

    (3)代码实现

    每次循环生成一个权值对应的哈夫曼编码,并从尾部开始存入temp数组中,再赋值给huffCode[n]数组

    void huffmanCoding(element *huffTree, char **huffCode, int n) {
    	char temp[n];//储存临时产生的编码串,n是结点的个数
    	temp[n - 1] = '\0';
    	int start, pos, parent;
    
    	for (int i = 0; i < n; i++) { //遍历哈夫曼树数组,生成哈夫曼编码
    		start = n - 1;
    		pos = i; //pos记录正在处理的当前位置
    		parent = huffTree[i].parent; //找到父结点
    		while (parent != -1) { //还能向上寻找根结点
    			if (huffTree[parent].lchild == pos) //判断当前是左孩子还是右孩子
    				temp[--start] = '0';
    			else
    				temp[--start] = '1';
    			pos = parent; //当前位置移动到父结点位置
    			parent = huffTree[parent].parent; //更新父结点
    		}
    		huffCode[i] = (char *)malloc(sizeof(char) * (n - start)); //建立哈夫曼编码储存空间
    		strcpy(huffCode[i], &temp[start]); //将临时储存的哈夫曼编码赋值给对应的空间
    	}
    }
    

    储存结构实现可以参考下图:

    3.完整代码

    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    //输入:
    //4
    //2 4 5 3
    //或者
    //7
    //9 11 5 7 8 2 3
    typedef struct element {
    	int weight;//权值域,保存结点的权值
    	int lchild, rchild, parent;
    	//指针域,分别保存结点的左孩子,右孩子和双亲在数组中的下标
    } element;
    
    main() {
    	int n;
    	printf("请输入结点个数:");
    	scanf("%d", &n);
    	int w[n];
    	printf("请输入%d个权值:", n);//由权值构建哈夫曼树,可以求出一组哈夫曼编码
    	for (int i = 0; i < n; i++)
    		scanf("%d", &w[i]);
    	element huffTree[2 * n - 1];
    	HuffmanTree(huffTree, w, n);
        printf("该哈夫曼树的带权路径长度:%d\n", huffLength(huffTree, n));
    	printf("打印构建好的哈夫曼树数组的内容:\n");
    	printhuffTree(huffTree, n);
    	char *huffCode[n];
    	huffmanCoding(huffTree, huffCode, n);
    	printf("打印生成的哈夫曼编码:");
    	printf("\n");
    	printhuffCode(huffCode, n, 1);
    	printf("完整形式:");
    	printhuffCode(huffCode, n, 2);
    	freehuffCode(huffCode, n);
    }
    
    void HuffmanTree(element *huffTree, int *w, int n) {
    	int i1, i2;
    	for (int i = 0; i < 2 * n - 1; i++) { //初始化项目结点
    		huffTree[i].parent = -1;
    		huffTree[i].lchild = -1;
    		huffTree[i].rchild = -1;
    	}
    	//初始化前n个结点的权值
    	for (int i = 0; i < n; i++) {
    		huffTree[i].weight = w[i];
    	}
    	for (int k = n; k < 2 * n - 1; k++) { //构建哈夫曼树
    		select(huffTree, k, &i1, &i2);
    		printf("最小下标:%d,次小下标;%d\n", i1, i2);
    		huffTree[k].weight = huffTree[i1].weight + huffTree[i2].weight;
    		huffTree[i1].parent = k;
    		huffTree[i2].parent = k;
    		huffTree[k].lchild = i1;
    		huffTree[k].rchild = i2;
    	}
    }
    
    void  select(element *huffTree, int k, int *i1, int *i2) {	//寻找parent为-1的权值最小和次小的两个结点
    	int index = 0, count = 0, temp;
    	int arr[k];
    	for (int i = 0; i < k; i++) {
    		if (huffTree[i].parent == -1)
    			arr[count++] = i; //将所有叶子结点的下标保存到arr中
    	}
    	for (int i = 0; i < count; i++) {//冒泡排序
    		for (int j = 0; j < count - i - 1; j++) {
    			if (huffTree[arr[j]].weight > huffTree[arr[j + 1]].weight) {
    				temp = arr[j];
    				arr[j] = arr[j + 1];
    				arr[j + 1] = temp;
    			}
    		}
    	}
    	*i1 = arr[0];
    	*i2 = arr[1];
    }
    
    void printhuffTree(element *huffTree, int n) {
    	printf("weight  parent lchild  rchild\n");
    	for (int i = 0; i < 2 * n - 1; i++) {
    		printf("%3d%8d%8d%8d\n", huffTree[i].weight, huffTree[i].parent, huffTree[i].lchild, huffTree[i].rchild);
    	}
    }
    
    void huffmanCoding(element *huffTree, char **huffCode, int n) {
    	char temp[n];//储存临时产生的编码串,n是结点的个数
    	temp[n - 1] = '\0';
    	int start, pos, parent;
    
    	for (int i = 0; i < n; i++) { //遍历哈夫曼树数组,生成哈夫曼编码
    		start = n - 1;
    		pos = i; //pos记录正在处理的当前位置
    		parent = huffTree[i].parent; //找到父结点
    		while (parent != -1) { //还能向上寻找根结点
    			if (huffTree[parent].lchild == pos) //判断当前是左孩子还是右孩子
    				temp[--start] = '0';
    			else
    				temp[--start] = '1';
    			pos = parent; //当前位置移动到父结点位置
    			parent = huffTree[parent].parent; //更新父结点
    		}
    		huffCode[i] = (char *)malloc(sizeof(char) * (n - start)); //建立哈夫曼编码储存空间
    		strcpy(huffCode[i], &temp[start]); //将临时储存的哈夫曼编码赋值给对应的空间
    	}
    }
    
    void printhuffCode(char **huffCode, int n, int type) {
    	if (type == 1) {
    		for (int i = 0; i < n; i++) {
    			printf("%s\n", huffCode[i]);
    		}
    	} else {
    
    		for (int i = 0; i < n; i++) {
    			printf("%s", huffCode[i]);
    		}
    	}
    }
    int huffLength(element *huffTree, int n) { //求带权路径长度
    	int temp, count = 0, sum = 0;
    	for (int i = 0; i < n; i++) {
    		temp = i;
    		count = 0;
    
    		while (huffTree[temp].parent != -1) { //求结点的深度
    			count++;
    			temp = huffTree[temp].parent;
    		}
    		sum += huffTree[i].weight * count;
    	}
    	return sum;
    }
    void freehuffCode(char **huffCode, int n) {
    	for (int i = 0; i < n; i++) {
    		free(huffCode[i]);
    	}
    }

    4.测试输出

    初学小白,有错误欢迎指正喔!X

    展开全文
  • 验 报 告 实验目的 掌握哈夫曼树的基本概念所用的存储结构 掌握哈夫曼树的建立算法 掌握哈夫曼树的应用哈夫曼树编码和译码 实验内容 给定权值529781423311建立哈夫曼树输出哈夫曼编码对上述给定的哈夫曼树及得到...
  • 数据结构:哈夫曼树构建及哈夫曼编码实现(C语言版) 严蔚敏数据结构C语言版

    目录

    1.哈夫曼树结构

    2.构造一个n个叶子结点的二叉树

    3.select函数的实现

    4.打印哈夫曼树

    5.哈夫曼编码

    6.根据哈夫曼树求哈夫曼编码


    1.哈夫曼树结构

    创建哈夫曼树结构体,我们额外添加了个character存储权值对应的字符

    //哈夫曼树储存表示
    typedef struct{
    	char character;//结点的字符
    	int weight;//结点的权值
    	int parent, lchild, rchild;//结点的双亲、左孩子、右孩子
    }HTNode, *HuffmanTree;
    

    2.构造一个n个叶子结点的二叉树 

    因为第0号单元未使用,所以根据传入的n开辟n+1个空间,传入二级指针以便改变一级指针。

    void CreateHuffmanTree(HuffmanTree* HT, int n) {
    	if (n <= 1)
    		return;
    	int i = 0;
    	int m = 2 * n - 1;//m为所有结点个数
    	
    	//因为从1号结点开始使用,0号结点未使用,所以开辟m+1个结点的空间
    	HuffmanTree ptr = (HuffmanTree)malloc(sizeof(HTNode) * (m + 1));
    	if (ptr == NULL)//开辟空间失败返回
    	{
    		perror("CreateHuffmanTree");
    		return;
    	}
    	*HT = ptr;//改变指针HT
    	//把1~m号结点中左孩子、右孩子、双亲下标初始化为0,字符初始化为空格
    	for ( i = 1; i <= m; i++)
    	{
    		(ptr + i)->lchild = 0;
    		(ptr + i)->rchild = 0;
    		(ptr + i)->parent = 0;
    		(ptr + i)->character = ' ';
    	}
    	//输入前n个叶子结点的权值
    	printf("输入%d个叶子结点的字符和权值\n", n);
    	for ( i = 1; i <= n; i++)
    	{
    		getchar();
    		scanf("%c", &((ptr + i)->character));
    		scanf("%d", &((ptr + i)->weight));
    	}
    	//开始创建哈夫曼树
    	for ( i = n + 1; i <= m; i++)
    	{
    		int s1, s2;
    		Select(ptr, i - 1, &s1, &s2);//在第1到第i-1个数中找权值最小的两个结点
    		(ptr + i)->lchild = s1;//结点i的左孩子为s1
    		(ptr + i)->rchild = s2;//结点i的右孩子为s2
    		(ptr + i)->weight = (ptr + s1)->weight + (ptr + s2)->weight;//结点i的权值为s1和s2的权值之和
    		//结点s1和s2的双亲改为i;
    		(ptr + s1)->parent = i;
    		(ptr + s2)->parent = i;
    	}
    }

    3.select函数的实现

    在构造哈夫曼树时,用于找到前n项两个最小值,返回两个最小权值的结点

    void Select(HuffmanTree HT, int n, int* s1, int* s2) {
    	int i = 0;
    	//把第1个双亲域为0的值的结点赋给s1
    	for (i = 1; i <= n; i++)
    	{
    		//如果双亲不为0,则跳过本次循环
    		if ((HT + i)->parent == 0) {
    			*s1 = i;
    			break;
    		}
    	}
    	//找到权值最小的下标
    	for (i = 0; i <= n; i++)
    	{
    		if (((HT + i)->weight) < (HT + *s1)->weight)
    			if ((HT + i)->parent == 0)
    				*s1 = i;//如果s1结点的权值大于i结点的权值,更新s1
    	}
    	//把第2个双亲域为0的值的结点赋给s1,避免第一个就是权值最小的结点,和s1重复
    	for (i = 1; i <= n; i++)
    	{
    		//如果双亲不为0,或为s1所在的最小值,则跳过本次循环
    		if (((HT + i)->parent == 0) && (i != *s1)) {
    			*s2 = i;//s2赋为第一个不为s1的结点
    			break;
    		}
    	}
    	//找到除去s1结点权值最小的下标
    	for (i = 0; i <= n; i++)
    	{
    		if (i == *s1)
    			continue;
    		if (((HT + i)->weight) < (HT + *s2)->weight)
    			if ((HT + i)->parent == 0) {
    				*s2 = i;//如果s2结点的权值大于i结点的权值,更新s2
    			}
    	}
    }

    4.打印哈夫曼树

    为方便验证按结点顺序打印哈夫曼树

    void print(HuffmanTree HT, int n) {
    	int m = 2 * n - 1;
    	printf("字符   权值   双亲   左孩子   右孩子\n");
    	for (int i = 1; i <= m; i++)
    	{
    		printf("%c\t%d\t%d\t%d\t%d\n",(HT + i)->character, (HT + i)->weight, (HT + i)->parent, (HT + i)->lchild, (HT + i)->rchild);
    	}
    }

    测试:

    int main() {
    	HuffmanTree HT;
    	int n;
    	printf("输入叶子结点个数:>");
    	scanf("%d", &n);
    	CreateHuffmanTree(&HT, n);//建立8个叶子结点的二叉树
    	print(HT, n);//打印验证
        return 0;
    }

    运行结果:

    5.哈夫曼编码

    typedef char** HuffmanCode;//动态分配数组存储哈夫曼编码表

    6.根据哈夫曼树求哈夫曼编码

    void CreatHuffmanCode(HuffmanTree HT, HuffmanCode* HC, int n) {
    	int start, c, f;
    	HuffmanCode ptr = (HuffmanCode)malloc(sizeof(char*)*(n+1));//分配n个字符的头指针矢量
    	if (ptr == NULL)//分配失败报错并返回
    	{
    		perror("CreatHuffmanCode");
    		return;
    	}
    	*HC = ptr;//更新指针HC
    	char* cd = (char*)malloc(sizeof(char) * n);//分配临时空间存放编码
    	cd[n - 1] = '\0';//最后一个位置放入字符串结束标志\0
    	for (int i = 1; i <= n; i++)
    	{
    		char* tmp = cd + n - 1;//保存此时存储位置
    		start = n - 1;
    		c = i;
    		f = HT[i].parent;
    		while (f != 0)
    		{
    			start--;
    			if (HT[f].lchild == c)//如果i结点为f结点的左孩子,把0存如数组
    				cd[start] = '0';
    			else//如果i结点为f结点的右孩子,把1存入数组
    				cd[start] = '1';
    			tmp--;//更新此时存储位置
    			c = f;
    			f = HT[f].parent;
    		}
    		ptr[i] = (char*)malloc(sizeof(char) * (n - start));//分配n-start个空间
    		strcpy(ptr[i],tmp);//将求得编码复制进ptr中
    	}
    	free(cd);//释放cd位置空间
    	cd = NULL;//置为空指针
    }

    测试:

    int main() {
    	HuffmanTree HT;
    	HuffmanCode HC;
    	int n;
    	printf("输入叶子结点个数:>");
    	scanf("%d", &n);
    	CreateHuffmanTree(&HT, n);//建立8个叶子结点的二叉树
    	print(HT, n);
    	CreatHuffmanCode(HT, &HC, n);
    	for (int i = 1; i <= n; i++)
    	{
    		printf("\n");
    		printf(HC[i]);
    	}
    	return 0;
    }

    运行结果:

    展开全文
  • C++实现哈夫曼树算法

    2020-12-20 18:16:44
    如何建立哈夫曼树的,网上搜索一堆,这里就不写了,直接给代码。 1.哈夫曼树结点类:HuffmanNode.h #ifndef HuffmanNode_h #define HuffmanNode_h template struct HuffmanNode { T weight; // 存储权值 ...
  • 哈夫曼树构建及编码

    千次阅读 2021-05-28 22:19:34
    文章目录哈夫曼树构建及编码一、什么是哈夫曼树二、什么是哈夫曼编码三、怎么建哈夫曼树、求哈夫曼编码四、为什么哈夫曼编码能实现压缩 声明:关于文件压缩,不是本文的重点,本文只说明并讨论哈夫曼树构建和...

    哈夫曼树的构建及编码


    声明:关于文件压缩,不是本文的重点,本文只说明并讨论哈夫曼树的构建和编码,不考虑文件压缩,实际上这个算法可以实现文件的压缩,但是我水平比较有限,涉及到文件操作,就不说了,另外本文后面编码和解码只是示范性举例型说明,并非真正实现了对文件的压缩。

    如果对哈夫曼树文件压缩感兴趣,想要成型的代码,可以直接将自己电脑的文件实现实质性压缩,移步至哈夫曼树编码压缩

    一、什么是哈夫曼树

    百科:

    给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

    解释:

    “带权路径长度”:也就是WPL,它是所有“带权节点”的“权值(或者称为权重)”与距离根节点的“路径长度”乘积之和。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3Sm3ekhx-1622211552152)(D:\f2a8531350e394c2d2f7eaaddd1b04c6.jpeg)]

    “带权节点”中存有原始数值,在建树过程中往往需要两个较小节点权值相加得到新节点再进行新一轮大小比较和筛选。比如如图5和3,它们的父母节点为8,但是,这个节点中的8并不是“原始”或者说不是“初始”数值,不能称为“带权节点”,所以图上该节点未作出标识,该节点确实存有8,但是不计入“带权路径长度”的计算中。

    “路径长度”可看作该“带权节点”到根节点所要走的线段数,比如以图中3为例,显然有4段线段才能到根节点,所以3的“路径长度”为4。

    上图为例:带权路径长度计算

    WPL = 3 * 4 + 5 * 4 + 11 * 3 + 23 * 2 + 29 * 2 + 14 * 3 + 7 * 4 + 8 * 4 = 271

    注:哈夫曼树的创建虽然有规则,但是创建结果不是唯一的,我们唯一可以作为标准的不是树的形状或者结构,而是“带权路径”,即WPL,无论什么结构,WPL值一定唯一且相等!

    二、什么是哈夫曼编码

    在这里插入图片描述

    哈夫曼编码即在哈夫曼树的基础上,左边路径标0,右边路径标1

    举个例子,这时候,i可以表示为00,即从根往下读路径数字。

    三、怎么建哈夫曼树、求哈夫曼编码

    这里就不拿书里面做法说了,书上面是顺序存储,这里介绍链式存储。

    方法 && 步骤:

    1. 改造“轮子”,主要是利用C++中STL库中的“优先队列(priority_queue)",优先队列(priority queue)介绍:

      普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有最高级先出 (first in, largest out)的行为特征。通常采用堆数据结构来实现。

      优先队列的特性,假如是小根堆的有限队列,依次进队5 6 4 2 1那么,其实在队列中顺序是 1 2 4 5 6,队头为1,队尾元素为6,相当于通过进队,在队中实现了排序,接下来要取出较小元素,取出队头即可。

      上面就是对于“轮子”的介绍,接下来改造一下

      为啥要改造?因为加入是一个队列元素是一个数字,优先队列完全不用任何其他操作,自动按照数字大小排序,但是如果队列元素是一个结构体,结构体中包含很多数据,优先队列不知道按照哪一个数据进行排序,这时候就需要“重载”函数,对优先队列中默认的“元素的比较规则”实现自定义重构,然后把我们规定的规则加入 优先队列中即可

    2. 经过改造轮子,我们可以轻松得两个较小节点。两个节点数值的和与两个较小节点构成“父母-左孩子-右孩子”,再将父母节点入优先队列。重复操作即可。便可实现构建哈夫曼树,下面是重载函数:

      struct myCmp
      {
          bool operator()(const tree &a, const tree &b)
      	{
          	
              return a->data > b->data;
          }
      };
      

      构建哈夫曼树总代码:

      #include <iostream>
      #include <vector>
      #include <cstdio>
      #include <string>
      #include <queue>
      #include <cstring>
      
      using namespace std;
      
      const int N = 1010;
      
      char st_c[N], str[N];
      //st_c[]数组存放输入的待编码的0-26英文字符
      //str[]数组读入原始带编码的英文字符,str_c[]数组存放的字
      //符是不同种类字符,无重复,而原始数组str[]中可能有重复
      int  st_n[N], ct_a;
      //st_n[]数组对应st_c[]中每个字符出现的次数
      double st_p[N];
      //st_p[]数组对应st_c[]中每个字符出现的比率
      char xtr[100], st_t[100][N];
      //xtr[]数组用来存放路径结果0/1
      typedef struct node
      {
      	double data;
      	struct node* lc, *rc;
      	
      }node, * tree;
      
      struct myCmp
      {
          bool operator()(const tree &a, const tree &b)
      	{
          	
              return a->data > b->data;
          }
      };
      
      void to_be_node(tree &T, tree T1, tree T2, double x)
      {
          T = new node;
          T->data = x;
          T->lc = T1, T->rc = T2;
          return;
      }
      
      int In(char ch)
      {
      	for (int i = 1; st_c[i]; ++ i){
      	 
      		if (st_c[i] == ch) return i;
      	}
      	  
      	return 0;
      }
      
      void preorder(tree &T, int cnt)//递归实现“编码”
      //类似于DFS(深度优先搜索)
      {	
      //    cout << "cnt = " << cnt << endl;
      	if (!T->lc && !T->rc)//递归出口
      	{
      		int temp = 0;
      		for (int i = 1; st_p[i]; ++ i){
      			
      			if (st_p[i] == T->data) { 
      //			   cout << "i = " << i << ' ' << "xtr = " << xtr << endl;
                     st_p[i] = -1;//防止出现概率相同的,第二次把第一次盖了 
      			   strcpy(st_t[i], xtr);//找到带权节点,拷贝路径到st_t[]数组中
      			   return;
      			} 
      		} 
      		return;
      	}
      	
      	xtr[cnt] = '0';//左边走路径为0
      	preorder(T->lc, cnt+1);
      	xtr[cnt] = '1';//右边走路径为1
      	preorder(T->rc, cnt+1);
      	xtr[cnt] = '\0';//一条路搜完了,回退,清空后一步的0/1
      }
      
      void preordtraver(tree T)//先序遍历
      {
          if (T == NULL) return;
          
          cout << T->data << endl;
          
          preordtraver(T->lc);
          preordtraver(T->rc);
      }
      
      tree build_hfmtree()//构建哈夫曼树
      {
      	priority_queue <tree, vector<tree>, myCmp> hm;
      	//优先队列
      	int judge, i = 1, j = 0;
      	
      	cin >> str;
      
      	while (str[j])
      	{
      		ct_a ++;
      		judge = In(str[j]);
      		if (judge) st_n[judge] ++;
      		else 
      		{
      		    st_c[i] = str[j];
      		    st_n[i] ++, i ++;
      		}
      		j ++; 
      	}
      	
      	cout << "占比如下:" << endl;
      	
      	for (int i = 1; st_c[i]; ++ i)
      	{
      		st_p[i] = (double)st_n[i] / ct_a;
      		cout << st_c[i] << ' ' << st_p[i] << endl;
      	} 
          cout << endl << endl;
          //将每个节点进队
      	for (int i = 1; st_p[i]; ++ i) 
          {
              node* T = new node;
              to_be_node(T, NULL, NULL, st_p[i]);
               
              hm.push(T);
          }
         
          while (hm.size() && hm.size() != 1)//当队中仅有1个节点时退出,这时候树就建成了。
          {
              node* t1 = hm.top(); hm.pop();
              node* t2 = hm.top(); hm.pop();
              
              node* T = NULL;
              to_be_node(T, t1, t2, t1->data + t2->data);
              
              hm.push(T);
          }
          
          node* T = hm.top(); hm.pop();
          //返回哈夫曼树根节点的指针
          return T;
      } 
      
      void encode()
      {
      	FILE *fp = NULL;
      	
      	fp = fopen("D:/HDU/teile.txt", "w");//建文件,路径自己写
      	if (fp == NULL) {
      		
      		cout << "sbai!" << endl;
      		exit(0); 
      	}
      	for (int i = 0; str[i]; ++ i)//将哈夫曼码写入文件
      	{
      		int s = In(str[i]);
      		
      		fputs(st_t[s], fp);
      	}
      	fclose(fp);
      }
      
      void decode()
      {
      	FILE *fp = NULL;
      	char ch, cstr[N] = {0}, cx[N] = {0};
      	
      	fp = fopen("D:/HDU/teile.txt", "r");//打开文件
      	if (fp == NULL) {
      		
      		cout << "sbai!!" << endl;
      		exit(0); 
      	}
      	int i = 0;
      	while (!feof(fp))//读取文件中字符
      	{
      		ch = fgetc(fp);
      		cstr[i ++] = ch;
      	
      		for (int j = 1; st_c[j]; ++ j)
      		{
      			if (!strcmp(cstr, st_t[j]))//进行解码
      			{
      				cout << st_c[j];
      			    while (i) cstr[i --] = '\0';
      				break;
      			}
      		}
      	}
      	fclose(fp);
      	
      	return;
      }
      
      int main()
      {	
          tree T = build_hfmtree();
          
          cout << "哈夫曼树建立完成!" << endl; 
          
          cout << "*******前缀码*****" << endl << endl;
      	
      	preorder(T, 0);
      	
      	for (int i = 1; st_c[i]; ++ i) cout << st_c[i] << " : "<< st_t[i] << endl; 
      	
      	cout << "******************" << endl << endl;
      	 
      	encode();
      	cout << "文件解密如下:\n";
      	
      	decode();
      	   
          return 0;
      }
      //测试:AAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCDDDDDDDDEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFFFFFFFFGGGHHHHHHHHHHH
      /*-------------------------测试时间:2021.5.26  21:25------------------------*/
      
      /*运行结果: 
      part 1.文件 
      1111111111111111111111111101010101010101010101010101010101010101010101
      0101010101010111011101110111011101110111000000000000000000000000011011
      0110110110110110110110110110110110110010101010101010101010101010101010
      1010101010101111101111011110001001001001001001001001001001001
      
      part 2. 运行窗口
      AAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCDDDDDDDDEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFFFFFFFFGGGHHHHHHHHHHH
      占比如下:
      A 0.05
      B 0.29
      C 0.07
      D 0.08
      E 0.14
      F 0.23
      G 0.03
      H 0.11
      
      
      哈夫曼树建立完成!
      *******前缀码*****
      
      A : 11111
      B : 10
      C : 1110
      D : 000
      E : 110
      F : 01
      G : 11110
      H : 001
      ******************
      
      文件解密如下:
      AAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCDDDDDDDDEEEEEEEEEEEEEEFFFFFFFFFFFFFFFFFFFFFFFGGGHHHHHHHHHHH
      
      */
      

    四、为什么哈夫曼编码能实现压缩

    这个很难解释,查资料吧…哈夫曼编码


    THE END…

    展开全文
  • 哈夫曼树构造哈夫曼编码

    千次阅读 2021-11-21 16:02:17
    请为用于通信的电文中的字母进行赫夫曼编码。如各个字母在电文中出现的频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11。试为这8个字母设计哈夫曼编码
  • 【数据结构】哈夫曼树及哈夫曼编码实现(C语言)

    千次阅读 多人点赞 2022-02-12 11:13:38
    哈夫曼树1.1 基本概念1.2 构造哈夫曼树1.3 哈夫曼树的类型定义1.4 哈夫曼树创建的算法实现2. 哈夫曼编码实现2.1 哈夫曼编码2.2 完整代码2.3 运行结果 1. 哈夫曼树 1.1 基本概念 路径:指从根结点到该结点的分支序列...
  • i++)//n个森林中的根结点存放在哈夫曼树数组中的1-n中 { int start = n - 1; int c = i; int f = HT[i].parent; while (f != 0) { start--; if (HT[f].lchild = c) ch[start] = 0; else ch[start] = 1; c = f; f = ...
  • 信息论课程设计-哈夫曼编码。将英文字符的统计概率作为待编码节点权值。编程得出哈夫曼的码表;输入一段英文字符,利用码表对其编码、译码。显示整个流程
  • 给定n个权值作为n的叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短...使用数组构建哈夫曼树,并可用该树构造哈夫曼编码
  • 哈夫曼树、哈夫曼编码详解

    千次阅读 多人点赞 2021-06-17 09:33:06
    哈夫曼树、哈夫曼编码,也就这么一回事,一文搞懂!
  • 本资源功能包括 创 建 哈 夫 曼 、生 成 所 有 字 符 的 Huffman编码、电文字符转Huffman编码 、Huffman编码转电文字符
  • 哈夫曼树的构建及哈夫曼树编码

    万次阅读 2018-09-09 14:56:29
    哈夫曼树的构建: 注意:(1).首先把一组数3 5 6 8 9 12 15从小到大排列 (2).选取里面最小2个,顶点出为2个数的和 (3).新产生的顶点在与原先的...(4)....哈夫曼树编码: 注意:(1).上图的a b c d e f假如...
  • 主要介绍了C++实现哈夫曼树简单创建与遍历的方法,对于C++算法的学习来说不失为一个很好的借鉴实例,需要的朋友可以参考下
  • 哈夫曼树c语言编写

    2017-08-30 18:15:09
    哈夫曼树构造 输出
  • (1)定长编码 我们要传输一条数据: i like like like java do you like a java //共40个字符 通过Ascii码将其转化为对应的二进制形式 http://tool.alixixi.com/ascii2/ 按照二进制来传递数据,总长度为359(包括...
  • 编写一个程序,根据输入节点的权值,建立哈夫曼树并实现哈夫曼编码,同时输出哈夫曼编码
  • 哈夫曼树编码解码.c

    2019-11-21 19:16:53
    该文件是关于用C语言构建哈夫曼树的代码,其中包括对字符的统计、对文档读取然后包括建树的过程,和对哈夫曼树解码的过程。
  • 哈夫曼树构建的核心思路是在创建每一个结点时给结点赋权值,同时推该结点进入“优先队列”。根据优先队列的特性,取优先队列的俩顶部结点生成新结点(俩顶部结点权值相加,并作为新结点的左右子结点),俩顶部结点出...
  • 超详细讲解哈夫曼树(Huffman Tree)以及哈夫曼编码的构造原理、方法,并用代码实现。
  • 常见应用:压缩,最基本的压缩编码的方法,使得总体的编码长度缩短,减少不必要的空间。什么可以称为哈夫曼树?公式判断:WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)Wi : 表示第i...哈夫曼树构建的步骤:① 给定n个权值{...
  • 哈夫曼树与哈夫曼编码

    千次阅读 2020-10-19 18:05:30
    介绍哈夫曼树及哈夫曼编码
  • 哈夫曼树及编码

    2022-05-28 17:41:43
    文章目录一、哈夫曼树的概念二、相关功能实现三、完整代码四、运行结果 一、哈夫曼树的概念 1、哈夫曼树:假设有m个权值,可以构造一棵含n个叶子结点的二叉树,若该树的带权路径长度达到最小,则称这样的二叉树为...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,711
精华内容 1,884
热门标签
关键字:

哈夫曼树的构建及哈夫曼树编码