cpp1.cpp

关于HUFFMAN树的算法及其应用

#include "iostream.h"
const int n=8;
const int m=2*n-1;
typedef struct
{
	float weight;
	int parent,lchild,rchild;
}nodetype;
typedef nodetype hftree[m];
hftree T;
void huffman(hftree T)
{
	int i,j,p1,p2;
	float small1,small2;
	for(i=0;i<n;i++)
	{
		T[i].parent=-1;
		T[i].lchild=T[i].rchild=-1;
	}
	cout<<"请依次输入字符出现的频率："<<endl;
	for(i=0;i<n;i++)
	{
		cin>>T[i].weight;
	}
	for(i=n;i<m;i++)
	{
		small1=small2=10000;
		for(j=0;j<=i-1;j++)
		{
			if(T[j].parent!=-1)continue;
			if(T[j].weight<small1)
			{
				small2=small1;
				small1=T[j].weight;
				p2=p1;
				p1=j;
			}
			else if(T[j].weight<small2)
			{
				small2=T[j].weight;
				p2=j;
			}
		}
		T[p1].parent=T[p2].parent=i;
		T[i].parent=-1;
		T[i].lchild=p1;
		T[i].rchild=p2;
		T[i].weight=small1+small2;
	}

}

typedef struct
{
	char bits[n];
	char ch;
	int start;
} chartype;
typedef chartype codelist[n];
codelist codes;
void encode(codelist codes,hftree T)
{
	int i,c,p,start;
	cout<<"请依次输入字符："<<endl;
	for(i=0;i<n;i++)
	{
		cin>>codes[i].ch;
		start=n;
		c=i;
		p=T[i].parent;
		while(p!=-1)
		{
			start--;
			if(T[p].lchild==c) codes[i].bits[start]='0';
			else codes[i].bits[start]='1';
			c=p;
			p=T[p].parent;
		}
		codes[i].start=start;
	}
}



void main()
{
	char code[10];
	huffman(T);
	encode(codes,T);
	cout<<"请任意输入一串字符："<<endl;
	for(int a=0;a<10;a++)
	{
		cin>>code[a];
	};
	cout<<"您输入的字符串的哈夫曼编码为："<<endl;
	for(a =0;a<10;a++)
	{
		for(int j=0;j<n;j++)
		{
			if(code[a]==codes[j].ch)
			{
				for(int i=0;i<n;i++)
				{
					if(codes[j].bits[i]=='0'||codes[j].bits[i]=='1')
					{
						cout<<codes[j].bits[i];
					}
					else continue;
				}
			}
			else continue;
		}
	}
	cout<<endl;
}