huffman.cpp

数据结构...哈夫曼编码... C++实现的数据结构算法

//HuffmanTree 问题求解



#include<iostream.h>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define INT_MAX 100000
#define N 10000


typedef struct HTNode{                       //类型定义
	 
	int weight;
	int parent;
	int lchild;
	int rchild;
	char data;
	char code[20];

}*HuffmanTree;




void Select(HuffmanTree HT,int end,int &s1,int &s2)      //查找权值最小的两个字符序号
{
  int i,j,t;
  int min1=INT_MAX;
  int min2;
  
     for (i=1;i<=end;i++)
	 {
          if (HT[i].parent==0&&HT[i].weight<min1)
		  { 
          s1=i;
          min1=HT[i].weight;
		  }
	 }
 
   min2=INT_MAX;
     
     for(j=1;j<=end;j++)
	 {
          if (HT[j].parent==0&&(s1!=j)&&min2>HT[j].weight)
		  {
              s2=j;
              min2=HT[j].weight;
          }
     }
	 if(s1>s2)
	 {
		 t=s1;
		 s1=s2;
		 s2=t;
	 }
}


void Initialization(HuffmanTree &ht,int a,int b)   //初始化HuffmanTree，建立该树
{
	int i,start,f,c,s1,s2;
	char *cd;
	char *str;
	int *w;

	str=new char[a+1];
    w=new int[a+1];

	cout<<"Let me know the initialization-words:"<<endl;
	for(i=1;i<=a;i++)                              //初始化输入字符时，注意：应连续输入，再按回车键！
		scanf("%c",&str[i]);            
	cout<<"then the weights?"<<endl;
    for(i=1;i<=a;i++)
		cin>>w[i];

	ht=new HTNode[b+1];

	for(i=1;i<=a;i++)
	{
		ht[i].weight=w[i];
		ht[i].parent=0;
		ht[i].lchild=0;
		ht[i].rchild=0;
		ht[i].data=str[i];
	}
	for(;i<=b;i++)
	{
		ht[i].weight=0;
		ht[i].parent=0;
		ht[i].lchild=0;
		ht[i].rchild=0;
		ht[i].data='\0';
		ht[i].code[0]='\0';
	}

   for(i=a+1;i<=b;i++){
        Select(ht,i-1,s1,s2);
        ht[s1].parent=i;
        ht[s2].parent=i;
        ht[i].lchild=s1;
        ht[i].rchild=s2;
        ht[i].weight=ht[s1].weight+ht[s2].weight;
    }


	cd=new char[a];

    cd[a-1]='\0';

      for(i=1;i<=a;++i)                           //求出各字符相应的编码
	 { 
        f=ht[i].parent;
		c=i;
		start=a-1; 
        while(f!=0)
		{ 
           if(ht[f].lchild==c) 
			   cd[--start]='0'; 
           else 
			   cd[--start]='1'; 
		   c=f;
		   f=ht[f].parent;
		} 

        strcpy(ht[i].code,&cd[start]); 

	 }

}

void Encoding(HuffmanTree ht)                   //要求输入报文，然后编码！
{
	int i=0,j;
	char str[N];
	getchar();                                  //吸收回车键！
	cout<<"Enter the messages you want to code:"<<endl;
    gets(str);
	cout<<"Now,the codes are:"<<endl;
	while(str[i]!='\0')
	{
		j=1;
		while(ht[j].data!=str[i])j++;
		cout<<ht[j].code;
		i++;
	}
}



void Decoding(HuffmanTree ht,int m)              //要求输入原码，进行译码！
{
	
	int i=0,p;
	char s[N];
	cout<<"Input the original messages:"<<endl;
	scanf("%s",s);
    cout<<"The real message:"<<endl;
	p=m;
	while(s[i]!='\0')
	{
		while(ht[p].lchild!=0&&s[i]!='\0')
		{
			if(s[i]=='0')
				p=ht[p].lchild;
			else 
				p=ht[p].rchild;
			i++;
		}	  
			
	        cout<<ht[p].data;
			p=m;
			
	}
		
}


void print(HuffmanTree ht,int n,int m)            //打印HuffmanTree到输出端
{ 
	int i;
	cout<<"OK,I will list the result ot HuffmanTree-initialization below:"<<endl<<endl;
	cout<<"loc"<<'\t'<<"w"<<'\t'<<"par"<<'\t'<<"lch"<<'\t'<<"rch"<<'\t'<<"data"<<'\t'<<"code"<<endl;
	
	for(i=1;i<=m;i++)
		cout<<i<<'\t'<<ht[i].weight<<'\t'<<ht[i].parent<<'\t'<<ht[i].lchild<<'\t'<<ht[i].rchild<<'\t'<<ht[i].data<<'\t'<<ht[i].code<<'\t'<<endl;
}



void main()
{
	int n,m;
	char a,b;
	HuffmanTree HT=NULL;

	while(b!='Q')                        //系统界面……
	{
		cout<<endl<<"Initialization(I)"<<'\t'<<"Encoding(E)"<<'\t'<<"Decoding(D)"<<'\t'<<"Print(P)"<<'\t'<<"Quit(Q)"<<endl;
		cout<<"Enter your command:"<<endl;
		cin>>a;

		switch(a){

		case 'I': 
			cout<<"Please tell me the number of initialization-words you want to code:"<<endl;
			cin>>n;
			m=2*n-1;
			Initialization(HT,n,m);
			break;
		case 'E':
			Encoding(HT);
			break;
		case 'D':
			Decoding(HT,m);
			break;
		case 'P':
			print(HT,n,m);
			break;
		case 'Q':
			b='Q';
			break;
		}
	}
}