1.cpp

根据huffman编码原理的带有接口的程序

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

#include <malloc.h> 
#include <iostream> 
using namespace std; 

void select(HuffmanTree HT,int n,int& s1, int& s2)
{
	int min1,min2,t,i=1;
	for(i=1;i<=n;i++)
		if(HT[i].weight>min1)min2=min1=HT[i].weight;
	for(i=1;i<=n;i++)
		if(HT[i].parent==0)if(HT[i].weight<min1){min1=HT[i].weight; s1=i;} 
	for(i=1;i<=n;i++) 
		if(HT[i].parent==0) 
		if((HT[i].weight<min2)&&(i!=s1)) 
		{min2=HT[i].weight; s2=i; } 
		if(s1>s2) {t=s2;s2=s1;s1=t;} 
}

void strcpy(int* a,int b[])
{ 
	a=b; 
} 

void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n)
{ 
	int m,i,s1,s2,start; 
	unsigned c,f; 
	HuffmanTree p; 
	char *cd; 
	if(n<=1)return; 
	m=2*n-1; 
	*HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); 
	for(p=*HT+1,i=1;i<=n;++i,++p,++w) 
	{ 
		(*p).weight=*w; 
		(*p).parent=0; 
		(*p).lchild=0; 
		(*p).rchild=0; 
	} 
	for(;i<=m;++i,++p) 
		(*p).parent=0; 
	for(i=n+1;i<=m;++i) 
	{ 
		select(*HT,i-1,s1,s2); 
		(*HT)[s1].parent=(*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)); 
	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)); 
		strcpy((*HC)[i],&cd[start]); } 
	free(cd); 
}
void main() 
{ 
	HuffmanTree HT; 
	HuffmanCode HC; 
	int *w,n,i; 
	printf("输入权值个数(>1): "); 
	scanf("%d",&n); 
	w=(int*)malloc(n*sizeof(int)); 
	printf("请依次输入这几个权值\n",n); 
	for(i=0;i<=n-1;i++) 
		scanf("%d",w+i); 
	HuffmanCoding(&HT,&HC,w,n); 
	for(i=1;i<=n;i++) puts(HC[i]); 
}