huff.h

哈夫曼编码的源程序

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define  OVERFLOW -1
extern num;
typedef struct
{   
	char letter;
	int weight;
	int parent;
	int lchild;
	int rchild;
}HTNode,*HuffmanTree;

typedef char * *HuffmanCode;

void Select(HuffmanTree &HT,int i,int &s1,int &s2)
{
/*选择森林中，根结点的权值最小和次小的两个树，
*将其根结点的下标号记入s1和s2中
	*/
	int j, k;
	for(k = 1; k < i; k++)
	{
		if(HT[k].parent != NULL)
			continue;
		s1 = k;/*init the number*/
		break;
	}
	for(j = 1; j < i; j++)
	{
		if(HT[j].parent != NULL)
			continue;
		if(HT[j].weight < HT[s1].weight)
			s1 = j;
	}
	for(k = 1; k <= i; k++)
	{
		if(HT[k].parent != NULL || k == s1)
			continue;
		s2 = k;
		break;
	}
	
	for(j = 1; j < i; j++)
	{
		if(HT[j].parent != NULL)
			continue;
		if(HT[j].weight <= HT[s2].weight && j != s1)
			s2 = j;
	} 
	
}


void  HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,char *zi,int *w,int n)
{
	HuffmanTree p;
	
	int m,i,s1,s2,f,c;
	int Istart = 1;
	char *cd;
	if(n <= 1)
		return;
	m = 2*n-1;
	if(!(HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode))))
		exit(OVERFLOW);
	for(p=HT+1,i=1;i<=n;++i,++zi,++p,++w)
	{
		/*生成独立的森林*/
		p->parent = NULL;
		p->letter = *zi;
		p->lchild = NULL;
		p->rchild = NULL;
		p->weight = *w;
	}
	
	for(;i<=m;++i,++p)
	{
		(*p).weight=0;
		(*p).parent=0;
		(*p).lchild=0;
		(*p).rchild=0;
	}
	
	for(i=n+1;i<=m;++i)
	{
		Select(HT,i,s1,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;
	}
	HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
	cd=(char*)malloc(n*sizeof(char));/*临时的code存储*/
	cd[n-1]='\0';
	for(i=1;i<=n;++i)
	{
		Istart = n - 1;
		/*按已生成的哈夫曼树，得到各个字符的哈夫曼编码
		*/
		
		for(c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent)
			if(HT[f].lchild == c)
				cd[--Istart] = '0';
			else 
				cd[--Istart] = '1';
			HC[i] = (char *)malloc((n - Istart) * sizeof(char));
			strcpy(HC[i], &cd[Istart]);
			
	}
	free(cd);
}
/*    中序打印树    */
void print_htree_ldr(HuffmanTree t, int head_i, int deep, int* path,HuffmanCode HC)

{

	int i;

	if (head_i == 0) return;

	path[deep] = 0;

	print_htree_ldr(t, t[head_i].lchild, deep + 1, path,HC);

	if (deep) printf("      ");

	for (i=1; i<deep; i++) printf("%s", path[i]==path[i-1]?"      ":"│    ");

	int dir = path[i]==path[i-1];

	if ( t[head_i].lchild == 0 && t[head_i].rchild == 0) 

		printf("%s── %d '%c'\n", dir? "┌":"└", 
			t[head_i].weight, t[head_i].letter );

	else if (head_i != num-1&&deep!=0)

		printf("%s─%02d┤\n", dir? "┌":"└", t[head_i].weight);

	else 

		printf("    %02d┤\n", t[head_i].weight);

	path[deep] = 1;

	print_htree_ldr(t, t[head_i].rchild, deep + 1, path,HC);

}