haff.cpp

构建哈夫曼树

#include<iostream>
#define N 3
using namespace std;
struct{
  char ch;
  int weight;
  int parent;
  int lchild;
  int rchild;
}haff[2*N-1];

struct point{
  int a;
  point* next;
};

struct HaffCode{
  point* p;
  char ch;
}hc[N];
int s1,s2;
int j;
void Select(int n, int& s1,int& s2)
{
    int i;
    i=0; 
	for(;haff[i].parent;i++);
	s1=i;
	while(i<n)
	{
		if(haff[i].weight<=haff[s1].weight&&!haff[i].parent)
		{
		
			s1=i;
			
		}
		i++;
	}
	i=0;
	for(;haff[i].parent;i++);
	s2=i;
	i++;
	while(i<n)
	{
		if(haff[i].weight<=haff[s2].weight&&i!=s1&&!haff[i].parent)
		{
			s2=i;
		}
		i++;
	}
	
}
int c[20];
int decode;
point* q;
int i=0;
int code=0;
int spot;
void Decode()
{
  
   
   for(decode=0;decode<N;decode++)
   {
	   j=0;
	   if((hc[decode].p)->next->a!=c[spot])
		   continue;
	     else
		 {
			 q=(hc[decode].p)->next;
		
			 while(q->next!=NULL&&q->next->a==c[++j+spot])
			 {
				 q=q->next;
			
			 }
			 if(q->next!=NULL)
				 continue;
			 else
			 {
				 
				 cout<<hc[decode].ch;
                 spot+=j+1;
				 if(c[spot]==2)
					 return;
				 else Decode();
			 }
		 }
   }
}

void main()
{
	for(i=0;i<N;i++)
	{
        cout<<"Please input the char and the weight\n";
		cin>>haff[i].ch>>haff[i].weight;
		haff[i].parent=0;
		haff[i].lchild=0;
		haff[i].rchild=0;
	}
	
	
	
	for(j=N;j<2*N-1;j++)
	{
		Select(j,s1,s2);
		haff[s1].parent=haff[s2].parent=j;
		haff[j].lchild=s1;
		haff[j].rchild=s2;
	}//initiation
   
    for(i=0;i<N;i++)
    {
		
		hc[i].p=new(point);
		hc[i].p->next=NULL;
	}

    for( code=0;code<N;code++)
	{
	   i=code;
	   hc[code].ch=haff[code].ch;
	   
	   while(haff[i].parent)
	   {
		   j=i;
		   i=haff[i].parent;
		   q=new(point);
		   if(j==haff[i].rchild)
		     q->a=1;
             else q->a=0;
		   q->next=hc[code].p->next;
           hc[code].p->next=q;
	   }
	}//code

    for(  i=0;i<20;i++)
	{
		c[i]=2;
	}
	cout<<"Please input the code\n";
	char cc[20];
	for(i=0;i<20;i++)
	{
		cc[i]='\0';
	}
	cin>>cc;
	i=0;
	while(cc[i]!='\0')
	{
		c[i]=cc[i]-'0';
		i++;
	}
    spot=0;
	Decode();
}