哈夫曼编译码器.cpp

输入各个字符及对应出现的次数 ； 建立赫夫曼树并对各个字符进行编码 ；然后 对 输入 的 二进制 串进行 译码

#include "iostream.h" 
const int max=100;
int i1=0; int i2=0;	int n=0; 
struct element    
{
	int weight;
	char body;
	int lchild,rchild,parent;
};
class Huffman
{
public:
	Huffman();
    void GetSmaller(int &i1,int &i2);
	void disppath(int p);
	void disletter();
private:
     char a[max];
     int w[max];
	 element huffTree[max];
	 int visited[max];
};

Huffman::Huffman()
{  cout<<"建立哈夫曼树:\n"<<endl;
	for(int q=0;q<max;q++)
	{
		a[q]=NULL;w[q]=0;visited[q]=0;
	}

	cout<<"请输入所需要的字符："<<endl; 
	cin>>a;
	cout<<"请输入其出现的频率： "<<endl;
	for(int i=0;a[i]!=NULL;i++,n++)
	{
		cout<<a[i]<<":";   cin>>w[i];
	}

	for(i=0;i<2*n-1;i++)
	{
		huffTree[i].parent=-1;
		huffTree[i].rchild=-1;
		huffTree[i].lchild=-1;
	}
	
	for(i=0;i<n;i++)
	{
		huffTree[i].weight=w[i];
	    huffTree[i].body=a[i];
	
	}

	for(int k=n;k<2*n-1;k++)
	{
		GetSmaller(i1,i2);     
        huffTree[i1].parent=k;
		huffTree[i2].parent=k;
		huffTree[k].weight=huffTree[i1].weight+huffTree[i2].weight;
		huffTree[k].lchild=i1;
		huffTree[k].rchild=i2;
	}
	

	cout<<"\n进行编码:"<<endl;

		for(int x=0;x<n;x++)
		{
		   cout<<huffTree[x].body<<" "; 
		   disppath(x);
	       cout<<endl;
	   }
	   cout<<"\n进行译码:"<<endl;                         


		  disletter();
		  cout<<endl;
	
}

void Huffman::disletter()
{   int t=-1;
     do { 
			t++;  
		}while(huffTree[t].parent!=-1);
   int root=t;
	cout<<"\n请输入0/1字码:"<<endl;
	char a[50]={NULL};
	cin>>a;
	cout<<"字符串是:  ";
	for(int i=0;a[i];i++)
	{
		if (a[i]=='0')
		{
			root=huffTree[root].lchild;
		}
		else if (a[i]=='1') 
		{
			root=huffTree[root].rchild;
		}

	   if (huffTree[root].body&&root<n)
		{
			cout<<huffTree[root].body<<" ";
			root=t;
		}
	  
	}
	cout<<endl;
}

void Huffman::GetSmaller(int &i1,int &i2)
{        i1=-1;
         do {
         	i1++;
         } while(visited[i1]==1);
	     for(int i=0;huffTree[i].weight>0;i++)
            if ((huffTree[i].weight<huffTree[i1].weight)&&visited[i]==0)
			{
			  i1=i;
			}
			visited[i1]=1;
			i2=-1;
			do {
				i2++;
			} while(visited[i2]==1);
		  for(i=1;huffTree[i].weight>0;i++)
			  if ((huffTree[i].weight<huffTree[i2].weight)&&visited[i]==0)
			  {
				  i2=i;
			  }
			  visited[i2]=1;
}

void Huffman::disppath(int p)
{
	if (huffTree[p].parent!=-1)
	{
		disppath(huffTree[p].parent);
        if (huffTree[huffTree[p].parent].lchild==p)
			cout<<"0";
		else
			cout<<"1";
	}
}



void main()
{
	 Huffman OneTree;
}