哈夫曼树与哈夫曼编码以及解码

ゝ一世哀愁。 2023-03-01 05:58 34阅读 0赞

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

咳咳，回归正题=\_=

接下来是正文

哈夫曼树即是带权路径最小的二叉树  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjAxMzM4_size_16_color_FFFFFF_t_70 1][]  
可以看出，哈夫曼树的特点是  
1.权值越大的叶子节点靠根节点越近，越小的越远；  
2.***只有度为0（叶子节点）和度为2（分支节点）的节点，不存在度为一的节点***；（这一特点很重要）  
构建哈夫曼树可以分为三个步骤，***选取，合并，删除与加入***  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjAxMzM4_size_16_color_FFFFFF_t_70 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;
    	}
    }

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

关于编码  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjAxMzM4_size_16_color_FFFFFF_t_70 3][]  
通过该图可以了解到，所谓编码，就是节点位于左边，则编码为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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjAxMzM4_size_16_color_FFFFFF_t_70]: /images/20230209/1eb23e18890d4763998bf09571098345.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjAxMzM4_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200722154549233.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjAxMzM4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjAxMzM4_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020072215514242.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjAxMzM4,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjAxMzM4_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200722160415592.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2NjAxMzM4,size_16,color_FFFFFF,t_70