huffman.cpp

构造哈夫曼树,录入权值,并求出最小生成树

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

typedef   struct   {   
	unsigned   int   weight;   
	unsigned   int   parent,lchild,rchild;   
}   HTNode,*HuffmanTree;   

typedef   char   **HuffmanCode;   

typedef   struct   {   
	unsigned   int   s1;   
	unsigned   int   s2;   
}   MinCode;   

void   Error(char   *message);   
HuffmanCode   HuffmanCoding(HuffmanTree   HT,HuffmanCode   HC,unsigned   int   *w,unsigned   int   n);   
MinCode   Select(HuffmanTree   HT,unsigned   int   n);   

void   Error(char   *message)   
{   
	fprintf(stderr,"Error:%s\n",message);   
	exit(1);   
}   

HuffmanCode   HuffmanCoding(HuffmanTree   HT,HuffmanCode   HC,unsigned   int   *w,unsigned   int   n)   
{   //w存放n个字符的权值（均>0），构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC。
	unsigned   int   i,s1=0,s2=0;   
	HuffmanTree   p;   
	char   *cd;   
	unsigned   int   f,c,start,m;   
	MinCode   min;   
	if(n<=1)   
		Error("Code   too   small!");   
	m=2*n-1;   
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0号单元未用。  
	for(p=HT,i=0;i<=n;i++,p++,w++)   
	{   
		p->weight=*w;   
		p->parent=0;   
		p->lchild=0;   
		p->rchild=0;   
	}   
	for(;i<=m;i++,p++)   
	{   
		p->weight=0;   
		p->parent=0;   
		p->lchild=0;   
		p->rchild=0;   
	}   
	for(i=n+1;i<=m;i++)   
	{   //建赫夫曼树
		//在HT[1..i-1]选择parent为0且weight最小的两个结点，其序号分别为s1和s2。
		min=Select(HT,i-1);   
		s1=min.s1;   
		s2=min.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("HT   List:\n");   
	printf("Number\t\tweight\t\tparent\t\tlchild\t\trchild\n");   
	for(i=1;i<=m;i++)   
		printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\n",   
		i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
	//从叶子到根逆向求每个字符的赫夫曼编码。 
	HC=(HuffmanCode)malloc((n+1)*sizeof(char   *)); //分配n个字符编码的头指针向量。  
	cd=(char   *)malloc(n*sizeof(char   *));   //分配求编码的工作空间。
	cd[n-1]='\0';   //编码结束符。
	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';   
			else   
				cd[--start]='1';   
			HC[i]=(char   *)malloc((n-start)*sizeof(char   *)); //为第i个字符编码分配空间。  
			strcpy(HC[i],&cd[start]);   //从cd复制编码（串）到HC。
	}   
	free(cd);   
	return   HC;   
}   

MinCode   Select(HuffmanTree   HT,unsigned   int   n)   
{   
	unsigned   int   min,secmin;   
	unsigned   int   temp;   
	unsigned   int   i,s1,s2,tempi;   
	MinCode   code;   
	s1=1;
	s2=1;   
	for(i=1;i<=n;i++)   
		if(HT[i].parent==0)   
		{   
			min=HT[i].weight;   
			s1=i;   
			break;   
		}   
		tempi=i++;   
		for(;i<=n;i++)   
			if(HT[i].weight<min&&HT[i].parent==0)   
			{   
				min=HT[i].weight;   
				s1=i;   
			}   
			for(i=tempi;i<=n;i++)   
				if(HT[i].parent==0&&i!=s1)   
				{   
					secmin=HT[i].weight;   
					s2=i;   
					break;   
				}   
				for(i=1;i<=n;i++) 
				{
					if(HT[i].weight<secmin&&i!=s1&&HT[i].parent==0)   
					{   
						secmin=HT[i].weight;   
						s2=i;   
					}  
				}
				if(s1>s2)   
				{   
					temp=s1;   
					s1=s2;   
					s2=temp;   
				}   
				code.s1=s1;   
				code.s2=s2;   
				return   code;   
}   

void main()   
{   
	HuffmanTree   HT=NULL;   
	HuffmanCode   HC=NULL;   
	unsigned   int   *w=NULL;   
	unsigned   int   i,n;   
	printf("Input   n:\n");   
	scanf("%d",&n);   
	w=(unsigned   int   *)malloc((n+1)*sizeof(unsigned   int   *)); //给权值分配空间。   
	w[0]=0; //给第一个空间赋0值。  
	printf("Enter   weight:\n");   
	for(i=1;i<=n;i++)   //录入权值。
	{   
		printf("w[%d]=",i);   
		scanf("%d",&w[i]);   
	}   
	HC=HuffmanCoding(HT,HC,w,n);   
	printf("HuffmanCode:\n");   
	printf("Number\t\tWeight\t\tCode\n");   
	for(i=1;i<=n;i++)   
		printf("%d\t\t%d\t\t%s\n",i,w[i],HC[i]);   
    
}