数据结构——构建Huffman树求Huffman编码

小灰灰 2022-04-17 06:39 192阅读 0赞

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    //一个节点的包含的信息
    typedef struct 
    {
    	unsigned int weight;  //权重
    	unsigned int parent;  //父节点的下标
    	unsigned int lchild;  //左孩子的下标
    	unsigned int rchild;  //右孩子的下标
    
    }HTNode,* HuffmanTree;
    
    #define ok 1
    #define error 0
    #define N 50
    
    typedef char * *HuffmanCode;
    
    
    //函数原型：
    int xinxi(int w[N],int &n);//存储权重
    int HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int*w,int n);//求Huffman编码函数
    int Select(HuffmanTree &HT,int n,int &s1,int &s2); //选择函数
    
    
    //*********************主函数
    int main()
    {
    	HuffmanTree HT;
    	HuffmanCode HC;
    	int w[N]; //存储每个节点的权值的数组
    	int n; //叶子节点的个数	
    	xinxi(w,n); //调用存储权值的函数
    	HuffmanCoding(HT,HC,w,n);//调用构造Huffman编码的函数
    	return 0;
    }
    
    //********************************存储权重
    int xinxi(int w[N],int &n)
    {
    	int i;
    	printf("请输入huffmanTree的叶子节点个数:");
    	scanf("%d",&n);
    	for(i=0;i<n;i++)
    	{
    		printf("请依次输入第%d个叶子节点的权重: ",i+1);
    		scanf("%d",&w[i]);
    	}
    	return ok;
    }
    
    //****************************构建Huffman树
    int HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int*w,int n)
    {
    	int m,i;
    	int s1,s2; //s1,s2是权重最小的两个节点的下标
    	int f,start;
    	unsigned int c;//循环变量
    	HuffmanTree p;//临时变量
    	char *cd;//Huffman编码的临时存储变量
    	if(n<=1)//节点个数不能少于1个
    	{
    		printf("只有一个节点\n");
    		return error; 
    	}
    	m=2*n-1; //m=总节点个数
    	//因为0号单元没有使用，所以要申请m+1个内存空间存储节点
    	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
    	//因为0号单元没有使用，所以p从HT+1号地址开始遍历；
    	//对n个叶子节点的信息进行初始化；
    	for(p=(HT+1),i=1;i<=n;++i,++p,++w)
    	{
    		p->weight=*w; //权重
    		p->lchild=0;  //目前都是单独的节点
    		p->rchild=0;  //左孩子，右孩子，父亲
    		p->parent=0;  //都应该初始化为0
    	}
    	for(i=n;i<=m;++i,++p) //剩下的m-n个节点
    	{
    		p->weight=0;    
    		p->lchild=0;
    		p->rchild=0;
     		p->parent=0;
    	}
    	for(i=n+1;i<=m;++i)
    	{
    		Select(HT,i-1,s1,s2);//调用找最小权重的函数
    		//最小权重的两个节点的父亲是i
    		HT[s1].parent=i;  HT[s2].parent=i;
    		//节点i就有了左孩子和右孩子
    		HT[i].lchild=s1;  HT[i].rchild=s2;
    		//节点i的权重也等于左右孩子权重的和
    		HT[i].weight=HT[s1].weight+HT[s2].weight;
    	}
        //将Huffman数每个节点的信息输出
    	//节点从1开始，共m个节点
    	printf("\nHuffman存储结构HT:\n");
    	for(i=1;i<=m;i++)
    	{
    		printf("%2d %2d %2d %2d\n",HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
    	}
    
    	///**********构造Huffman编码
    	///********从叶子到根逆向求每个字符的Huffman编码
    	//分配n个字符编码的头指针向量，存储每个字符数组的首地址，0号单元不用
    	HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
        //Huffman编码最长不会超过n，所以请求分配n个char型内存空间
    	cd=(char*)malloc(n*sizeof(char));
    	cd[n-1]='\0';//将字符串结束标志存入
    	for(i=1;i<=n;i++)//循环n次
    	{
    		start=n-1;//字符串末尾
    		for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
    		{
    			if(HT[f].lchild==c) cd[--start]='0';
    			else cd[--start]='1';
    		}
    		//节点i的节点的Huffman编码的个数是n-start个
    		HC[i]=(char*)malloc((n-start)*sizeof(char));
    		//将创建好的字符串复制到HC[i]开始的字符数组中
    		strcpy(HC[i],&cd[start]);
    	}
    	free(cd); //释放空间
    	//打印Huffman编码
    	printf("\nHuffman编码是:\n");
    	for(i=1;i<=n;i++)
    	{
    		printf("%3d %s\n",HT[i].weight
    			,HC[i]);
    	}
    	return ok;
    }
    
    //*****************************找权值最小的两个节点
    //在HT数组中i-1个节点中找到权重最小的两个，下标存在s1和s2中
    int Select(HuffmanTree &HT,int n,int &s1,int &s2)   //n=i-1
    {
    	int i,j;
    	//找到第一个父节点为0的节点，将下标存进s1中
    	for(i=1;i<=n;i++)
    	{
    		if(HT[i].parent==0)
    		{
    			s1=i;
    			break;
    		}
    	}
    	//寻找一个权重最小并且父节点为0
    	for(i=1;i<=n;i++)
    	{
    		if(HT[i].weight<HT[s1].weight && HT[i].parent==0)
    		{
    			s1=i;
    		}
    	}
    	//找到第二个父节点为0的节点，将下标存进s2中，s1和s2不能相等
    	for(j=1;j<=n;j++)
    	{
    		if(HT[j].parent==0 && j!=s1)
    		{
    			s2=j;
    			break;
    		}
    	}
    	//找到第二个权重最小并且没有父亲的节点，将下标赋给s2,s2!=s1
    	for(j=1;j<=n;j++)
    	{
    		if(HT[j].weight<HT[s2].weight && HT[j].parent==0 && j!=s1)
    		{
    			s2=j;
    		}
    	}
    	return ok;
    }

加油兄弟们！