huffman.cpp

构造哈夫曼树 哈弗曼树中没有度为一的节点

#include <stdio.h> 
#include <malloc.h> 
#include <stdlib.h>
#include<string.h> 

 
typedef struct HTNode                   //声明结构体,有成员变量weight,lchild,rchild,parent
{
	int weight;
	int lchild;
	int rchild;
	int parent;
} *huffmantree;                        //动态存储内存数组存储哈夫曼树

typedef char **huffmancode;            //动态分配数组存储哈夫曼编码表


void Select(int n,int &s1,int & s2,HTNode *ht) //选择parent为0且权值最小的两个节点
{	
	int min1=999;                       //附较大的初值
	int min2=1000;
	s1=1;

	for(int i=1;i<=n-1;i++)            //选出权值最小的元素
		if((ht[i].parent==0 )&& (ht[i].weight<min1)) 
		{
				min1=ht[i].weight;
				s1=i;                  //序号为s1
			}
				
	
	for( i=1;i<=n-1;i++)                //选出权值次小的元素,序号为s2
		if((ht[i].parent==0) && (i!=s1) &&(ht[i].weight<min2))
		{
			min2=ht[i].weight;
			s2=i;                        
		}

}


void Huffman(int n, int * w)        //哈夫曼编码及输出
{
    char *cd;                      //编码
	int start;                     //次数
	int m=2*n-1;
	int s1,s2,c,f;                 //c,f在逆向编码时用到
    int l;
    HTNode *ht=(huffmantree)malloc((m+1)*sizeof(HTNode)); //分配哈夫曼树的空间
	char **hc=(huffmancode)malloc((n+1)*sizeof(char *)); //存放字符编码的头指针
	cd=(char*)malloc(n*sizeof(char ));                  //求编码的工作空间
	cd[n-1]='\0';
	
//以下两个循环是构造huffman树贮存表

  for(int i=1;i<=n;i++)     //前n个元素有权值,其父,左孩子,右孩子,为第0 号元素
  {
	  ht[i].weight=*(w+i-1);
	  ht[i].lchild=0;    
	  ht[i].rchild=0;
	  ht[i].parent=0;
	  
  }
  for(;i<=m;i++)            //后n-1个元素的权值,左孩子,右孩子,父都为0;
  {
	  ht[i].weight=0;
	  ht[i].lchild=0;
	  ht[i].parent=0;
	  ht[i].rchild=0;
	  
  }
  
  for( l=n+1;l<=2*n-1;l++)     //huffman树构造
  {
	 Select(l,s1,s2,ht);
     ht[l].weight=ht[s1].weight+ht[s2].weight; //权值相加
     ht[l].lchild=s1;            //节点的左孩子为最小值
     ht[l].rchild=s2;            //右孩子为次小
     ht[s1].parent=l;
     ht[s2].parent=l;
  }

 
  for(i=1;i<=n;i++)
  {
	  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';               //左孩子编码为0
		 else cd[--start]='1';               //右孩子为一
	  }
	hc[i]=(char*)malloc((n-start)*sizeof(char));//为第i个字符编码分配空间
	strcpy(hc[i],&cd[start]);                     //字符串复制

	printf("w%d:",i);                         //输出编码
    printf("%s\n",hc[i]);
  
  }
  free(cd);
}


void main()                        //主函数对上述代码进行验证
{
	int n=4 ;
//	printf("请依次输入%d个权值(正整数，权值之间用空格分隔):",&n);
	
	int w[4]={1,2,3,4};
	 Huffman(n, w);
    }