数据结构——哈弗曼编码问题

缺乏、安全感 2022-12-28 06:58 137阅读 0赞

实验六 基于哈夫曼树的数据压缩算法  
【实验目的】

1.  掌握哈夫曼树的构造算法。
2.  掌握哈夫曼编码的构造算法。  
    【实验内容】  
    问题描述  
    输入一串字符,根据给定的字符串中字符出现的频率建立相应的哈夫曼树,  
    构造哈夫曼编码表,在此基础上可以对压缩文件进行压缩(即编码),同时可以对  
    压缩后的二进制编码文件进行解压(即译码)。  
    输入要求  
    多组数据,每组数据 1 行,为一个字符串(只考虑 26 个小写字母即可)。当输  
    入字符串为“00”时,输入结束。  
    输出要求  
    每组数据输出 2n+3 行(n 为输入串中字符类别的个数)。第 1 行为统计出来  
    的字符出现频率（只输出存在的字符,格式为字符:频度),每两组字符之间用一个  
    空格分隔,字符按照 ASCII 码从小到大的顺序排列。第 2 行至第 2n 行为哈夫曼树  
    的存储结构的终态（参照实验提示表 5.2，一行当中的数据用空格分隔)。第 2n+1  
    行为每个字符的哈夫曼编码(只输出存在的字符,格式为字符：编码),每两组字符  
    之间用一个空格分隔,字符按照 ASCII 码从小到大的顺序排列。第 2n+2 行为编码  
    后的字符串,第 2n+3 行为解码后的字符串(与输入的字符串相同)。  
    输入样例  
    aaaaaaabbbbbccdddd  
    aaccb  
    00  
    输出样例  
    a:7 b:5 c2 d:4  
    1 7 7 0 0  
    2 5 6 0 0  
    3 2 5 0 0  
    4 4 5 0 0  
    5 6 6 3 4  
    6 1 1 7 2 5  
    7 1 8 0 1 6  
    a:0 b:10 c:110 d:111  
    00000001010101011011011111  
    aaaaaaabbbbbccdddd  
    a:2 b:1 c:3  
    1 2 4 0 0  
    2 1 4 0 0  
    3 3 5 0 0  
    4 3 5 2 1  
    5 6 0 3 4  
    a:11 b:10 c:0  
    111110000  
    aabccc  
    【实验提示】  
    首先,读入一行字符串,统计每个字符出现的频率;然后,根据字符出现的频  
    率利用提示算法 1 建立相应的哈夫曼树;最后,根据得到的哈夫曼树利用算法 2  
    求出每个字符的哈夫曼编码。

思路：

1.  该问题使用顺序表来存储哈夫曼树
2.  char\_statiscal()函数统计每种字符出现的次数
3.  CreatHuffmanCode()构建哈弗曼树数组，共有n个叶子结点，n-1个非叶子结点。
4.  select()函数选取哈弗曼数组中权值最小的两个叶子结点，返回到CreatHuffmanCode()函数中，用于完成对非叶子结点的构建  
    并且同时修改叶子结点的父亲结点，和非叶子结点的孩子结点
5.  结构体  
    typedef struct  
    \{  
    char info;//存储每一个结点对应的字符  
    int weight;//权值  
    int parent,lchild,rchild;  
    int index;//存储每一个结点对应的下标  
    char code\[MAXCODE\];//存储每一个字符对应的二进制编码

\}HTNode,\*HuffmanTree;

6.CreatHuffmanCode()函数为每种字符创建各自的二进制编码

1.  encode()将每个字符的编码放到该叶子结点的code\[\]  
    中去。  
    具体过程：依次读入字符，在哈弗曼编码表（数组中）找到次字符，将字符转换为编码表中存放的编码串。
2.  decode()利用以构建好的哈弗曼树来进行解码  
    对编码后的文件进行译码的过程必须借助于哈弗曼树。  
    具体过程：依次读入文件的二进制码，从哈弗曼树的根节点出发，若是0，则走向左子树，否则走向右子树。一旦到达叶子结点，便译出相应的字符编码。然后继续从根节点出发继续译码，直到全部结束。

#include<stdio.h>
    #include<iostream>
    #include<string.h>
    using namespace std;
    #define MAXSTRLEN 255
    #define MAXCODE 20
    
    char alphabet[26]={
        0};
    char alphabet2[26];
    typedef char **HuffmanCode;
    typedef struct
    {
        
    	char String[MAXSTRLEN]; 
    }SqString;
    
    typedef struct
    {
        
    	char info;//存储每一个结点对应的字符 
    	int weight;//权值 
    	int parent,lchild,rchild;
    	int index;//存储每一个结点对应的下标 
    	char code[MAXCODE];//存储每一个字符对应的二进制编码 
    
    }HTNode,*HuffmanTree;
    
    //统计字符串中每种字符出现的次数 
    void char_statiscal(SqString &S,char *alphabet,int &num,char *alphabet2)
    {
        
    	int i=0,j=0;
    	for(i=0;S.String[i]!='\0';i++)
    	{
        
    		if(S.String[i]>='a'&&S.String[i]<='z')
    		alphabet[S.String[i]-'a']++;
    	}
    	
    	for(int j=0;j<26;j++)
    	{
        
    		if(alphabet[j]>0)
    		{
        
    			printf("%c:%d  ",'a'+j,alphabet[j]);
    			num++;
    		}
    		
    	}
    	printf("\n"); 
    	
    	
    	  int x=0;
    	for(int j=0;j<26;j++)
    	{
        
    		if(alphabet[j]>0)
    		{
        
    			alphabet2[x]='a'+j;
    			x++;
    		}
    		
    	}
    	
    }
    
    //创建一个简单的哈弗曼树用于复制一个复杂的哈弗曼树  主要用于排序了 
    void createHuffmanTree2(HuffmanTree &HT,int n,char *alphabet,char*alphabet2)
    {
        
    
    	if(n<1)
    		return ;
    	int m=2*n-1;
    	int number=0;
    	HT=new HTNode[m+1];
    	for(int i=1;i<=n;i++)
    	{
        
    		
    		HT[i].parent=0;
    		HT[i].lchild=0;
    		HT[i].rchild=0;
    		HT[i].index=i;
    	 }
    	 for(int j=0;j<26;j++)
    	 {
        
    	 	if(alphabet[j]>0)
    	 	HT[++number].weight=0;
    	  }
    
    	 
    }
    
    
    //HT哈夫曼树，ht,是用于存储排序后的哈夫曼树，n是所要排序的哈夫曼树的节点个数
    void select(HuffmanTree &HT,int length,int &s1,int &s2)
    {
         
    	HuffmanTree ht;
    	createHuffmanTree2(ht,length,alphabet,alphabet2);
    	
    		for(int i=1;i<=length;i++)
    	{
        
    	
    		{
        	
    		ht[i].weight=HT[i].weight;
    		ht[i].index=HT[i].index;
    		}
    	
    	}
    	
    	
    	
    	int temp_index=0;
    	int temp_weight=0;
    	for(int i=1;i<length;i++)
    	{
        
    		for(int j=1;j<=length-i;j++)
    		{
        
    			if(ht[j].weight>ht[j+1].weight)
    			{
        
    				temp_weight=ht[j].weight;
    				ht[j].weight=ht[j+1].weight;
    				ht[j+1].weight=temp_weight;
    				
    				
    				temp_index=ht[j].index;
    				ht[j].index=ht[j+1].index;
    				ht[j+1].index=temp_index;
    				
    				
    				
    				
    			}
    		}
    	 }
    	 
    	 	
    	  
    	 
    	 for(int i=1;i<=length;i++)
    	{
        
    		if(HT[ht[i].index].parent==0)
    		{
        
    		s1=ht[i].index;
    		HT[ht[i].index].parent=length+1;
    	
    		break;
    		}
    		
    	}
    	
    	for(int j=1;j<=length;j++)
    	{
        
    		if(HT[ht[j].index].parent==0)
    		{
        
    		s2=ht[j].index;
    		HT[ht[j].index].parent=length+1;
    	
    		break;
    		}
    		
    	}
    	
    	
    	
    	
    	
    	
    	
    	
    }
    
    //构建一颗完整的哈夫曼树 
    void createHuffmanTree(HuffmanTree &HT,int n,char *alphabet)
    {
        
    //----------------------------创建哈夫曼树---------------------// 
    	if(n<1)
    		return ;
    	int m=2*n-1;
    	int number=0;
    	HT=new HTNode[m+1];//构造哈夫曼树节点 的结构体数组，0号单元不占用，其中共有n个叶子节点，n-1个非叶子节点；
    	for(int i=1;i<=m;i++)
    	{
        
    		HT[i].info=alphabet2[i-1];
    		HT[i].parent=0;
    		HT[i].lchild=0;
    		HT[i].rchild=0;
    		HT[i].index=i;
    	 }
    	 for(int j=0;j<26;j++)
    	 {
        
    	 	if(alphabet[j]>0)
    	 	HT[++number].weight=alphabet[j];
    	  }
    //---------------------------------初始化--------------------------------//
    	int a,b;
    	
    	for(int i=n+1;i<=m;i++)
    	{
        
    		select(HT,i-1,a,b);
    		HT[a].parent=i;
    		HT[b].parent=i;
    		HT[i].lchild=a;
    		HT[i].rchild=b;
    		HT[i].weight=HT[a].weight+HT[b].weight;
    	}
    	
    	
    	
    		for(int a=1;a<=2*n-1;a++)
    	{
        
    		printf("下标为%d的权为 %d 父亲节点:%d,左孩子：%d,右孩子：%d\n",HT[a].index,HT[a].weight,HT[a].parent,HT[a].lchild,HT[a].rchild);
    
    	}
    	 
    }
    
    //为每一个字符创建好各自的二进制编码 
    void CreatHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n)
    {
        
    	HC=new char*[n+1];
    	char *cd;
    	cd=new char[n];
    	cd[n-1]='\0';
    	int start;
    	int c;
    	int f;
    	for(int i=1;i<=n;i++)
    	{
        
    		start=n-1;
    		c=i,f=HT[i].parent;
    		while(f!=0)
    		{
        
    			--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]);
    	}
    	delete cd;
    	
    	for(int i=1;i<=n;i++)
    	printf("%c:%s  ",alphabet2[i-1],HC[i]);
    	printf("\n");	
    }
    
    //为字符串进行编码 
    void encode(SqString &S,HuffmanCode HC,int n,HuffmanTree HT,char *sum)
    {
        
    	
    	for(int i=0;S.String[i]!='\0';i++)
    	{
        
    		for(int j=1;j<=n;j++)
    		{
        
    			if(S.String[i]==HT[j].info)
    			{
        
    				strcat(sum,HC[j]);
    				strcpy(HT[j].code,HC[j]);
    			
    				break;
    			}
    			
    		}
    	}
    	printf("%s\n",sum);
    }
    
    //对已经编码好的字符串进行解码 
    void decode(char *sum,int n,HuffmanTree HT)
    {
        
    	int index=2*n-1;//根节点开始 
    	int j=0;
    	
    	while(sum[j]!='\0')
    	{
        
    		if(sum[j]=='0')
    			index=HT[index].lchild;
    		else 
    			index=HT[index].rchild;
    		if(HT[index].lchild==0&&HT[index].rchild==0)
    		{
        
    			printf("%c",HT[index].info);
    			index=2*n-1;
    			}
    			
    		j++;
    	}
    	
    
    	
    	
    }
    
    
    int main()
    {
        
    	
    		SqString S;
    	do
    	{
        
    		gets(S.String);
    	HuffmanTree HT;
    	char sum[100]={
        ""};
    	int num=0;
    	char alphabet[26]={
        0};
    	
    	char_statiscal(S,alphabet,num,alphabet2);
    	
    	createHuffmanTree(HT,num,alphabet);
    
    	HuffmanCode HC;
    	
    	CreatHuffmanCode(HT,HC,num);
    
    	encode(S,HC,num,HT,sum);
    	
    	decode(sum,num,HT);
    	printf("\n"); 
    	}while(S.String!="00");
    	
    
    	
    }

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center 6]  
关于n个字符的哈弗曼编码的计算时间复杂度为（n*logn）  
因为最小堆的插入和删除都需要（logn）的时间，而n-1次的合并就需要n*（logn）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/29326b0cdbd540c197021f45a461b10b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/aad0cccfe4604fe2bec938f9a6081542.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/15422914f1db48d8bbb0180983fdc17e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/58606afe20764247a7724c700b864686.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20201215231749532.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20201215231758852.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/20201215231806998.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzUwNjc1ODEz,size_16,color_FFFFFF,t_70#pic_center