hufftree.h

这里实现了一个比较系统的哈夫曼编码系统。具有如下功能。 1:输入字符

#include<iostream>
#include<iomanip>
using namespace std;

typedef char** HuffmanCode;

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

void select(HTNode*&HT,int i,int &s1,int &s2)//在哈夫曼树HT前i棵子树中选择权值最小且parent==0，序号给s1，第二小给s2.
{
	int min1=1000000,min2=1000000,k;
	for(k=1;k<=i;k++)
	{
	if(HT[k].weight<min1&&HT[k].weight<min2&&HT[k].parent==0)
	{
		//先将s1内容传给s2，再讲HT[k]内容传给s1
        s2=s1;min2=min1;
		 s1=k;min1=HT[k].weight;
	}
	else 
		if(HT[k].weight==min1&&HT[k].weight<min2&&HT[k].parent==0)
		{
			min2=HT[k].weight;
		    s2=k;
		}
	else 
		if(HT[k].weight>min1&&HT[k].weight<min2&&HT[k].parent==0)
		{
			min2=HT[k].weight;
		    s2=k;
		}
	}
}

void HuffmanCoding(HTNode*&HT,HuffmanCode&HC,int*w,int n)//权值数组是从0开始
{
	int m,i,s1,s2,start,c,f;
	m=2*n-1;
	HT=new HTNode[m+1];
	for(i=1;i<=n;i++)
	{
		HT[i].weight=w[i-1];
		HT[i].parent=HT[i].lchild=HT[i].rchild=0;
	}
	for(;i<=m;i++)
	HT[i].weight=HT[i].parent=HT[i].lchild=HT[i].rchild=0;
	for(i=n+1;i<=m;i++)
	{	
		select(HT,i-1,s1,s2);//在哈夫曼树HT前i-1棵子树中选择权值最小且parent==0，序号给s1，第二小给s2.
	    HT[s1].parent=HT[s2].parent=i;
	    HT[i].weight=HT[s1].weight+HT[s2].weight;
	    HT[i].lchild=s1;
	    HT[i].rchild=s2;
	}
	HC=new char*[n+1];
    char *cd;
    cd=new char[n];
    cd[n-1]='\0';
    for(i=1;i<=n;i++)
	{
		start=n-1;
	    for(c=i,f=HT[i].parent;f;c=f,f=HT[f].parent)
		{
		  if(HT[f].lchild==c)cd[--start]='0';
		  else cd[--start]='1';
		}
		HC[i]=new char[n-start];
	    strcpy(HC[i],&cd[start]);
	}
	delete cd;
	return;
}

int FindIndex(char ch,char *str,int len)//len为字符串str的长度,注意str为原来输入的，ch为想编码的
{
	int i;
	for(i=0;i<len;i++)
		if(ch==str[i])return i;
	return -1;
}

void Trans(HuffmanCode&HC,char*str,int len,char *ch)
{
	int i,count;
	for(i=0;i<strlen(ch);i++)
	{
		count=FindIndex(ch[i],str,len)+1;
		if(!count)continue;
		else cout<<HC[count];
	}
	cout<<endl;
	return;
}