hafuman.cpp

哈夫曼编码,也是用C++实现哈夫曼的编码,对一组概率数据进行哈夫曼编码

#include<iostream>
#include<string>
using namespace std;
#define MAX 1000 
typedef struct {
 int weight;
 int flag;
 int parent;
 int lchild;
 int rchild;
}hafuman1;
typedef struct {
 int bit[10];
 int start;
 char leaf;
}hafuman2;
void huf(char cha[],double m[],int n){
	int i,j,m1,m2,x1,x2,c,p;
	hafuman1 *a=new hafuman1[2*n-1];
	hafuman2 *b=new hafuman2[n],cd;
    for(i=0;i<2*n-1;i++)
	{
		//初始化哈夫曼树
		a[i].weight=0;
		a[i].parent=0;
		a[i].flag=0;
		a[i].lchild=-1;
		a[i].rchild=-1; }
	 for(i=0;i<n;i++) {
		 //哈夫曼结点赋初值
		 a[i].weight=m[i];
		 b[i].leaf=cha[i];
	 }
	 for(i=0;i<n-1;i++) 
	 {
		 //对结点进行编码
		 m1=m2=10000000;
		 x1=x2=0;
		 for(j=0;j<n+i;j++)
		 {
			 if(a[j].weight<=m1&&a[j].flag==0)
			 {
				 m2=m1;
				 x2=x1;
				 m1=a[j].weight;
				 x1=j;
			 }
			 else if(a[j].weight<=m2&&a[j].flag==0)
			 {
				 m2=a[j].weight;
				 x2=j;
			 }
		 }
		 a[x1].parent=n+i;
		 a[x2].parent=n+i;
		 a[x1].flag=1;
		 a[x2].flag=1;
		 a[n+i].weight=a[x1].weight+a[x2].weight;
		 a[n+i].lchild=x1;
		 a[n+i].rchild=x2;
	 }
	 for(i=0;i<n;i++)
	 {
		 //生成哈夫曼树
		 cd.start=n-1;
		 c=i;
		 p=a[c].parent;
		 while(p!=0)
		 {
			 if(a[p].lchild==c)
				 cd.bit[cd.start]=0;
			 else
				cd.bit[cd.start]=1;
			    cd.start--;
				c=p;
				p=a[c].parent;
	 }
		 cout<<b[i].leaf<<":";
		 for(j=cd.start+1;j<n;j++)
		 {
			 b[i].bit[j]=cd.bit[j];
			 cout<<cd.bit[j];
	 }
		 cout<<endl;
   b[i].start=cd.start;
	 }
      delete[] b;
     delete[] a;
}
void input()
{
    int i=0,n;
    double m[MAX]; 
    char cha[MAX];	
	double sum=0;
	cout<<"输入信源个数:";
    cin>>n; 
    cout<<"输入"<<n<<"个字符:";
	for(i=0;i<n;i++){ cin>>cha[i]; }
    cout<<"输入"<<n<<"个字符该信源概率:"<<endl;
    for(i=0;i<n;i++){ cin>>m[i];  sum=sum+m[i];}
   if(sum!=1)
     { cout<<"输入概率和是"<<sum<<"不为1，请重输";
      input(); }
   cout<<"该字符串为:\t";
   for (i=0;i<n;i++){ cout<<cha[i]<<"\t"; }
   cout<<endl;
   cout<<"字符加权为:\t";
   for (i=0;i<n;i++){cout<<m[i]<<"\t";}
   cout<<endl;
  cout<<"各字符的哈夫曼码为："<<endl;
	huf(cha,m,n);
	cout<<endl;
}
void main()
{  input();}