精华内容
下载资源
问答
  • 主要为大家详细介绍了C++实现哈夫曼树编码解码,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 哈夫曼树编码解码.c

    2019-11-21 19:16:53
    该文件是关于用C语言构建哈夫曼树的代码,其中包括对字符的统计、对文档读取然后包括建树的过程,和对哈夫曼树解码的过程。
  • 哈夫曼编码解码

    2017-12-25 16:45:13
    通过二叉树构造哈夫曼树,并用哈夫曼树对读取的txt文件进行哈夫曼编码编码完成后通过哈夫曼树进行解码
  • 哈夫曼树编码解码 可直接运行 哈夫曼树编码解码 +英语文章 全代码
  • /********************************************************************** * Description : create huffmanTree and huffmanCode by input string * and decode a 0、1 sequence by huffmanCode ...
  • 哈夫曼树及哈夫曼编码解码

    千次阅读 2018-11-02 23:07:35
    哈夫曼树,又称最优树,是带权路径最小的树。 基本概念: 节点间的路径长度:两个节点间所包含的边的数目。 树的路径长度:从根到树中任意节点的路径长度之和。 权:将节点赋予一定的量值,该量值成为权。 树的带权...

    哈夫曼树,又称最优树,是带权路径最小的树。
    基本概念:
    节点间的路径长度:两个节点间所包含的边的数目。
    树的路径长度:从根到树中任意节点的路径长度之和。
    权:将节点赋予一定的量值,该量值成为权。
    树的带权路径长度:树中所有叶子结点的带权路径长度。

    哈夫曼算法:给定一个保存权值的数组,求最优树的算法。对于此权值数组找出其中最小的权值和第二小的权值,用这两个权值创建树,并把这两个权值相加所得作为一个新权值放入到原数组中(注意:此时数组中已经去掉了刚才用过的权值),重复以上操作即可建立最优树。

    哈弗曼编码和解码的优点不再赘述。

    哈夫曼树的实现
    1.建立结构体,比较简单

    typedef struct Tree{
    	struct Tree *left;
    	struct Tree *right;
    	int data;
    }Tree;
    

    2.利用权值数组创建哈夫曼树(代码注释已相对清晰)

    Tree *create(int *a,int n){//对数组 a 进行实现哈夫曼树 a 中存放的为权值, n 为数组的长度
    	Tree *tree;
    	Tree **b;
    	int i,j; 
    	b = malloc(sizeof(Tree)*n);//动态一维数组的申请来保存权值 
    	for(i = 0; i < n; i++){
    		b[i] = malloc(sizeof(Tree));
    		b[i]->data = a[i];
    		b[i]->left = b[i]->right = NULL;
    	} 
    	//创建哈夫曼树
    	for(i = 1; i < n; i++){
    		int small1 = -1,small2;//small1指向权值最小,small2是第二小,其初始指向分别是数组的前两个元素
    								//注意前两个元素并不一定是最小的和第二小的
    		//下面一个 for 循环是让small1指向第一个权值,small2指向第二个权值 
    		for(j = 0; j < n; j++){  
    			if(b[j] != NULL && small1 == -1){
    				small1 = j;
    				continue;
    			}
    			if(b[j] != NULL){
    				small2 = j;
    				break;
    			}
    		} 
    		//接下来就是对数组剩下的权值逐个与small1、small2比较,找出最小与第二小的权值 
    		for(j = small2; j < n; j++){
    			if(b[j] != NULL){
    				if(b[j]->data < b[small1]->data){
    					small2 = small1;
    					small1 = j;
    				}
    				else if(b[small2]->data > b[j]->data){
    					small2 = j;
    				}
    			}
    		} 
    		
    		//由两个最小权值建立新树,tree 指向根节点 
    		tree = malloc(sizeof(Tree));
    		tree->data = b[small1]->data + b[small2]->data;
    		tree->left = b[small1];
    		tree->right = b[small2];
    		
    		//以下两步是用于重复执行 
    		b[small1] = tree;
    		b[small2] = NULL; 
    		
    	} 
    	
    	free(b);
    	return tree;
    }
    

    3.打印哈夫曼树

    //打印哈夫曼树 
    void print(Tree *tree){
    	if(tree){
    		printf("%d ",tree->data);
    		if(tree->left && tree->right){
    			printf("(");
    			print(tree->left);
    			if(tree->right)
    			printf(",");
    			print(tree->right);
    			printf(")");
    		}
    	}
    }
    

    4.获取哈夫曼树的带权路径长度

    //获得哈夫曼树的带权路径长度
    int getWeight(Tree *tree,int len){
    	if(!tree)
    	return 0;
    	if(!tree->left && !tree->right)//访问到叶子结点 
    	return tree->data * len;
    	return getWeight(tree->left, len + 1) + getWeight(tree->right,len + 1);//访问到非叶子结点 
    }
    

    5.下面便是哈夫曼编码与解码,思路也较为简单

    //哈夫曼编码 
    void getCoding(Tree *tree,int len){
    	if(!tree)
    	return;
    	static int a[20]; //定义静态数组a,保存每个叶子的编码,数组长度至少是树深度减一
    	int i;
    	if(!tree->left && !tree->right){
    		printf(" %d  的哈夫曼编码为:",tree->data);
    		for(i = 0; i < len; i++)
    		printf("%d",a[i]);
    		printf("\n");
    	}
    	else{//访问到非叶子结点时分别向左右子树递归调用,并把分支上的0、1编码保存到数组a ,的对应元素中,向下深入一层时len值增1 
    		a[len] = 0;
    		getCoding(tree->left, len + 1);
    		a[len] = 1;
    		getCoding(tree->right, len + 1);
    		
    	}
    }
    

    6.哈夫曼解码,比较容易实现
    节点与左子节点之间记为 0 ,节点与右节点之间记为 1 ,如图
    在这里插入图片描述

    //哈夫曼解码
    void Decoding(Tree *tree){
    	printf("请输入要解码的字符串\n");
    	char ch[100];//输入的待解码的字符串 
    	gets(ch);
    	int i;
    	int num[100];//用于保存字符串对应的0 1 编码对应的节点 
    	Tree *cur;
    	for(i = 0; i < strlen(ch); i++){
    		if(ch[i] == '0')
    		num[i] = 0;
    		else
    		num[i] = 1;
    	}
    	
    	if(tree){
    		i = 0;
    		while(i < strlen(ch)){
    			cur = tree;
    			while(cur->left && cur->right){
    				
    				if(num[i] == 0)
    				cur = cur->left;
    				else
    				cur = cur->right;
    				i++;
    			}
    			printf("%d",cur->data);
    		}
    		
    	}
    } 
    

    完整代码如下

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    typedef struct Tree{
    	struct Tree *left;
    	struct Tree *right;
    	int data;
    }Tree;
    
    
    Tree *create(int *a,int n){//对数组 a 进行实现哈夫曼树 a 中存放的为权值, n 为数组的长度
    	Tree *tree;
    	Tree **b;
    	int i,j; 
    	b = malloc(sizeof(Tree)*n);//动态一维数组的申请来保存权值 
    	for(i = 0; i < n; i++){
    		b[i] = malloc(sizeof(Tree));
    		b[i]->data = a[i];
    		b[i]->left = b[i]->right = NULL;
    	} 
    	//创建哈夫曼树
    	for(i = 1; i < n; i++){
    		int small1 = -1,small2;//small1指向权值最小,small2是第二小,其初始指向分别是数组的前两个元素
    								//注意前两个元素并不一定是最小的和第二小的
    		//下面一个 for 循环是让small1指向第一个权值,small2指向第二个权值 
    		for(j = 0; j < n; j++){  
    			if(b[j] != NULL && small1 == -1){
    				small1 = j;
    				continue;
    			}
    			if(b[j] != NULL){
    				small2 = j;
    				break;
    			}
    		} 
    		//接下来就是对数组剩下的权值逐个与small1、small2比较,找出最小与第二小的权值 
    		for(j = small2; j < n; j++){
    			if(b[j] != NULL){
    				if(b[j]->data < b[small1]->data){
    					small2 = small1;
    					small1 = j;
    				}
    				else if(b[small2]->data > b[j]->data){
    					small2 = j;
    				}
    			}
    		} 
    		
    		//由两个最小权值建立新树,tree 指向根节点 
    		tree = malloc(sizeof(Tree));
    		tree->data = b[small1]->data + b[small2]->data;
    		tree->left = b[small1];
    		tree->right = b[small2];
    		
    		//以下两步是用于重复执行 
    		b[small1] = tree;
    		b[small2] = NULL; 
    		
    	} 
    	
    	free(b);
    	return tree;
    }
    
    //打印哈夫曼树 
    void print(Tree *tree){
    	if(tree){
    		printf("%d ",tree->data);
    		if(tree->left && tree->right){
    			printf("(");
    			print(tree->left);
    			if(tree->right)
    			printf(",");
    			print(tree->right);
    			printf(")");
    		}
    	}
    }
    
    //获得哈夫曼树的带权路径长度
    int getWeight(Tree *tree,int len){
    	if(!tree)
    	return 0;
    	if(!tree->left && !tree->right)//访问到叶子结点 
    	return tree->data * len;
    	return getWeight(tree->left, len + 1) + getWeight(tree->right,len + 1);//访问到非叶子结点 
    }
    
    //哈夫曼编码 
    void getCoding(Tree *tree,int len){
    	if(!tree)
    	return;
    	static int a[20]; //定义静态数组a,保存每个叶子的编码,数组长度至少是树深度减一
    	int i;
    	if(!tree->left && !tree->right){
    		printf(" %d  的哈夫曼编码为:",tree->data);
    		for(i = 0; i < len; i++)
    		printf("%d",a[i]);
    		printf("\n");
    	}
    	else{//访问到非叶子结点时分别向左右子树递归调用,并把分支上的0、1编码保存到数组a ,的对应元素中,向下深入一层时len值增1 
    		a[len] = 0;
    		getCoding(tree->left, len + 1);
    		a[len] = 1;
    		getCoding(tree->right, len + 1);
    		
    	}
    }
    
    //哈夫曼解码
    void Decoding(Tree *tree){
    	printf("请输入要解码的字符串\n");
    	char ch[100];//输入的待解码的字符串 
    	gets(ch);
    	int i;
    	int num[100];//用于保存字符串对应的0 1 编码对应的节点 
    	Tree *cur;
    	for(i = 0; i < strlen(ch); i++){
    		if(ch[i] == '0')
    		num[i] = 0;
    		else
    		num[i] = 1;
    	}
    	
    	if(tree){
    		i = 0;
    		while(i < strlen(ch)){
    			cur = tree;
    			while(cur->left && cur->right){
    				
    				if(num[i] == 0)
    				cur = cur->left;
    				else
    				cur = cur->right;
    				i++;
    			}
    			printf("%d",cur->data);
    		}
    		
    	}
    } 
    
    int main(int argc, char *argv[]) {
    	int a[4] = {2,6,7,3};
    	Tree *tree = create(a,4);
    	print(tree);
    	printf("\n哈夫曼树的权值为:");
    	printf("%d\n",getWeight(tree,0));
    	getCoding(tree,0);
    	printf("解码时请参照上方编码\n");
    	Decoding(tree); 
    }
    

    运行结果如下
    在这里插入图片描述

    展开全文
  • 压缩包中包含实验报告,运行视频,是数据结构实验课程作业,可以借鉴参考。其中功能包括输入字母及频率,然后生成相应的哈夫曼编码,然后编码txt文件中的...重新打开控制台,可以通过读取文件重新建立哈夫曼树,就很强
  • java语言、简单实现了哈夫曼编码解码的可视化界面。
  • 可以打开文档读取文档中的字符,并对其进行哈夫曼编码,生成哈夫曼代码,保存至文档。还可以在对编码进行译码,保存至文档。
  • 哈夫曼树与哈夫曼编码以及解码

    千次阅读 多人点赞 2020-07-22 16:23:13
    哈夫曼树即是带权路径最小的二叉树 可以看出,哈夫曼树的特点是 1.权值越大的叶子节点靠根节点越近,越小的越远; 2.只有度为0(叶子节点)和度为2(分支节点)的节点,不存在度为一的节点;(这一特点很重要) ...

    先来一张图,看看程序的效果OvO
    怎么样,484很心动??
    放心,我是不会告诉你我把完整代码都放在最后面了d

    咳咳,回归正题=_=

    接下来是正文

    哈夫曼树即是带权路径最小的二叉树

    可以看出,哈夫曼树的特点是
    1.权值越大的叶子节点靠根节点越近,越小的越远;
    2.只有度为0(叶子节点)和度为2(分支节点)的节点,不存在度为一的节点;(这一特点很重要)
    构建哈夫曼树可以分为三个步骤,选取,合并,删除与加入

    首先选取权值最小的节点2和3,再将它们的权值加起来作为其父节点的权值,最后将合并后的新节点加入原来的集合中。
    重复该操作即可得到哈夫曼树。

    下面的代码是哈夫曼树的构建部分的代码,全部的代码我会在最后面给出来。

    struct Element {
    	int weight;
    	int parent, Lchild, Rchild;
    };
    
    void Select(Element hufftree[], int &i1, int &i2)
    {
    	int min1 = 10000, min2 = 10000, i = 0;
    	while (hufftree[i].weight != -1)
    	{
    		if (min1 > hufftree[i].weight&& hufftree[i].parent == -1)
    		{
    			min1 = hufftree[i].weight;
    			i1 = i;
    		}
    		i++;
    	}
    	i = 0;
    	while (hufftree[i].weight != -1)
    	{
    		if (min2 > hufftree[i].weight&& hufftree[i].parent == -1 && i != i1)
    		{
    			min2 = hufftree[i].weight;
    			i2 = i;
    		}
    		i++;
    	}
    }
    void HuffManTree(Element hufftree[], int n,int w[])//哈夫曼树的创建函数
    {
    	int i1 = 0, i2 = 0;
    	for (int i = 0; i < n; i++)
    	{
    		hufftree[i].weight = w[i];
    	}
    	cout << endl;
    	for (int i = n; i < 2 * n - 1; i++)
    	{
    		Select(hufftree, i1, i2);
    		hufftree[i].weight = hufftree[i1].weight + hufftree[i2].weight;
    		hufftree[i].Lchild = i1; hufftree[i].Rchild = i2;
    		hufftree[i1].parent = i; hufftree[i2].parent = i;
    	}
    }
    

    哈夫曼树的一个重要用途是将叶子节点所包含的信息用二进制编码来表示,也就是编码,并且可以给出的二进制编码来得到里面包含的信息,也就是解码。

    关于编码

    通过该图可以了解到,所谓编码,就是节点位于左边,则编码为0,右边则为1

    void makecode(int q[][10],int road[], Element huffTree[],int n)//编码函数
    {
    	int bianma[10] ;//储存字符的编码
    	int parent = 0, current = 0;
    	memset(bianma,0,sizeof(bianma));
    	int x= 0;//bianma字符串数组的指针
    	for (int i = 0; i < n; i++)
    	{
    		current= i;  //current保存当前节点下标
    		parent = huffTree[current].parent;
    		while (parent!=-1)
    		{
    			if (huffTree[parent].Lchild == current)//当前节点为其双亲的左孩子,编码为0
    			{
    				bianma[x] = 0;
    				road[i]++;
    			}
    			else if (huffTree[parent].Rchild == current)//当前节点为其双亲的右孩子,编码为1
    			{
    				bianma[x] = 1;
    				road[i]++;
    			}
    			x++;
    			current = parent;
    			parent = huffTree[parent].parent;//向上寻找双亲节点
    		}
    		for (int y = 0; y < x; y++)
    		{
    			q[i][y] = bianma[x - y -1];
    		}
    		x = 0;
    	}
    	cout << "编码成功!"<<endl;
    }
    

    而解码便是通过编码表来对给出的二进制编码进行解码,但是给出的编码不一定全是正确的,因此解码函数应该还要拥有报错功能,即指出那部分的编码有误。考虑到篇幅和理解上的问题,这里解码函数不单独列出来了。

    了解了构建,编码,解码过程下面就是具体的代码了(由于把编码和解码函数都加在了里面所以代码会有点长)
    该程序的主要功能是:输入一段字符串后,输给出字符串中不同字符出现的次数,即所对应的权值,哈夫曼树表,不同字符对应的编码,以及其到根节点的路径长度,再输入二进制编码,即可得到对应的解码。

    #include<iostream>
    #include<string.h>
    #include<iomanip>
    using namespace std;
    
    const int SIZE = 100;
    
    struct Element {
    	int weight;
    	int parent, Lchild, Rchild;
    };
    
    void Select(Element hufftree[], int &i1, int &i2)
    {
    	int min1 = 10000, min2 = 10000, i = 0;
    	while (hufftree[i].weight != -1)
    	{
    		if (min1 > hufftree[i].weight&& hufftree[i].parent == -1)
    		{
    			min1 = hufftree[i].weight;
    			i1 = i;
    		}
    		i++;
    	}
    	i = 0;
    	while (hufftree[i].weight != -1)
    	{
    		if (min2 > hufftree[i].weight&& hufftree[i].parent == -1 && i != i1)
    		{
    			min2 = hufftree[i].weight;
    			i2 = i;
    		}
    		i++;
    	}
    }
    void HuffManTree(Element hufftree[], int n,int w[])//哈夫曼树的创建函数
    {
    	int i1 = 0, i2 = 0;
    	for (int i = 0; i < n; i++)
    	{
    		hufftree[i].weight = w[i];
    	}
    	cout << endl;
    	for (int i = n; i < 2 * n - 1; i++)
    	{
    		Select(hufftree, i1, i2);
    		hufftree[i].weight = hufftree[i1].weight + hufftree[i2].weight;
    		hufftree[i].Lchild = i1; hufftree[i].Rchild = i2;
    		hufftree[i1].parent = i; hufftree[i2].parent = i;
    	}
    }
    int findelementNum(char code[], char p[],int w[])//找出字符串中的不同字符,并计算其权重
    {
    	if (strlen(code) == 0)return 0;
    	int num = 1;//记录code中不同的字符个数
    	p[0] = code[0];
    	w[0]++;
    	for (int i = 1; i < strlen(code); i++)
    	{
    		for (int j = 0; j < num; j++)
    		{
    			if (code[i] == p[j])//code[i]已经出现过,则其权值加1,并退出内循环
    			{
    				w[j]++; 
    				break;
    			}
    			if (j == num - 1)//code[i]未出现过,则录入p中,其权值变为1
    			{
    				p[num] = code[i];
    				w[num]++;
    				num++;
    				break;
    			}
    		}
    	}
    	return num;
    }
    
    void makecode(int q[][10],int road[], Element huffTree[],int n)//编码函数
    {
    	int bianma[10] ;//储存字符的编码
    	int parent = 0, current = 0;
    	memset(bianma,0,sizeof(bianma));
    	int x= 0;//bianma字符串数组的指针
    	for (int i = 0; i < n; i++)
    	{
    		current= i;  //current保存当前节点下标
    		parent = huffTree[current].parent;
    		while (parent!=-1)
    		{
    			if (huffTree[parent].Lchild == current)//当前节点为其双亲的左孩子,编码为0
    			{
    				bianma[x] = 0;
    				road[i]++;
    			}
    			else if (huffTree[parent].Rchild == current)//当前节点为其双亲的右孩子,编码为1
    			{
    				bianma[x] = 1;
    				road[i]++;
    			}
    			x++;
    			current = parent;
    			parent = huffTree[parent].parent;//向上寻找双亲节点
    		}
    		for (int y = 0; y < x; y++)
    		{
    			q[i][y] = bianma[x - y -1];
    		}
    		x = 0;
    	}
    	cout << "编码成功!"<<endl;
    }
    
    void decode(int code2[],Element Hufftree[],char p[],int n)//解码函数
    {
    	int i = 0, j = 2 * n - 2, x = 0, count = 0;//j为根节点下标
    	while (code2[i] == 1||code2[i]==0)
    	{
    		if (code2[i] == 1)
    		{
    			count++;
    			x = Hufftree[j].Rchild;
    			j = x;//更新根节点
    			if (Hufftree[x].Rchild == -1)//当前节点没有右孩子,说明他为叶子节点(原因是哈夫曼树的特点是只存在度为0和度为2的节点),即找到对应解码
    			{
    				cout << p[x];
    				j = 2 * n - 2;
    				count = 0;
    			}
    			else if (code2[i + 1] == -1 && Hufftree[x].Rchild != -1)//给出的二进制编码已经结束但是却未能找到对应解码,说明这段编码有误
    			{
    				cout << "(第" << i - count+1 << "到第" << i << "号编码有误)";
    				j = 2 * n - 2;
    				count = 0;
    			}
    			
    		}
    		else if (code2[i] == 0)
    		{
    			count++;
    			x = Hufftree[j].Lchild;
    			j = x;
    			if (Hufftree[x].Rchild == -1)
    			{
    				cout << p[x];
    				j = 2 * n - 2;
    				count = 0;
    			}
    			else if (code2[i + 1] == -1 && Hufftree[x].Rchild != -1)
    			{
    				cout << "(第" << i - count+1 << "到第" << i << "号编码有误)";
    				j = 2 * n - 2;
    				count = 0;
    			}
    		}
    		i++;
    	}
    }
    
    void print(int q[][10],char p[],int n)
    {
    	int j = 0;
    	for (int i = 0; i < n; i++)
    	{
    		cout <<p[i] <<":";
    		while (q[i][j] != -1)
    		{
    			cout << q[i][j];
    			j++;
    		}
    		j = 0;
    		cout << endl;
    	}
    }
    int main()
    {
    	Element huffTree[SIZE];
    	int n;//叶子节点的个数
    	int w[SIZE] ;//储存叶子节点的权重
    	int road[SIZE];//储存叶子节点到根节点的路径长度
    	int q[SIZE][10] ;//储存不同字符的编码
    	char code[50];//待编码的字符串
    	char p[27] = { -1 };//储存字符串中不同的字符
    
    	memset(huffTree, -1, sizeof(huffTree));
    	memset(w, 0, sizeof(w));
    	memset(road, 0, sizeof(road));
    	memset(q, -1, sizeof(q));
    
    	
    	cout << "请输入待编码的字符串:";
    	cin >> code;
    	n = findelementNum(code, p, w);
    	cout << "叶子节点个数为:"<<n<<endl;
    	cout << "各叶子节点的权重为:";
    	for (int i = 0; i < n; i++)
    	{
    		cout <<p[i]<<":"<< w[i] << "   ";
    	}
    	HuffManTree(huffTree, n, w);
    	for (int i = 0; i < 2 * n - 1; i++)
    	{
    		cout << setiosflags(ios::left) << setw(4) << i;
    		cout << setiosflags(ios::left) << setw(4) << huffTree[i].parent;
    		cout << setiosflags(ios::left) << setw(4) << huffTree[i].Lchild;
    		cout << setiosflags(ios::left) << setw(4) << huffTree[i].Rchild;
    		cout << setiosflags(ios::left) << setw(4) << huffTree[i].weight<<endl;
    	}
    	makecode(q,road, huffTree, n);
    	print(q,p, n);
    	cout << "各叶子节点的路径为:" << endl;
    	for (int i = 0; i < n; i++)
    	{
    		cout<<p[i]<<":"<< road[i]<<" ";
    	}
    	cout << endl;
    	int code2[SIZE],t,I=0;
    	memset(code2, -1, sizeof(code2));
    	cout << "请输入待解码编码(以-1截止):";
    	cin >> t;
    	while (t != -1)
    	{
    		code2[I] = t;
    		cin >> t;
    		I++;
    	}
    	decode(code2, huffTree, p, n);
    }
    

    都看到这了还不点个赞吗QvQ

    展开全文
  • 哈夫曼树编码解码

    千次阅读 2019-12-21 22:30:04
    DS二叉树——Huffman编码解码 哈夫曼树简介 给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树哈夫曼树是带权路径长度最短的树,权值较...

    DS二叉树——Huffman编码与解码

    哈夫曼树简介

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

    • 根据数据出现的频率,使用不同长度的编码

    一段文字由x个字符组成,每个字符的出现频率不同,比如a出现114514次,而c只出现了810次,如果对a使用短长度的编码(比如01),对b使用较长的编码(比如01011),相比于使用同样长度的编码(00001 与 01011),可使编码效率变高

    题目

    • 给定n个字符及其对应的权值,构造Huffman树,并进行huffman编码和译(解)码。
    • 构造Huffman树时,要求左子树根的权值小于、等于右子树根的权值。
    • 进行Huffman编码时,假定Huffman树的左分支上编码为‘0’,右分支上编码为‘1’。

    输入
    第一行测试次数
    第2行:第一组测试数据的字符个数n,后跟n个字符
    第3行:第一组测试数据的字符权重 待编码的字符串s1 编码串s2

    输出
    第一行~第n行,第一组测试数据各字符编码值
    第n+1行,串s1的编码值
    第n+2行,串s2的解码值,若解码不成功,输出error!

    样例输入
    2 5 A B C D E
    15 4 4 3 2
    ABDEC
    00000101100
    4 A B C D
    7 5 2 4
    ABAD
    1110110

    样例输出
    A :1
    B :010
    C :011
    D :001
    E :000
    1010001000011
    error!
    A :0
    B :10
    C :110
    D :111
    0100111
    DAC

    哈夫曼树的构造规则

    共有 n 个不同的字符需要编码,编码规则如下:

    • 每次合并,选择没有被选择的,两个权值最小的根节点:x1, x2,将他们的合并
    • 合并之后的根节点的权值是 x1的权值 + x2的权值
    • 合并之后的根节点仍然可以作为新的根节点被选择
    • 需要合并 n-1 次,最后剩下一个根,就是哈夫曼树的根

    使用顺序结构(数组)构造哈夫曼树

    初始状态:
    在这里插入图片描述

    第一次合并,选择 2,3 合并 在这里插入图片描述 在这里插入图片描述

    第二次合并,选择 4, 4 在这里插入图片描述 在这里插入图片描述

    第三次合并,选择 5, 8
    在这里插入图片描述
    在这里插入图片描述

    第四次合并,选择 15, 13
    在这里插入图片描述
    在这里插入图片描述

    哈夫曼树结构实现与创建:

    #define maxlen 100
    
    // 哈夫曼树节点类
    class hft_node
    {
    public:
    	hft_node();
    	int weight;
    	int parent;
    	int lchild;
    	int rchild;
    	char ch;		// 该节点代表的字符
    	string code;	// 该节点字符对应的编码
    };
    
    hft_node::hft_node()
    {
    	this->lchild = -1;
    	this->rchild = -1;
    	this->parent = -1;
    }
    
    // 哈夫曼树类
    class hft
    {
    public:
    	hft();
    	int n;					// 需要编码的字符个数
    	hft_node nodes[maxlen];	// 节点
    	int visited[maxlen];	// 选择标识数组
    	
    	// 找两个未被选择的最小权值节点
    	void min2(int &index1, int &m1, int &index2, int &m2, int range);
    	void encode(string s);	// 获得字符的01编码
    	void decode(string s);	// 对01编码解码获得字符串
    };
    

    创建哈夫曼树

    • 找两个最小权值且未被选择的节点:函数实现
    void hft::min2(int &index1, int &m1, int &index2, int &m2, int range)
    {
    	int i;
    	int min = 114514;
    	int min_index = 0;
    	
    	// min
    	for(i=0; i<range; i++)
    	{
    		if(visited[i]==0 && min>nodes[i].weight)
    		{
    			min = nodes[i].weight;
    			min_index = i;
    		}
    	}
    	visited[min_index] = 1;
    	m1 = min;
    	index1 = min_index;
    	
    	// sub min
    	min = 114514;
    	min_index = 0;
    	for(i=0; i<range; i++)
    	{
    		if(visited[i]==0 && min>nodes[i].weight)
    		{
    			min = nodes[i].weight;
    			min_index = i;
    		}
    	}
    	visited[min_index] = 1;
    	m2 = min;
    	index2 = min_index;
    }
    
    • 两两合并节点
    // build hfm tree
    	for(i=n; i<2*n-1; i++)
    	{
    		int idx1, m1, idx2, m2;
    		min2(idx1, m1, idx2, m2, i);
    		
    		nodes[i].weight = m1 + m2;
    		nodes[i].lchild = idx1;
    		nodes[i].rchild = idx2;
    		nodes[idx1].parent = i;
    		nodes[idx2].parent = i;
    	}
    

    哈夫曼树编码

    在这里插入图片描述 在这里插入图片描述

    // hft coding
    #define push push_back
    #define pop pop_back
    #define top back
    for(i=0; i<n; i++)	// 对每个叶子,下标: 0~n-1 进行编码
    {
    	deque<char> s;
    	int x = i;
    	while(1)
    	{	
    		int pa = nodes[x].parent;
    		if(pa == -1)
    		{
    			break;
    		}
    		
    		if(nodes[pa].lchild == x)
    		{
    			s.push('0');
    		}
    		else
    		{
    			s.push('1');
    		}
    		x = pa;
    	}
    	
    	// 因为是由叶子向根回溯,需要逆序输出才是真正的编码结果
    	while(!s.empty())
    	{
    		nodes[i].code += s.top();
    		s.pop();
    	}
    }// end of hft coding
    

    对给定的字符串,得到它的01编码

    void hft::encode(string s)
    {
    	for(int i=0; i<s.length(); i++)
    	{
    		char c = s[i];
    		for(int j=0; j<n; j++)
    		{
    			if(c == nodes[j].ch)
    			{
    				cout<<nodes[j].code;
    				break;
    			}
    		}
    	}
    	cout<<endl;
    }
    

    给定一串01串,得到解码后的字符串

    void hft::decode(string s)
    {
    	deque<char> q;	// 队列保存解码结果
    	
    	int x = 2*n-2;	// 从根节点出发
    	for(int i=0; i<s.length(); i++)
    	{
    		if(s[i] == '0')
    		{
    			x = nodes[x].lchild;
    		}
    		else 
    		{
    			x = nodes[x].rchild;
    		}
    		
    		// 如果是叶子,解码完成
    		if(nodes[x].lchild==-1 && nodes[x].rchild==-1)
    		{
    			q.push_back(nodes[x].ch);
    			x = 2*n-2;	// 下一次循环再次从根出发
    		}
    	}
    	
    	// 如果读取01串之后,没有到达叶子节点,出错
    	if(n<=x && x<2*n-2)
    	{
    		cout<<"error!"<<endl;
    	}
    	else 
    	{
    		while(!q.empty())
    		{
    			cout<<q.front();
    			q.pop_front();
    		}
    		cout<<endl;
    	}
    }
    

    完整代码

    #include <iostream>
    #include <string>
    #include <deque>
    
    using namespace std;
    #define maxlen 100
    
    class hft_node
    {
    public:
    	hft_node();
    	int weight;
    	int parent;
    	int lchild;
    	int rchild;
    	char ch;
    	string code;
    };
    
    hft_node::hft_node()
    {
    	this->lchild = -1;
    	this->rchild = -1;
    	this->parent = -1;
    }
    
    class hft
    {
    public:
    	hft();
    	int n;
    	hft_node nodes[maxlen];	
    	int visited[maxlen];
    	
    	void min2(int &index1, int &m1, int &index2, int &m2, int range);
    	void encode(string s);
    	void decode(string s);
    };
    
    void hft::min2(int &index1, int &m1, int &index2, int &m2, int range)
    {
    	int i;
    	int min = 114514;
    	int min_index = 0;
    	
    	// min
    	for(i=0; i<range; i++)
    	{
    		if(visited[i]==0 && min>nodes[i].weight)
    		{
    			min = nodes[i].weight;
    			min_index = i;
    		}
    	}
    	visited[min_index] = 1;
    	m1 = min;
    	index1 = min_index;
    	
    	// sub min
    	min = 114514;
    	min_index = 0;
    	for(i=0; i<range; i++)
    	{
    		if(visited[i]==0 && min>nodes[i].weight)
    		{
    			min = nodes[i].weight;
    			min_index = i;
    		}
    	}
    	visited[min_index] = 1;
    	m2 = min;
    	index2 = min_index;
    }
    
    hft::hft()
    {
    	cin>>n;
    	int i;
    	for(i=0; i<n; i++)
    	{
    		cin>>nodes[i].ch;
    	}
    	
    	for(i=0; i<n; i++)
    	{
    		cin>>nodes[i].weight;
    	}
    	
    	for(i=0; i<2*n; i++)
    	{
    		visited[i] = 0;
    	}
    	
    	// build hfm tree
    	for(i=n; i<2*n-1; i++)
    	{
    		int idx1, m1, idx2, m2;
    		min2(idx1, m1, idx2, m2, i);
    		
    		nodes[i].weight = m1 + m2;
    		nodes[i].lchild = idx1;
    		nodes[i].rchild = idx2;
    		nodes[idx1].parent = i;
    		nodes[idx2].parent = i;
    	}
    	
    	// hft coding
    	#define push push_back
    	#define pop pop_back
    	#define top back
    	for(i=0; i<n; i++)
    	{
    		deque<char> s;
    		int x = i;
    		while(1)
    		{	
    			int pa = nodes[x].parent;
    			if(pa == -1)
    			{
    				break;
    			}
    			
    			if(nodes[pa].lchild == x)
    			{
    				s.push('0');
    			}
    			else
    			{
    				s.push('1');
    			}
    			x = pa;
    		}
    		
    		while(!s.empty())
    		{
    			nodes[i].code += s.top();
    			s.pop();
    		}
    	}// end of hft coding
    	
    	// hft display
    	for(i=0; i<n; i++)
    	{
    		cout<<nodes[i].ch<<" :"<<nodes[i].code<<endl;
    	}
    }
    
    void hft::encode(string s)
    {
    	for(int i=0; i<s.length(); i++)
    	{
    		char c = s[i];
    		for(int j=0; j<n; j++)
    		{
    			if(c == nodes[j].ch)
    			{
    				cout<<nodes[j].code;
    				break;
    			}
    		}
    	}
    	cout<<endl;
    }
    
    void hft::decode(string s)
    {
    	deque<char> q;
    	
    	int x = 2*n-2;
    	for(int i=0; i<s.length(); i++)
    	{
    		if(s[i] == '0')
    		{
    			x = nodes[x].lchild;
    		}
    		else 
    		{
    			x = nodes[x].rchild;
    		}
    		
    		if(nodes[x].lchild==-1 && nodes[x].rchild==-1)
    		{
    			q.push_back(nodes[x].ch);
    			x = 2*n-2;
    		}
    	}
    	
    	if(n<=x && x<2*n-2)
    	{
    		cout<<"error!"<<endl;
    	}
    	else 
    	{
    		while(!q.empty())
    		{
    			cout<<q.front();
    			q.pop_front();
    		}
    		cout<<endl;
    	}
    }
    
    int main()
    {
    	int n;
    	cin>>n;
    	while(n--)
    	{
    		hft t;
    		string s;
    		cin>>s;
    		t.encode(s);
    		cin>>s;
    		t.decode(s);	
    	}
    
    	return 0;
    }
    
    展开全文
  • 采用二叉树结构 构建哈夫曼树 并对字符串进行赫夫曼编码跟赫夫曼解码
  • 哈夫曼树以其编码解码 本人大二学渣,写的不好的地方大神勿喷! 哈夫曼树以其编码解码要求: 1.从终端读入字符集大小为n(即字符的个数),逐一输入n个字符和相应的n个权值(即字符出现的频度),建立哈夫曼树,进行...

    哈夫曼树以其编码解码

    本人大二学渣,写的不好的地方大神勿喷!

    哈夫曼树以其编码解码要求:

    1.从终端读入字符集大小为n(即字符的个数),逐一输入n个字符和相应的n个权值(即字符出现的频度),建立哈夫曼树,进行编码并且输出。
    将它存于文件hfmtree中(选做)。
    2.利用已建好的哈夫曼编码文件hfmtree,对键盘输入的正文进行译码。输出字符正文,再输出该文的二进制码。
    [测试数据]
    用下表中给出的字符集(n=27)和频度的实际统计数据建立哈夫曼树:

    并实现以下报文的译码和输出:HUANGWAN

    结点代码:

    public class HNode {
    public String code = “”;// 节点的哈夫曼编码
    public String data = “”;// 节点的数据
    public int count;// 节点的权值
    public HNode lChild;
    public HNode rChild;
    public HNode() {
    } ublic HNode(String data, int count) {
    this.data = data;
    this.count = count;
    }public HNode(int count, HNode lChild, HNode rChild) {
    this.count = count;
    this.lChild = lChild;
    this.rChild = rChild;
    }
    public HNode(String data, int count, HNodlChild,HNode rChild) {
    this.data = data;
    this.count = count;
    this.lChild = lChild;
    this.rChild = rChild;
    }}

    哈夫曼树及编码解码  public cla
    

    ss Huffman {
    private String str;// 字符串
    private HNode root;// 哈夫曼二叉树的根节点
    private boolean flag;// 最新的字符是否已经存在的标签
    private LinkedList charList;// 存储不同字符的队列 相同字符存在同一位置
    private LinkedList NodeList;// 存储节点的队列

     private class CharData {
         int num = 1; // 字符个数
         char c; // 字符
    
         public CharData(char ch){
             c = ch;
         }
     }
    
    /**
     * 构建哈夫曼树
     */
    public void creatHfmTree(String str) {
        this.str = str;
    
        NodeList = new LinkedList<HNode>();
        charList = new LinkedList<CharData>();
    
        // 1.统计字符串中字符以及字符的出现次数
        // 以CharData类来统计出现的字符和个数
        getCharNum(str);
    
        // 2.根据第一步的结构,创建节点
        creatNodes();
    
        // 3.对节点权值升序排序
        Sort(NodeList);
    
        // 4.取出权值最小的两个节点,生成一个新的父节点
        // 5.删除权值最小的两个节点,将父节点存放到列表中
        creatTree();
    
        // 6.重复第四五步,就是那个while循环
        // 7.将最后的一个节点赋给根节点
        root = NodeList.get(0);
    }
    
    /**
     * 统计出现的字符及其频率
     */
    private void getCharNum(String str) {
    
        for (int i = 0; i < str.length(); i++) {
            char ch = str.charAt(i); // 从给定的字符串中取出字符
            flag = true;
    
            for (int j = 0; j < charList.size(); j++) {
                CharData data = charList.get(j);
    
                if(ch == data.c){ 
                    // 字符对象链表中有相同字符则将个数加1
                    data.num++;
                    flag = false;
                    break;
                }
            }
    
            if(flag){
                // 字符对象链表中没有相同字符则创建新对象加如链表
                charList.add(new CharData(ch)); 
            }
        }
    }
    
    /**
     * 将出现的字符创建成单个的结点对象
     */
    private void creatNodes() {
    
        for (int i = 0; i < charList.size(); i++) {
            String data = charList.get(i).c + "";
            int count = charList.get(i).num;
    
            HNode node = new HNode(data, count); // 创建节点对象
            NodeList.add(node); // 加入到节点链表
        }
    
    }
    
    /**
     * 构建哈夫曼树
     */
    private void creatTree() {
    
        while (NodeList.size() > 1) {// 当节点数目大于一时
            // 4.取出权值最小的两个节点,生成一个新的父节点
            // 5.删除权值最小的两个节点,将父节点存放到列表中
            HNode left = NodeList.poll();
            HNode right = NodeList.poll();
    
            // 在构建哈夫曼树时设置各个结点的哈夫曼编码
            left.code = "0";
            right.code = "1";
            setCode(left);
            setCode(right);
    
            int parentWeight = left.count + right.count;// 父节点权值等于子节点权值之和
            HNode parent = new HNode(parentWeight, left, right);
    
            NodeList.addFirst(parent); // 将父节点置于首位
            Sort(NodeList); // 重新排序,避免新节点权值大于链表首个结点的权值
        }
    }
    
    /**
     * 升序排序
     */
    private void Sort(LinkedList<HNode> nodelist) {
        for (int i = 0; i < nodelist.size() - 1; i++) {
            for (int j = i + 1; j < nodelist.size(); j++) {
                HNode temp;
                if (nodelist.get(i).count > nodelist.get(j).count) {
                    temp = nodelist.get(i);
                    nodelist.set(i, nodelist.get(j));
                    nodelist.set(j, temp);
                }
    
            }
        }
    
    }
    
    /**
     * 设置结点的哈夫曼编码
     */
    private void setCode(HNode root) {
    
        if (root.lChild != null) {
            root.lChild.code = root.code + "0";
            setCode(root.lChild);
        }
    
        if (root.rChild != null) {
            root.rChild.code = root.code + "1";
            setCode(root.rChild);
        }
    }
    
    /**
     * 遍历
     */
    private void output(HNode node) {
    
        if (node.lChild == null && node.rChild == null) {
            System.out.println(node.data + ": " + node.code);
        }
        if (node.lChild != null) {
            output(node.lChild);
        }
        if (node.rChild != null) {
            output(node.rChild);
        }
    }
    
    /**
     * 输出结果字符的哈夫曼编码
     */
    public void output() {
        output(root);
    }
    
    private String hfmCodeStr = "";// 哈夫曼编码连接成的字符串
    
    /**
     * 编码
     */
    public String toHufmCode(String str) {
    
        for (int i = 0; i < str.length(); i++) {
            String c = str.charAt(i) + "";
            search(root, c);
        }
        return hfmCodeStr;
    }
    
    private void search(HNode root, String c) {
        if (root.lChild == null && root.rChild == null) {
            if (c.equals(root.data)) {
                hfmCodeStr += root.code; // 找到字符,将其哈夫曼编码拼接到最终返回二进制字符串的后面
            }
        }
        if (root.lChild != null) {
            search(root.lChild, c);
        }
        if (root.rChild != null) {
            search(root.rChild, c);
        }
    }
    
    // 保存解码的字符串
    String result="";
    boolean target = false; // 解码标记
    /**
     * 解码
     * @param codeStr
     * @return
     */
    public String CodeToString(String codeStr) {
    
        int start = 0;
        int end = 1;
    
        while(end <= codeStr.length()){
            target = false;
            String s = codeStr.substring(start, end);
            matchCode(root, s); // 解码
            // 每解码一个字符,start向后移
            if(target){
                start = end;
            }
            end++;
        }
        return result;
    }
    
    private void matchCode(HNode root, String code){
        if (root.lChild == null && root.rChild == null) {
            if (code.equals(root.code)) {
                result += root.data; // 找到对应的字符,拼接到解码字符穿后
                target = true; // 标志置为true
            }
        }
        if (root.lChild != null) {
            matchCode(root.lChild, code);
        }
        if (root.rChild != null) {
            matchCode(root.rChild, code);
        }
    }
    
    public static void main(String[] args) {
    
        Huffman huff = new Huffman();// 创建哈弗曼对象
        String data = "THIS PROGRAM IS MY FAVORITE"; 
        huff.creatHfmTree(data);// 构造树
        huff.output(); // 显示字符的哈夫曼编码
        // 将目标字符串利用生成好的哈夫曼编码生成对应的二进制编码
        String hufmCode = huff.toHufmCode(data); 
        System.out.println("编码:" + hufmCode);
        // 将上述二进制编码再翻译成字符串
        System.out.println("解码:" + huff.CodeToString(hufmCode));            
    }
    }
    

    最后运行如下:
    A: 00
    N: 01
    G: 100
    W: 101
    H: 110
    U: 111
    编码:11011100011001010001
    解码:HUANGWAN

    展开全文
  • 主要介绍了Python完成哈夫曼树编码过程及原理详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
  • 哈夫曼树解码

    千次阅读 2019-05-09 22:39:05
    哈夫曼树解码 题目: 思路: 代码: #include <iostream> #include <stdio.h> #include <string.h> #include <stdlib.h> using namespace std; typedef struct Node{ ...
  • 哈夫曼编码解码哈夫曼树

    千次阅读 2019-09-25 10:52:19
    第二遍则根据第一遍扫描得到的哈夫曼树进行编码,并把编码后得到的码字存储起来。 哈夫曼编码 比如需要的电文是 ABCACCDAEAE ,其中 A 出现次数为 4, B 出现次数为 1, C 出现次数为 3, D 出现次数为 ...
  • 数据结构课程 实验报告 实验名称 哈弗曼编码和译码 专业班级 电子信息科学与技术0904 姓 名 秦杰 学 号 1404090506 指导教师 胡志坤 2011年 11月 实验四哈夫曼编码和译码 实验目的和要求 掌握哈夫曼树的基本概念及其...
  • 数据结构哈夫曼树编码解码,自己用c++编的,vc6.0通过,可运行
  • NULL 博文链接:https://touch-2011.iteye.com/blog/1058800
  • 输入一段英文原文,构造哈夫曼树,生成对应的编码表,输出原文对应的编码,或者是根据已经生成的编码表,输入一段二进制数编码,得到对应的字符原文。 #include<stdio.h> #include<iostream> #include...
  • 1.哈夫曼树 给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度(wpl)达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。 构成哈夫曼树的步骤: 从小到大进行排序, 将每一个...
  • 1 概述给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。哈夫曼编码...
  • 源代码——哈夫曼树编码解码

    千次阅读 2016-09-03 19:51:21
    哈夫曼树 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include //哈夫曼编码分析: //问题是:给一个输入的字符串进行哈夫曼编码 //前提:需要知道这个字符串字符种类及其频度(权) /...
  • 哈夫曼树如果不清楚是什么概念的话可以看一下百度百科的介绍,这里的哈夫曼树节点存储的是char字符 Node节点数据结构: public class Node implements Comparable<Node>{ //需要改写compareTo方法,实现权重...
  • 有讲到了哈夫曼树的原理及哈夫曼编码解码的过程。原理讲解直接移步上述链接,就不再画蛇添足。作为巩固随手练习一道题: 给定一篇文章,统计里面的各个字符出现的频次,并构建哈夫曼树,实现哈夫曼编码和解码的过程...
  • 哈夫曼树的应用(哈夫曼树的建立,编码解码
  • 这里我用的实例为: ...哈夫曼树的结构定义 typedef struct { int weight; int parent, left, right; }Htnode, * Huffmantree; typedef char** Huffmancode; 建立哈夫曼树 void select(Huffmantree a

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,461
精华内容 1,384
关键字:

哈夫曼树编码解码