Huffman树的实现

快来打我* 2022-04-04 05:42 154阅读 0赞

昨天下午看了Huffman树的算法，写了部分代码，今天试着调试了一下，虽然过程有点坎坷，但是最终还是出来结果了。这个代码写的很粗糙，好多地方需要改进：比如选择最小的两个数的时候，应该对这两个数进行排序再去构造数，代码里好多地方没有注释。  
等有时间我会再把这个代码完善一下，慢慢精细化。  
代码如下：\`

#include "stdafx.h"
    #include "string.h"
    #include "stdio.h"
    #include "stdlib.h"
    
    char ** HufmanCode;
    
    typedef struct CharType
    {
        
    	char data;//字符
    	int fre;//字符出现的频率
    }CharType;//字符型结构体字符及每个字符出现的频率
    
    typedef struct HufTNode
    {
        
    	char data;//
    	int weight;//节点权值
    	int parent;//该节点对应的父节点的下标
    	int lchild;//该节点的左孩子的位置
    	int rchild;//该节点的右孩子的位置
    }HufTNode,*HufTree;//huffman树节点
    //输入字符串，并统计字符串中不同字符出现的频率
    CharType* putString(int &len)
    {
        
    	char string[100];
    	scanf("%s",string);
    	char ch[100];
    	strcpy(ch,string);
    	int i = 1,j = 1;
    	while(ch[i] != '\0')
    	{
        
    		int k = 0;
    		for(k = 0;k < j;k ++)
    		{
        
    			if(ch[i] == ch[k])
    				break;
    		}
    		if(k >= j)
    			ch[j ++] = ch[i];
    		i ++;
    	}
    	ch[j] = '\0';
    	CharType* charSet;
    	charSet = (CharType*)calloc(j,sizeof(CharType));
    	for(i = 0;i < j;i ++)
    	{
        
    		charSet[i].data = ch[i];
    		charSet[i].fre = 0;
    		int k = 0;
    		while(string[k] != '\0')
    		{
        
    			if(string[k] == ch[i])
    				charSet[i].fre ++;
    			k ++;
    		}
    	}
    	len = j;
    	
    	return charSet;
    }
    //选择没有使用过的频率最小的两个节点
    void SelectMin(HufTNode *HufTnodes,int m,int &addnum1,int &addnum2)
    {
        
    	int i = 1;
    	int min1 = 0,min2 = 0;
    	for(i = 1;i <= m;i ++)
    	{
        
    		if(HufTnodes[i].parent == 0)
    		{
        
    			if(min1 == 0)
    			{
        
    				min1 = HufTnodes[i].weight;
    				addnum1 = i;
    			}
    			else if(min2 == 0)
    			{
        
    				min2 = HufTnodes[i].weight;
    				addnum2 = i;
    			}
    			else
    			{
        
    				if(min1 > HufTnodes[i].weight)
    				{
        
    					min1 = HufTnodes[i].weight;
    					addnum1 = i;
    				}
    				else if(min2 > HufTnodes[i].weight)
    				{
        
    					min2 = HufTnodes[i].weight;
    					addnum2 = i;
    				}
    			}
    		}
    	}
    }
    
    void CreatHuffTree(CharType* charSet,int len)
    {
        
    	int i = 0,num1,num2;
    	int m = 2 * len;
    	HufTNode *HufTnodes = (HufTNode*)malloc(m * sizeof(HufTNode));
    	for(i = 0;i < len ;i ++)
    	{
        
    		HufTnodes[i + 1].data = charSet[i].data;
    		HufTnodes[i + 1].weight = charSet[i].fre;
    		HufTnodes[i + 1].lchild = 0;
    		HufTnodes[i + 1].rchild = 0;
    		HufTnodes[i + 1].parent = 0;
    	}
    	for(i = len + 1;i < m;i ++)
    	{
        
    		HufTnodes[i].data = 0;
    		HufTnodes[i].weight = 0;
    		HufTnodes[i].lchild = 0;
    		HufTnodes[i].rchild = 0;
    		HufTnodes[i].parent = 0;
    	}
    	for(i = len + 1;i < m;i ++)
    	{
        
    		SelectMin(HufTnodes,i - 1,num1,num2);
    		HufTnodes[i].lchild = num1;
    		HufTnodes[i].rchild = num2;
    		HufTnodes[i].weight = HufTnodes[num1].weight + HufTnodes[num2].weight;
    		HufTnodes[num1].parent = i;
    		HufTnodes[num2].parent = i;
    	}
    	HufmanCode = (char **)malloc((len + 1) * sizeof(char*));
    	char * ch = (char *)malloc(len * sizeof(char));
    	int start = len - 1;
    	ch[start] = '\0';
    	for(i = 1;i <= len;i ++)
    	{
        
    		start = len - 1;
    		int j = i,f = HufTnodes[j].parent;
    		while(f)
    		{
        
    			if(j == HufTnodes[f].lchild)
    				ch[-- start] = '0';
    			else ch[-- start] = '1';
    			j = f;
    			f = HufTnodes[j].parent;
    		}
    		HufmanCode[i] = (char *)malloc((len - start) * sizeof(char));
    		strcpy(HufmanCode[i],&ch[start]);
    	}
    	for(i = 1;i <= len;i ++)
    	{
        
    		printf("%s, %c\n",HufmanCode[i],HufTnodes[i].data);
    	}
    }
    
    int main(int argc, char* argv[])
    {
        
    	int len = 0,i = 0;
    	CharType* charSet = putString(len);
    	CreatHuffTree(charSet,len);
    	return 0;
    }

Huffman树算法并不是很难，但是很多地方却要仔细思量，因为要考虑算法的时间复杂度和空间复杂度。  
至于运行结果如下：  
![在这里插入图片描述][20181215113430478.png]  
第一行对应于输入的字符串，下面则是每个字符串对应的编码。  
至于二叉树的后序遍历(非递归)算法，明天再更新！今天要出去逛街啦~

[20181215113430478.png]: /images/20220404/d02512c21eca4ea3be4a8afce2832f74.png