哈夫曼编码C/C++代码实现

逃离我推掉我的手 2023-02-17 02:17 8阅读 0赞

## 哈夫曼编码的特点： ##

**因为哈夫曼树的特点是**：叶子结点权值越大的，离根越近。**又因为构造不等长编码的原则是**：字符使用频率越高，编码越短，故采用哈夫曼树进行编码可以得到最优前缀编码。  
约定左分支标记为0, 右分支标记为 1

## 求哈夫曼编码: ##

为不浪费存储空间，动态分配一个长度为n(字符编码长度一定小于n) 的一维数组cd, 用来临时存放当前正在求解的第i个字符的编码，当第i个字符的编码求解完毕后，根据数组cd的字符串长度分配HC\[i\]的空间，然后将数组cd中的编码复制到HC\[i\]中。

依照上一篇文章的哈夫曼树：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]  
哈夫曼编码表HC：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]  
注意：由于哈夫曼树不唯一，故哈夫曼编码也不唯一。

## 代码如下： ##

#include<stdio.h>
    #include<iostream>
    
    
    //哈夫曼树定义
    typedef struct {
        
    	int weight;
    	int parent, lchild, rchild;
    }HTNode, *HuffmanTree;
    
    //选择两个双亲域为0且权值最小的结点，并返回在HT中的序号s1，s2
    void Select(HuffmanTree &HT, int n, int &s1, int &s2)
    {
        
    	//寻找第一个双亲域为0且权值最小的结点
    	int min;
    	for (int i = 1; i <= n; i++)	//找到第一个双亲域为0的，下标暂存到min
    	{
        
    		if (HT[i].parent == 0)
    		{
        
    			min = i;
    			break;
    		}
    	}
    
    	for (int i = 1; i <= n; i++)
    	{
        
    		if (HT[i].parent == 0)
    		{
        
    			if (HT[i].weight < HT[min].weight)
    			{
        
    				min = i;
    			}
    		}
    	}
    	s1 = min;
    
    	//寻找第二个双亲域为0且权值最小的结点
    	for (int i = 1; i <= n; i++)	//找到第一个双亲域为0的，下标暂存到min
    	{
        
    		if (HT[i].parent == 0 && i != s1)
    		{
        
    			min = i;
    			break;
    		}
    	}
    
    	for (int i = 1; i <= n; i++)
    	{
        
    		if (HT[i].parent == 0 && i != s1)
    		{
        
    			if (HT[i].weight < HT[min].weight)
    			{
        
    				min = i;
    			}
    		}
    	}
    	s2 = min;
    }
    
    //输出
    void println(HuffmanTree &HT, int m)
    {
        
    	printf("==============================\n");
    	for (int i = 1; i <= m; i++)
    	{
        
    
    		printf("%d，   ", i);
    		printf("%d   ", HT[i].weight);
    		printf("%d   ", HT[i].parent);
    		printf("%d  ", HT[i].lchild);
    		printf("%d   \n", HT[i].rchild);
    		printf("---------------------------\n");
    	}
    }
    
    //创建哈夫曼树
    void CreateHuffmanTree(HuffmanTree &HT,int n, int *ht)
    {
        
    	//初始化
    	int i, m = 2 * n - 1, s1, s2;		//m为所有结点的个数
    	if (n <= 1) return;
    	HT = new HTNode[m + 1];				//0号不用从1开始，多申请一行，前1~n存放叶子结点
    	for (i = 1; i <= m; ++i)			//遍历每一个结点并赋值为0
    	{
        
    		HT[i].parent = 0;
    		HT[i].lchild = 0;
    		HT[i].rchild = 0;
    	}
    
    	//创建树
    	for (i = 1; i <= n; ++i)			//把叶子结点权值放入表中
    	{
        
    		HT[i].weight = ht[i - 1];
    	}
    
    	printf("\nHT的初态\n");
    	println(HT, m);
    	for (int i = n + 1; i <= m; ++i)     //从非叶子结点开始创建
    	{
        
    		Select(HT, i - 1, s1, s2);		//选择两个最小的结点
    
    		HT[s1].parent = i;
    		HT[s2].parent = i;				//把叶子结点双亲域赋上
    		HT[i].lchild = s1;
    		HT[i].rchild = s2;
    		HT[i].weight = HT[s1].weight + HT[s2].weight;
    	}
    	printf("\nHT的终态\n");
    	println(HT, m);
    }
    
    
    
    
    //哈夫曼编码
    typedef char **HuffmanCode;		//哈夫曼编码表，指针数组
    char *cd;						//用来临时存放当前正在求解的第i个字符的编码
    int start;						//cd数组的下标指针
    
    void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)
    {
        
    	int i, c, f;
    	HC = new char*[n + 1];
    	cd = new char[n];
    	cd[n - 1] = '\0';
    	for (i = 1; i <= n; ++i)
    	{
        
    		start = n - 1;
    		c = i;						//当前结点
    		f = HT[i].parent;			//双亲结点
    
    		while (f != 0)				//因为cd数组的start指针从后往前，所以哈夫曼树从下往上即从叶子到根结点进行比较，
    		{
        
    			if (HT[f].lchild == c) cd[--start] = '0';
    			else				   cd[--start] = '1';
    			c = f;
    			f = HT[f].parent;
    		}
    		HC[i] = new char[n - start];
    		strcpy(HC[i], &cd[start]);
    
    		//输出
    		printf("第%d组--->", i);
    		for (int j = start; j <= n - 1; ++j)
    		{
        
    			printf("%c ", cd[j]);
    		}
    		printf("\n");
    
    	}
    	delete cd;
    }
    
    
    int main() {
        
    	HuffmanTree HT;						//构造哈夫曼
    	HuffmanCode HC;						//哈夫曼编码
    	int n = 8;							//n为叶子节点的个数
    	int ht[8] = {
         5,29,7,8,14,23,3,11 };
    
    	CreateHuffmanTree(HT, n, ht);
    	CreatHuffmanCode(HT, HC, n);
    }

## 运行结果： ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200610175302909.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200610174513215.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200610175603340.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ4MjY4MzAx,size_16,color_FFFFFF,t_70